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.” To get Shakey from A to B efficiently, Peter Hart, Nils Nilsson, and Bertram Raphael invented A* (1968), a best-first search that keeps the optimality guarantee of Dijkstra’s algorithm but uses an estimate of the remaining distance to search far less. The robot now stands in the Computer History Museum.

A Robot That Reasons

In 1966, with DARPA funding, SRI’s Artificial Intelligence Center, under Charles Rosen and 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 worked in rooms furnished with large blocks and ramps, and its programs ran on a separate PDP computer. Given a command such as “push the block off the platform,” it worked out the steps itself: find the platform, find a ramp, push the ramp against the platform, roll up, and push the block. No machine had turned a goal into its own plan of physical actions before. Several pieces of Shakey’s software outlived the robot: the STRIPS planner (Fikes and Nilsson, 1971), the starting point for decades of AI planning and automated reasoning research; the Hough transform in computer vision; the visibility graph; and A*.

The Algorithm

Shakey’s planner needed routes that were short and could be found quickly on 1960s hardware. Two methods existed. Dijkstra’s algorithm (1959) spreads outward from the start; it always finds the shortest path, but it examines every nearby node whether or not it leads toward the goal. Greedy heuristic search heads for whatever looks closest to the goal; it is fast but easily misled. In 1968 Hart, Nilsson, and Raphael combined the two. They scored every node on the search frontier 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 expanded the node with the lowest f. Their key theorem: if the heuristic is admissible, meaning it never overestimates the remaining cost, A* is guaranteed to find an optimal path while typically exploring a small fraction of the nodes Dijkstra’s algorithm must visit. With h = 0, A* is Dijkstra’s algorithm. They also proved that 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₁ and 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.”

In 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). Sat-navs and mapping services run descendants of A* over continent-scale road graphs, sped up by better heuristics and by preprocessing such as hierarchies and contraction (see Digital Maps and GIS). Warehouse robots and protein-structure searches use it as well; it fits any problem that can be framed as the 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 specially built block-worlds, with minutes of computation per move. Critics, amplified by the 1973 Lighthill Report, judged that robot autonomy had been oversold, and AI funding collapsed into the first AI winter. The complete system came decades too early: sensors, computers, and batteries were not ready, and Shakey’s real successors are the Mars rovers and self-driving cars of the 2000s. Its components were useful at once, and A*, STRIPS, and the Hough transform outlived the funding cuts that ended the robot. Shakey received an IEEE Milestone in 2017 and stands in the Computer History Museum.

📚 Sources