Navigation and the A* Algorithm
Shakey had to find its way around, so several short-est-path algorithms were developed. One, called A*
by its creators, Peter Hart, Nils Nilsson, and Bertram
Raphael, had two very desirable properties. It can be
rigorously proved that (a) it always finds the shortest
path, and (b) that it does so while considering the
smallest possible number of alternatives. In nonmathematical shorthand, we can say that it always
works and it’s computationally efficient.
One would think that such a strong result would
be eagerly accepted by any reputable publication, but
it’s perhaps a sign of those times that just the oppo-
site was the case. The A* manuscript was rejected by
the most prestigious journals of the day. Looking at
those old reviews, we can speculate that review edi-
tors sent the manuscript to mathematicians, because
of all those intimidating-looking theorems. But
mathematicians were unimpressed because the
proofs were limited to graphs with only a finite num-
ber of nodes. It seemed to the authors at the time that
mathematicians saw no difference between a graph
with ten nodes and one with ten trillion nodes, but
to computer scientists that difference matters.
The paper (Hart, Nilsson, and Raphael 1968) was
finally accepted by the IEEE Transactions on Systems
Science and Cybernetics, where it eventually got
noticed and continues to be referenced more than 45
years after it was published.
The World Back Then
The foregoing gives a glimpse of some (though by no
means all!) of the work done by the Shakey project
team. To place this work in a broader societal context we can take a brief look at the intellectual and
cultural climate of the time.
In 1970, Life, 3 a popular magazine of the day, ran
a big story about Shakey (figure 10). The author, journalist Brad Darrach, seemed to hyperventilate a bit,
with a subtitle, “the fascinating and fearsome reality
of a machine with a mind of its own.” But while
some like Darrach worried that machines might take
over the world, there were deep skeptics. Hubert
Dreyfus was one, who argued on deep philosophical
grounds that AI is in principle impossible. And some-
Figure 8. STRIPS.
STRIPS: The Stanford Research
Institute Problem Solver
“GPS, A Program That Simulates
Human Thought,” A. Newell and H.
A. Simon, in Lernende Automaten,
H. Billing, editor, Muchen: R.
Resolution as a Basis for Question-Answering Systems,” Cordell Green,
in Machine Intelligence 4, Bernard
Meltzer and Donald Michie, editors,
Edinburgh University Press,
Edinburgh, Scotland, 1969.
“STRIPS, A New Approach to the
Application of Theorem Proving to
Problem Solving,” R. E. Fikes and
N. J. Nilsson, in Proceedings of the
Second International Joint Conference
on Artificial Intelligence (IJCAI), 1971.