A bit of history

shakey-rosen-x640

Charles Rosen, leader of the Artificial Intelligence Center at SRI during the days Shakey was developed.

TR’s roots can be traced back to work done in the late 1960s by Nils Nilsson and colleagues at the Stanford Research Institute (SRI) on executing actions for the mobile robot Shakey. Shakey became famous two years later: Life magazine (1970) declared that Shakey was “the first electronic person,” and National Geographic (Nov, 1970) included a picture of Shakey.

Shakey’s environment comprised several rooms, containing moveable boxes of various shapes and colors, and connecting doorways — some of which might be blocked by boxes. The idea of TR programs was foreshadowed by Shakey’s “Intermediate” or “Mid-Level” actions.

The SRI researchers wanted the mid-level actions to be robust, in the sense that they could easily recover from execution failures.  They also wanted them to be opportunistic, in the sense that actions best able to achieve a goal would be preferred.  In Nilsson’s words:

“In thinking about how to achieve this robustness, I was inspired both by Miller, Galanter, and Pribram’s TOTE units and by the idea of homeostasis. (Recall that a TOTE unit for driving in a nail keeps pounding until the nail is completely driven in and that homeostatic systems take actions to return them to stability in the face of perceived environmental disturbances.) I wanted the mid-level programs to seek and execute that action that was both ‘closest’ to achieving their goals and that could actually be executed in the current situation. If execution of that action produced a situation in which, as anticipated, an action even closer to achieving the goal could be executed, fine; the mid-level program was at least making progress. If not, or something unexpected caused a setback, some other action would be executed next to get back on track. Richard Duda and I developed a format, called “Markov tables,” for writing these intermediate-level programs having this ‘keep-trying’ property.” [From Nils J. Nilsson The Quest for Artificial Intelligence: A History of Ideas and Achievements, p. 169, New York: Cambridge University Press, 2010].

Markov table used to achieve robust execution of plan actions.

Markov table used to achieve robust execution of plan actions.

The conditions mentioned in the Markov Table were stored in a Belief Store (BS) of percept facts about objects, rooms, and doorways. These facts were initially provided by Shakey’s programmers, but they could be updated by image analysis routines specially developed for “seeing” things of interest in camera images of the robot’s  environment, taken by an on-robot camera.  The BS store was dynamic, allowing the Markov Table programs to be selected as appropriate for the current perceived situation.

Shakey was also able to assemble mid-level actions into plans for achieving goals. The plans were generated using a planner called STRIPS (an acronym for STanford Research Institute Problem Solver).  After STRIPS assembled a plan for achieving a specific goal, it was “generalized” by replacing non-essential constants in the actions and their corresponding pre-conditions and effects by variables. The generalised plan was then represented as a triangular table whose various cells contained both the pre-conditions and the effects of each action in the plan.

The arrangement of the cells in the table permitted easy identification of that action sequence in the plan that was both executable in the current situation and that was also closest to achieving the goal. Thus Shakey’s method for executing plans, just like its method for executing mid-level actions, was both robust and opportunistic—another foreshadowing of TR programs.

Influenced by these early ideas, Nilsson and a student (Mark Torrance) developed the first actual TR programs while Nilsson was on sabbatical at MIT (in Rod Brook’s Lab) in the summer of 1990. With other students, Nilsson continued working on them when he returned to Stanford.

For a complete set of photos about Shakey the Robot visit this link or this at SRI. A demonstration of 1969 of Shakey running in a  24-minute film (“SHAKEY: Experimentation in Robot Learning and Planning”) is available here.

 

Bibliography

  • Richard Fikes, Peter E. Hart, and Nils J. Nilsson, “Learning and Executing Generalized Robot Plans”, Artificial Intelligence, 3(4):251-288, 1972. (Online version available, as an SRI Technical Note: http://www.ai.sri.com/pub_list/1095.)
  • Nils J. Nilsson, Shakey The Robot, Technical Note 323, pp. 37 and Chapter Eight, AI Center, SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025, Apr 1984.
  • W. Ross Ashby, Design for a Brain, Chapman and Hall, 1952.
  • George A. Miller, E. Galanter, and K. H. Pribram, “Plans and the Structure of Behavior”, New York: Holt, Rinehart and Winston, 1960.
  • Nils J. Nilsson The Quest for Artificial Intelligence: A History of Ideas and Achievements, p. 169 and 336-338, New York: Cambridge University Press, 2010.