Nächste Seite: 4.7.5 Lineare Logik Vorige Seite: 4.7.3 Lineare Konnektionsmethode

4.7.4 Gleichungslogik

1989 hat einer der Autoren zusammen mit Josef Schneeberger einen Ansatz zum deduktiven Planen entwickelt, der auf einer Hornlogik unter Einbeziehung einer speziellen Gleichungstheorie beruht [HS90]. Aussagen über Situationen werden darin mit Funktionen, dh. als Terme, dargestellt. Sobald in einer Situation mehrere Aussagen gelten, werden die sie repräsentierenden Funktionen mittels eines zweistelligen Funktors miteinander verknüpft, wobei assoziativ und kommutativ ist sowie die Konstante als Einselement besitzt.

Im Eisen und Schwefel Problem wird beispielsweise die Situation, in der sowohl Schwefel als auch Eisen vorliegt, durch den Term repräsentiert. In anderen Worten, alle Aussagen über eine Situation werden durch Situationsfluenten als Terme dargestellt und sind somit Objekte erster Klasse in einer Prädikatenlogik erster Stufe.

Aktionen und Pläne werden in dem in diesem Abschnitt vorgestellten Ansatz durch ein dreistelliges Prädikatszeichen repräsentiert. wird dabei wie folgt interpretiert. Die Ausführung von Plan in der Ausgangssituation führt in die Zielsituation . Mit dieser Interpretation können jetzt die Aktionen füge_Schwefel_hinzu, warte und erhitze_Eisen_und_Schwefel wie folgt dargestellt werden.

Somit erhalten wir ein logisches Programm im Sinne der logischen Programmierung, wobei jedoch die zugrunde liegende Horntheorie durch die Axiome (AC1) sowie die üblichen Axiome (E) der Gleichheit (Reflexivität, Symmetrie, Transitivität und Substitutivität) gegenüber einem (reinen) PROLOG-Programm erweitert wurde. Da in (4.23) nur Regeln spezifiziert sind, würde ein solches Programm niemals terminieren. Wir benötigen also noch ein Faktum.

Damit kann eine Berechnung dann erfolgreich beendet werden, wenn die Ausgangssituation gleich (modulo (AC1)) der Zielsituation ist, wobei , wie schon in der linearen Konnektionsmethode, als der leere Plan interpretiert wird.

Wie zuvor können wir jetzt fragen, ob das Hintereinanderausführen der füge_Schwefel_hinzu, warte und erhitze_Eisen_und_Schwefel Aktionen zu Schwefeleisen führt. Die Aufgabe besteht darin zu zeigen, daß

allgemeingültig ist. Man beachte, daß die hier verwendete Kodierung des Planes bis auf die Klammerung mit der in der linearen Konnektionsmethode verwendeten Kodierung übereinstimmt. Um die Allgemeingültigkeit von (4.25) nachzuweisen, müssen die Axiome (AC1) und (E) nicht explizit angeben, sondern können in den deduktiven Apparat -- genauer gesagt, in die Berechnung der Unifikatoren -- eingebaut werden (siehe Abschnitte 4.5 und 4.6 in [Bib92]). In anderen Worten, wenn wir zwei Atome miteinander unifizieren, dann suchen wir nicht nur nach einer Substitution, so daß die entsprechenden Instanzen der Atome syntaktisch gleich werden, sondern wir suchen nach einer Substitution, so daß die entsprechenden Instanzen der Atome unter der durch (AC1) und (E) defininierten Gleichungstheorie gleich werden. Verwenden wir anstelle des syntaktischen Unifikationsalgorithmus in der SLD-Resolution einen Unifikationsalgorithmus für die durch (AC1) und (E) defininierte Gleichungstheorie, so wollen wir die Ableitungsregel als SLDE-Resolution bezeichnen [Höl89]. Mit Hilfe der SLDE-Resolution können wir jetzt durch die in Abbildung 4.20 dargestellte Widerlegung nachweisen, daß (4.25) allgemeingültig ist.

Abbildung 4.20: Ein SLDE-Resolutionsbeweis für (4.25). Dabei wird die initiale Zielklausel nacheinander mit den Konklusionen der in (4.23) definierten Regeln für die Aktionen füge_Schwefel_hinzu, warte, und erhitze_Eisen_und_Schwefel modulo (AC1) und (E) unifiziert und durch die jeweilige, entsprechend instantiierte Bedingung ersetzt.

Das erste Argument des -Prädikats ist eine Realisierung des von McCarthy und Hayes vorgeschlagenen Rahmens. In der Definition einer Aktion (wie den in 4.23 angegebenen) werden nur die Aussagen spezifiziert, die durch die Ausführung der Aktion auch verändert werden. Alle eventuell vorhandenen übrigen Aussagen werden im Zuge der Unifikation unter (AC1) an die Variable gebunden und somit unverändert an die Resolvente weitergegeben. Dies wird insbesondere dann deutlich, wenn wir Terme der Form als Multimengen von Situationsfluenten , , interpretieren. Mit dieser Interpretation bedeutet die Anwendung einer Aktion in einer Situation , daß die Vorbedingungen der Aktion aus der durch definierten Multimenge entfernt werden und die Nachbedingungen der Aktion zu der so erhaltenen Multimenge hinzugefügt werden. Abbildung 4.21 zeigt die entsprechenden Multimengen für das Eisen und Schwefel Beispiel. Man beachte, daß wir einen Ausdruck der Form nicht als Menge interpretieren können, da nicht idempotent ist, dh. es gilt nicht .

Abbildung 4.21: Situationen sind Multimengen von Fluenten. Aktionen entfernen die Elemente aus einer Multimenge, die ihren Vorbedingungen entsprechen, und fügen neue Elemente hinzu, die ihren Nachbedingungen entsprechen. Die Abbildung zeigt die entsprechenden Situationsänderungen für das Eisen und Schwefel Beispiel.

Würden wir jedoch die Idempotenz zu (AC1) hinzufügen, dann hätten wir ein System ähnlich zu STRIPS spezifiziert. STRIPS ist ein von R.E. Fikes und N.J. Nilsson entwickeltes Planungssystem [FN71], das durch prädikatenlogische Ausdrücke beschriebene Situationen modelliert und dessen Aufgabe es ist, Sequenzen von Aktionen zu finden, die eine vorgegebene Ausgangssituation in eine Zielsituation überführen. Erst 1986 gelang es Vladimir Lifschitz, für eine Variante von STRIPS eine Semantik anzugeben [Lif86b]. In dieser Variante ist eine Situation durch eine (als Konjunktion aufzufassende) Menge von Grundatomen und beliebigen Aussagen einer Logik erster Stufe beschrieben. Während sich die Grundatome von einer Situation zur anderen ändern können -- genauer gesagt, Grundatome, die in einer Situation gelten, können in der nächsten Situation falsch sein und umgekehrt -- müssen die übrigen Aussagen in allen Situationen gelten. Eine Aktion wird dann durch ein Tripel angegeben, wobei ein prädikatenlogischer Ausdruck -- die sogenannte Vorbedingung -- ist und bzw. Listen von Grundatomen sind (engl. delete- bzw. add-list). Ausgehend von der initiatialen Situation definiert nun eine Sequenz von Aktionen eine Sequenz von Situationen durch

wenn für alle die Voraussetzung in erfüllt ist. Eine Sequenz von Aktionen löst ein Planungsproblem genau dann, wenn die Zielsituation, wiederum ein beliebiger prädikatenlogischer Ausdruck, in erfüllt ist.

STRIPS unterscheidet sich also von den zuvor dargestellten Planungsverfahren (lineare Konnektionsmethode und Hornlogik mit Gleichheit) im wesentlichen durch die Verwendung von Mengen -- im Gegensatz zu Multimengen -- zur Repräsentation von Situationen. Die übrigen Unterschiede, nämlich allgemeine prädikatenlogische Ausdrücke als Vorbedingung von Aktionen, als Eigenschaften, die in jeder Situation gelten müssen, und als Zielsituationen, sind nicht essentiell, da sich die zuvor genannten Ansätze entsprechend erweitern lassen.

Dieser entscheidende Unterschied der Verwendung von Multimengen macht die hier besprochenen Verfahren im Vergleich zu STRIPS wesentlich effizienter. Dies mag ein einfaches Beispiel verdeutlichen. Betrachten wir eine Domäne mit vier verschiedenen Münzen zu je 1 DM. Da wir bei einer Mengenrepräsentation die einzelnen Münzen unterscheiden müssen, gibt es verschiedene Situationen, wobei die Situationen, in denen wir keine bzw. alle vier Münzen haben, die entsprechenden Extremfälle sind. Im Alltag unterscheiden wir jedoch ia. nur fünf verschiedene Situationen: entweder wir haben keine, eine, zwei, drei oder vier DM. In anderen Worten, uns interessiert eigentlich nur die Kardinalität der (Multi-) Menge von 1 DM-Münzen, die auch im Multimengenansatz indiviuell nicht voneinander unterschieden werden. Diese Reduktion kann durchaus drastisch sein. Besteht die Domäne aus zwei Mineralwasserflaschen, vier 10 DM-Scheinen und vier 1 DM-Münzen, dann reduziert sich die Anzahl der verschiedenen Situation von auf und damit die Zahl der möglichen Situationsänderungen von auf ! Im Vergleich zu STRIPS realisieren die obigen Verfahren diese Reduktion, da in der Multimengenrepräsentation gleichartige Objekte eben nicht unterschieden werden müssen. Dies ist auch eine sehr natürliche Reduktion, denn kaufen wir Mineralwasser und benutzen dafür eine von vier 1 DM-Münzen, dann wissen wir in der Regel nicht, welche der verschiedenen Münzen wir benutzt haben.