STRIPS

Im Bereich Künstliche Intelligenz beschreibt STRIPS (Stanford Research Institute Problem Solver) einen automatischen Planer, entwickelt von Richard Fikes und Nils Nilsson im Jahre 1971. Der Name STRIPS wurde später verwendet, um sich auf die Formale Sprache zu beziehen, die als Eingabe für den Planer diente. Diese Sprache bietet heutzutage die Grundlage zum Beschreiben der meisten Problemdomänen. Dieser Artikel bezieht sich nur auf die Sprache, nicht auf den Planer.

Definition

Ein STRIPS-Modell besteht aus:

• einem Anfangszustand;
• einem Zielzustande, also die Situation, die der Planer erreichen will;
• eine Menge von Aktionen. Für jede Aktion muss Folgendes gegeben sein:
  • Vorbedingungen (was muss gegeben sein, bevor die Aktion ausgeführt werden kann);
  • Nachbedingungen (was ist erreicht, nachdem die Aktion ausgeführt wurde).

Mathematisch gesehen, ist ein STRIPS-Modell ein 4-Tupel $\langle P,O,I,G \rangle$, in dem jede Komponente folgende Bedeutung hat:

1. P ist eine Menge von Bedingungen;
2. O ist eine Menge von Operationen; jeder Operator ist dabei selbst ein 4-Tupel $\langle \alpha, \beta, \gamma, \delta \rangle$, wobei jedes Element eine Menge von Bedingungen ist. Die vier Mengen beschreiben in gegebener Reihenfolge, welche Bedingungen müssen wahr sein, damit die Aktion ausgeführt werden kann, welche Bedingungen müssen falsch sein, welche Bedingungen werden durch das Ausführen der Aktion wahr, welche werden falsch;
3. I der Startzustand, beschrieben durch eine Menge von Bedingungen, die zu Beginn wahr sind (alle anderen sind demnach falsch);
4. G der Zielzustand; gegeben als Paar $\langle N,M \rangle$, das Beschreibt, welche Bedingungen wahr und welche falsch sein müssen.

Ein Plan in einem solchen Planungsmodell ist eine Sequenz von Aktionen, die vom Startzustand aus erfolgen und zu dem Zielzustand führen.

Formal gesehen, ist ein Zustand eine Menge von Bedingungen – ein Zustand wird dabei von den Bedingungen beschrieben, die wahr sind.

Übergänge zwischen den Zuständen werden durch eine Übergangsfunktion beschrieben, die einen Zustand und eine Aktion auf einen anderen Zustand abbildet:

$\operatorname{t}: 2^P \times O \rightarrow 2^P,$, indem 2^P Menge aller Teilmengen von P ist, und somit alle möglichen Zustände bei einer gegebenen Menge P von Bedingungen.

Die Übergangsfunktion kann wie folgt definiert werden, wobei davon ausgegangen wird, dass Aktionen immer ausgeführt werden können, jedoch keinen Effekt haben, wenn ihre Vorbedingungen nicht erfüllt sind:

$\operatorname{t}(C,\langle \alpha,\beta,\gamma,\delta \rangle)$	= $C \backslash \delta \cup \gamma$	falls $\alpha \subseteq C$ und $\beta \cap C = \varnothing$
	= P	sonst

Die Übergangsfunktion $\operatorname{t}$ kann auf Folgen von Aktionen mittels Rekursion angewandt werden:

$\operatorname{t}(C,[\ ]) = C$

$\operatorname{t}(C,[a_1,a_2,\ldots,a_n])=\operatorname{t}(\operatorname{t}(C,a_1),[a_2,\ldots,a_n])$

Ein Plan für ein STRIPS-Modell ist eine Folge von Aktionen, sodass der Zustand, der aus der Folge von Aktionen resultiert, angefangen beim Startzustand, letztendlich zum Zielzustand führt. Formal $[a_1,a_2,\ldots,a_n]$ ist ein Plan für $G = \langle N,M \rangle$, falls $F=\operatorname{t}(I,[a_1,a_2,\ldots,a_n])$ die folgenden beiden Bedingungen erfüllt:

$N \subseteq F$

$M \cap F = \varnothing$

Beispiel für ein STRIPS-Problem

Ein Affe ist an der Position A in einem Labor. Eine Box steht an der Position C. Der Affe möchte die Bananen haben, die von der Decke an der Position B hängen. Er muss jedoch die Box bewegen und auf sie klettern, um sie zu erreichen.

Anfangszustand: At(A), Level(low), BoxAt(C), BananasAt(B) Zielzustand: Have(Bananas)

Aktionen:
               // move from X to Y
               _Move(X, Y)_
               Preconditions:  At(X), Level(low)
               Postconditions: not At(X), At(Y)
               
               // climb up on the box
               _ClimbUp(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(low)
               Postconditions: Level(high), not Level(low)
               
               // climb down from the box
               _ClimbDown(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(high)
               Postconditions: Level(low), not Level(high)
               
               // move monkey and box from X to Y
               _MoveBox(X, Y)_
               Preconditions:  At(X), BoxAt(X), Level(low)
               Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
               
               // take the bananas
               _TakeBananas(Location)_
               Preconditions:  At(Location), BananasAt(Location), Level(high)
               Postconditions: Have(bananas)

Quellen

• C. Bäckström and B. Nebel (1995). Complexity results for SAS+ planning. Computational Intelligence, 11:625-656.
• T. Bylander (1991). Complexity results for planning. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI'91), pages 274-279.
• R. Fikes and N. Nilsson (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189-208.
• Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz, August 2004, Pearson Studium, ISBN 3-8273-7089-2 (deutsche Übersetzung der 2. Auflage)