tially known, and changing environments in an efficient, optimal, and complete manner.
Most route-finding algorithms in maps use variants and elaborations of A*. Elaborations include the
use of hierarchies, saved routes (which don’t need to
be recomputed), and much more.
In other uses of A*, linguists Dan Klein and Chris
Manning write, “The use of A* search can dramatically reduce the time required to find a best parse …”
(Klein and Manning 2003). And Steven Woodcock, a
computer games consultant, wrote that “A* is far and
away the most used … and most useful … algorithm
for [nonplayer-character] path finding in games
today …. developers have noted that they make more
use of A* than any other tool for pathfinding.” 11
(Actually, we are gratified that the major applications
of A* are on problems a bit more serious than video
As mentioned earlier, we had hoped that we could
use then-existing computer vision routines to
process images from Shakey’s camera. But the state of
computer vision was quite primitive at that time, so
we did have to develop some routines of our own.
One, which influenced subsequent vision systems,
was a system for segmenting images into “
like-appearing regions” (Brice and Fennema 1970). An
example of the regions found for some of the objects
in Shakey’s environment is illustrated in figure 16.
Segmentation is still a major technique used in computer vision today. 12
Another result of work on computer vision during
the Shakey project was the development of the
“modern form” of the Hough transform for finding
lines and curves in images. As mentioned earlier,
Richard Duda and Peter Hart modified the original
Figure 14. Application of a STRIPS Rule.
Preconditions: On(A,C), Clear(A), Clear(B)
Delete List: (On(A,C), Clear(B)
Add List: On(A,B), Clear (C)