Ereignisrechnung - Event calculus

Die Ereignisrechnung ist eine logische Sprache zur Darstellung und Begründung von Ereignissen und deren Auswirkungen, die erstmals 1986 von Robert Kowalski und Marek Sergot vorgestellt wurde. Sie wurde in den 1990er Jahren von Murray Shanahan und Rob Miller erweitert . Ähnlich wie in anderen Sprachen zum Nachdenken über Veränderungen repräsentiert die Ereigniskalkulation die Auswirkungen von Handlungen auf fließende Sprachkenntnisse . Allerdings Ereignisse können auch außerhalb des Systems sein. In der Ereignisrechnung kann man den Wert von Flusen zu bestimmten Zeitpunkten, die Ereignisse, die zu bestimmten Zeitpunkten stattfinden, und deren Auswirkungen angeben.

Fließend und Veranstaltungen

In der Ereignisrechnung werden Fließen verdinglicht . Das heißt, sie werden nicht durch Prädikate, sondern durch Funktionen formalisiert . Ein separates Prädikat HoldsAt wird verwendet, um anzugeben, welche Fluents zu einem bestimmten Zeitpunkt gültig sind. Bedeutet beispielsweise, dass die Box zum Zeitpunkt t auf dem Tisch liegt ; In dieser Formel ist HoldsAt ein Prädikat, während on eine Funktion ist.

Ereignisse werden auch als Begriffe dargestellt. Die Auswirkungen von Ereignissen werden mit den Prädikaten Initiates und Terminates angegeben . Bedeutet insbesondere, dass, wenn das durch den Ausdruck e dargestellte Ereignis zum Zeitpunkt t ausgeführt wird , der Fluss f nach t wahr ist . Das Prädikat Terminates hat eine ähnliche Bedeutung, mit dem einzigen Unterschied, dass f nach t falsch ist .

Domänenunabhängige Axiome

Wie andere Sprachen zur Darstellung von Aktionen formalisiert der Ereigniskalkül die korrekte Entwicklung der fließenden Sprache über Formeln, die den Wert jeder fließenden Sprache angeben, nachdem eine beliebige Aktion ausgeführt wurde. Der Ereigniskalkül löst das Rahmenproblem auf ähnliche Weise wie die Nachfolgezustandsaxiome des Situationskalküls : Ein fließend ist zum Zeitpunkt t genau dann wahr, wenn es in der Vergangenheit wahr gemacht wurde und in der nicht falsch gemacht wurde inzwischen.

Diese Formel bedeutet, dass das durch den Term f repräsentierte Fluid zum Zeitpunkt t wahr ist, wenn:

  1. ein Ereignis e hat stattgefunden: ;
  2. dies geschah in der Vergangenheit: ;
  3. dieses Ereignis hat das fließende f als Auswirkung: ;
  4. das Fließende wurde zwischenzeitlich nicht falsch gemacht:

Eine ähnliche Formel wird verwendet, um den umgekehrten Fall zu formalisieren, in dem ein Fließen zu einem bestimmten Zeitpunkt falsch ist. Es werden auch andere Formeln benötigt, um Fluide korrekt zu formalisieren, bevor sie Auswirkungen eines Ereignisses waren. Diese Formeln ähneln den obigen, werden jedoch durch ersetzt .

Das Clipped- Prädikat, das angibt, dass ein Fließen während eines Intervalls falsch gemacht wurde, kann wie folgt axiomatisiert oder einfach als Abkürzung genommen werden:

Domänenabhängige Axiome

Die obigen Axiome beziehen sich auf den Wert der Prädikate HoldsAt , Initiates und Terminates , spezifizieren jedoch nicht, welche Fluents als wahr bekannt sind und welche Ereignisse Fluktuationen tatsächlich wahr oder falsch machen. Dies geschieht durch die Verwendung einer Reihe von domänenabhängigen Axiomen. Die bekannten Werte von fließend werden als einfache Literale angegeben . Die Auswirkungen von Ereignissen werden durch Formeln angegeben, die die Auswirkungen von Ereignissen mit ihren Voraussetzungen in Beziehung setzen. Wenn beispielsweise das Ereignis open den fließenden isopen wahr macht, aber nur, wenn haskey aktuell wahr ist, lautet die entsprechende Formel im Ereigniskalkül:

Der rechte Ausdruck dieser Äquivalenz besteht aus einer Disjunktion: Für jedes Ereignis und fließend, das durch das Ereignis wahr gemacht werden kann, gibt es eine Disjunktion, die besagt, dass e tatsächlich dieses Ereignis ist, dass f tatsächlich so fließend ist und dass die Voraussetzung für die Veranstaltung ist gegeben.

Die obige Formel gibt den Wahrheitswert von für jedes mögliche Ereignis und fließend an. Daher müssen alle Wirkungen aller Ereignisse in einer einzigen Formel zusammengefasst werden. Dies ist ein Problem, da das Hinzufügen eines neuen Ereignisses das Ändern einer vorhandenen Formel erfordert, anstatt neue hinzuzufügen. Dieses Problem kann durch die Anwendung der Umschreibung auf eine Reihe von Formeln gelöst werden, die jeweils einen Effekt eines Ereignisses angeben:

Diese Formeln sind einfacher als die obige Formel, da jeder Effekt jedes Ereignisses separat angegeben werden kann. Die einzige Formel, die angibt , welche Ereignisse e und Fließen f wahr machen , wurde durch eine Reihe kleinerer Formeln ersetzt, von denen jede die Auswirkung eines Ereignisses auf ein Fließen angibt .

Diese Formeln entsprechen jedoch nicht der obigen Formel. Tatsächlich spezifizieren sie nur hinreichende Bedingungen , um wahr zu sein, was durch die Tatsache ergänzt werden sollte, dass Initiates in allen anderen Fällen falsch ist. Diese Tatsache kann formalisiert werden, indem man einfach das Prädikat Eingeweihte in der obigen Formel umschreibt . Es ist wichtig zu beachten, dass diese Umschreibung nur bei den Formeln erfolgt, die Eingeweihte spezifizieren und nicht bei den domänenunabhängigen Axiomen. Das Prädikat Terminates kann auf die gleiche Weise wie Initiates angegeben werden.

Ein ähnlicher Ansatz kann für das Happens- Prädikat gewählt werden. Die Auswertung dieses Prädikats kann durch Formeln erzwungen werden, die nicht nur angeben, wann es wahr und wann es falsch ist:

Die Umschreibung kann diese Spezifikation vereinfachen, da nur notwendige Bedingungen angegeben werden können:

Das Prädikat Happens umschreibend , ist dieses Prädikat an allen Stellen falsch, an denen es nicht explizit als wahr angegeben ist. Diese Umschreibung muss getrennt von der Umschreibung der anderen Formeln erfolgen. Mit anderen Worten, wenn F die Menge der Formeln der Art ist , G die Menge der Formeln und H die gebietsunabhängigen Axiome sind, lautet die korrekte Formulierung des Gebietes:

Die Ereignisrechnung als Logikprogramm

Der Ereigniskalkül wurde ursprünglich als eine Menge von Hornklauseln formuliert , die durch Negation als Fehler ergänzt wurden und als Prolog- Programm ausgeführt werden konnte. Tatsächlich ist die Umschreibung eine von mehreren Semantiken, die der Negation als Misserfolg zugeschrieben werden können, und ist eng mit der Vervollständigungssemantik verbunden (in der "wenn" als "wenn und nur wenn" interpretiert wird - siehe logische Programmierung ).

Erweiterungen und Anwendungen

Das ursprüngliche Papier zur Ereignisrechnung von Kowalski und Sergot konzentrierte sich auf Anwendungen für Datenbankaktualisierungen und Erzählungen. Erweiterungen des Ereigniskalküls können auch nicht-deterministische Aktionen, gleichzeitige Aktionen, Aktionen mit verzögerten Effekten, graduelle Änderungen, Aktionen mit Dauer, kontinuierliche Änderung und nicht-Trägheitsflüsse formalisieren.

Kave Eshghi zeigte, wie der Ereigniskalkül für die Planung verwendet werden kann, indem er Entführung verwendet , um hypothetische Ereignisse in der abduktiven Logikprogrammierung zu generieren . Van Lambalgen und Hamm zeigten , wie der Ereigniskalkül auch verwendet werden kann , um eine algorithmische Semantik für Tempus und Aspekt in natürlicher Sprache mit Hilfe von Constraint Logic - Programmierung zu geben .

Andere bemerkenswerte Erweiterungen des Event Calculus umfassen auf Markov Logic Networks basierende, probabilistische , epistemische Varianten und deren Kombinationen.

Argumentationshilfen

Neben Prolog und seinen Varianten stehen noch einige weitere Werkzeuge zur Argumentation mit der Ereignisrechnung zur Verfügung:

Siehe auch

Verweise

  1. ^ Kowalski, Robert; Sergot, Marek (1986-03-01). "Eine logikbasierte Ereignisrechnung" . Computer der neuen Generation . 4 (1): 67–95. doi : 10.1007/BF03037383 . ISSN  1882-7055 . S2CID  7584513 .
  2. ^ Müller, Rob; Shanahan, Murray (2002), Kakas, Antonis C.; Sadri, Fariba (Hrsg.), "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, pp . 452–490, doi : 10.1007/3-540-45632-5_17 , ISBN 978-3-540-45632-2, abgerufen 2020-10-05
  3. ^ Kowalski, Robert (1992-01-01). "Datenbankaktualisierungen in der Ereignisrechnung" . Die Zeitschrift für Logikprogrammierung . 12 (1): 121-146. doi : 10.1016/0743-1066(92)90041-Z . ISSN  0743-1066 .
  4. ^ Eshghi, Kave (1988). "Abduktive Planung mit Ereignisrechnung" . Iclp/SLP : 562–579.
  5. ^ Lambalgen, Hamm (2005). Die richtige Behandlung von Ereignissen . Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC  212129657 .
  6. ^ Skarlatidis, Anastasios; Paliouras, Georgios; Artikis, Alexander; Vouros, George A. (2015-02-17). "Probabilistische Ereignisrechnung zur Ereigniserkennung" . ACM-Transaktionen auf Computerlogik . 16 (2): 11:1–11:37. arXiv : 1207.3270 . doi : 10.1145/2699916 . ISSN  1529-3785 . S2CID  6389629 .
  7. ^ Skarlatidis, Anastasios; Artikis, Alexander; Filippou, Jason; Paliouras, Georgios (März 2015). "Ein probabilistischer Logikprogrammierungsereigniskalkül" . Theorie und Praxis der logischen Programmierung . 15 (2): 213–245. doi : 10.1017/S1471068413000690 . ISSN  1471-0684 . S2CID  5701272 .
  8. ^ Ma, Jiefei; Müller, Rob; Morgenstern, Leora; Patkos, Theodore (2014-07-28). „Ein epistemischer Ereigniskalkül für ASP-basiertes Denken über das Wissen der Vergangenheit, Gegenwart und Zukunft“ . EPiC-Serie in der Informatik . Sessel. 26 : 75–87. doi : 10.29007/zswj .
  9. ^ D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Lukas; Müller, Rob (01.10.2020). "Probabilistische Argumentation über epistemische Handlungserzählungen" . Künstliche Intelligenz . 287 : 103352. doi : 10.1016/j.artint.2020.103352 . ISSN  0004-3702 .

Weiterlesen