Robotics Reference
In-Depth Information
Fikes and Nils Nilsson at Stanford Research Institute. STRIPS is a sim-
ple model for expressing planning problems that need to be solved on
behalf of a hypothetical robot operating in a “world” of several rooms,
with doors, some boxes and some other objects that the robot can ma-
nipulate. STRIPS represented this world by a set of facts expressed in
first-order predicate calculus—the logic of Russell and Whitehead's
Prin-
cipia Mathematica
described earlier in this chapter.
The STRIPS robot can implement a plan of action by means of
op-
erators
such as going somewhere or moving something. Each operator
works on the basis of preconditions, for example if the robot needs to go
from A to B it must first be at A, and if it wants to move an object it
must first be next to that object. The traditional form of STRIPS-based
planner starts with a goal, looks at what preconditions must exist for that
goal to be achieved, and then decides what action will come
last
in the
planning process in order to achieve that goal. It does this by finding an
action that directly leads to the goal state. It then needs to determine
whether the robot will be able to take that action, so it must ensure that
the preconditions of that action are satisfied. It does this by adding those
preconditions to its list of what it needs to achieve.
The planning process proceeds in this fashion, looking at the facts
in its new goal (i.e., the new list of what it needs to achieve), finding
another action that achieves some of these facts, adding the precondi-
tions of that action to the list of what it needs to achieve, and so on.
If STRIPS encounters an action that will not achieve any of the facts
that make up its goal, then it admits defeat in this particular part of the
plan (for the time being at least) and backtracks, before choosing a dif-
ferent action. A STRIPS planner as described here could be improved
in its performance by selecting actions for consideration in a hopefully
intelligent order, for example with those having fewer preconditions be-
ing examined first. This heuristic is based on the simple notion that the
more preconditions there are, the greater the amount of work that the
planner has to do in order to achieve the goal.
Although the terminology differs, the STRIPS approach to planning
is actually nothing more than another search problem. This type of
planner is usually referred to as a backward search—one in which the
search process starts with the goal and works back towards the original
problem. The opposite approach, called forward search, starts from the
original problem and plans in a “forward” direction, towards a solution.
In this respect a forward planner bears considerable similarities to the
