our proposals, and suggested that the
modified algorithm was not only better,
but (under certain conditions) might be
unique and optimal. Then, for the next
week or two, we studied and established
under what conditions the revised al-
gorithm was provably optimal, and we
called it A* just to distinguish it from any
simpler algorithm A. That’s about it!”
Nils Nilsson’s initial response to
Jeff’s email supported a relationship to
the Kleene star interpretation.b
Peter Hart then gave a detailed replyc
to everyone, initially saying this may
be the first time all three of them have
participated together on this topic, and
then stated “we seem to have different
recollections about some details of no-
menclature and notation.”
“Only a few years earlier, I had com-
pleted a Ph.D. dissertation at Stanford
in the area of nonparametric statisti-
cal decision theory. So when I started
working on the mathematical proofs
with Nils and Bert, I adapted some
standard nomenclature and notation
I was familiar with from the field of
mathematical statistics. This comes
up in several places: ‘Admissibility’ it-
self is a standard concept in statistics
and statistical decision theory, you
can easily find lots of examples and ex-
planations. From an intuitive point of
view, it usually means that something
has a ‘good’ property. From a math-
ematical point of view, it limits con-
sideration of things (like say decision
rules) to a ‘good’ class, about which in-
teresting theorems can be proven.
“The circumflex (^) or ‘hat’ notation
is commonly used in statistics to denote
an estimate, as of a random variable.
So, if for example â might be used to
denote an estimate of a random variable ‘a’. I introduced the hat notation
for the f, g and h functions in A* to suggest they were estimates of the true, but
unknown, underlying values (in particular of the look-ahead function, h). That
brings us to the asterisk, the ‘star’ in A*.
b N. Nilsson, Email communication, February
7, 2019. Sadly, Nils Nilsson passed away soon
after we submitted this material for publication in Communications; see https://stanford.
io/333qB3A. We are grateful we had the opportunity to correspond with Nils; our sincere
thanks to Peter Hart and Bert Raphael for their
participation and historical perspectives contributing to the development of this Viewpoint.
c P. Hart, Email communication, February 7, 2019.
The star notation is probably a bit over-
used in statistics, with different authors
employing it in different ways. But it
can mean a special or optimal value of a
parameter, such as one that minimizes
some cost or loss. I introduced the A*
notation with the thought that our al-
gorithm (A*) was better than any other
algorithm, better than anyone else’s al-
gorithm A, and we’re gonna prove it! So
from my PoV, the star has nothing what-
soever to do with Kleene star syntax.”
Lastly, Nilsson clarified his position
to support the statement made by Hart,
affirming “that’s my understanding
too”. (Afterward, a Nilsson reference was
actually found that similarly supports a
“special property” interpretation.
Decades after the A* algorithm was
initially published we finally have our
answer(s). Though there remain slight
differences in opinion behind the true
meaning and use of the star (
distinction vs. optimality), it has nonetheless
been an interesting and illuminating
historical journey through A*. Perhaps
it is time to update the textbooks.
1. CSE 5052. Survey of Artificial Intelligence for
Non-Majors. Department of Computer Science and
Engineering, Ohio State University, 2019.
2. Hart, P.E., Nilsson, N.J., and Raphael, B. A formal
basis for the heuristic determination of minimum cost
paths. IEEE Transactions on Systems Science and
Cybernetics SSC4 4, 2 (Feb. 1968), 100–107.
3. Kleene, S.C. Representation of events in nerve nets
and finite automata. In Automata Studies. Princeton
University Press, Princeton, New Jersey, 1956, 3–41.
4. Nilsson, N. The Quest for Artificial Intelligence.
Cambridge University Press, 2009.
James W. Davis ( firstname.lastname@example.org) is a Professor in
the Department of Computer Science and Engineering,
Ohio State University, Columbus, OH, USA.
Jeff Hachtel ( email@example.com) received
a Management Information Systems degree from Ohio
State University and is currently a Consulting Analyst for
Accenture, Columbus, OH, USA.
Copyright held by authors.
the A* algorithm
we finally have
For further information
or to submit your
ACM TIOT publishes
in several research
domains whose synergy
enable the IoT vision.
TIOT focuses on system
and on publishing
results and insights
corroborated by a
ACM Transactions on
Internet of Things