A* Search Algorithm Published by Hart, Nilsson, and Raphael at Stanford Research Institute
In 1968, Peter E. Hart, Nils J. Nilsson, and Bertram Raphael at the Stanford Research Institute published 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths', introducing the A* search algorithm, which finds shortest paths in graphs efficiently by combining actual path cost with a heuristic estimate of remaining cost.
Background
By the mid-1960s, researchers in artificial intelligence had ways to search through graphs, meaning networks of states connected by paths of varying cost. The goal was usually to find a route from a starting point to a goal, the kind of problem that turns up in robot planning, puzzle-solving, and game-playing.
Two broad approaches existed, and both had problems. Exhaustive methods, which checked every possible path, were too slow for any reasonably sized problem. Heuristic methods used rules of thumb to focus the search, but there was no proof that they would find the best answer, or even a correct one. A heuristic might lead a search astray entirely, and the researcher had no formal way to know when that might happen.
Edsger Dijkstra had published a method in 1959 that guaranteed finding the shortest path, but it worked by spreading out in all directions at once, making no use of any knowledge about where the goal actually was. That guaranteed correctness at the cost of a great deal of wasted effort. The gap between “provably correct” and “practically fast” was the problem Hart, Nilsson, and Raphael set out to close.
What happened
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, all working at Stanford Research Institute, published their paper in IEEE Transactions on Systems Science and Cybernetics in 1968. They called the algorithm A*, pronounced “A star”, and the paper did two things together that had not been done before: it described a practical search method and it supplied a mathematical proof of the method’s correctness.
The search works by assigning every candidate point along a path a score written as f = g + h. The g part is the actual cost already spent to reach that point from the start. The h part is a heuristic estimate, a calculated guess about the remaining cost to reach the goal from there. The algorithm always expands the point with the lowest combined f score, so effort is concentrated where the combined evidence says it is most likely to be worthwhile.
The central proof in the paper addressed the heuristic directly. Hart, Nilsson, and Raphael showed that if h never overestimates the true remaining cost, a property they called admissibility, then A* is guaranteed to find the optimal path. It will not just find a solution; it will find the best one, and it will do so without exploring more of the graph than necessary given what the heuristic tells it. That combination, a guarantee of optimality alongside a formal account of efficiency, was what earlier heuristic work had lacked. The f = g + h formulation gave researchers something precise to reason about, and the admissibility condition gave them a testable criterion to apply to any heuristic they might invent.
The paper was theoretical. It laid out the algorithm and its proof on the page. Practical applications came later, built by others who took the framework and applied it to their own problems.
Why it mattered
A* provided a mathematically rigorous proof that a best-first graph search guided by an admissible heuristic will always find an optimal solution, unifying prior heuristic search ideas into a single, principled framework. Its combination of completeness, optimality, and practical efficiency made it foundational to AI planning, robotics motion planning, and game pathfinding, and it remains the canonical reference point against which subsequent search algorithms are evaluated. The paper's formalism of the f = g + h cost function directly shaped how later fields, from autonomous navigation to puzzle solving, approach state-space search.
People
Peter E Hart, Nils Johan Nilsson, Bertram Raphael
Organisations
Sources
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths.IEEE Transactions on Systems Science and Cybernetics.Primary source
- A* Search: What It Is and Where It Came From.ResearchGate.Secondary
Cite this page
AI Achievements. (1968). A* Search Algorithm Published by Hart, Nilsson, and Raphael at Stanford Research Institute. Retrieved 2026-08-22, from https://achievements.ai/milestone/a-search-algorithm-at-stanford-university
@misc{achievements_a_search_algorithm_at_stanford_university,
title = {A* Search Algorithm Published by Hart, Nilsson, and Raphael at Stanford Research Institute},
author = {{AI Achievements}},
year = {1968},
url = {https://achievements.ai/milestone/a-search-algorithm-at-stanford-university}
}