3a Programming robots with learning from demonstration

< 3 Artificial Intelligence

Before a robot can be programmed, there is a need to define what the problem is about. The problem is not to invent yet another programming language or speak to the robot on a hardware level. Also the problem is not about creating databases, or program a servo controller in the assembly language. All these topics are solved already and are getting analyzed by computer experts and programmers. But they are located outside of AI.

The AI side of a robot has to do with keyframe models for animation, defining a reward function and trace human actions with motion capture suits. These tools sound a bit uncommon because they have nothing to do with classical robots. They are located within AI and have to do with how to build future technology.

Learning from demonstration with Karel the robot

The programming game “Karel the robot” is a runtime engine to execute short scripts. The user can type in a list of commands the the robot will behave according to the statements. A sample program contains of:

right;

forward;

forward;

stop;

The dominant reason why Karel the robot is described in the literature is because it can be used for teaching programming skills. The first task is to program the robot simulator itself, and the second task is to create the script which gets executed in the simulator. Unfortunately, most tutorials doesn't provide further hints how to improve the setup. So it's up to the user to invent an additional challenge on top of the Karel game.

Let us imagine how to combine the technique “learning from demonstration” with “Karel the robot”. Learning from demonstration (LfD) works by defining skills which are stored together with precondition in a database. Learning means, that these skills are generated on the fly by user demonstration. The first task to do is, that the user is operating the Karel robot with a keyboard but not with a program. He is pressing the arrow keys and records a motion over a longer time. Then he demonstrates a second motion and so on.

The idea of LfD is to store the motion recordings in a database.


motion0={
precondition=(100,100),
action=[right, forward, forward, stop]
}

motion1={
precondition=(200,100),
action=[left, forward, stop]
}

motion2={
precondition=(100,200),
action=[forward, right, forward, stop]
}


In the playback phase the karel robot is located at the position (200,100) which fits to motion1 and then the actions from the skill are executed. Sound's pretty easy, isn't it? The idea is not to write a normal computer program which contains of loops and if statements but to create a database with recorded motions. If the database is large enough, every possible situation is provided in advance. The LfD playback engine has to search in the list of all cases and then the motion gets executed. Sometimes, Learning from demonstration is described as similar to case based reasoning because in both cases the database holds the information what to do next.

What is missing in the pipeline is a cost function. A cost function will allow the Karel robot to adapt to new situation more easily. If the robot collides with an obstacle, the cost function will detect it. The result is, that a trajectory from the database can be evaluated if it's useful or not. The planner is searching for a matching case and it's trying to reduce the costs.

A second option to improve the system is to combine create high level skills. Skill1 brings the robot to the middle of the map for different starting positions, while skill2 brings the robot from the middle to the exit of the map. If the script executes a skill not a concrete action is executed, but the skill is a database which contains of possible movements. These cases are searched on the fly.

Extending learning from demonstration into Reward learning from demonstration

The vanilla learning from demonstration idea is about recording the human's demonstration and replay the trajectory on the robot. For example, the human operator is executing a trajectory (100,10),(150,30),(150,80) and this waypoints are used for control the robot's arm.

The disadvantage is, that the connection between demonstration and replay is very static. One option to avoid the cons is to use the demonstration as an indirect pathway. In the literature the concept is called reward learning and the idea is to create a heatmap. The heatmap allows to find many different trajectories which are all bring the robot into the goal state.

A heatmap aka costmap is a visual representation of a learned cost function. The idea is that colors from green to red are shown as overlay picture over the normal map. The information which pixel becomes which color is given by the demonstration of the human operator. Bascially spoken, the human demonstration creates a path in the map, and the path is extended to a colored heatmap. A trajectory planner like RRT is used to find in this map a path.

Clicker training with dogs

In animal training there is a powerful technique available called clicker training. For the newbie the technique is hard to understand. The human trainer is using a noise making device, and feeds the dog with some cookies. After a while the dog is able to do lots of tricks. But how does it work from a technical perspective?

Teaching skills can be done in two forms: direct and indirect. Suppose the idea is to explain who to move from start to goal. This can be done in giving the direct command. At first, the dog has to walk 10 meter ahead, and then he has to go left for 5 meters. The problem with this method is, that the explanation can't be adapted to new situations. For example, if the pathway is blocked, it makes no sense to walk 10 meter ahead. So the question is how to give a tutorial which is more flexible?

Clicker training is working with a cost map. What the human trainer is doing with the noise making device is produce a cost map for the dog. He sets reward points on the map. A reward is a situation in which the dog gets a cookie. The dog labels the point on the map with the positive reward. In the replay mode, the dog is approaching all the +1 rewards on it's reward map and this will make the human trainer happy.

In case of spatial maps, it's not very complicated to imagine such a map. In abstract situation the map looks more complicated. For example, if the goal is not to reach a point in space, but to walk in a circle, it's an abstract behavior. If the dog is smart he can create the cost map for such abstract tasks as well.

Introduction into Learning from demonstration

I would like to introduce the topic with a small example, suppose an Artificial Intelligence should play Lemmings, because, quote “The game of Lemmings has been offered as a new Drosophila for AI research” [1] The naive approach would be to understand the Lemmings game as some kind of search problem in which the solver has to find the actions for winning the game. Because the state space is very large, this attempt will fail. To make things a bit shorter, the better alternative is to invent a plan language which will guide to search process. But let us go into the details.

A simple level of Lemmings in shown in the figure.

The entrance is on top in the middle and the lemmings must master the falling step, then a stopper has to be set on the right side, and the wall needs a digger before all the lemmings are allowed to go into the exit at the left bottom. The arrows in the map demonstrate what the solution is. The interesting point is, that these markers are equal to the walkthrough tutorial, that means, the level is already solved and the Lemmings has to follow only the guidance. Exactly this aspect is typical for learning from demonstration. Before the software gets started the walkthrough is available, which is formalized as a plan.

Learning from demonstration means in it's core to formalize a plan language. If the plan language exists a solver can calculate the subactions. Now let us imagine what will happen in a different Lemmings map. No plan is available and the Lemmings doesn't know what to do. The funny thing is, that the Artificial Intelligence is no longer forced to control the game in all details, but the only missing thing is a plan. The overall pipeline contains of two items: finding a plan for a map, using a plan for control the Lemmings.

The plan source can be human but it can be also a pathplanner which is working on a abstract level. Even if the human provides the plan, the system will work a bit autonomous. Because the human has to draw only the plan into the map and the system is doing the rest. From a certain standpoint this can be called cheating, because the AI only follows the walkthrough tutorial which is already there.

And exactly here comes “Learning from demonstration” into the game. The main principle is to invent a plan notation for a domain. This plan notation is used for recording and playback of demonstrations. The sad news is, that no standard is available for a plan language. It can be a graphical notation, a textbased langauge or a trajectory which is produced by Dynamic movement primitives. What is important to know, is that LfD is located between teleoperated robot and autonomous robot. The link between both consists of an abstract plan language.

Let us observe what a Lemmings AI is doing if the plan is known. The input for the system is the figure which contains the arrows. The plan is stored internally as a waypoint list which has some smaller annotation. For example the first step in the level is annotated with “parachute” while the second step is annotated with “stopper”. The AI Solver takes this plan and converts it into low level actions. It has to make sure that the plan is fulfilled. This is equal to a subgoal. For the solver, a subproblem is given which is only some seconds long and in which the general idea is provided by the plan. And the solver has to figure out only the detail adjustments to the plan. This can be done on a standard PC without much effort.

The funny thing is, that the same principle can be transfered to any game. No matter if it's called Sokoban, grasping robot, Lemmings or RC-Car control, in all these domains a plan notation is used as an intermediate between walkthrough-knowledge which is provided by humans and lowlevel solver which executes a plan.

Human guided teleoperation

The term “learning from demonstration” is a bit misleading because the association is, that some sort of machine learning algorithm takes place. The more exact terminology is to call such systems human guided teleoperation. Teleoperation means, that in the basic setup a human operator controls the robot with a joystick. Plan guided teleoperation is equal to replace the joystick with a plan notation which allows to control the system from an abstract level. In both cases the knowledge how to solve a robot problem comes from the outside. Either by direct human commands, or from an abstract plan provided also by a human.

The overall system doesn't have much in common with a classical AI planner, but it's more a human-to-robot interface. The plan notation is similar to a joystick an input device which transmits the human knowledge into machine readable information.

[1] Kendall, Graham, and Kristian Spoerer. "Scripting the game of Lemmings with a genetic algorithm." Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753). Vol. 1. IEEE, 2004.

The essence of Learning from demonstration

In the literature Learning from demonstration is not precisely defined. Instead a mixture of Dynamic movement primitives, Reinforcement learning and direct manipulation of robotgrippers are presented under this term. The first step is the define what LfD means at it's core. The basic idea can be summarized as “plan following”. A plan is feed into the system in a high level language. One option (but not the only one) is to create a plan by teaching. That means, the human moves the robot gripper to a goal. But the plan can created with a textinterface as well.

Let us go a step backward and start with a system which is more easier to describe. A teleoperated robot lacks of any kind of AI. Instead the system is controlled with a joystick but it can't do something autonomously. To improve the system, a plan formalization is needed. That is a plan language and a concrete plan in that language. All learning from demonstration systems are based on a plan. Possible way in doing so are natural language vocabulary, waypoint trajectories, photographed keyframes or a function in the state space. The idea of a plan is to reduce the state space, it explains to the robot what to do next.

Learning from demonstration means usually to track a plan, to think about the plan language, to replay a given plan autonomously and to annotate a demonstration with plan elements. The most simple form of a plan notation is a waypoint list for example (100,100), (100,150), (200,100). The plan is equal to an abstract description for solving a task. That means, the AI isn't able to find the solution by it's own, instead the robot has a walkthrough tutorial and executes it.

The open question is, how exactly a plan language should be. In the given example, the plan language is a simple point list. But more demanding tasks like grasping will need a more elaborated formalization which goes into the direction of a domain specific language. Somebody may argue, that a plan is fixed and isn't flexible enough. That is correct, Learning from demonstration is restricted to a concrete domain. If the situation is changing the plan will become useless. But that is not a problem, because the idea is that a robot can do a narrow AI task like open a bottle which is always the same.

Plan recognition for a line following robot

Most line following robot competitions are created with autonomy as a goal. The idea is, that after pressing the run button, the robot will drive by it's own along the line on the ground. The more interesting way in fulfill the challenge is to let a human operator control the robot and track if he is able to follow the line. That means, there is a line given and the operator has to move along the line. Does this has to do with robotics at all? Yes, because it's a plan recognition challenge. The plan is given by the line and the system has to track if the human operator fulfills the plan or not.

Such a systems starts with the assumption, that no robot control system at all is available but the teleoperation mode is the only available technology. On top of a working teleoperation controller an activity tracker / plan recognition system is put on top with the aim to improve the overall software. The idea is, that the transition from a teleoperated system into a fully autonomous one contains of many steps in between and the quest is to explore them slowly.

From a formal persective the line of the ground is equal to a lan. It explains to the robot and to the human what the goal is. The plan is equal to a 2d trajectory. It's a spline which goes through different waypoints. The robot can move on the line of outside the line.