Milestones:Shakey: The World’s First Mobile, Intelligent Robot, 1972

Title

SHAKEY: The World’s First Mobile Intelligent Robot, 1972

Citation

Stanford Research Institute's Artificial Intelligence Center developed the world’s first mobile intelligent robot, SHAKEY. It could perceive its surroundings, infer implicit facts from explicit ones, create plans, recover from errors in plan execution, and communicate using ordinary English. SHAKEY's software architecture, computer vision, and methods for navigation and planning proved seminal in robotics and in the design of web servers, automobiles, factories, video games and Mars rovers.

Street address(es) and GPS coordinates of the Milestone Plaque Sites

37.4548167, -122.1720328, SRI International, 333 Ravenswood Avenue, Menlo Park, CA 94025-3493

Details of the physical location of the plaque

The plaque would be installed in the main lobby of SRI International in Menlo Park, CA, next to the "Inception of the ARPANET, 1969" IEEE Milestone plaque that was dedicated in 2009.

How the intended plaque site is protected/secured

The main lobby of SRI International is publicly accessible.

Historical significance of the work

The Shakey project was initiated by Charles A. Rosen, who envisioned it not just as a “mobile automaton”, but as an experimental platform for integrating all the subfields of artificial intelligence as then understood. Logical reasoning, autonomous plan creation, robust real-world plan execution, machine learning, computer vision, navigation, and communication in ordinary English were integrated in a physical system for the first time. Nils J. Nilsson, Bertram Raphael and Peter E. Hart led the project subsequent to Rosen.

As a first broad indicator of Shakey’s historical significance, Shakey resides in the Computer History Museum in Mountain View, CA, where it’s the centerpiece of the Museum’s exhibit on Artificial Intelligence and Robotics. See http://www.computerhistory.org/revolution/artificial-intelligence-robotics/13/289

In more specific technical terms, Shakey is historically significant for three distinct reasons: (1) Its control software was structured—a first for robots—in a layered architecture that became a model for subsequent robots; (2) Its computer vision, planning and navigation methods have been used not only in many subsequent robots, but in a wide variety of consumer and industrial applications; and (3) Shakey served as an existence proof that encouraged later developers to develop more advanced robots.

The significance of these contributions is captured by an unsolicited quote from James Kuffner (http://research.google.com/pubs/author39726.html), who as of 2016 has led robotics research at Google for seven years. In a private communication, he wrote “It is truly amazing how both in terms of architecture and algorithms the Shakey project was ahead of its time and became a model for future robot systems for half a century”.

The following sections elaborate on the above discussion, with verifiable references.

[Note 1: Shakey was developed as a pure research project at a time when software patents were unknown, and government contractors like Stanford Research Institute could not obtain intellectual property rights to their work. There are thus neither product sales figures nor patent counts that can be reported. Instead, for this pure research achievement, the influence of the Shakey project is better evaluated by citations to published papers and by comments made by leaders in the field of robotics.

To help understand the significance of citation numbers given below, it’s helpful to bear in mind that by the year 2015, according to Google Scholar, only around 175 of computer scientists worldwide have a lifetime citation count of more than 5,000. In other words, the total citations to all of their published work is more than 5,000. Accordingly, a citation count of 5,000 for a single paper (not a textbook), is extremely high.]

[Note 2: Many refereed journal articles and conference papers were published about various technical components of Shakey . The key technical publications describing original research, referenced below, were all published no later than 1972. However, there is no single published article describing the overall system. There is, fortunately, an SRI publication [Ref. 1: SRI-AIC Tech Note 323] from 1984 that collates material from many internal project reports prepared by the research team in the 1966 – 1972 time frame. This report is probably the best single overview of the project. A PDF of the report, entitled “Shakey the Robot”, is included in the supplementary materials. There is also a 24 minute video at http://ai.stanford.edu/~nilsson/Shakey.mp4, converted from a 16mm movie that was made by the project team, that provides a good introduction.]

1.1 Layered Control Software for Robots

Shakey’s control software was structured as a multi-level hierarchy with physical actions at the lowest levels, autonomous planning in a middle level, and plan execution (with error recovery) at the top level [Ref. 1: SRI-AIC Tech Note 323]. This design has been adopted by many subsequent robots. An outstanding example is STANLEY, the self-driving vehicle that won the DARPA Grand Challenge in 2005 for driving itself across the Mojave Desert. Sebastian Thrun, the project leader wrote (in a personal communication), “…at the core we had layers just like Shakey. Figure 5 in this paper summarizes the high level software architecture, which should look familiar.” Ref. 2: Thrun] An inspection of Figure 5 will confirm the layered software design at the core of the “Planning and Control” section.

1.2 Shakey’s Algorithms

Of the many computational methods developed in the course of the Shakey project, three in particular have had long term impacts on both technology and on the daily lives of all of us.

1.2.1 The “Hough” Transform for Detecting Lines in Images

In 1962 Paul Hough patented a method for detecting co-linear points in images by transforming image points to straight lines in a transform space. His method was not widely used, because his transform space is infinite in extent and therefore computationally infeasible. In 1972, Peter E. Hart and Richard O. Duda introduced a new sinusoidal version of the transform that eliminated this difficulty (though they did not rename the transform) [Ref. 3: Hough]. The history of this invention was later documented by Hart. [Ref. 4: Hough History]

Hart’s version of the Hough transform is one of the most widely-used algorithms in computer vision. It has been used for decades in applications like visual inspection in manufacturing. By 2014 it started appearing in automobiles, where it enables a safety feature that alerts the driver if the car is drifting out of lane.

According to Google Scholar, the referenced paper has been cited nearly 5,000 times as of 2015. According to the US Patent and Trademarks Office database, 2,115 US patents reference the Hough Transform by this same date.

1.2.2 STRIPS “Rules”; Real World Plan Execution and Error Recovery

Shakey’s planning system was named STRIPS [Ref. 5: STRIPS] (for Stanford Research Institute Problem Solver). STRIPS represented the logic of actions available to it by a set of three “Rules”: The Pre-conditions, Delete List, and Add List of the action. This representation is a practical solution to a famous problem in Artificial Intelligence called the Frame Problem. STRIPS, and particularly STRIPS Rules, were the basis of many subsequent planning systems, as this quote shows: “…. the STRIPS representation and reasoning framework was used as the basis for most automatic planning research for many years.“ [Ref. 6: STRIPS Retro]

STRIPS plans were “learned” so they could be used in future problems and they also were integrated into a plan execution monitoring and error-recovery system called PLANEX. A seminal paper [Ref. 7: STRIPS.PLANEX] on this system is among the most re-published papers in the history of artificial intelligence, the most recent re-publication occurring more than 20 years after initial publication.[Ref. 8: Re.Pub]

1.2.3 The A* Shortest Path Algorithm

The A* algorithm [Ref. 9: AStar] provably computes the shortest (or in general minimum cost) path through a network, and provably does so with minimum computation (as measured by the number of branch points considered). These attractive properties have made A*, and its later elaborations and variants, the path-finding algorithm of choice for a wide variety of applications. These include computing driving directions (whether by a web service or a car navigation system), planning the paths of characters in video games [Ref. 10: Woodcock], parsing strings, or plotting the path of Mars rover vehicles [Ref. 11: DStar].

By 2015, according to Google Scholar, the referenced A* paper has been cited nearly 5,000 times. By the same date, according to the US Patent and Trademarks Office database, 460 US Patents reference A*.

1.3 Shakey as an Existence Proof for Intelligent Robots

At the 2015 meeting of the International Conference on Robotics and Automation, there was a special session (see http://icra2015.org/conference/shakey-celebration#!A99Q0441) called a Celebration of the 50th Anniversary of Shakey. The session included a discussion by a distinguished panel: Prof. Ruzena Bajcsy (UC Berkeley, Director of CITRIS), Rodney Brooks (former head of the CS/AI Lab at MIT, founder of both iRobot and Rethink Robotics), Peter Hart (Shakey project leader and the most-cited author in the field of Robotics according to Google Scholar), Nils Nilsson (Shakey project leader, former Chair of CS at Stanford), James Kuffner (Director of Robotics Research at Google), Prof. Benjamin Kuipers (University of Michigan), and Prof Manuela Veloso (endowed Chair in AI and Robotics at CMU). The panel was asked to name Shakey’s biggest impact or major contribution. The panel’s consensus was that the totality of Shakey—the first physical system with computational abilities to perceive, reason and act—was the single biggest contribution. A video of the panel discussion, as of this writing, is posted at http://icra2015.org/conference/shakey-celebration#!A99Q0441. (The viewer may have to scroll a bit to find it.)

Features that set this work apart from similar achievements

As already emphasized, Shakey was the world’s first mobile, intelligent robot. Nothing like it previously existed outside the realm of fiction.

There was, however, a programmable factory automation device called a Unimate (http://www.robothalloffame.org/inductees/03inductees/unimate.html) that was introduced commercially in 1961. It was a stationary mechanical arm that was programmed by setting waypoints and actions with a hand-held controller. Unlike Shakey, it did not have an ability to perceive its world, to create plans, to recover from execution errors, or to communicate with users in ordinary English. It was, however, sometimes referred to as a ‘robot’ or ‘robot arm’, a usage that continues to this day when describing the painting and welding programmable arms now common in automobile factories.

Two earlier machines also deserve brief mention just to present a complete account. Around 1950 the physiologist Grey Walter built a small mobile “Turtle” whose analog circuits could be arranged so that it moved either towards or away from a light source [Ref-14: Turtle]. And in the early 1960’s researchers at Johns Hopkins University built a mobile device called the “Beast” that was programmed to plug itself into a wall socket when its batteries ran low. [Ref-15: Beast] Neither of these machines were designed to have perceptual, planning, execution monitoring, error recovery or natural language ability.

Significant references

Shakey Reference 1 (Ref-1): SRI International AIC Technical Note 323 “Shakey the Robot,” edited by Nils J. Nilsson, April 1984 (TechNote 323). Ref-01_AICTechNote323.pdf

Shakey Reference 2 (Ref-2): Thrun, S., et al, “Stanley: The Robot that Won the DARPA Grand Challenge”, J. Field of Robotics, 23(9) 661 – 692 (2006), Wiley Interscience. (Thrun at http://onlinelibrary.wiley.com/doi/10.1002/rob.20147/epdf) Figure 5, p. 667. Figure 5 also is available at Ref-02_ThrunDiagram.pdf

Shakey Reference 3 (Ref-3): Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp 11-15 (January, 1972) (Hough). In Ref-03_UseOfTheHoughTransformationToDetect LinesAndCurvesInPictures.pdf

Shakey Reference 4 (Ref-4): Hart, Peter E., “How the Hough Transform was Invented”, IEEE Signal Processing Magazine, Vol 26, Issue 6 (November, 2009) pp 18-22 (Hough History). Ref-04_HowHoughTransformWasInvented.pdf

Shakey Reference 5 (Ref-5): Fikes, R. E., and N. J, Nilsson, “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving”, Artificial Intelligence 2 (1971) pp 189-208. (STRIPS) Ref-05_STRIPS.pdf

Shakey Reference 6 (Ref-6): Fikes, R. E, and N. J. Nilsson, “STRIPS, a retrospective”, Artificial Intelligence 59, (1993) p 229 (STRIPS Retro) Ref-06_STRIPS-Retro.pdf

Shakey Reference 7 (Ref-7): Fikes, R. E., P. E. Hart and N. J. Nilsson, "Learning and Executing Generalized Robot Plans," Artificial Intelligence, Vol. 3, No. 4, pp 251-288 (Winter 1972) ) (STRIPS.PLANEX) Ref-07_STRIPS-PLANEX.pdf

Shakey Reference 8 (Ref-8) (Re.Pub): This paper was republished in the following edited collections: Fikes, R. E., P. E. Hart and N. J. Nilsson, "Learning and Executing Generalized Robot Plans," Artificial Intelligence, Vol. 3, No. 4, pp 251-288 (Winter 1972); also in the following: Readings in Artificial Intelligence, B. L. Webber and N. J. Nilsson (eds.), (Tioga Publishing Company, Palo Alto, California, 1981); Readings in Machine Learning, J. W. Shavlik and T. G. Dietterich (eds.), (Morgan Kaufmann Publishers, San Mateo, California, 1990); Readings in Planning, J. Allen, J. Hendler, and A. Tate (eds.), (Morgan Kaufmann Publishers, San Mateo, California, 1990); Readings in Knowledge Acquisition, B. G. Buchanan and D. C. Wilkins (eds.), (Morgan Kaufmann Publishers, San Mateo, California, 1993).

Shakey Reference 9 (Ref-9): Hart, P. E., N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs," IEEE Trans. on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp 100-107, (July 1968) (AStar) Ref-09_AStar.pdf

Shakey Reference 10 (Ref-10): “A* is far and away the most used. . . and most useful. . . algorithm for path finding in games today.” Email from Steven Woodcock, Computer Games Consultant (Woodcock)

Shakey Reference 11 (Ref-11)(Dstar): The Mars rovers Spirit and Opportunity (that reached the surface of Mars in 2004), and the Curiosity rover (that reached the surface of Mars in 2012) use a derivative of A* called Field D* to navigate on Mars. Autonomous navigation is required because Mars rovers cannot be effectively driven manually from earth because of the lengthy round trip signal propagation time between Earth and Mars. Information on the use of Field D* on Curiosity was given in a personal communication with a Curiosity project team leader. Use of D* on Spirit and Opportunity is documented in Carsten, J., A. Rankin, D. Ferguson and A. Stentz, “Global Planning on the Mars Exploration Rovers: Software Integration and Surface Testing”, J. Field Robotics, 26(4), 337 – 357 (2009). Ref-11_FieldDStar.pdf

Shakey Reference 12 (Ref-12): Nilsson, N. J., The Quest for Artificial Intelligence, Cambridge University Press, 2010, p. 164.

Shakey Reference 13 (Ref-13): Stanford hosted a Shakey retrospective at which Charles A. Rosen described some of the political obstacles he faced in securing funding to start the project. Rosen’s comments begin at approximately 15 minutes into a video of the event posted at http://www.ai.sri.com/movies/Shakey-3487234/Shakey-BACHP-19951024.mov

Shakey Reference 14 (Ref-14): Nilsson, N. J., The Quest for Artificial Intelligence, Cambridge University Press, 2010, pp. 23-24.

Shakey Reference 15 (Ref-15): Nilsson, N. J., The Quest for Artificial Intelligence, Cambridge University Press, 2010, pp. 162-163.

Supporting materials

{{{support}}}