Hart, Nilsson, Raphael, and A*: Heuristic Search for Shakey
A* gave the Shakey robot project a principled way to combine path cost already paid with an estimate of cost still ahead, turning heuristic guidance into a search method with formal optimality properties.
Robot navigation forced search theory to confront a combinatorial world
A mobile robot cannot try every possible route through an environment. It needs a way to prefer promising paths while still avoiding traps created by locally attractive choices. The Shakey project at SRI brought this problem into early artificial intelligence by combining perception, planning and movement in a physical system.[1]
Path search became one of the project’s enduring algorithmic legacies because it turned vague “intelligence” into a precise question: which state should the program explore next?
Hart, Nilsson and Raphael published the formal A* framework in 1968
Peter E. Hart, Nils J. Nilsson and Bertram Raphael published “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” in 1968.[2] The paper described how domain-specific heuristic information could be incorporated into graph search and established optimality properties for a class of strategies.
The name A* became attached to the best-known member of that framework.
The contribution was not simply “use a guess”
Heuristics had been used before. The important step was to define conditions under which a heuristic could guide search aggressively without destroying guarantees about the cost of the returned path.
A* combines known cost with estimated remaining cost
The familiar evaluation function is written as f(n) = g(n) + h(n). The term g(n) records the path cost from the start to the current node, while h(n) estimates the remaining cost to a goal. Search prioritizes nodes according to the combined estimate.
This creates a useful continuum. If h is zero, the method behaves like uniform-cost search; a more informative h can focus exploration dramatically.
The heuristic changes the order of work, not the definition of a solution
A* does not replace the actual path cost with intuition. It uses the heuristic to decide where to spend computation while preserving the real accumulated cost in the evaluation.
Admissibility made heuristic optimism mathematically useful
An admissible heuristic does not overestimate the true remaining cost. Under the assumptions developed in the original theory, that property supports optimal-path guarantees.[2] Later discussion and corrections refined parts of the formal treatment, which Nilsson’s publication record preserves alongside the original paper.[3]
The result gave AI researchers a language for comparing heuristics by both correctness and search efficiency.
Shakey made the algorithm part of a larger planning architecture
SRI’s history of Shakey describes the robot as a landmark system combining sensing, reasoning and action across the late 1960s and early 1970s.[1] Computer History Museum material specifically identifies A* as one of the sophisticated search techniques developed in connection with Shakey.[4]
This setting matters because A* was not invented as an isolated puzzle solver. It arose inside an effort to make an autonomous system choose actions in a modeled environment.
Search quality depends on representation as much as on the queue rule
A good heuristic cannot rescue a state space whose representation hides useful structure or creates needless branching. Shakey’s legacy includes the broader systems lesson that planning algorithms and world models must be designed together.
The tradeoff is memory as well as time
A* can be extremely effective when the heuristic is strong, but it may retain many frontier and explored nodes. On large problems, memory can become the limiting resource long before raw arithmetic does.
That limitation inspired iterative-deepening and memory-bounded descendants, but the core f = g + h principle remained a reference point for evaluating alternatives.
Better heuristics are a form of compiled domain knowledge
A heuristic encodes facts about the problem into a cheap estimate. The more informative it is while respecting the required guarantees, the less blind search the program must perform.
A* escaped robotics and became a general search primitive
The algorithm spread into route planning, games, network optimization, automated planning and many other domains. IEEE’s retrospective on Shakey emphasizes the continuing importance of the project and its algorithmic descendants.[5]
A* became especially durable because its design is modular: change the graph, cost function and heuristic, and the same search architecture can serve very different tasks.
Why A* belongs in the CodeHistory timeline
A* marks a moment when heuristic search gained a rigorous mathematical foundation. Hart, Nilsson and Raphael connected problem-specific estimates with optimal-path reasoning, while Shakey provided a demanding environment in which that theory mattered.[2][4]
Its lasting idea is simple but profound: computation can be saved by knowing where to look, provided that the guidance itself is designed with explicit guarantees.
Works Cited
- 01
- 02
- 03
- 04Computer History Museum — Shakey and A* computerhistory.org
- 05IEEE Spectrum — Shakey the Robot Honored as an IEEE Milestone spectrum.ieee.org
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead