"Planning: The STRIPS Approach"
Motivation: Problem-Solving Before
Action
While many search problems consist of exploring a space of states in order to find a particular state that corresponds to a solution, or to find a path through the state space to a goal state, there are some search problems in which the path through the state space corresponds to a sequence of actions in "the real world".
Finding (in the computer) a sequence of actions to perform (in the real world) is called planning.
An example of real world actions
are manipulations of a robot arm.
Another is taking flights as part
of an airplane trip.
Planning typically involves a particular
flavor of problem solving: the state spaces are huge, and the "moves"
tend to be operators that affect particular components of the state.
Operators are often described in terms of their preconditions and postconditions.
Blocks World
In part because early experiments
with robots involved manipulating blocks on a table,
it is common to present planning
algorithms using examples involving moving blocks.
The blocks world is an informal problem-solving domain in which there is a flat horizontal surface called the table, and there are several blocks with simple geometric shapes. In presentations of planning methods, the blocks world is usually two-dimensional, and the blocks are usually square.
(On the other hand, in computer vision work, the blocks world is three-dimensional, and the blocks are rectangular prisms or other polyhedra).
[C ]
[A]
[B]
<- blocks
------------
<- tabletop
The 2D blocks world usually has various properties such as having gravity; objects cannot be suspended in space but must be supported on the tabletop or other blocks.
The size of the space may be an issue, and it is common to assume that it is a "cellular" space, in which each object is always in one of a discrete set of places.
Typical moves in such a blocks world are move a gripper on unit of distance in one of the directions north, east, west, or south or to open or close the gripper.
At a higher level of abstraction
one can have moves consisting of picking up one block (whose top must be
clear) and placing it either on the table or upon another block (whose
top must also be clear).
Planning with Iterative-Deepening
DFS
Suppose the problem is to find a sequence of moves that transforms a starting configuration (e.g., three blocks side-by-side on the table) into a goal configuration (e.g., a tower with block A on top, B in the middle, and C on the bottom).
One way to solve this problem is with a blind search such as breadth-first search or IDDFS.
At least these two algorithms find a shortest path to the goal.
IDDFS has the advantage that its
storage needs then to be lower than those for Breadth-FS.
The STRIPS Representation
In order to modularize the operators for robot planning problems, researchers at SRI (formerly the Stanford Research Institute) in Menlo Park, CA, developed a representation now known as the STRIPS representation. This representation facilitates reasoning about the planning situation as well as doing the planning.
Rather than giving a function that performs the "move", we give two lists:
ADD LIST: A list of statements (in predicate calculus) that should be added to the state description in order to show the effects of the operator.
DELETE LIST: A list of statements that should be removed from the state description.
However, before an operator can be applied to a state, the state must satisfy the "preconditions" of the operator.
PRECONDITIONS: A list of statements
that must be true in the state in order for the operator to be meaningfully
applied to it.
World-Space vs Plan Space Planning
We have thus far seen examples of planning in "world space". Each state that is visited corresponds to a configuration of conditions in the world. One problem with this is that if a poor choice of operator is made early on in the search, the algorithm lives with the consequences for a long time. Then after that move is retracted, many good moves previously done by the algorithm must be rediscovered.
In order to avoid such inefficiency,
another approach has been studied. This is to let the operators transform
not the state of the world (or state of the model of the world) but the
plan itself. Operators can add new steps to the plan, combine partial
plans, create new pieces of plans, etc. Reasoning about partial plans
as constructed in plan space can be more complicated than for those constructed
by a world-space planner, and this is the price one may pay for the extra
efficiency possible with plan-space planners.
Last modified: December 1, 1998
Steve Tanimoto