Milestone-Proposal:Shakey: The World’s First Mobile, Intelligent Robot, 1972
To see comments, or add a comment to this discussion, click here.
Docket #:2016-04
This Proposal has been approved, and is now a Milestone
To the proposer’s knowledge, is this achievement subject to litigation? No
Is the achievement you are proposing more than 25 years old? Yes
Is the achievement you are proposing within IEEE’s designated fields as defined by IEEE Bylaw I-104.11, namely: Engineering, Computer Sciences and Information Technology, Physical Sciences, Biological and Medical Sciences, Mathematics, Technical Communications, Education, Management, and Law and Policy. Yes
Did the achievement provide a meaningful benefit for humanity? Yes
Was it of at least regional importance? Yes
Has an IEEE Organizational Unit agreed to pay for the milestone plaque(s)? Yes
Has the IEEE Section(s) in which the plaque(s) will be located agreed to arrange the dedication ceremony? Yes
Has the IEEE Section in which the milestone is located agreed to take responsibility for the plaque after it is dedicated? Yes
Has the owner of the site agreed to have it designated as an IEEE Milestone? Yes
Year or range of years in which the achievement occurred:
1966-1972
Title of the proposed milestone:
SHAKEY: The World’s First Mobile Intelligent Robot, 1972
Plaque citation summarizing the achievement and its significance; if personal name(s) are included, such name(s) must follow the achievement itself in the citation wording: Text absolutely limited by plaque dimensions to 70 words; 60 is preferable for aesthetic reasons.
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.
200-250 word abstract describing the significance of the technical achievement being proposed, the person(s) involved, historical context, humanitarian and social impact, as well as any possible controversies the advocate might need to review.
IEEE technical societies and technical councils within whose fields of interest the Milestone proposal resides.
In what IEEE section(s) does it reside?
Santa Clara Valley
IEEE Organizational Unit(s) which have agreed to sponsor the Milestone:
IEEE Organizational Unit(s) paying for milestone plaque(s):
Unit: Santa Clara Valley
Senior Officer Name: Joseph Wei
IEEE Organizational Unit(s) arranging the dedication ceremony:
Unit: Santa Clara Valley
Senior Officer Name: Joseph Wei
IEEE section(s) monitoring the plaque(s):
IEEE Section: Santa Clara Valley
IEEE Section Chair name: Joseph Wei
Milestone proposer(s):
Proposer name: Brian Berg
Proposer email: Proposer's email masked to public
Please note: your email address and contact information will be masked on the website for privacy reasons. Only IEEE History Center Staff will be able to view the email address.
Street address(es) and GPS coordinates in decimal form of the intended milestone plaque site(s):
SRI International, 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
Describe briefly the intended site(s) of the milestone plaque(s). The intended site(s) must have a direct connection with the achievement (e.g. where developed, invented, tested, demonstrated, installed, or operated, etc.). A museum where a device or example of the technology is displayed, or the university where the inventor studied, are not, in themselves, sufficient connection for a milestone plaque.
Please give the address(es) of the plaque site(s) (GPS coordinates if you have them). Also please give the details of the mounting, i.e. on the outside of the building, in the ground floor entrance hall, on a plinth on the grounds, etc. If visitors to the plaque site will need to go through security, or make an appointment, please give the contact information visitors will need. The intended site is SRI International (known as Stanford Research Institute until 1977), the location of the conception, development and creation of Shakey.
Are the original buildings extant?
N/A
Details of the plaque mounting:
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 is the site protected/secured, and in what ways is it accessible to the public?
The main lobby of SRI International is publicly accessible.
Who is the present owner of the site(s)?
SRI International
What is the historical significance of the work (its technological, scientific, or social importance)? If personal names are included in citation, include detailed support at the end of this section preceded by "Justification for Inclusion of Name(s)". (see section 6 of Milestone Guidelines)
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.)
What obstacles (technical, political, geographic) 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.
What features 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.
Why was the achievement successful and impactful?
Supporting texts and citations to establish the dates, location, and importance of the achievement: Minimum of five (5), but as many as needed to support the milestone, such as patents, contemporary newspaper articles, journal articles, or chapters in scholarly books. 'Scholarly' is defined as peer-reviewed, with references, and published. You must supply the texts or excerpts themselves, not just the references. At least one of the references must be from a scholarly book or journal article. All supporting materials must be in English, or accompanied by an English translation.
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 (supported formats: GIF, JPEG, PNG, PDF, DOC): All supporting materials must be in English, or if not in English, accompanied by an English translation. You must supply the texts or excerpts themselves, not just the references. For documents that are copyright-encumbered, or which you do not have rights to post, email the documents themselves to ieee-history@ieee.org. Please see the Milestone Program Guidelines for more information.
Please email a jpeg or PDF a letter in English, or with English translation, from the site owner(s) giving permission to place IEEE milestone plaque on the property, and a letter (or forwarded email) from the appropriate Section Chair supporting the Milestone application to ieee-history@ieee.org with the subject line "Attention: Milestone Administrator." Note that there are multiple texts of the letter depending on whether an IEEE organizational unit other than the section will be paying for the plaque(s).
Please recommend reviewers by emailing their names and email addresses to ieee-history@ieee.org. Please include the docket number and brief title of your proposal in the subject line of all emails.
