The History of AI

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).

A* scores each point by the distance already covered, g, plus an estimate of what remains, h, and expands the one with the smallest sum first.

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

Sources

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.

Open in the interactive timeline