STRIPS - An Example of a Linear Planner

   A linear planner is one in which the order in which subproblems are solved is linearly related to the order in which the actions of the plan are executed. We will use STRIPS as our example of a linear planning system. The domain knowledge that was represented in the Difference Operator Table of GPS is represented in the STRIPs operators. Several groups of these operators are shown below. The first group shown below lists the various types of  'GO' actions that STRIPS has available to it.


   Each operator consists of a name together with a list of the arguments for the operator and three groups of expressions which are referred to as:

  • Preconditions;
  • Deletions;
  • Additions.

The Preconditions consist of a conjunctive logical expression which is intended to describe the conditions that must be true in order to apply the operator. The Deletions consist of a set of expressions that must be deleted from a model of a situation if the operator is applied. The Additions consist of a set of expressions that must be added to a model of the situation if the operator is applied.

The operators for 'opening' and 'closing a door' are shown above and the several operators for 'pushing a box' are shown below. Notice that there are four "flavors'" of push. The first is for 'pushing a box to an object,' the next is for 'pushing a box to a door,' the next is for 'pushing a box to a location,' and the last is for 'pushing a box through a door into the next room.'  Distinct push operators must be represented because the semantics of these actions differ. In our everyday usage of the English term 'push' we don't usually think of these different senses because we and our listeners automatically choose the correct semantics. However, this knowledge must be explicitly represented in a planning system.

Overview of Strips Control

An operator is needed only if a subgoal cannot be proven from the current model of the situation. (Proof is carried out using a resolution theorem prover where the current model, Mi, is used as the basis for the axioms used in the proof. Note that the well-formed-formula (wffs) that one tries to prove are either the goal wff or precondition wffs.

The operators are scanned to identify an operator whose add list specifies clauses that would allow the proof to be successfully continued (if not completed). When an add list is found whose clauses permit an adequate continuation of the proof, then the associated operator is declared relevant...the substitutions used in the proof continuation serve to at least partially instantiate the arguments of the operator. The inner loop of STRIPS is described as:

(1) Select a subgoal and try to establish that it is true in the appropriate model. If it is, then go to Step 4.


(2) Choose as a relevant operator one whose add list specifies clauses that allow the incomplete proof of Step 1 to be continued.

(3) The appropriately instantiated precondition wff of the selected operator constitutes a new subgoal. Go to Step 1.

(4) If the subgoal is the main goal, terminate, Otherwise, create a new model by applying the operator whose precondition is the subgoal just established. Go to Step 1.

[ The search can be Represented as an AND/OR tree where step 2, at least implicitly, gives the OR, the list of relevant operators, and step 2 chooses one of these...Step 3 does the AND expansion...Step 1 tests for satisfaction and if True goes to step 4 the model is mapped from Mi -> Mi+1. Mi+1 would be "passed" back up to the parent node and control goes again to Step 1 to retest for satisfaction of the parent subgoal in this new model. ]

The output of STRIPS is a list of instantiated operators whose corresponding actions will achieve the goal.

The STRIPS system is described in Richard E. Fikes, Peter E. Hart, and Nils J. Nilsson, Learning and Executing Generalized Robot Plans. Artificial Intelligence, 3 (1972) 251-288.

Example of STRIPS Planning

 © Charles F. Schmidt

Planning - Table of Contents