Strips

Strips

Shakey, the first AI mobile robot, needed a generalized algorithm for planning
how to accomplish ALGORITHM goals. (An algorithm is a procedure which is correct
and terminates.) For example, it would be useful to have the same program
allow a human to type in that the robot is in Office 311 and should go to
Office 313 or that the robot is in 313 and should the red box.
GENERAL PROBLEM The method finally selected was a variant of the General Problem Solver
SOLVER (GPS) method, called Strips. Strips uses an approach called means-ends analysis,
STRIPS
MEANS-ENDS ANALYSIS
where if the robot can’t accomplish the task or reach the goal in one “movement”,
it picks a action which will reduce the difference between what state
it was in now (e.g., where it was) versus the goal state (e.g., where it wanted
to be). This is inspired by cognitive behavior in humans; if you can’t see how
to solve a problem, you try to solve a portion of the problem to see if it gets
you closer to the complete solution.
Consider trying to program a robot to figure out how to get to the Stanford
AI Lab (SAIL). Unless the robot is at SAIL (represented in Strips as a
GOAL STATE variable goal state), some sort of transportation will have to arranged.
INITIAL STATE Suppose the robot is in Tampa, Florida (initial state). The robot may
represent the decision process of how to get to a location as function called an
OPERATOR operator which would consider the Euclidean distance (a variable named
DIFFERENCE difference) between the goal state and initial state. The difference
between locations could be computed for comparison purposes, or evalDIFFERENCE
uation, by the square of the hypotenuse (difference evaluator). For
EVALUATOR example using an arbitrary frame of reference that put Tampa at the center
of the world with made-up distances to Stanford:

But suppose the robot flew into the San Francisco airport. It’d be within
100 miles of SAIL, so the robot appears to have made an intelligent decision.
But now the robot has a new difference to reduce. It examines the
difference table with a new value of difference. The table says the robot
should drive. Drive what? A car? Ooops: if the robot did have a
personal car, it would be back in Tampa. The robot needs to be able to distinguish
between driving its car and driving a rental car. This is done by listing
PRECONDITIONS the preconditions that have to be true in order to execute that particular
operator. The preconditions are a column in the difference table, where
a single operator can have multiple preconditions. In practice, the list of
preconditions is quite lengthy, but for the purposes of this example, only
drive_rental, drive_personal will be shown with preconditions.

The difference table is now able to handle the issue of deciding to drive a
rental car. But this introduces a new issue: how does the robot know where
it is at? This is done by monitoring the state of the robot and its world. If
it took an airplane from Tampa to the San Francisco airport, its state has
changed. Its initial state is now at the San Francisco airport, and no

longer Tampa. Therefore, whenever the robot executes an operator, there
is almost always something that has to be added to the robot’s knowledge
of the world state (ADD-LIST which is entered into a add-list) and something that
DELETE-LIST has to be deleted (delete-list). This two lists are stored in the difference
table so that when the robot picks an operator based on the difference and
operator, it can easily apply the appropriate modifications to the world. The
difference table below is expanded to show the add and delete lists.

Of course, the above difference table is fairly incomplete. Driving a rental
car should have a precondition that there is a rental car available. (And that
the robot have a waiver from the state highway patrol to drive as an experimental
vehicle and a satisfactory method of payment.) The number of facts
and preconditions that have to be explicitly represented seem to be growing
explosively. Which is Very Bad from a programming standpoint.
The main point is that the difference table appears to be a good data structure
for representing what a robot needs in planning a trip. It should be
apparent that a recursive function can be written which literally examines
each entry in the table for the first operator that reduces the difference. The
resulting list of operators is actually the plan: a list of the steps (operators)
that the robot has to perform in order to reach a goal. The robot actually
constructs the plan before handing it off to another program to execute.
At this point in time, it isn’t likely that a robot will get on a plane and then
drive. So perhaps the criticisms of Strips is because the example used too
complicated a task to be realistic. Let’s see if Strips is more streamlined with
a simple task of getting from one room to another.