Robohub.org
Shakey is first robot to receive IEEE Milestone award
Shakey the Robot, the world’s first mobile, intelligent robot, developed at SRI International between 1966-1972, was the first robot to be honored with a prestigious IEEE Milestone in Electrical Engineering and Computing. The IEEE Milestone program honors significant inventions, locations or events related to electrical engineering and computing that have benefitted humanity, and which are at least 25 years old.
“Shakey was groundbreaking in its ability to perceive, reason about and act in its surroundings,” said Bill Mark, Ph.D., president of SRI’s Information and Computing Sciences Division. “We are thrilled that Shakey has received this prestigious recognition from the IEEE as it is a testament to its profound influence on modern robotics and AI techniques even to this day.”
The original Shakey robot is on display at the Computer History Museum where it is the centerpiece of the Artificial Intelligence portion of its “Revolution: The First 2000 Years of Computing” exhibition. In 1970, Life magazine referred to Shakey as the “first electronic person”, and National Geographic also carried a picture of Shakey in an article on the present uses and future possibilities of computers. Shakey was also inducted into the Carnegie Mellon’s Robot Hall of Fame in 2004.
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.
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, 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”.
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 in the daily lives for 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 probably 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 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 can also be viewed here.
As cast on a bronze plaque at SRI International, the IEEE Milestone’s citation reads: “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.”
References:
tags: ieee, robotics
