STRIPS

STRIPS (or STanford Research Institute Problem Solver ) is a traditional algorithm of Planification designed by Richard Fikes and the Nile Nilsson in 1971. The algorithm of STRIPS is rather basic, but it is interesting like teaching example. One also names by this name the language of representation of the data used by the algorithm.

With GPS (General Problem Solver) of Newell and Simon of 1961, it belongs to the first planners used in Artificial intelligence and followed many derivatives (GraphPlan, IP, STAN, etc).

Description of the algorithm

General principle

The algorithm of STRIPS functions according to the analyzes ends and means (or Mean Ends Analysis ) stated by Aristote: one leaves the goals which one wants to reach and one tries to find the means which can lead to it. That produced of new goals which one tries to solve and so on until one falls on the assumptions from departure. The plan is then obtained while walking on opposite direction. In practice the algorithm calculates the difference between the states of the world which he considers. He considers actions able to reduce these differences and combines them to build the plan.

Elements of the algorithm

The components of this algorithm are:

the predicates describing the world, for example: dansPiece (objet4, piece2)
the possible states of the world, each state is a whole of predicates.
the goals which are conjunctions of predicates
the actions (also called operators ) defined by their preconditions and their modifications on the state of the world.

the preconditions are a conjunction of predicates. Each one of these predicates must be checked at the time when the action is carried out.
the modifications can be represented like a list of addition and a list of suppression of predicates.

the pile of treatments containing actions to be carried out and goals and under-goals to carry out

Operation

The algorithm maintains a representation of the world which evolves/moves during the unfolding of the algorithm. During this unfolding, the algorithm can decide to carry out an action which will modify the state of the world.

The algorithm consists to store in a pile a succession of goals and actions to be achieved. The initial goal is positioned in bottom of the pile, the under-goals appear with the top, and the under-under-goals even higher…

With each stage, one treats the element in top of the pile.

It presents two cases:

if it is about a goal:

If the goal is checked in the current world, it is removed, if not, the algorithm chooses an action making it possible to obtain this goal. The selected action is piled up, as well as the under-goals to obtain (these under-goals are the predicates contained in the precondition of the action). One then reiterates the algorithm to treat these under-goals.

If several actions are usable to satisfy a goal, one chooses one of them, the others will be tested if the algorithm fails by using the first. This requires a Backtracking (or the use of the recursivity).

if it is about an action:

it is checked that the precondition is checked. If so, one carries out the action (what updates the world) one depilates the action and one reiterates the algorithm. If not, the algorithm carries out a backtrack until the last choice of actions (that implies that it depilates until finding an action for which there exists an alternative). If no alternative action exists, or if they all were tested, the algorithm fails.

Remark inherent in the treatment of an action

If the top of the pile is occupied by an action, it is that all the under-goals resulting from the precondition of this action were treated. The treatment of a under-goal consists in carrying out actions which transform the state of the world so that it satisfies the under-goal. However it is possible that in spite of these treatments, the state of the world does not satisfy the precondition. Indeed, the treatment of a under-goal can demolish a under-goal previously treated.

Algorithm

Algorithm: Linear planning in STRIPS

SatisfactionButs (Goals, S, Pile) for each Goal with Aims of making NouvelEtat < - RealisationBut (Goal, S, Pile) if NouvelEtat = FAILURE then to turn over FAILURE if all the goals in Buts are satisfied in the state NouvelEtat then to turn over NouvelEtat if not to turn over FAILURE fine .

RealisationBut (Goal, S, Pile) if But is marked satisfied in the state S then to turn over S if But belonged to Pile then to turn over FAILURE EnsembleOperateurs < - {O/O can satisfy the goal But} for each operator O in EnsembleOperateurs to make NouvelEtat < - AppliquerOperateur (O, S, Pile U {Goal}) if NouvelEtat <> FAILURE then To mark the goal Drank satisfied in the state S to turn over NouvelEtat to turn over FAILURE fine

AppliquerOperator (Operator, State, Pile) NouvelEtat < - SatisfactionButs (Operator, Preconditions, State, Pile) if NouvelEtat <> FAILURE then to make Operateur.Action NouvelEtat < - NouvelEtat - Operateur.ListeSuppressions to turn over NouvelEtat U Operateur.ListeAjouts if not to turn over FAILURE fine .

Limits

The problem of STRIPS is the linearity: that means that the under-goals are treated the ones after the others. That causes blockade situations if the realization of the first under-goal generates an action making impossible the second under-goal.

For example, let us suppose a problem with a house, a garden with a letter-box in the garden. Let us define then two predicates:

" the door of the house is fermée" , noted porteFermee () and
" The key is in the letter-box " , noted dansBoite () .

If the purpose of the robot is in the garden and is: porteFermee () $\ wedge$ dansBoite () , it may find it beneficial to deal with the porteFermee under-goal () before the dansBoite under-goal () if not it is likely to slip the key into the letter-box without being able to close the door not the continuation. The first solution, which résoud not always the problem, is to order the under-goals a priori and of an intelligent way (that functions for the preceding example). Let us suppose now that the predicates are ordered as follows: to treat porteFermee () before dansBoite () .

If the robot is from now on in the house, it will close the door then will be blocked at the time to go to put the key in the letter-box which has misfortune to be in the garden. If the two goals had been reversed, one would have found in the case of blocking explained previously.

The solution with this problem is non-linear planning. There or STRIPS forces an order of execution, it makes it possible to carry out the actions and to order them only when it is necessary: one speaks about engagement at the latest ( Least Commitment Planning ).

Sources

Fikes, R.E. & NR. J. Nilsson, " STRIPS: In New Approach to the Application off Theorem Proving" , in Artificial Intelligence, vol. 2, 1971.

Elaine Rich, " Artificielle" intelligence; , 1987.

Random links: