Rachunek zdarzeń - Event calculus

Rachunek wydarzenie jest logiczny język za reprezentowanie i wnioskowania o wydarzeniach i ich skutków pierwszy prezentowanych przez Roberta Kowalskiego i Marek Sergot w 1986 roku został przedłużony przez Murray Shanahan i Rob Miller w 1990 roku. Podobnie jak w przypadku innych języków wnioskowania o zmianach, rachunek zdarzeń przedstawia wpływ działań na biegle . Jednak zdarzenia mogą być również zewnętrzne w stosunku do systemu. W rachunku zdarzeń można określić wartość biegłości w określonych punktach czasowych, zdarzenia zachodzące w danych punktach czasowych oraz ich skutki.

Biegli i wydarzenia

W rachunku zdarzeń biegły są reifikowane . Oznacza to, że nie są one sformalizowane za pomocą predykatów, ale za pomocą funkcji . Oddzielny predykat $HoldsAt$ służy do określenia, które biegły trzymają się w danym punkcie czasowym. Na przykład oznacza, że pudełko znajduje się na stole w czasie $t$ ; w tej formule $HoldsAt$ jest predykatem, podczas gdy $on$ jest funkcją. ${\ Displaystyle {\ mathit {HoldsAt}} (na (pudełku, stole), t)}$

Wydarzenia są również przedstawiane jako terminy. Skutki zdarzeń podaje się za pomocą predykatów $Inicjuje$ i $Kończy$ . W szczególności oznacza to, że jeśli zdarzenie reprezentowane przez wyrażenie $e$ jest wykonywane w czasie $t$ , to biegły $f$ będzie prawdziwe po $t$ . $Kończy$ orzeczenie ma podobne znaczenie, z tą tylko różnicą, że $F$ będą fałszywe po $t$ . ${\ Displaystyle {\ mathit {inicjuje}} (e, f, t)}$

aksjomaty niezależne od domeny

Podobnie jak inne języki do reprezentowania działań, rachunek zdarzeń formalizuje poprawną ewolucję biegłości poprzez formuły określające wartość każdego biegłości po wykonaniu dowolnej czynności. Rachunek wydarzenie rozwiązuje problemu ramki w sposób, który jest podobny do aksjomatów następca państwowych na rachunku sytuacji : a biegły jest prawdą w chwili $t$ wtedy i tylko wtedy, gdy został on prawdziwe w przeszłości i nie został fałszywe w w międzyczasie.

{\ Displaystyle {\ mathit {trzyma na}} (f, t) \ leftarrow [{\ mathit {zdarza się}} (e, t_ {1}) \ klin {\ mathit {inicjuje}} (e, f, t_ {1 })\wedge (t_{1}<t)\wedge \neg {\mathit {Obcięty}}(t_{1},f,t)]}

Ten wzór oznacza, że biegły reprezentowany przez wyraz $f$ jest prawdziwy w czasie $t,$ jeżeli:

wydarzenie $e$ miało miejsce: ; ${\mathit {zdarza się}}(e,t_{1})$
miało to miejsce w przeszłości: ; ${\mathit {t}}_{1}<t$
to zdarzenie ma płynny efekt $f$ : ; ${\mathit {inicjuje}}(e,f,t_{1})$
biegły nie został w międzyczasie sfałszowany: ${\mathit {przycięty}}(t_{1},f,t)$

Podobny wzór jest używany do sformalizowania odwrotnego przypadku, w którym biegły jest fałszywy w danym momencie. Inne formuły są również potrzebne do prawidłowego sformalizowania biegłości, zanim staną się one skutkami zdarzenia. Te formuły są podobne do powyższych, ale zostały zastąpione przez . ${\ Displaystyle {\ mathit {zdarza się}} (e, t_ {1}) \ klin {\ mathit {inicjuje}} (e, f, t_ {1})}$ ${\mathit {trzymasAt}}(f,t_{1})$

$Clipped$ orzeczenie, stwierdzając, że biegły został fałszywe czasie przerwy można axiomatized, lub po prostu traktowane jako skrót, co następuje:

{\ Displaystyle {\ mathit {przycięte}} (t_ {1}, f, t_ {2}) \ równoważne \ istnieje e, t [{\ mathit {zdarza się}} (e, t) \ klin (t_ {1} \leq t<t_{2})\wedge {\mathit {zakończenia}}(e,f,t)]}

Aksjomaty zależne od domeny

Powyższe aksjomaty odnoszą się do wartości predykatów $HoldsAt$ , $Initiates$ i $Terminates$ , ale nie określają, które biegły są znane jako prawdziwe, a które zdarzenia faktycznie powodują, że biegły są prawdziwe lub fałszywe. Odbywa się to za pomocą zestawu aksjomatów zależnych od domeny. Znane wartości biegłości są podane jako proste literały . Skutki zdarzeń określane są za pomocą formuł wiążących skutki zdarzeń z ich warunkami wstępnymi. Na przykład, jeśli zdarzenie $open$ powoduje, że płynne $isopen jest$ prawdziwe, ale tylko wtedy, gdy $haskey$ jest aktualnie prawdziwe, odpowiednia formuła w rachunku zdarzeń to: ${\ Displaystyle {\ mathit {HoldsAt}} (f, t)}$

{\ Displaystyle {\ mathit {inicjuje}} (e, f, t) \ equiv [e = otwarty \ klin f = isopen \ klin {\ mathit {trzymasAt}} (haskey, t)] \ vee \ cdots}

Wyrażenie po prawej stronie tej równoważności składa się z alternatywy: dla każdego zdarzenia i płynności, które mogą być spełnione przez zdarzenie, istnieje alternatywa mówiąca, że $e$ jest w rzeczywistości tym zdarzeniem, że $f$ jest w rzeczywistości tą płynną i że warunek imprezy jest spełniony.

Formuła powyżej Określa wartość prawda o wszystkich możliwych zdarzeń i płynnie. W rezultacie wszystkie efekty wszystkich zdarzeń muszą być połączone w jedną formułę. Jest to problem, ponieważ dodanie nowego zdarzenia wymaga modyfikacji istniejącej formuły, a nie dodawania nowych. Problem ten można rozwiązać przez zastosowanie circumscription do zbioru formuł, z których każda określa jeden efekt jednego zdarzenia: ${\ Displaystyle {\ mathit {inicjuje}} (e, f, t)}$

{\ Displaystyle {\ mathit {Inicjuje}} (otwarty, isopen, t) \ leftarrow {\ mathit {HoldsAt}} (haskey, t)}

{\ Displaystyle {\ mathit {Inicjuje}} (przerwa, isopen, t) \ leftarrow {\ mathit {HoldsAt}} (hashammer, t)}

{\ Displaystyle {\ mathit {wtajemniczony}} (przerwa, złamany, t) \ leftarrow {\ mathit {HoldsAt}} (hashammer, t)}

Te formuły są prostsze niż formuła powyżej, ponieważ każdy efekt każdego zdarzenia można określić osobno. Pojedynczy wzór wiadomo, które zdarzenia $e$ i fluentów $f$ marki prawdziwego została zastąpiona przez zespół małych wzorach każdy mówi efekt zdarzenia na płynne. ${\ Displaystyle {\ mathit {inicjuje}} (e, f, t)}$

Jednak te formuły nie są równoważne z powyższym wzorem. W rzeczywistości określają one tylko warunki wystarczające, aby były prawdziwe, co powinno być uzupełnione faktem, że $Wtajemniczony$ jest fałszywy we wszystkich innych przypadkach. Fakt ten można sformalizować, po prostu opisując predykat $Inicjuje$ w powyższej formule. Ważne jest, aby zauważyć, że ten opis jest wykonywany tylko na formułach określających $Inicjowanych,$ a nie na aksjomatach niezależnych od domeny. Predykat $Zakończenia$ można określić w taki sam sposób, jak $Inicjuje$ . ${\ Displaystyle {\ mathit {inicjuje}} (e, f, t)}$

Podobne podejście można zastosować dla predykatu $Happens$ . Ocena tego predykatu może być wymuszona przez formuły określające nie tylko kiedy jest prawdziwe, a kiedy fałszywe:

{\ Displaystyle {\ mathit {zdarza się}} (e, t) \ equiv (e = otwarte \ t klina = 0) \ vee (e = wyjście \ t klina = 1) \ vee \ cdots}

Obwód może uprościć tę specyfikację, ponieważ można określić tylko niezbędne warunki:

{\mathit {zdarza się}}(otwarty,0)

{\mathit {zdarza się}}(wyjście,1)

Pomijając predykat $Happens$ , ten predykat będzie fałszywy we wszystkich punktach, w których nie jest wyraźnie określony jako prawdziwy. Obwód ten należy wykonać oddzielnie od obwodu innych formuł. Innymi słowy, jeśli $F$ jest zbiorem formuł typu , $G$ jest zbiorem formuł , a $H$ są aksjomatami niezależnymi od dziedziny, poprawnym sformułowaniem dziedziny jest: ${\ Displaystyle {\ mathit {inicjuje}} (e, f, t) \ leftarrow \ cdots}$ ${\mathit {zdarza się}}(e,t)$

{\ Displaystyle {\ mathit {Okrąg}} (F; {\ mathit {Inicjuje}}, {\ mathit {Zakończy}}) \ Okrąg klina (G; Dzieje się) \ Klin H}

Rachunek zdarzeń jako program logiczny

Rachunek zdarzeń został pierwotnie sformułowany jako zbiór klauzul Horna wzbogaconych o negację jako niepowodzenie i mógł być uruchamiany jako program Prolog . W rzeczywistości obwódka jest jedną z kilku semantyk, które można przypisać negacji jako niepowodzenie i jest ściśle związana z semantyką uzupełnienia (w której „jeśli” jest interpretowane jako „jeśli i tylko wtedy” — patrz programowanie logiczne ).

Rozszerzenia i aplikacje

Pierwotny artykuł Kowalskiego i Sergota dotyczący rachunku zdarzeń koncentrował się na zastosowaniach do aktualizacji i narracji baz danych. Rozszerzenia rachunku zdarzeń mogą również sformalizować działania niedeterministyczne, działania współbieżne, działania ze skutkami opóźnionymi, zmiany stopniowe, działania z czasem trwania, zmianę ciągłą i płynność nieinercyjną.

Kave Eshghi pokazał, w jaki sposób rachunek zdarzeń można wykorzystać do planowania, wykorzystując uprowadzenia do generowania hipotetycznych zdarzeń w programowaniu logiki abdukcyjnej . Van Lambalgen i Hamm pokazali, w jaki sposób rachunek zdarzeń można również wykorzystać do nadania semantyki algorytmicznej napięciom i aspektom w języku naturalnym przy użyciu programowania w logice z ograniczeniami .

Inne godne uwagi rozszerzenia rachunku zdarzeń obejmują warianty oparte na sieciach logicznych Markowa , warianty probabilistyczne , epistemiczne i ich kombinacje.

Narzędzia rozumowania

Oprócz Prologu i jego wariantów dostępnych jest również kilka innych narzędzi do wnioskowania za pomocą rachunku zdarzeń:

Zobacz też

Bibliografia

^ Kowalski, Robert; Sergot, Marek (1986-03-01). „Rachunek zdarzeń oparty na logice” . Obliczenia nowej generacji . 4 (1): 67–95. doi : 10.1007/BF03037383 . ISSN 1882-7055 . S2CID 7584513 .
^ Miller, Rob; Shanahan, Murray (2002), Kakas, Antonis C.; Sadri, Fariba (red.), „Some Alternative Formulations of the Event Calculus” , Computational Logic: Logic Programming and Beyond: Essays in Honor of Robert A. Kowalski Part II , Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, s. 452-490, doi : 10.1007/3-540-45632-5_17 , ISBN 978-3-540-45632-2, pobrane 2020-10-05
^ Kowalski Robert (1992-01-01). "Aktualizacje bazy danych w rachunku zdarzeń" . Dziennik programowania logicznego . 12 (1): 121-146. doi : 10.1016/0743-1066(92)90041-Z . ISSN 0743-1066 .
^ Eshghi, Kave (1988). „Planowanie abdukcyjne z rachunkiem zdarzeń” . Iclp /SLP : 562–579.
^ Lambalgen Hamm (2005). Właściwe traktowanie wydarzeń . Malden, MA: Pub Blackwell. Numer ISBN 978-0-470-75925-7. OCLC 212129657 .
^ Skarlatidis, Anastazjusz; Paliouras, Georgios; Artikis, Aleksander; Vouros, George A. (17.02.2015). "Rachunek prawdopodobieństwa zdarzeń do rozpoznawania zdarzeń" . Transakcje ACM w logice obliczeniowej . 16 (2): 11:1 do 11:37. arXiv : 1207.3270 . doi : 10.1145/2699916 . ISSN 1529-3785 . S2CID 6389629 .
^ Skarlatidis, Anastazjusz; Artikis, Aleksander; Filippou, Jazon; Paliouras, Georgios (marzec 2015). „Rachunek zdarzeń programowania probabilistycznego” . Teoria i praktyka programowania logicznego . 15 (2): 213–245. doi : 10.1017/S1471068413000690 . ISSN 1471-0684 . S2CID 5701272 .
^ Ma, Jiefei; Miller, Rob; Morgensterna, Leorze; Patkos, Teodor (28.07.2014). „Rachunek zdarzeń epistemicznych do rozumowania opartego na ASP na temat wiedzy o przeszłości, teraźniejszości i przyszłości” . Seria EPiC w informatyce . Fotel klubowy. 26 : 75-87. doi : 10.29007/zswj .
^ D'Asaro, Fabio Aurelio; Bikaki, Antonis; Dickens, Łukasz; Miller, Rob (01.10.2020). „Probabilistyczne rozumowanie na temat epistemicznych narracji akcji” . Sztuczna Inteligencja . 287 : 103352. doi : 10.1016/j.artint.2020.103352 . ISSN 0004-3702 .

Dalsza lektura

Brandano, S. (2001) " Ocena rachunku zdarzeń ", Sympozjum IEEE TIME : 7-12.
Kowalski R. i F. Sadri (1995) " Warianty rachunku zdarzeń " ICLP : 67-81.
Mueller, Erik T. (2015). Rozumowanie zdroworozsądkowe: podejście oparte na rachunku zdarzeń (wyd. 2) . Waltham, MA: Morgan Kaufmann/Elsevier. ISBN 978-0128014165 . (Przewodnik dotyczący korzystania z rachunku zdarzeń)
Shanahan, M. (1997) Rozwiązywanie problemu ramowego: matematyczne badanie zdroworozsądkowego prawa bezwładności . MIT Naciśnij.
Shanahan, M. (1999) „ Objaśnienie rachunku zdarzeń ” Springer Verlag, LNAI (1600): 409-30.

[1] Kowalski, Robert; Sergot, Marek (1986-03-01). „Rachunek zdarzeń oparty na logice” . Obliczenia nowej generacji . 4 (1): 67–95. doi : 10.1007/BF03037383 . ISSN 1882-7055 . S2CID 7584513 .

[2] Miller, Rob; Shanahan, Murray (2002), Kakas, Antonis C.; Sadri, Fariba (red.), „Some Alternative Formulations of the Event Calculus” , Computational Logic: Logic Programming and Beyond: Essays in Honor of Robert A. Kowalski Part II , Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, s. 452-490, doi : 10.1007/3-540-45632-5_17 , ISBN 978-3-540-45632-2, pobrane 2020-10-05

[3] Kowalski Robert (1992-01-01). "Aktualizacje bazy danych w rachunku zdarzeń" . Dziennik programowania logicznego . 12 (1): 121-146. doi : 10.1016/0743-1066(92)90041-Z . ISSN 0743-1066 .

[4] Eshghi, Kave (1988). „Planowanie abdukcyjne z rachunkiem zdarzeń” . Iclp /SLP : 562–579.

[5] Lambalgen Hamm (2005). Właściwe traktowanie wydarzeń . Malden, MA: Pub Blackwell. Numer ISBN 978-0-470-75925-7. OCLC 212129657 .

[6] Skarlatidis, Anastazjusz; Paliouras, Georgios; Artikis, Aleksander; Vouros, George A. (17.02.2015). "Rachunek prawdopodobieństwa zdarzeń do rozpoznawania zdarzeń" . Transakcje ACM w logice obliczeniowej . 16 (2): 11:1 do 11:37. arXiv : 1207.3270 . doi : 10.1145/2699916 . ISSN 1529-3785 . S2CID 6389629 .

[7] Skarlatidis, Anastazjusz; Artikis, Aleksander; Filippou, Jazon; Paliouras, Georgios (marzec 2015). „Rachunek zdarzeń programowania probabilistycznego” . Teoria i praktyka programowania logicznego . 15 (2): 213–245. doi : 10.1017/S1471068413000690 . ISSN 1471-0684 . S2CID 5701272 .

[8] Ma, Jiefei; Miller, Rob; Morgensterna, Leorze; Patkos, Teodor (28.07.2014). „Rachunek zdarzeń epistemicznych do rozumowania opartego na ASP na temat wiedzy o przeszłości, teraźniejszości i przyszłości” . Seria EPiC w informatyce . Fotel klubowy. 26 : 75-87. doi : 10.29007/zswj .

[9] D'Asaro, Fabio Aurelio; Bikaki, Antonis; Dickens, Łukasz; Miller, Rob (01.10.2020). „Probabilistyczne rozumowanie na temat epistemicznych narracji akcji” . Sztuczna Inteligencja . 287 : 103352. doi : 10.1016/j.artint.2020.103352 . ISSN 0004-3702 .

Languages

In other projects