 |
Example of STRIPS Planning
|
The figure
below illustrates some of the features of the STRIPS planner
as exemplified in its search for a plan that results in 'Box
1' being located in 'Room R1.' The top left of the figure provides
a schematic representation of the initial problem situation.
The planner's representation of this problem situation is shown
in the top-most green box labeled 'Initial Model.' This initial
model, M0, consists of a set of wffs. The goal
that the planner is to achieve, G0,
is shown in the yellow box in the middle of the figure. The planner
attempts to prove the conjunctive goal, G0,
of 'having both a box and the robot in Room R1.' The first
conjunct is false. Consequently, the planner searches for an
operator with an expression in the Add List that might make this
first conjunct true. We have shown two of the operators, the
ones that will be needed for this plan, at the top of the figure.
The operator
PUSHTHRU has INROOM(b,r2) in its Add List and when BOX 1 is substituted
for b and Room R1 for r1 then the first conjunct is satisfied.
The next step is to determine whether this operator can be applied
to the current model, M0. In order to determine this, an attempt
is made to prove the Precondition wff against M0.
This attempt fails and the Precondition wff for this operator
becomes a new subproblem. This new subproblem, G1,
is shown as the second line in the yellow box. It is indented
to indicate that its position in the goal stack.
|
| |
 |
|
| Finally, G2,
the instantiated precondition obtained from GOTHRU, is proved
True in M0. Consequently, this operator can be
applied. The Delete and Add Lists for GOTHRU are used to create
the model that results from the application. This is shown as
M1 in the figure above. G1
is now at the top of the goal stack and an attempt is made to
prove this wff against M1 and this proof succeeds. Consequently
PUSHTHRU is applied resulting in model, M2.
G0 is now at the top of the stack and it
is provable against M2. Consequently, the problem is solved
and the plan in this instantiated and completely order set of
actions shown at the bottom of the figure in the yellow box. |
| Note the way in which the STRIPS operator
representation is used both as a non-terminal rule as well as
a terminal rule. The precondition portion of these operators
serves to decompose a problem into subproblems. When the preconditions
of an operator are satisfied, then the Delete and Add Lists are
used to "solve" that subproblem and create a new model.
This is a very compact representation, but it does restrict the
decompositions considered to those that are represented in operators
that are intended to model executable actions. |
| The researchers were not only interested
in finding plans that solved given problem. They also developed
a method in which to learn from the planning. The Triangle Table
Representation of the plan played a central role in the learning
algorithm. We continue with this example, but now consider the
problem of generalizing this plan so that it is applicable to
new problem situations. |
Example
plan adapted from: Richard E. Fikes, Peter E. Hart, and Nils
J. Nilsson, Learning and Executing Generalized Robot Plans. Artificial
Intelligence, 3 (1972) 251-288.
|
|
|