Situationskalkül

Beim Situationskalkül handelt es sich um ein Konzept der künstlichen Intelligenz. Es werden Auswirkungen von Aktionen auf Situationen in einer Modellwelt unter Verwendung der Prädikatenlogik beschrieben. Angewendet wird der Situationskalkül zum Beispiel in der Sprache GOLOG, welche unter anderem in der Robotik zur Aktionsplanung eingesetzt wird.

Es geht auf John McCarthy und Pat Hayes in den 1960er Jahren zurück. Weiterentwickelt wurde er von Ray Reiter in den 1990er Jahren.

Beschreibung der Modellwelt

Die Durchführung einer Aktion a führt zu einer Nachfolgesituation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{i+1}} , die von der vorherigen Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_i} und der durchgeführten Aktion abhängig ist. Das lässt sich formal durch eine binäre Funktion $do(a,s)$ ausdrücken: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{i+1}=do(a,s_i)} . Nicht jede Aktion lässt sich in jeder Situation durchführen. Die Durchführbarkeit lässt sich mit Hilfe des Prädikats Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Poss(a,s)} definieren, welches in allen Situationen wahr ist, in denen die Aktion erlaubt ist. Für diese Definition sind häufig situationsabhängige Prädikate notwendig. Relationen, die ihren Wahrheitswert über die Zeit ändern, heißen Fluents.

Beispiel

Als Beispiel dient ein Schrank mit mehreren Schubladen. Aus den Schubladen können Gegenstände genommen werden, die Schubladen können geöffnet und geschlossen werden. Dieser Sachverhalt lässt sich folgendermaßen beschreiben:

• Geschlossene Schubladen können geöffnet werden! → Die Schublade x lässt sich genau in den Situationen s öffnen, in denen sie geschlossen ist.

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\textrm {Poss}}({\mathit {oeffneSchublade}}(x),s)\equiv {\mathit {istGeschlossen}}(x,s)}

• Wenn man eine Schublade öffnet, dann ist sie danach geöffnet! → Wird die Schublade x in einer Situation s geöffnet, so folgt daraus, dass sie in der darauffolgenden Situation nicht mehr geschlossen ist.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{Poss}(\mathit{oeffneSchublade}(x),s)\rightarrow \neg \mathit{istGeschlossen}(x,\textrm{do}(\mathit{oeffneSchublade}(x),s))}

• Gegenstände, die sich in einer geöffneten Schublade befinden, können herausgenommen werden! → Der Gegenstand y kann genau in den Situationen s aus der Schublade x genommen werden, in denen gleichzeitig die Schublade nicht geschlossen ist und sich der Gegenstand in der Schublade befindet.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{Poss}(\mathit{nimmAusSchublade}(x,y),s)\equiv \neg \mathit{istGeschlossen}(x,s) \wedge \mathit{istInSchublade}(x,y,s)}

• Nimmt man einen Gegenstand raus, dann ist er danach nicht mehr in der Schublade! → Wird der Gegenstand y in einer Situationen s aus der Schublade x genommen, so befindet sich der Gegenstand in der nachfolgenden Situation nicht mehr in der Schublade.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{Poss}(\mathit{nimmAusSchublade}(x,y),s)\rightarrow \neg \mathit{istInSchublade}(x,y,\textrm{do}(\mathit{nimmAusSchublade}(x,y),s))}

• Geöffnete Schubladen können geschlossen werden! → Die Schublade x lässt sich genau in den Situationen s schließen, in denen sie nicht geschlossen ist.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{Poss}(\mathit{schliesseSchublade}(x),s)\equiv \neg \mathit{istGeschlossen}(x,s)}

• Wenn man eine Schublade schließt, dann ist sie danach geschlossen! → Wird die Schublade x in einer Situation s geschlossen, so folgt daraus, dass sie in der darauffolgenden Situation geschlossen ist.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{Poss}(\mathit{schliesseSchublade}(x),s)\rightarrow \mathit{istGeschlossen}(x,\textrm{do}(\mathit{schliesseSchublade}(x),s))}

Rahmenproblem

→ Hauptartikel: Rahmenproblem

Das vorangegangene Beispiel führt direkt zum Rahmenproblem, da die Klauseln noch nicht ausreichen, um die Welt zu beschreiben. Es fehlen noch triviale Klauseln, die nur aussagen, dass alle anderen Dinge durch die Aktionen nicht verändert werden. Diese Klauseln werden schon bei kleinen Welten außerordentlich zahlreich: Bei 100 verschiedenen Aktionen mit 50 Fluenten sind schon zirka 10000 Klauseln zur Beschreibung notwendig. Raymond Reiter hat für dieses Problem 1991 eine Lösung gefunden, die nur eine Klausel zur Darstellung eines Fluenten benötigt:

• Wenn es möglich ist, eine Aktion a in einer Situation s durchzuführen, dann folgt daraus, dass die Schublade genau dann in der Nachfolgesituation geschlossen ist, wenn entweder die Aktion a das Schließen der Schublade war oder wenn die Schublade vorher schon geschlossen war, und es sich bei der Aktion nicht um das Öffnen der Schublade gehandelt hat.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{Poss}(a,s)\rightarrow [\mathit{istGeschlossen}(x,\textrm{do}(a,s))\equiv [\, \, a=\mathit{schliesseSchublade}(x)\, \, \vee \, \, \mathit{istGeschlossen}(x,s)\, \wedge\, a\neq \mathit{oeffneSchublade}(x)\, \, ]]}

Dieser Lösungsansatz ist unter dem Namen Successor State Axiom bekannt.

Axiome des Situationskalküls

Die Axiome sind folgende Klauseln, die in jeder Welt gelten:

Es gibt genau eine Anfangssituation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_0} , keine Situation $s$ liegt vor der Anfangssituation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \neg (s\sqsubset S_{0})}

Jede Situation ist einmalig. Wenn zwei Situationen gleich sind, die durch die Aktion $a_{1}$ in der Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1} und durch die Aktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_2} in der Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_2} entstanden sind, dann sind sowohl die Situationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_1} und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle s_{2}} gleich, als auch die Aktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_2} .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{do}(a_{1},s_{1})\! =\! \textrm{do}(a_{2},s_{2})\; \rightarrow \; a_{1}\! =\! a_{2}\, \wedge \, s_{1}\! =\! s_{2}}

Eine Aussage ist in allen Situationen wahr, wenn sie in der Anfangssituation wahr ist, und die Aussage auch nach Durchführung einer beliebigen Aktion in einer beliebigen Situation wahr bleibt.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall \textrm{P}.\quad \textrm{P}(S_{0})\, \wedge \, \forall a\, \forall s\left[\textrm{P}(s)\! \rightarrow \! \textrm{P}(\textrm{do}(a,s))\right]\; \rightarrow \; \forall s\, \textrm{P}(s) }

Ein Teil der Situationen ist sortierbar. Der Vergleichsoperator Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqsubset} wird rekursiv definiert: Eine Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{1}} , die vor einer Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{do}(a,s_{2})} liegt, die sich durch Ausführung der Aktion $a$ in der Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{2}} ergibt, ist entweder die Situation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{2}} oder eine Situation, die vor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{2}} liegt.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{1}\sqsubset \textrm{do}(a,s_{2})\, \, \equiv \, \, s_{1}\! =\! s_{2}\, \vee \, s_{1}\sqsubset s_{2}\, \, \equiv \, \, s_{1}\sqsubseteq s_{2}}

Bemerkung

Wenn man als Anfangsbedingung setzt, dass sich ein Ball in der geschlossenen linken Schublade befindet, und als Ziel, dass der Ball sich dort nicht mehr befinden soll, lässt sich unter Berücksichtigung aller Klauseln ein Plan berechnen, der die linke Schublade öffnet und den Ball aus der Schublade nimmt.

Siehe auch

• Logikkalkül

Literatur

• Hermann Scheffler: Der Situationskalkul. Versuch einer arithmetischen Darstellung der niederen und höheren Geometrie auf Grund einer abstrakten Auffassung der räumlichen Größen, Formen und Bewegungen. Braunschweig, Friedrich Vieweg, 1851.
• Christoph Beierle, Gabriele Kern-Isberner: Methoden wissensbasierter Systeme: Grundlagen, Algorithmen, Anwendungen. Teubner-Verlag, 2008, S. 304.
• Raymond Reiter: Knowledge in Action. Logical Foundations for Specifying and Implementing Dynamical Systems. 2001, ISBN 0-262-18218-1.
• Raymond Reiter: The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. In: Vladimir Lifschitz (Hrsg.): Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, S. 359–380. Academic Press, New York, 1991. ISBN 0-124-50010-2.