Shakey: how the first mobile robot was arranged

Created in the 60s, Shakey became the first mobile robot with the ability to analyze its actions. The ambitious goals of the project were not fully achieved, but it had a great influence on the further development of robotics.

About how the robot control was arranged, the authors of the Shakey project were told in a large article, AI Magazine. In this post - translation of the most interesting and important piece of text. Its author, Peter Hart, was on the development team.

Creating Shakey

The Shakey project was launched in January 1965 at the initiative of the Center for Artificial Intelligence at the Stanford Research Institute (SRI International). The institute proposed the development of a “smart machine” for intelligence use. But the working group had a different motivation. They wanted to create a test platform for connecting all areas of artificial intelligence (system representation, reasoning, planning, machine learning, computer vision and understanding of natural speech).

When developing Shakey, engineers were guided by two rules:

the mechanic needs to keep it as simple as possible - therefore, not a single arm has been installed on the robot;
so as not to work on reducing the design, the electronics rack was installed on top.

Since the mechanical and sensory capabilities of Shakey were limited, the project team created an appropriately simple experimental environment for the robot - half a dozen rooms with large geometric blocks inside. The blocks were painted to be recognized by a low resolution camera.

Shakey's first computer was an SDS 940 with less memory than the L2 cache of modern laptops. In 1970, it was replaced by a more powerful DEC PDP-10. Shakey spoke to the PDP-10 through a communication processor. This system was one of those nodes that contributed to the birth of the ARPANET. At about the same time, a complete rewrite of the Shakey software began. "Iron" needed only minimal improvements.

Basic Shakey Design Elements

Shakey software

The basis of the second version of the product formed two fundamental ideas. The first is to introduce the Shakey world through first-order predicate calculus, complementing the form with a grid model, a key component of the first version.

The second idea was to structure the Shakey software into several layers. This approach to robot control was used for the first time. Next, we briefly describe each level, starting with the commands of the lower level.

Lower Level Commands

Lower level commands, such as ROLL and PAN, were sent directly to the hardware component of Shakey. At this level, there are also commands such as PANTO, which was responsible for turning the “head” of the device in the chosen direction.

Intermediate teams: Markov chains

At this level are commands such as GOTHRUDOOR (“go through the door”). They were allocated to a separate level, since they were all presented in the form of Markov chains .

Markov chain for GOTHRUDOOR team

Markov chains can be “read” by first scanning the left column until the first true condition is met that performs the corresponding action, and then returning back to the beginning of the table. Accordingly, stability is characteristic of Markov's chains (this algorithm of actions is slightly simplified, but the practice of “returning to the beginning” is fundamental and, as we shall see, an important feature of these chains).

If mid-level teams were the last Shakey could perform, the robot would be very limited in its actions. He could only achieve goals that require only one pre-programmed action. To do more, Shakey had to be able to make a sequence of actions (as a plan). The automatic scheduler STRIPS (Stanford Research Institute Problem Solver) was responsible for this. He was the next higher level of software.

STRIPS, Stanford Research Institute Problem Solver

The automatic STRIPS scheduler came about by combining two great concepts. The first was a planning strategy called analysis of goals and means. It is represented in the “Universal Problem Solver” system (General Problem Solver) by Herbert Simon and Allen Newell.
The second concept was the proof of the theorem in the predicate calculus and its application in question-answer systems. This is discussed in the work of Cordell Green. Richard Fikes and Nils Nilsson combined this knowledge to create STRIPS in 1971, which applied the analysis of goals and means to the predicate calculus.

PLANEX Plan Execution Executive

Soon after the creation of STRIPS, the institute team found a way to summarize the STRIPS plan, replacing the constants in the system with variables. They also invented a data structure called the triangle table, which demonstrates the internal interdependencies of the generalized plan. These designs formed the basis of the PLANEX system — the latest level of Shakey software (Fykes, Hart and Nilson, 1972).

Using this software, PLANEX can monitor the actual implementation of the plan. The system may notice if something went wrong and reschedule the work from now on, reusing parts of the existing plan where possible. It may even be an “adventurous” decision: if Shakey was suddenly closer to completing his task, he could turn it in his favor.

This ability to detect and recover errors was a critical part of Shakey software. There is a big difference between creating an action plan for a real robot, which functions in the present world, where something can go wrong, and an “abstract” planner, who simply needs to print a symbolic plan. PLANEX and the Markov chains have become the solution for achieving a reliable, realistic plan.

Shakey Software Level Hierarchy

Computer vision

The original project plan did not require intensive research in the field of computer vision. Rather, the plan was to integrate existing methods of computer vision into an experimental platform. But, as it turned out, at that time there were very few technologies available, so the specialists had to work hard in the field of computer vision research.

One of the important results of this work was the invention of what can be called the modern form of Hough transformation, the method used to extract elements from an image (R. Duda, P. Hart, 1972). This was achieved by combining the two concepts, which at first glance seem completely unrelated.

The first idea is contained in the Paul Hough patent. It describes the transformation from points in the image plane to straight lines in the transform space. Intersecting lines in the latter correspond to collinear points in the form. But the problem of endless slopes arises, which makes this transformation computationally cumbersome.

The second idea comes from the so-called integral geometry. Mathematicians had theoretical reasons to use the parameterization of the angular radius of the line, rather than the more familiar intercept slope used by Hough. Peter Hart noted that replacing the linear Hough transform with a sinusoidal not only solves the problem of infinite slopes, but the new transformant is invariant to the choice of coordinates. In addition, Peter Hart and Richard Duda expanded this method to detect analytical curves in images, and this transformation has been used since then.

Navigation and A * algorithm

Shakey had to navigate the terrain, so several shortest path algorithms were developed. One of them, named A *, was created by Peter Hart, Niels Nilson and Bertram Rafael. The new algorithm had very useful properties: firstly, it always found the shortest path, and secondly, at the same time it selected the minimum number of alternative possibilities. It can be said that it always works and is computationally efficient.

One might think that such a significant result would gladly welcome any publication, but it turned out the opposite. The presentation of the A * algorithm was rejected by all prestigious scientific journals of the time.

Looking through these old reviews, one might think that the editors gave the report to mathematicians because of all these frightening theorems. However, mathematicians were not impressed, because of the evidence only graphs with a finite number of nodes were presented. At that time, it seemed to the authors that mathematicians did not see the difference between a ten-node graph and a ten trillion-graph graph. But for scientists working in the field of computer science, this difference is significant.

In the end, the report was accepted at the Institute of Electrical and Electronics Engineers (IEEE Transactions on Systems Science and Cybernetics) and has continued to refer to it for over 45 years.

World at that time

The above gives an idea of the part (although far from the whole volume!) Of the work done by the Shakey project team. To have an idea of this work in a wider social context, we will look at the intellectual and cultural climate of that time.

In 1970, a popular article on the Shakey project was published in the popular magazine Life. The author, journalist Brad Darrah, apparently, went a little too far with the headline: "The fascinating and terrible reality of a machine with its own mind." However, at a time when some believed that robots could enslave the world, others were rather skeptical about such articles. Hubert Dreyfus was one of those who philosophically argued that the concept of AI is unreal in principle. And somewhere between Darrach and Dreyfus there were those who feared that robots might someday take human jobs.

Shakey in Life Magazine

Shakey guests

The developers of the robot welcomed every visitor interested in their work. A review of the reactions received also says a lot about the state of the world at that time. Here are some examples:

A group of schoolchildren visited the laboratory. The teacher accompanying them asked what the “real jobs” of engineers are: “This robot is your hobby, isn't it?”
The general asked if a 36-inch knife could be attached to the robot.
Arthur Clark visited the laboratory immediately after the release of the 2001 film “Space Odyssey”, but was more interested in talking about the New York Times review of the film than in discussions about the future of robots.
A high school student drove from Seattle to Menlo Park in California to see Shakey. Decades later, Bill Gates recalled that what he saw impressed him.
An auditor from the US government asked whether SRI really took over the delivery of billions of “bit packets”. This question was followed by others, including whether corrosion was noticed on one of these bits.

Shakey project completion

The Shakey project was closed in 1972 - not because of a lack of ideas, but because of a lack of funding. What has been achieved during its existence?

There were as many opinions on this score as there are team members, but several generalizations can be made:

Many of the project’s private results (STRIPS, PLANEX, A * algorithm and new Hough transformation form) have become a significant technical contribution.
Overall, Shakey was a significant achievement. He was at the same time the first mobile intelligent robot and the first system that combined software with AI with physical hardware.
Shakey's overall capabilities, in terms of both mechanics and software, did not reach the level of initial aspirations. This is not surprising, given the initially high level of claims. It took decades to achieve some of the stated goals, while others still remain unresolved.

References:

1. "Shakey: From Conception to History". Original article. The second part of the material tells about the further application of the Shakey discoveries. Go to
2. “How Much Does It Take To Redo Shakey the Robot?” - an attempt to reproduce Shakey in modern conditions. Go to

More interesting about robotics - on robo-hunter.com: