The A* algorithm
Era 2 · AI is born (1943–1979) › Symbolic AI
- Lineage
- Symbols and logic
- Kind
- Publication
Who
Stanford Research Institute
What happened
Peter Hart, Nils Nilsson, and Bertram Raphael of the Stanford Research Institute publish "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in the IEEE Transactions on Systems Science and Cybernetics.
Why it mattered
A finds the shortest path by steering with an estimate of the distance remaining. If the estimate never overstates it, A always finds the optimum. It was created so that the Shakey robot could plan its routes.
The full story
Shakey had to move through several rooms while avoiding obstacles, and for that it needed to find short routes without examining every possible one. Nilsson first proposed a method based on the Graph Traverser, and Raphael suggested scoring each point along the way by adding two quantities.
The first, g, is the cost of the path already traveled from the start. The second, h, is an estimate of the cost remaining to the destination, such as the straight-line distance. The algorithm always expands the point with the smallest sum f = g + h. If h were zero, it would be Dijkstra's algorithm, of 1959, which advances equally in every direction; with a good estimate, it heads toward the goal and examines far fewer points.
Hart's contribution was to prove when the method can be trusted. If the estimate never exceeds the real cost, what Hart called an admissible heuristic, A* always finds the optimal path.
A* became the pathfinding algorithm par excellence: it is in navigation systems, in robotics, and in almost every video game where a character finds its way. It also set an example of how to give a heuristic formal guarantees.
A jagged path runs from the start to a node n; that is the cost g(n). From n, a straight dashed line reaches the goal; that is the estimate h(n). Below, the formula f(n) = g(n) + h(n).
Under the hood
A* keeps a list of open points ordered by f(n) = g(n) + h(n). At each step it takes out the one with the smallest f. If it is the goal, it stops; if not, it computes g and f for its neighbors and adds them to the list.
With h = 0 the order depends only on g, and the algorithm is Dijkstra's. If h never exceeds the real remaining cost, the heuristic is admissible and the first path to reach the goal is the shortest.
Hart, Nilsson, and Raphael also proved that, with an admissible heuristic that meets a consistency condition, no algorithm using the same information expands fewer points than A* without risking missing the optimal path.
Builds on
Shakey (March 1966)
Documented direct influence
Both were created within the project
Threads that pass through here
- Shakey and its algorithms (step 2 of 3)
Sources
Original source
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), pp. 100-107 (opens in a new tab). Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, 1968
Scholarship and context
Further reading
How to cite
“The A* algorithm.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/a-star-algorithm
This entry was last reviewed on November 13, 2026.