Situation Calculus

In der Sprache Golog (Algorithmic Language based on Situation Calculus). Man programmiert High-Level-Roboter. proc go_to_office { while not at_office do move_forward end }. Der Interpreter (Prolog) beweist dann, welche Aktionen nötig sind, damit at_office wahr wird. Es ist Programmieren in Logik.

1. Fluents

Prädikate, die sich ändern können. Rain(S) ist ein Fluent. (Es regnet in Situation S). MountainSize(S) ist (meist) statisch (kein Fluent). Man muss für jedes Fluent definieren, wie es auf Aktionen reagiert (Successor State Axioms). Poss(A, S): Wann ist Aktion A möglich? Rain(do(A, S)) <-> (A = StartRain) v (Rain(S) & A != StopRain). (Es regnet im nächsten Schritt, wenn ich Regen starte ODER es schon geregnet hat und ich nicht stoppe). Das löst das Frame Problem sauber (aber geschwätzig).

2. Regression

Wie prüft man LichtAn(do(C, do(B, do(A, S0))))? Man rechnet rückwärts (Regression) bis $S_0$. Da man den Startzustand kennt, kann man alles beweisen. Lange Historien machen das aber langsam.

1. Successor State Axioms & The Frame Problem

John McCarthy erfand den Kalkül, aber Raymond Reiter löste 1991 das Frame-Problem darin. Anstatt für jede Aktion zu schreiben, was sich nicht ändert, nutzt man Successor State Axioms. Die Formel lautet: Fluent(do(a, s)) <-> (Aktion_a_macht_es_wahr) v (Fluent(s) & Aktion_a_macht_es_nicht_falsch). Das ist mathematisch elegant, weil man pro Fluent nur noch genau eine Gleichung braucht. In der Produktion (KI-Systeme) reduziert dies die Anzahl der Axiome von $O(A \cdot F)$ auf $O(A + F)$, was den Unterschied zwischen "rechnet ewig" und "funktioniert" ausmacht.

2. The Projection Problem

Das Hauptproblem in der Anwendung: "Wenn ich die Aktionen $A_1, A_2, \dots A_n$ mache, gilt dann am Ende $\phi$?" Dies nennt man Projection. Es wird durch Regression gelöst: Man transformiert die Anfrage $\phi(S_{final})$ Schritt für Schritt rückwärts durch die Aktionen, bis eine Formel entsteht, die nur noch den Startzustand $S_0$ betrifft. In der Robotik erlaubt dies dem Roboter zu "träumen": Er prüft im Kopf, ob sein Plan funktionieren wird, bevor er den ersten Arm-Motor bewegt.

3. GOLOG und High-Level Control

GOLOG (Logic for Programming) ist die praktische Anwendung des Kalküls. Es erlaubt nicht-deterministische Programme: (A | B); C ("Mach A oder B, dann C"). Der Interpreter sucht nun eine Sequenz von atomaren Aktionen (einen Pfad im Situations-Baum), die das Programm erfolgreich beendet. Das ist ideal für dynamische Umgebungen (z.B. Logistik-Roboter in einem Lager), wo der Roboter zwar ein festes Programm hat, aber flexibel entscheiden muss, welchen Gang er nimmt, wenn einer durch ein Hindernis blockiert ist.