Figure 12. Teleo-Reactive Programs.
K1 => a1
K2 => a2
Km => am
Figure 13. Shakey’s Adaptive Grid Model.
Adaptive Cell Decomposition
Shakey used a grid model, such as the one shown in
figure 13, 6 to map the obstacles in its environment.
If a cell is not completely empty or completely full, it
is divided into smaller cells and so on until one of
these conditions is met for all cells. We believe
Shakey’s was the first use of an adaptive grid model.
Adaptive cell decomposition is still used in robot
navigation and in computer-aided design and manufacturing.
STRIPS was the system Shakey used for generating
plans to accomplish goals. Figure 14 shows a STRIPS
rule for modeling the action of moving a toy block
from C to B. The preconditions must be satisfied before
the action can be applied, and the terms on the delete
list can no longer be guaranteed to be satisfied after
the action is applied, so they are deleted from
Shakey’s post-action model of the world. The terms
on the add list are added to the post-action model.
STRIPS rules (or their derivatives) are used in most
modern planners. (The STRIPS paper gets over 5000
citations on Google Scholar, and “STRIPS-style planning” gets over 3410 results on Google.) It’s the rules
that are used, not the STRIPS program itself. STRIPS
rules were a practical solution to the “frame problem” — inherent in the use of the “situation calculus,” proposed by McCarthy and Hayes (1969) for
Hierarchical task networks (HTNs) are much used
and powerful planning systems that use STRIPS
rules. 7 These systems assemble plan steps into networks of actions, some of which can be executed in
parallel and others that must be executed serially. We
show an example in figure 15.
SIPE- 2, 8 O-Plan (Currie and Tate 1991), and
SHOP29 are examples of implemented HTNs. Among
other important applications of HTNs, SIPE- 2 has
been used for production planning at an Australian
Some video games make use of STRIPS rules and
HTNs for planning the actions of nonolayer characters (NPCs). 10
Heuristic Search and A*
A* is a heuristic search algorithm developed during
the Shakey project for efficiently searching a graph of
navigation waypoints. It uses an evaluation function
to rank the nodes reached during search and continues the search below the best-ranked node. The evaluation function for a node, n, is the sum of the cost
of the links traversed already on the way to n plus an
estimate of the cost from n to a goal node.
There are lots and lots of descendants and variants
of A*. Here is a list of just some of them: D*, Field D*,
Theta*, Real-Time A*, Iterative Deepening A*, Life-
Long Planning A*, Simplified Memory Bounded A*,
and Generalized Adaptive A*. Richard Korf at UCLA
and researchers at Carnegie-Mellon University have
played major roles in the development of many of
The Mars rover, Curiosity, uses Field D*, a derivative of A* written by CMU’s Tony Stentz and his student, Dave Ferguson (now with Google). It is capable
of planning paths around obstacles in unknown, par-