Communications of the ACM

Viewpoint

A* Search: What's in a Name?

By James W. Davis, Jeff Hachtel
Communications of the ACM, January 2020, Vol. 63 No. 1, Pages 36-37
10.1145/3326600
Comments

Originally published in 1968 by Hart, Nilsson, and Raphael,² the well-known A^* search algorithm is a foundational pathfinding algorithm in computer science and artificial intelligence (AI) for traversing trees and graphs. The method provides the optimal path from the initial state to the target goal state, given the use of an admissible heuristic (must not overestimate the remaining distance to the goal). The A^* algorithm is included in nearly all AI textbooks and courses worldwide. Given its widespread fame, however, there is no reliably documented evidence as to the origin of the name "A^*": What does it really stand for and what does it mean? This Communications Viewpoint answers the question.

At Ohio State University, we offer a specialty course on AI designed for non-computer science students¹ (due to the large interest and demand in AI from multiple disciplines). During the course offering this year while teaching the A^* algorithm, a student raised his hand and asked: "What does A^* stand for?". Out of all my years teaching AI, I have never been asked that question! I realized I did not know the answer myself, and therefore would need to seek the explanation. After an exhaustive search online (including reading the original publication²) and a thorough inspection of the classic AI textbooks on my bookshelf, I could not find a definitive answer. During the next class, I stated the lack of evidence available and therefore put out a challenge to the class to see if anyone could find a credible source for the answer.

Jeff Hachtel, an ambitious Management Information Systems undergraduate in my course, took that challenge to heart and began his search. One potential source was found stating the A^* name is based on the (plausible) use of Kleene star syntax³ (uvsed in regular expressions), however it was not properly verifiable. Jeff then boldly decided to take the question straight to the authors of A^* themselves. He found the email addresses of Hart, Nilsson, and Raphael and sent them a brief inquiry asking how the name was selected and if it was related to Kleene star syntax.³ Given the paper was published in 1968, it was not expected any response(s) would be forthcoming.

Incredibly, the very next day responses from the authors sharing their recollection and historical perspective began to appear in Jeff's email inbox. Jackpot!

Bert Raphael was the first to respond,^a and began with the statement "A^* was a quick, easy, and rather arbitrary name for the algorithm we came up with."

Raphael continued, recalling: "As I remember, Nils called me into his office (in about 1968) to show me his proposed algorithm for how 'Shakey the Robot' could plan its route through a room containing obstacles. For lack of anything better, he called it Algorithm A. I suggested a modification of Algorithm A that I had a hunch would be more efficient. Peter then dropped in, looked at 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 algorithm 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 reply^c 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 nomenclature and notation."

"Only a few years earlier, I had completed a Ph.D. dissertation at Stanford in the area of nonparametric statistical 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' itself is a standard concept in statistics and statistical decision theory, you can easily find lots of examples and explanations. From an intuitive point of view, it usually means that something has a 'good' property. From a mathematical point of view, it limits consideration of things (like say decision rules) to a 'good' class, about which interesting 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^*. The star notation is probably a bit overused 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 algorithm (A^*) was better than any other algorithm, better than anyone else's algorithm A, and we're gonna prove it! So from my PoV, the star has nothing whatsoever to do with Kleene star syntax."

---

Decades after the A* algorithm was initially published we finally have our answer(s).

---

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.

Back to Top

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.

---

No entries found