Pros and cons of the Shakey the robot project

A while ago a paper was published, which introduces the Shakey the robot project again and explains the advantage and disadvantages of the STRIPS planning system. On page 1 it was also explained, that Rodney Brooks wrote an anti-Shakey paper in which he explains that formalized planning is a dead end. It's important to focus first on the idea of a logical model of the environment. The Shakey robot has a preprogrammed environment model in which his own position, the allowed actions and other objects are foramlized in the situation calculus. This model allows Shakey to plan from the current situation into any future goal state.

The disadvantage of the concept and the reason why Brooks wrote a STRIPS critique is, that such a logical model is hard to program and it doesn't fit to the environment. In reality, it's not possible to reuse an existing STRIPS model. The Shakey description can't be utilized in a different robot for example a modern Lego Mindstorms system. Instead the STRIPS model has to be programmed again, which takes a large amount of time.

To understand the problem we have to go a step backward. The normal interaction between a robot and a human operator is done via teleoperation. That human can move the robot by using a joystick. If the robot should drive autonomously, he needs a logical model. The basic question is how to come from a teleoperated robot into an autonomous robot system. The answer is called plan recognition and learning from demonstration. This is the step inbetween and means, that the human interaction with the robot is tracked and converted into a model.

Plan recognition is equal to model tracking. The idea is not that Shakey should plan the next actions, but the idea is analyze if the logical model of the environment is right. The idea of STRIPS and Shakey goes into the right direction, what is missing is the ability to analyze human interaction with a teleoperated robot.

In the literature the idea of plan recognition is a new development because it's hard to explain why this technique is needed. From a practical standpoint it's equal to control a robot with a joystick and the software is able to recognize the actions. That means, the human operator let Shakey collide with an obstacle, and on the screen it is shown “collision detected”. Because the human operators knows the information in advance it seems that for such a message there is no need. Without a working plan recognition it's not possible to verify or build a logical representation of the environment. That's the reason why most STRIPS based projects have failed.´

Shakey the robot and STRIPS is working great, if the logical representation is there. The planner can take the model and plan the next steps to reach a goal. It's not very complicated to write such a planner and he will run with maximum performance. The bottleneck is there if the logical model isn't correct or no such model is available. In such a case, the robot won't make any action.

Plan recognition is equal to human-machine communication.[2] The robot and the human operator are speaking the same language. The problem is not how the Shakey software works internally, the question is, if Shakey is able to understand the teleoperator.

The plan recognition problem is a relative new develoopment which was analyzed after Shakey was built:

quote ”Schmidt, Sridharan and Goodson [1978, 1976] are the first to identify plan recognition as a problem in its own right” [3]

In contrast to robot control, plan recognition doesn't result into a working system. Instead the idea is to annotate the movements of a teleoperated robot. Somebody may argue, that it has nothing to do with Artificial Intelligence because the robot is controlled by a human operator. Additionally, the detected events and activities are grounded in natural language and psychology which is outside of computer science.

Debugging

Plan recognition can be seen as a model debugger. It is only successful, if the plan library contains of predefined actions which are able to detect events in the environment.[4] This allows for the programmer to implement and test new plan libraries, similar to writing computer code. He types in an action and used the plan recognizer to verify if the action makes sense.

Plan corpus

To simplify the process of plan recognition it's useful to build a plan corpus. That is a large plan library which contains action primitives and events for detecting and annotating raw data. It's not possible to generate a plan corpus automatically, but it's a manual task similar to create an English dictionary. A plan library is usually created by asking human participant to do a task, for example to walk on a line. Then the motion capture suite is recording all the information and they are annotated manual. On top of the recorded trajectory a parser is programmed. The overall plan library project has to provided as Open Science project in the internet which allows other researchers to participate.

Examples for corpus from the past are: HASC corpus, USC-HAD, Hugadb[5], PRAXICON and other datasets for activity recognition. Most of these projects were realized in the last 10 years.

[1] Shanahan, Murray. "Reinventing shakey." Logic-based artificial intelligence. Springer, Boston, MA, 2000. 233-253.

[2] Pollack, Martha E. "The uses of plans." Artificial Intelligence 57.1 (1992): 43-68.

[3] Mao, Wenji, and Jonathan Gratch. Decision-theoretic approach to plan recognition. ICT Technical Report ICT-TR-01-2004, 2004.

[4] Goultiaeva, Alexandra, and Yves Lespérance. "Incremental plan recognition in an agent programming framework." Working Notes of the AAAI Workshop on Plan, Activity, and Intention Recognition (PAIR). 2007.

[5] Chereshnev, Roman, and Attila Kertész-Farkas. "Hugadb: Human gait database for activity recognition from wearable inertial sensor networks." International Conference on Analysis of Images, Social Networks and Texts. Springer, Cham, 2017.

Planning vs. plan recognition

Successful example of Artificial Intelligence for gameplaying is chess and tictactoe. In both cases the AI works by creating the gametree and search for a node in the tree. Because this strategy works so great, most AI amateurs are trying to transfer this idea to robotics as well. The problem is, that robotics has a larger state space and it's not possible to build the entire state space.

To overcome the bottleneck we have to describe what AI planning in general is. Planning means, that a game engine is available in which actions are allowed. In case of chess, the game engine allows the player to make different moves in the game. The underlying game engine affects the size of the state space. If the player has more possible actions and if the game tooks longer, then the state space will become greater. The only way in reducing the state space is to modify the underlying game engine. If the game contains of a small amount of moves the state space is much smaller.

The question is not how to plan with the existing game engine, the more interesting question is how to create a new game ontop of the old one which has an abstract state space. I want to explain this on a simple maze robot. In the normal game, the robot can walk in four directions: up, down, left, right. The result is a certain type of games. For example, if the robot would like to go 10 steps upward, he has to execute the sequence: up, up, up, up, up, up, up, up, up, up.

To simplify the game, we can add a macro-actiion which is called “5up”. In the newly create game, the robot can change it's position with the 5up command directly to 5 steps upwards. To reach the same goal position, he has to execute the sequence: 5up, 5up. On the first look, the idea of macro-actions looks not very powerful, but it is. It allows to reduce the state space for any game. The result is, that the solver can plan longer sequences in a shorter amount of steps. We are not talking about an improvement of 10% or 50%, but the improvement will become 1 million percent and more. It's possible to exploit macro-actions as the only problem solving technique to play all kinds of games.

The only difficulty is, that most games, doesn't provide macro-actions. They have to be invented by the programmer first. This is called domain knowledge, because it's annotate the gameplay on a semantic level. But let us go back to the planning process. If the game engine is fixed, it's indeed hard or even not possible to plan for a complicated game. A game has a fixed amount of actions, and if the solver can only the normal actions he will have to search the game step by step. If the gameengine is a physics simulation, the costs of executing a single action will become much harder than in chess. That means, if the programmer is not allowed to improve the game engine with macro-actions he will struggle with AI planning.

The interesting point is, that it's ok to extend a game engine with new actions. It's not cheating to invent an action like “5up”. It's the same what humans would do if they want to play the game. They are not saying, that the player has to press 10x times the up key, but they will say “go to the top”. That's shorter and increases the abstraction level. The same strategy will improves the human-machine communication as well. If the game engine gets new abstract commands, it will allows the human player to formulate more elaborated commands.

The only problem is, that creating hierarchical abstract macro-actions for a given game is more complicated than only traverse a given game engine. That means, the overall concept is a bit harder to grasp. To make the understanding more easier, it's important to know, that in AI planning the planning can be ignored. If the STRIPS file is available, it's very easy to search in the gametree. This can be realized with 20 lines of code, or with an existing solver. The more demanding task is to create the STRIPS file for a certain domain. This is the real bottleneck in AI planning. Let us explain why AI planning itself is easy.

Suppose a game engine is available. The game engine provides to the outside world a set of possible actions: action0=left, action1=right, action2=up, action3=down. If the actions are executing in serial order a gametree is the result. This is a graph of all possible combinations. A solver can send the sequence (left, left, up, up) or he can send (up, up, right, down) to the game engine. Traversing the game tree means, either to send random commands to the game engine which takes a bit longer, or to create a dedicated tree which speeds up the search a bit. And now we can ask which issue will limit the solver, it's the size of the state space. That means, if the total amount of nodes is only 100 or maybe 1000 the solver will find the plan very fast. But if the number of nodes is higher, he will struggle.

Instead of explaining what AI planning is, the better idea is to ask what the size of the gametree will be. If the size is too large, AI planning will fail and we have to modify the game engine with macro actions.

Plan recognition for a kitchen robot

The desired behavior of a kitchen robot is, that the machine can do something useful by it's own. The human has to press only the start button and the robot will cook something. Unfortunately, such an AI system isn't available yet. The overall architecture is complicated and many scientists have failed in building such robots. What can be realized is a weaker form of a kitchen robot, who is teleoperated. Teleoperation means, that the human operator has to cook the meal and he is doing so with a dataglove controlled robot.

From an economical standpoint teloperation is not very productive. The overall workflow will take longer than without the robot in the loop. But it will help to make some AI related topics visible, especially the task of plan recognition. What does that mean? If the human operator will cook the meal he will do some actions for example “grasp the bottle”, “cut the apple with a knife” and so on. Formalizing these actions into a plan description language is a first but important step towards robot autonomy. The sad news is, that a perfect working plan recognition system isn't able to repeat the task by it's own. The human operator has to control the robot with the teleoperation interface. The extra service is, that at the same time the executated plan is made visible on the screen.

The proposed plan description language contains of a plan library which holds the actions: grasp, open, close, ungrasp, cut and so forth. And it contains of subplans, for example “open bottle” means to approach the object, put the finger on the top side and move the closure to the left. That means, a plan contains of hierarchical actions which are taken from a library.

I'd like to describe such a system in action. The first thing what the human operator is doing is to put his hand into the dataglove. This gives him control over the robot hand. If the human operator opens the finger, the robot will do the same. All what the dataglove is doing is to transmit the actions to the robotarm as fast as possible. This allows the operator to manipulate the scene. The second element of the system is a plan recognition system in the background. It checks what the human is doing and matches the actions with the plan description language. The generated plan is similar to the real actions of the robot. The human operator is doing something, and at the same time the textual description is shown on the monitor.

The interesting point is, that more AI related technology is not needed for the moment. The operator can do every task and with a bit luck, the system will recognize the subactions with a parser. The combination of a remote controlled robot arm plus a plan recognizer are useful introductions into the subject of robotics. They will not result into a fully autonomous household robot, but they can bring Artificial Inteligence forward. I belief it's important to identify such low hanging fruits. They are located between a teleoperated system and a fully autonomous robot. Somewhere in between is the demand for AI related research. The goal is to realize the steps in between in software. The fallback mode is always the teleoperated robot. Teleoperation is something which works always. Even if no Artificial Intelligence at all is available, it's possible to control a robot with a joystick or a dataglove. It's similar to playing a computergame the normal way, which means that the human is pressing buttons and moves the mouse.

Artificial Intelligence is everything which goes beyond this minimum requirement. It can be a plan recognition system, a learning from demonstration framework or in the maximum degree it can be equal to an autonomous robot who can handle the task by it's own.

The steps on this path are unknown. And the technology to realize them too. Which means, it's unexplored land and the propability of failure is high. In most cases, an autonomous robot won't work. After starting the system with “run” nothing will happen, because something is wrong with the AI. This is a hint, that a major step from teleoperation to fully autonomy is missing. Engineers have to answer the question which step in between is needed. This missing step explains the reason of failure. I would give a rought outlook how the transition can be described in detail:

1. Teleoperation

1a: plan recognition

1b: hierarchical plan recognition with subactions

1c: learning from demonstration

1d: sketch based goal formulation

1e: plan creation and monitoring

2 Fully autonomous robot

The steps in between are not complete. It's only a general description what the missing steps are. Most failed robot projects can be located on the coordinate system between step 1. teleoperation and step 2 fully autonomy. The overall task is very similar to building a bridge. he left side (teleoperation) is well known. The technology in doing so is available out of the box. A dataglove, a microcontroller and a robothand is sold in most electronics store. The other side of the bridge (the autonomous robot) is not available. It is only a vision, known from movies. The question is what are the steps in between? How to connect the bridge?^

The reason why Teleoperation is equal to the baseline is because it's reproducable. If somebody has made a youtube in which a teleoperated robot manipulator is shown, it's obvious how to build such a system from scratch. It's mostly a hardware problem of connecting the joystick to the robot gripper and then the signals are transmitted over the wire. There is no magic but it's normal engineering.

IN contrast, if somebody has shown a self-working robot who doesn't need teleoperation it's a mystery. Because this technology wasn't invented yet. The engineer has invented something which is new. Such a system may be working or it doesn't work. The details have to figured out and perhaps the robot can't be reproduced.

The reason why there is a difference between teleoperation and fully autonomous robots is because in the first case, the data doesn't contain semantic information. Teleoperation works usually by transmitting raw signals from the input interface to the robotarm. That means, the joystick is pressed upward, and the robotarm is doing the same action. The problem is, that “upward” has no meaning. What is missing is a domain model in which a certain low level action make sense. A normal teleoperated robot doesn't have such a model and this is reason why each action has to controlled by a human in the loop. The human has the overall plan and he knows what the current task is. The challenge is to make parts or even all hidden knowledge of the human visible for the computer. This would allow to improve teleoperation into something better.

JSON Format

planlanguage = { 
"lowlevel action": "left",
"lowlevel action": "right",
"lowlevel action": "up",
"lowlevel action": "down",
"highlevel action": "open gripper",
"highlevel action": "close gripper",
"highlevel action": "walkto",
}

A convenient way for storing the plan language grammar is a json dictionary. Such a datastructure allows to crate a hierarchical string list. In the example only two layers are available and a small number of skills. In contrast to the PDDL format and in contrast to a BNF grammar, the json dictionary can be parsed in most programming languages easily.

The purpose of a json dictionary is, to restrict the allowed dataset which stores the game log. All the actions in the game log belong to the json dictionary. The actions of the human are stored with a predefined format in the log file. Somebody may argue, that a game-logfile and dictionary to parse the file itself are useless and he is right. Because it's not possible to control a robot with such a logfile. The purpose is to define a standard how a plan will look like. The overall system is a teleoperated system which is enhanced by a plan specification language and a logfile.

Plan recognition as the transition from teleoperation to autonomous robots

The main problem in robotics is, to extend a given teleoperating system to an autonomous system which is equal to lower the workload of the human operator. The baseline for highly complex tasks with a robot is teleoperation which means, that the human is using a joystick to control the gripper. Such technique is working great but is not very advanced. The more elaborated way in robot control would be a software which is working alone. One way in realizing such system is with the help of plan recognition.

Plan recognition means to formalize actions on a higher level. The simplest form of a plan is path through a maze. If a plan is already there it is much easier to solve the task. In most cases, the robot has only to follow the plan. In most situation the problem is not to generate a plan with a planner, but to realize a formal plan at all. Most domains like dexterous manipulation have the problem, that a formal description in a plan language is difficult. That means, it's not possible to give the system a predefined plan because the notation is unknown.

Let us introduce some plan notations. For a maze game, the plan is equal to a 2d trajectory. Which means it contains of points which are connected with edges. The plan is equal to a spline. In case of a pick&place scenario the plan is build with a plan library. Each node in the planning graph is equal to a skill for example “open gripper”.

If a robot is controlled with a teleoperating system the human user is executing a plan. He has a rough idea who to solve a task and the robot is used for executing the plan. The main challenge is to convert between plans and actions in reality. A given plan can be translated in control actions, and executed actions can be recognized as a plan.

Planning language

In the trivial case of a maze solving robot, the plan is equal to a 2d trajectory. It can be stored in a table in the form:

p1, p2, p3, p4, p5

The plan is that the robot moves across the waypoints. He drives from p1 to p2, then to p3 and so on. The more formal description includes the walkto action in the plan:

start, moveto p1, moveto p2, moveto p3, moveto p4, moveto p5

In more demanding domains like a manipulation task the plan is more complicated. Instead of following points the robot is doing something at each point in time. This requires a more elaborated plan description language. An example would be:

start, opengripper, moveto p1, graspobject o1, closegripper, moveto p2, end

Similar to a maze solving robot, the plan describes the single steps. But this time, the steps are more complicated than only a trajectory in the 2d space. Instead the actions are given by natural language instructions. The term “opengripper” describes a certain motion primitive which is executed by the robot's gripper. During executing the robot doesn't move to a different place, but he standsstill and is doing something with the hand.

I'd like to describe the minimum requirement for a plan recognition system. Such a system is not working autonomously, it can only monitor the execution of a human's plan. The teleoperated robot hand is trying to solve a pick&place task. The plan is known in advance. And the AI is monitoring if the human is following it's own plan. According to the plan, the first step is to open the gripper. Does the human operator doing so in reality? If not, then the AI can print out a warning message.