Skip to content

A* and Shakey the Robot

Abstract

The pathfinding algorithm inside every video game, sat-nav, and logistics router was invented for a wobbling cabinet on wheels. Shakey, built at Stanford Research Institute from 1966 to 1972, was the first mobile robot that could perceive its surroundings and reason about its own actions; Life magazine called it the “first electronic person.” Getting Shakey from A to B efficiently forced Peter Hart, Nils Nilsson, and Bertram Raphael to invent A* (1968), the best-first search that marries Dijkstra’s guaranteed optimality with the speed of informed guessing. The robot was retired into a museum; its algorithm runs billions of times a day.

A Robot That Reasons

In 1966, with DARPA funding, SRI’s Artificial Intelligence Center (under Charles Rosen, with Nils Nilsson and Peter Hart leading the research) set out to build a robot that could operate autonomously in a real environment: perceive it, plan in it, act in it, and recover when things went wrong. The machine (a tower of camera, rangefinder, bump sensors, and radio link, trembling as it moved) was christened Shakey (“We worked for a month trying to find a good name for it,” Rosen recalled, “and then one of us said, ‘Hey, it shakes like hell and moves around, let’s just call it Shakey.’”).

Shakey lived in rooms of tidy blocks and ramps, and its intelligence ran on a remote PDP computer. Told “push the block off the platform,” it would decompose the goal itself: find the platform, find a ramp, push the ramp to the platform, roll up, push the block. No machine had ever turned a goal into its own plan of physical actions before. The project’s software byproducts became foundational: the STRIPS planner (Fikes and Nilsson, 1971) that seeded decades of AI planning and its descendants in automated reasoning, the Hough transform in computer vision, the visibility graph, and A*.

The Algorithm

Shakey needed routes that were good and found quickly on 1960s hardware. Two traditions existed: Dijkstra’s algorithm (1959) explored outward from the start, guaranteed optimal but blindly exhaustive; greedy heuristic search chased whatever looked closest to the goal, fast but easily fooled. In 1968, Hart, Nilsson, and Raphael published the synthesis: score every frontier node by

f(n) = g(n) + h(n)

g(n): actual cost from the start to n
h(n): heuristic estimate from n to the goal
       (e.g., straight-line distance)

and always expand the node with the lowest f. Their key theorem: if the heuristic is admissible (it never overestimates the remaining cost) A* is guaranteed to find an optimal path, while typically exploring a small fraction of what Dijkstra must. (With h = 0, A* is Dijkstra; the heuristic is pure profit.) They proved more: among algorithms using the same heuristic information, A* is optimally efficient, no rival can expand fewer nodes in general and stay correct.

The name is bare mathematics: variants A₁, A₂ had been considered; the version proven optimal earned the star, as in “the best A.” The 1968 paper, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” became one of the most cited in computer science.

Everywhere Paths Are Found

A* escaped robotics almost immediately and became the default answer to “get from here to there”:

  • Video games: A* on grids and navigation meshes moves the units in essentially every strategy game and the NPCs in most 3D worlds; game AI programming is, to a first approximation, applied A* (see The History of the Video Game Industry).
  • Navigation, routing engines in sat-navs and mapping services run A* descendants tuned with better heuristics and preprocessing (hierarchies, contraction) over continent-scale road graphs (see Digital Maps and GIS).
  • Planning and scheduling, from warehouse robots to protein-structure search spaces, anything castable as cheapest-path-through-a-state-graph.

Dead End: Shakey’s Winter

Shakey itself stopped in 1972, when DARPA declined to renew the project’s funding.

Why the Robot Stopped and the Algorithm Didn’t

Shakey’s demos ran in engineered block-worlds, minutes of ponderous computation per move; critics (amplified by the 1973 Lighthill Report) judged that robot autonomy had overpromised, and funding across AI collapsed into the first AI winter. The pattern is instructive: the integrated system was decades premature (sensing, compute, and batteries weren’t ready; Shakey’s true heirs are the Mars rovers and self-driving cars of the 2000s), but the components were immediately, permanently useful. A*, STRIPS, and the Hough transform outlived the hype cycle that killed their vehicle. Shakey received the IEEE Milestone designation in 2017 and now stands in the Computer History Museum, a monument to the most productive “failure” in robotics.

📚 Sources