STRIPS

STRIPS (Stanford Research Institute Problem Solver ) is a standard developed by Richard Fikes and Nils Nilsson in 1971 automatic planner. The name STRIPS was used later to refer to the formal language that served as input for the planner and today provides the basis for describing the most problem domains. This article refers only to the language, not the planner.

Definition

A STRIPS model consists of:

  • An initial state;
  • A target state, that is, the situation that will achieve the scheduler;
  • A set of actions. For each action, the following must be met: Preconditions ( what must be given before the action can be executed);
  • Postconditions (which is reached after the action was executed ).

Mathematically, a STRIPS model is a 4- tuple, where each component has the following meaning:

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

Formally, a state is a set of conditions - a condition is described here of the conditions are true.

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

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

The transition function can be applied to sequences of actions using recursion:

A plan for a STRIPS model is a sequence of actions, so that the condition resulting from the sequence of actions, starting with the start state, ultimately leading to the goal state. Formally, a plan for if the following two conditions are met:

Example of a STRIPS problem

A monkey is at position A in a laboratory. A box is at position C. The monkey wants the banana, the B hanging from the ceiling at the position. However, he needs to move the box and climb on them to reach them.

Actions:                 / / 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.
  • Bylander T. (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 Education, ISBN 3-8273-7089-2 ( German translation of the 2nd edition)
  • Artificial intelligence
745298
de