What was Shakey the robot, and what did it teach AI?

Picture a tall, boxy cart on wheels, topped with a TV camera and a long radio antenna, rolling slowly through a set of plain rooms. When someone types "push the block off the platform," it pauses, looks around, works out that it cannot climb onto the platform directly, finds a ramp, pushes the ramp into place, rolls up and nudges the block over the edge. That cart was Shakey, and what made it remarkable was not its body but the fact that nobody had told it the steps.

Shakey was built in Menlo Park, California, by the Artificial Intelligence Center at Stanford Research Institute (SRI, now SRI International). The project ran from 1966 to 1972 and was funded by ARPA, the US Defense Department's research agency. Its name came from the way it wobbled as it moved; project manager Charles Rosen recalled that the team spent a month looking for something grander before settling on the obvious.

Who built it, and why

Rosen, an applied physicist, spent about two years trying to get funding for what he called an "intelligent automaton." Work finally began in March 1966. His aim was not just a moving machine but a test bed where all the separate branches of AI could be joined in one system: seeing, reasoning, planning, learning and understanding plain English. Nils Nilsson, Bertram Raphael and Peter Hart led the project after Rosen, with a team that included Richard Duda, Richard Fikes, Helen Chan Wolf, Michael Wilber and others.

The hardware was modest. Shakey carried a TV camera with only 120 lines of resolution, sonar range finders and "bump detectors" that sensed collisions. Its brain was not on board at all. A radio link connected it to a large shared computer in another room, first an SDS 940 and later a DEC PDP-10, and most of its programs were written in Lisp.

How Shakey thought

Shakey's software was arranged in layers, an idea that was new for robots. At the bottom were simple physical actions such as "roll forward" or "turn." In the middle was a planner that strung actions together to reach a goal. At the top, a supervisor ran the plan, watched what actually happened, and recovered when something went wrong, such as a door being closed or a box not where expected.

The planner was called STRIPS (Stanford Research Institute Problem Solver). It described each action with three lists: the conditions that must hold before the action, the facts the action makes false, and the facts it makes true. Everything else is assumed to stay the same. Here is how that looks for the block task:

Step	Action	Must be true first	Becomes false	Becomes true
1	Go to the ramp	Path is clear	Shakey at start	Shakey at ramp
2	Push ramp to platform	Shakey at ramp	Ramp in old spot	Ramp at platform
3	Roll up the ramp	Ramp at platform	Shakey on floor	Shakey on platform
4	Push block off	Shakey on platform, next to block	Block on platform	Block on floor

Notice what the table leaves out: it never says that the lights stay on or the doors stay where they are. Not having to list everything an action does not change was a practical answer to what logicians were starting to call the frame problem, discussed in its own article on this site.

To move between rooms, Shakey needed to find good routes. Hart, Nilsson and Raphael worked out a method, published in 1968, called A* (pronounced "A-star"). It searches a map by combining the distance already travelled with an estimate of the distance still to go, and it is guaranteed to find the cheapest route while exploring as few options as possible. For vision, Duda and Hart reworked an older technique, the Hough transform, into a practical way of finding straight lines, such as the edges of walls and boxes, in a grainy camera image.

Try it: Draw a 5-by-5 grid on paper, mark a start and a goal, and shade a few squares as walls. For each square you consider, write two numbers: steps taken so far and a straight-line guess of steps remaining. Always expand the square with the smallest total next. That is A* in miniature.

Why it mattered

Shakey caught the public's imagination. SRI released a 24-minute film about it in 1969, SHAKEY: Experimentation in Robot Learning and Planning, and in 1970 Life magazine called it the "first electronic person." Carnegie Mellon University added it to its Robot Hall of Fame in 2004, and in February 2017 the IEEE named it a Milestone in electrical engineering and computing, calling it the world's first mobile intelligent robot. The robot itself is now on display in Mountain View, California, at the Computer History Museum.

Not everyone agreed that building a physical robot was the best use of the effort. Some AI researchers argued that simulated worlds, like the blocks world of Terry Winograd's SHRDLU program, taught more for less trouble, because a real robot could fail for reasons as dull as a change in the lighting. Its defenders answered that a real machine has to cope with plans going wrong, and the project's methods for watching a plan unfold and recovering from failures had no precedent.

Where can you see Shakey's ideas at work today?

The most visible legacy is A*. Variants of it plan routes in car navigation systems and web mapping services, and game developers use it to steer characters around obstacles. A related algorithm helps NASA's Mars rovers plan their own drives, since commands from Earth take too long to arrive for live steering.

The layered design lives on too. The team behind Stanley, the self-driving car that won the 2005 DARPA Grand Challenge across the Mojave Desert, has said its software was organized in layers much like Shakey's. STRIPS-style action descriptions became the starting point for most automated planning research for many years, and the Hough transform is a standard tool in computer vision, used for example to spot lane markings on roads.

What Shakey showed above all is that seeing, planning and acting have to work together. Any mobile robot built in 2019 still has to answer Shakey's basic questions: where am I, what do I want, and what should I do next if things go wrong?