STRIPS

STRIPS ( St Anford R esearch I nstitute P roblem S olver) is one of Richard Fikes and Nils Nilsson developed in 1971 automatic planner. The name STRIPS was later used to refer to the formal language that served as input to the planner and which today provides the basis for describing most problem domains . This article is for the language only, not the planner.

definition

A STRIPS model consists of:

an initial state;
a target state, i.e. the situation that the planner wants to achieve;
a lot of actions. For each action the following must be given:
- Preconditions (what must be given before the action can be performed);
- Postconditions (what is achieved after the action is taken).

Mathematically speaking, a STRIPS model is a 4-tuple in which each component has the following meaning: ${\ displaystyle \ langle P, O, I, G \ rangle}$

${\ displaystyle P}$ is a lot of conditions ;
${\ displaystyle O}$ is a lot of operations ; each operator is itself a 4-tuple , where each element is a set of conditions. The four sets describe in given order which conditions must be true for the action to be carried out, which conditions must be false, which conditions become true when the action is carried out, which become false; ${\ displaystyle \ langle \ alpha, \ beta, \ gamma, \ delta \ rangle}$
${\ displaystyle I}$ the starting state, described by a set of conditions that are initially true (all others are therefore false);
${\ displaystyle G}$ the target state; given as a pair that describes which conditions must be true and which must be false. ${\ displaystyle \ langle N, M \ rangle}$

A plan in such a planning model is a sequence of actions that take place from the starting state and lead to the target state.

Formally, a state is a set of conditions - a state is described by the conditions that are true.

Transitions between the states are described by a transition function that maps a state and an action to another state:

{\ displaystyle \ operatorname {t}: 2 ^ {P} \ times O \ rightarrow 2 ^ {P},}

where is set of all subsets of , and thus all possible states for a given set P of conditions.

{\ displaystyle 2 ^ {P}}

{\ displaystyle P}

The transition function can be defined as follows, assuming that actions can always be performed, but have no effect if their preconditions are not met:

${\ displaystyle \ operatorname {t} (C, \ langle \ alpha, \ beta, \ gamma, \ delta \ rangle)}$	= ${\ displaystyle C \ backslash \ delta \ cup \ gamma}$	if and ${\ displaystyle \ alpha \ subseteq C}$ ${\ displaystyle \ beta \ cap C = \ varnothing}$
	= ${\ displaystyle C}$	otherwise

The transition function can be applied to sequences of actions using recursion: ${\ displaystyle \ operatorname {t}}$

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

{\ displaystyle \ operatorname {t} (C, [a_ {1}, a_ {2}, \ ldots, a_ {n}]) = \ operatorname {t} (\ operatorname {t} (C, a_ {1} ), [a_ {2}, \ ldots, a_ {n}])}

A plan for a STRIPS model is a sequence of actions, so that the state that results from the sequence of actions, starting with the starting state, ultimately leads to the target state. Formal is a plan for if the following two conditions are met: ${\ displaystyle [a_ {1}, a_ {2}, \ ldots, a_ {n}]}$ ${\ displaystyle G = \ langle N, M \ rangle}$ ${\ displaystyle F = \ operatorname {t} (I, [a_ {1}, a_ {2}, \ ldots, a_ {n}])}$

{\ displaystyle N \ subseteq F}

{\ displaystyle M \ cap F = \ varnothing}

Example of a STRIPS problem

A monkey is at position A in a laboratory. There is a box at position C. The monkey wants the bananas that are hanging from the ceiling at position B. However, he has to move the box and climb on it to reach it.

Initial state: At (A), Level (low), BoxAt (C), BananasAt (B)

Target state: 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)

swell

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: Artificial Intelligence: A Modern Approach , August 2004, Pearson Studies, ISBN 3-8273-7089-2 (German translation of the 2nd edition)