Milestones:SHAKEY: The World’s First Mobile Intelligent Robot, 1972
- Date Dedicated
- 2017/02/16
- Dedication #
- 172
- Location
- Menlo Park, CA
- IEEE Regions
- 6
- IEEE sections
- Santa Clara Valley
- Achievement date range
- 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
- Site 1: SRI International Building A, 333 Ravenswood Ave., Menlo Park, CA 94025; 37.45758, -122.17642
- Site 2: Computer History Museum, 1401 N. Shoreline Blvd, Mountain View, CA 94043, 37.414757, -122.077679
Details of the physical location of the plaque
- Site 1: In the SRI Building A Visitors Lobby, the 2nd of 3 Milestone plaques mounted on the left wall
- Site 2: On the inside face of the front patio brick wall, near the museum's Main Entrance
How the plaque site is protected/secured
- Site 1: Open to the public 7am-6pm on weekdays
- Site 2: Building security; 24/7 access.
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.)
Obstacles (technical, political, geographic) that needed to be overcome
The Shakey project faced funding and political problems, beyond the daunting technical challenge of undertaking to do something that had never been done before.
2.1 Funding Challenges
It took two years of promotional efforts by Rosen to secure a first round of funding from ARPA (a part of the Department of Defense). A 1964 Statement of Work [Ref. 12: SoW] for such a project was prepared by an ARPA official who shortly left the Agency and set promotional efforts back. The project didn’t begin until March of 1966. Bearing in mind that, until Shakey, intelligent robots existed only in works of fiction, it’s easy to understand why funding requests would be met with skepticism.
2.2 Political Challenges
Research in artificial intelligence at that time was pursued in only handful of mainly academic centers. Stanford Research Institute was not considered to be on a research par with the most famous research universities, nor did Rosen have the academic credentials in artificial intelligence of the most famous computer science professors. (Rosen’s academic background was in applied physics. As an indicator of his passion for innovation, he co-authored the world’s first textbook on transistors.) Perhaps for these reasons, Rosen’s proposals to build an “intelligent automaton” (there were several written before the project was funded) were not supported by the leading academic figures in the field [Ref 13: CAR].
2.3 Technical Challenges
The technical challenges faced by the project team are almost too numerous to list, so we’ll group them into major areas:
2.3.1 Conceptual Challenges
Since a mobile intelligent robot had never before been built, what should it look like? Should the robots of science fiction be copied? How much effort should be allocated to engineering the physical robot, compared to inventing the artificial intelligence methods and developing the software? What should the experimental environment look like? What were achievable overall capabilities that could be set as goals?
2.3.2 Computational Limitations
The computational limitations of the late 60’s and early 70’s are hard to fathom today. All computation was done off-robot on a time-shared mainframe. The first mainframe was an SDS 940. It’s main memory—this on a machine serving dozens of simultaneous users—was half the size of the L2 cache of a 2015 Apple laptop. The second and more powerful mainframe was a DEC PDP 10. It had a “swapping drum” (used for swapping time-shared jobs in and out of main memory) that was bigger than a refrigerator, held a little over one megabyte, and cost more than $1.5 million in 2015 dollars. That’s more than one dollar per byte!
2.3.3 Shakey’s Model of the World
What formalism(s) should be used to represent Shakey’s physical world? Certainly the geography and geometry of its world had to be represented in some fashion. Beyond that, what does Shakey need to know about logical relations? For example, how would you represent that for Shakey to “climb” on to a low platform there has to be a ramp available? How should geometric and symbolic models be coordinated?
2.3.4 Planning Challenges
For Shakey to do more than execute pre-programmed actions that achieved pre-defined goals, it needed a means to compose plans consisting of a sequence of actions. Very few examples of such planning systems existed at the time, and the ones that did had limitations that made them hard to use in the context of a physical robot.
2.3.5 Plan Execution Challenges
A crucial difference between a physical robot like Shakey and the abstract “agents” that existed up to that point is the issue of real-world execution. Planning systems before Shakey assumed that their job was finished once a plan was printed out. But Shakey had to execute plans in the physical world, where things often go wrong. So Shakey required the ability to monitor real-world execution, detect when something has gone wrong, and recover from execution errors. None of this had been done before.
2.3.6 Computer Vision Challenges
Shakey’s primary sensor was a video camera with only 120 lines of resolution. The state of the art in computer vision at the time was very rudimentary. (Even the term “pixel” had not yet come into common use.) So no existing computer vision methods existed that could extract required information from low resolution images. The most important computer vision methods used in Shakey were invented by the project team.
2.3.7 Navigation Challenges
Graph-searching algorithms existed before Shakey, but it appeared questionable that they would be scalable to the level that would some day be needed. New algorithms had to be invented.
2.3.8 Natural Language Challenges
An explicit research goal of the Shakey project was to enable communication with people using ordinary English. Computational linguistics was in its infancy, so this presented a major technical challenge.
2.3.9 Learning Challenges
Another explicit research goal was to enable Shakey to learn. Learning machines in the sense of neural nets were in their infancy, and were ill-suited to Shakey’s tasks. Rather than pursue that approach, the research team invented a way to give Shakey the ability to learn plans and use them to help solve future problems.
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.
5-minute video created by SRI for the Milestone dedication event
SHAKEY Milestone website created by dedication event organizer Brian Berg
Supporting materials
See references
Dedication Ceremony
SHAKEY's Impact on the Mars Rovers
SHAKEY: A Capsule Overview
Map
