Transition from teleoperation towards Object Action Complexes

The most powerful robot can be realized with teleoperation. Teleoperation means, that the robot is equipped with human level skills and can adapt to any situation. A pick&place with a teleoperated robot arm works perfect. The most interesting feature of remote control is, that no program is needed. The only piece of software transmits the joystick signals to the robot, but the robot movements itself are not determined by a program.

Suppose the idea is to program a robot which means, that the steering signal is not generated in realtime by a human but from a macro, script or any other robot program. The resulting question is which kind of software is needed for controlling the robot? In the easiest case a robot program is a list of points which are forming a trajectory. In the python language a typical robot program looks like the following example:


moveto(250,200)
time.sleep(1)
moveto(60,210)
time.sleep(1)
moveto(50,325)
time.sleep(1)


The robot program looks different from normal Python sourcecode, it has more in common with a list of absolute values which are executed by the robot. Will this program work? Oh yes it works great, the movements are executed precisely. The more complicated question is, if the robot movements are useful for the environment. That means, in a real life application an industrial robot is asked to do a task, for example to pick&place an object. The robot can fulfill the task or not.

The same robot program can become a failed robot project or a successful robot project. It depends on the task. If the task is easy the given robot trajectory will solve the problem. But if the environment changes to much, the trajectory of the robot doesn't make sense and it won't be able to pick&place any objects.

The overall successrate of the robot project depends on two factory. The robot program and the task description. The combination of a simple repetitive task and a simple robot program is a great choice. The problem is, if the task description is complicated but the robot program is an easy one. The result is a failed robot program.

Let us take a look into real applications. A welding robot is a typical example of an easy task description plus an easy robot program. The task for the robot is, to move the endeffector precisely along a list of points. The trajectory is always the same, and not kind of planning is needed. Such a task can be realized with the mentioned robot program which contains of two simple actions: moveto and time.sleep. The problems will upraise if the task description is more complicated. For example, if the robot should pick&place objects, but the objects can have a different location. In such a case, the easy fixed trajectory of the robot won't be succesful anymore. There are two options available to overcome the issue: first reduce the task description into something more easier or secondly, increase the complexity of the robot program.

A slightly more advanced form of creating a robot program is working with Object action complexes. This technique is derived from the STRIPS notation. The idea is not only provide a list of points, but provide a list of actions which can have preconditions and postconditions. Such motion primitives can be reordered so that the robot isn't executing a fixed trajectory, but is able to create different plans. The good news is, that the STRIPS notation can be used to generate a fixed trajectory as well.

Symbolic Planning is equal to GOFAI

The term classical AI and symbolic AI is often used to describe a certain period in AI research, mostly before the advent of neural networks and behavior based robotics. This kind of understanding summarizes all efforts in the early years under the same description. But at the same time is leaves out what the word “symbolic” means.

I've investigated the problem in the literature and found that symbolic AI is equal to symbolic planning..And this is equal to high level planning in which the STRIPS language is the most important tool. As a result, GOFAI is not over but it's state of the art AI if the focus is on the higher leyer of a robot control system.

After this theoretical introduction it make sense to give some details for symbolic planning. Suppose there is a game of robocup which is played by a robot swarm. On the bottom side there is the need of low level control and low level sensor interpretation. This kind of tasks is ignored in the following description. Instead the more interesting aspect of the problem is to control the robots on a higher level. Which means to plan the general strategy and long term tasks. Before symbolic AI can be formlized some kind of abstract simulation is needed. This is a simplified robocup simulation in which all the details are missing. It doesn't work with a physics engine, but with a symbolic engine. In most cases the game will look like an early Commodore 64 which contains of low resolution graphics or the extreme case no graphics at all, but a textual menu in which the player can play soccer.

On the first look this kind of simulation is step backward, because it doesn't contains a colorful highly realistic simulation. Instead the game is played on a 10x8 pixel map and the movements of the ball are abstract. The advantage is, this kind of simulations are easily to play autonomously by an AI. The state space is reduced and the allowed actions are working on a higher level. The advantage is, that the computational requirements are low.

Atari 2600 games

A less powerful computer than the Commodore 64 was the Atari 2600 device. It has a maximum resolution of 160x192 pixels but many games are using a smaller resolution. The amount of colors was small and the RAM was 128 bytes. For today's eyes the games on the Atari 2600 are equal to a joke. They doesn't have interesting sound, they are not using 3d graphics, and the movements are unrealistic and slow. What all the games from this area have in common is a low state space. If the map is limited, the amount of possible paths is reduced too. This is equal to a symbolic game.

If the goal is to simplify the game more, the next lower step would be avoid any kind of graphics, and create games in the textmode which are using at maximum only 80 Bytes. According to a fan forum there were few text adventures released, for example “Dark Mage” Another game is “STELLAR TRACK” which was rated by the gamers as poor. The user has to control a spaceship. In detail he sets the maximum warp speed and the feedback is shown on the screen textual.

For explaining what symbolic AI is, the “Stallar Track” game is ideal. It contains of a map which is 8x8 pixel large, everything is in textmode and the overall game is very limited. That means, the player can choose between a small number of actions and after a short period the game gets boring. The advantage is, this sort of domains can be easily simulated and solved by an AI player. He can use a fixed strategy or try to test out alternatives with monte carlo tree search. We can summarize, that symbolic AI has to do with a certain sort of game engine which is a very reduced one. The game engines uses not more than 100 bytes of RAM and the output is given in textual screens.

Turn based strategy games

Before the advent of Real time strategy games, there was a period in computer gaming history which were devoted to turn based strategy games. A notable example is Oil Imperium. It's major feature is, that the gameplay is very slow. The amount of decision to take are working on a high level. The player can relax while the other player takes a move.

This sort of games has felt out of fashion but they are important from the perspective of Artificial Intelligence. Even modern real time strategy games have a high level component which needs only a small amount of decisions. For example the question, if the user likes to build 10 houses or 30 housing. Most games can be split into a low level layer and a high level layer.

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.

What is symbolic AI?

In the history of AI the well known General problem solver was the first example for an abstract planning system. Later examples were STRIPS and a modern version is called GOAP (goal oriented action planning). What these systems have in common is that they are using rules to solve a problem. A rule is part of a simulation, very similar to what a player activates in a textadventure to reach a goal.

The difference between rules and normal functions in a c program is, that the order of rules isn't fixed. It's the task of the solver to determine the sequence by it's own. This provides a higher flexibility. The simulation can start at a initstate and can be transfered into a goal state. Very similar to what a classcal pathplanner is doing, except that the world isn't a 100x100 pixel map but the state space contains of abstract actions like “take key”, “walkto location” and “open door”.

To get an idea how to use symbolic AI in the reality, a new environment was published in the year 2018 by Microsoft Research called Textworld. https://www.microsoft.com/en-us/research/project/textworld/ It is a textadventure and a solver in the same program. The textadventure simulates a world in which the player can do tasks which have to be entered on the command line. The solver is able to determine the actions autonomously to reach any state in the simulation.

The reason why robotics can profit from this idea is because the state space of a textadventure is much smaller than the geometrical statespace. The amount of possible goals and actions in a symbolic simulation is not very great. A graph search solver will find the actions very fast. The interesting aspect is, that GOAP like solvers doesn't need a certain framework, nor a dedicated STRIPS like programming language. The more important aspect is, to convert a domain into a textadventure. This is the most harder part.

In the famous monkey banana problem the domain contains of only 3 actions and 2 objects. In a robotics domain, the amount of actions is higher. The AI engine for a computergame will need hundred of rules and a dozens of subgoals. This programming task can be handled with the normal software engineering paradigm. That means with the help of UML diagrams, git version control and bugtesting. Or let me explain it from the other perspective. The question is how does a textadventure look like which is about a self-driving car, a biped robot, a Lemmings playing AI or a Mario AI bot? If somebody has answered these question he gets a fully working AI which is planning very fast. Sometimes the concept is called “Task and motion planning”. Task planning is referencing to symbolic AI planning which is equal to GOAP, STRIPS and GPS. Motion planning is the lowlevel side which includes inverse kinematics and pathplanning in a map. The more important part is the task planner, or to be more specific, the textadventure in which possible tasks are formalized.

Text adventure solver

The fascinating information about text adventures is, that they can be solved relative easily automatically. In contrast to a normal computer the amount of possible actions is not billions but only a few thousands. The famous blocksworld example in which a robot arm has to pick and place boxes can be interpreted as a textadventure as well. The robot has certain commands like grasp, ungrasp, moveto and the goal is to find the correct action sequence. It's some kind of puzzle game which can be solved with a graph search algorithm in under a minute.

Unfortunately, most games are not available as a textadventure. For example, Mario AI, Lemmings, or Starcraft are working with graphics but not with text and the available actions are unknown. To overcome the bottleneck one idea is to monitor an existing textadventure if it's fit to a game. That means, the Mario AI original game plus the Mario AI textadventure are started at the same time and the question is, if both instances are in the same state. If not, the textadventure version has to be modified.

Simulation

The Situation calculus is the theoretical background behind the STRIPS planning language. It describes a world which contains of a world state which has actions to change the state. Running such simulation is called a qualitative simulation because it's not based on numerical values but on natural language. For example, if the player types in “open door”, the string of the door variable gets changed into “door is open”. It's important to understand, that a qualitative model isn't an algorithm but it's a text adventure. It forms an environment in which a human player can execute actions and observe the resulting game state. An algorithm is needed only on top of the simulation to bring the system into a goal state.

In the history of AI many techniques were developed to realize a qualitive simulation. One example are the planning languages which are ADL, STRIPS, Golog or PDDL. Another attempt are XML based models and the latest innovation are RDF-triple storage and General description languages. All of these techniques are trying to build a textadventure as easy as possible.

Again, GOAP architecture explained

Goal oriented action planning is basically an explanation how to implement the STRIPS planner in a computer game. The first step is to create a table with actions:

name, precondition, postcondition, costs

The table gets filled with actions like “walktolocation”, “getupobject”, “opendoor”. The table can be seen as an abstract textadvanture, in which the robot can execute actions which brings the system into a new state. If the textadventure contains some possible actions, it's possible to start the simulation with an inputstate for example “robot is in the middle” and a goal state “robot is at the exit”. And now, the planner calculates the steps in between. The solver works with a graph search algorithm, similar to a pathplanner but only for symbolic actions.

And now comes the funny part, what will happen if an action like “walktolocation” should be executed? Right, the details are not stored in the table. The action name has to send to the physics engine in the game. That means, the game has the same table which is enriched with the details how to execute an action. In most cases, it is realized with normal computer code. That means, in the game engine there is a method called “walktolocation”, and this method contains of some statements.

Explaining the difference between GOAP and STRIPS is a bit difficult. From a technical perspective it's the same. I would go a step further and call GOAL a slim down version of STRIPS. That means, it's a step backward. The advantage of GOAP over STRIPS is, that the surrounding documentation is easier to read. All the philosophical and mathematical parts of the STRIPS project are missing, and GOAP is some kind of tutorial how to realize a non player character for a game. It's not an algorithm nor a framework and be programmed with any language like Python or C++. GOAP is some kind of documentation how to create a symbolic planner from scratch. The tutorial explains, that the first thing which is needed is a table which contains of actions, also the precondition/costs and postconditions are stored in the table. And then a planner figures out the next steps for the robot. GOAP can be seen as software engineering pattern for creating a simple planning robot.

No Algorithm available

Computer programmers are trained to search for a library, an algorithm or a framework which can solve a task. Unfortunately, GOAP isn't an algorithm and even some example sourcecode is available at github it makes no sense to use this code in the own project. The inner working of GOAP is to create a textadventure around a given problem. That means, it won't solve an issue but it will make things more complicated. GOAP can be described as an abstract game engine which is traversed by a solver. It is not located within the domain of computer science and algorithm theory, but has to do with software engineering.

Let us observe how existing GOAP solvers were created in the past. In all cases, the programmers are using an existing programming language like C# or Python and build their own GOAP datastructure. Then, the table is filled with actions from the domain. The problem is, that the process of doing so is highly individual and can't be reproduced very well. What we can for sure is, that an object-oriented programming language was used and that the GOAP framework fits into the normal version control contributions which are made with the git tool. The programming of a GOAP solver is motivated by the requirements to program a non player character which has a certain feature set. And the understanding of the AI programmer how to realize such features in software.

It's interesting to know, that GOAP was first described by practical game developers. Perhaps one reason is, that it can't be formalized in algorithmic notation and can't be described with mathematical terms. I would located GOAP next to software engineering discipline which is a highly individual discplines which is dominated by personal stories from real projects. It makes sense to explain how a certain game was upgraded with a goap solver, and it make sense to summarize different software projects in comparison. But the attempt of explaining GOAP from a theoretical perspective will fail.

Text adventure generator

A GOAP model is equal to a text adventure. Producing such models can be realized with a text adventure generator. This is a piece of software which is producing a game. In the game, it's possible to do actions like “opendoor” or “walktolocation”. The textadventure which is the GOAP model will figure out what happens next. The advantage of a textadventure is, that a solver can determine the needed actions easily because the overall state space is small. It can be converted into a graph and the solver will take under a second to find complex action sequences.

The open problem is how to convert a normal game into a textadventure. The term textadventure generator implies that the process can be done autonomously, but in reality most GOAP models are created in a software engineering process by human programmers. They take a look at the game and write for the game a text interface. This results into the agent architecture which can solve the game autonomously.

Is there a need for an alternative to SOAR?

The cognitive architecture SOAR is a well known and intensively documented framework for creating Artificial Intelligence agents which contains lots of interesting features like subgoaling, chunking and graph based working memory. But something is wrong with SOAR, which prevents that the software can be recommended for serious application. It has mainly to do with the documentation which are formulated always in the “you can do something”, and “you have to click this button” and so on. This kind of language works similar to the promotional language used in advertisement campaign, in which the new car is simply great, and and all what the user has to do is to get excited.

From an academic standpoint, this kind of description doesn't fulfill the minimum standard, which means, that the SOAR documentation can't be called scientific, but it's a waste of time reading it. Sure, SOAR itself is great, it combines most of the advanced features which are available for modern agent architectures but it's possible to make the overall system much better.

Which means, there is a need to invent things from scratch and built a new cognitive architecture from scratch which is less powerful than SOAR, but provides a better self-description what the project is about. The first step in doing so is to explain what the idea behind SOAR is. In contrast to normal solver, which is searching in the gametree for a goal node SOAR is working with heuristics. That means, the requirement for CPU ressources is low and no high computational task is needed to solve a problem. Everthing in the SOAR universe works reactive and with human engineered knowledge. The concept is sometimes called symbolic AI because no number crunching is involved in the game.

A first approach to understand SOAR better is to compare it with a STRIPS planner. A strips planner contains of actions which can be executed by the solver, and the precondition/postcondition for each action is given in the strips file. A cognitive architecture is some kind of advanced strips planner which has the ability to access a working memory and to learn new goals on the fly.

The Strips notation is a good starting point for developing a cognitive architecture from scratch, because the concept is described in mainstream Gaming AI and it's not very complicated to grasp the basic idea. The game starts with an init state, the solver is trying to find a sequence of actions, and this will guide the robot to the game.

In a paper [1] a mixture was described between a classical HTN planner and a memory architecture. The resulting architecture isn't so powerful like SOAR, bit explains more easier to understand what the idea is. It starts with a vanilla HTN planner for figuring out the actions for the robot. Before the planning process gets started, some operations on the internal memory have to be done. The paper admits, that it has reverse engineered the SOAR architecture, and the similarity is there. Exactly this approach makes sense, because this kind of inventing something twice is equal to learn something. If somebody isn't able to clone a software, he hasn't understand it.

HTN planning plus short term memory

The idea of combining HTN planning with a memory was also discussed in another paper.[2] It describes a non player character in a game, which doesn't have full information about the game, but sees only a limited amount of information which are stored in the short term memory. Similar to the previous referenced paper, the systems starts with a normal HTN planner for generating actions which is extended by additional components like a subgoal generator and a short term memory.

It's interesting to know, that the concept of a working memory plus subgoaling is described as well in the SOAR context as in Game AI non player characters as well. It seems, that life-like characters in games have a natural demand for a working memory and for hierarchical planning capabilities.

Let us imagine, how a non player character can be created which is more flexible. The first thing to do is to realize the working memory not as a normal datastructure but as a semantic network. All kind of variables can be stored there and nodes inbetween the items are possible, similar to a linked list. The second thing to do is to add a learning functionality. Which is a decision tree ID3 learning algorithm. This allows the non player character to adapt his behavior in realtime.`

[1] Zhang, Jun, et al. "MBHP: A memory-based method on robot planning under uncertainties." 2011 IEEE International Conference on Robotics and Biomimetics. IEEE, 2011.

[2] Mahmoud, Ibrahim M., et al. "Believable NPCs in serious games: HTN planning approach based on visual perception." 2014 IEEE Conference on Computational Intelligence and Games. IEEE, 2014.

Short description of symbolic AI in the 1960s

The General Problem solver and the Logic Theorist program was both realized in the late 1950s on mainframe computers. It was an early attempt in realizing a production systems. Later examples from the same subject were OPS5 (late 1970s) and SOAR (early 1980). A production system has much in common with STRIPS and PDDL planning tools. The idea is to formalize a problem into abstract actions which are planned by a solver. Sometimes, the planning process is supported by a goal stack and (Strips) and a working memory which is common for cognitive architectures for agent simulation.

The reason why the General Problem Solver and modern PDDL planners doesn't match the requirements into Artificial Intelligence is, because the planner/solver itself is useless, if the domain model is not available. All the capabilities which are provided by the STRIPS planner which includes the recursive goal stack will not solve a problem, if the strips input file is missing.

A production system is similar to an expert shell only the environment which is able to find the actions for a given STRIPS file, but it can't answer the question how to transform a domain into the strips file. Before it's possible to start the SOAR program, execute the PDDL solver or taking advantage of the OPS5 system an input file has to provided which contains of the action names, the variable names and the effects written down in a programming language. Even a modern cognitive architecture has the ability to learn, it's not so powerful that it can learn the domain description itself.

Let us analyze the simplest possible cognitive architecture which is a strips planner. Strips takes a domain description as input, creates a graph, and then it will search for a path through the symbolic graph. Programming a strips solver from scratch isn't very hard, because the algorithm for backtracking a graph is well known and the sourcecode is available at Rosettacode. The more demanding problem is how to convert a problem for example a game of Lemmings into a STRIPS domain description. This transformation is called grounding and STRIPS nor General Problem solver has the answer to the problem.

STRIPS domain file

Every STRIPS like planner needs as input file a domain description. This is equal to a domain specific language (Formalized as a grammar) plus some routines written in that language. In the well known robot gripper domain (blocksworld) the grammar is equal to a robot programming language. It contains of commands like opengripper, closegripper and movedown. The STRIPS planner is able to transform the language specification into a program. It's some kind of automatic programming aka genetic programming. The program can be executed on the robot which brings the system into a goal state.

“Learning from demonstration” allows acquire a robot language from human interaction.[1]

[1] Mohan, Shiwali, et al. "Learning grounded language through situated interactive instruction." 2012 AAAI Fall Symposium Series. 2012.

Natural language interface for solving the frame-problem with a layered game-engine

Title: Natural language interface for solving the frame-problem with a layered game-engine

Author: Manuel Rodriguez

Date: 13. June 2018

Abstract: A planning algorithm like A* and RRT works only efficient for small problem spaces. Most robotics problems have a huge problem space. The answer to the mismatch is a domain model which is enriched with heuristics. In the early history of AI this problem is discussed under the term “frame problem” and means to describe the action model in a object-oriented programming language. For the example of an textadventure and the parking with a car, a game-engine is presented which is using natural language commands for storing domain specific knowledge.

Table of Contents

1 AI Planning
1.1 Knowledge based planning
1.2 The GIVE challenge
1.3 Automatic creating of a pddl file
1.4 Theorem proving for beginners
1.5 Storing domain knowledge in a game-engine
1.6 Plan stack in HTN-planning
1.7 Building a simulator for HTN-planning
1.8 Combining autonomous and remote-control
2 Example
2.1 HTN Planner
2.2 Car physics
References

1 AI Planning

Mindmap

1.1 Knowledge based planning

Artificial Intelligence in simple games like chess and more complex robotics domains can be realized with AI-planning:

“Planning is the most generic AI technique to generate intelligent behaviour for virtual actors.“ [8]

How a planning system looks like for a chess-like game is already known. It is a brute-force search technique in the game-tree. More complex games can be planned too, but the algorithm is more complicated. A combination of a hierarchical planning system together with machine-readable knowledge representation is the standard procedure. It means to store the game on different layers in a formal model so that it can be searched in real time. Well known forms of storing knowledge are STRIPS and PDDL. Both are languages for formulating a symbolic game engine. They are used for the high-level-layer of a planning domain.

But let us go a step backwards. The only known algorithm for solving a planning task is a search in the game tree. The algorithm is called A* or in newer literature RRT. RRT alone is not able to solve complex tasks, it must be implemented on different layers at the same time. The layers are depended from the game, they are representing the domain specific knowledge.

The bottleneck is, that for most games, no machine readable domain description is available. For example in a pick&place task for a robot, it is unknown how the story looks like and what the outcome of an action is. The programmer is not searching for a solving-strategy, instead he is searching for the game. That means, he must enrich the given game with detailed rules. Only these rules can be solved by the planner.

[12] calls the process “domain knowledge engineering” and describes a software (GIPO) which makes it easier to create a planning game from scratch. On page 4 an example is given. The original game is the “docker worker robot” and the programmer must define potential states of the robot like “load”, “unload”, “at-base”, “busy” and so forth to enrich the game with knowledge. The result is a pddl file which can be used in a planning task.

LfD & HTN

A human operator has an implicit domain model, he knows that before he can grasp an object, first the gripper has to be opened. This domain model is not available in sourcecode and has to be programmed first. To overcome the gap the "learning from demonstration" is the right choice for constructing a "hierarchical task network" from scratch.[3] [6] The human operator has a GUI in which he records a manual motion, and from this demonstration a machine readable ontology is created. This task model can be used by the HTN-planner for handling the task autonomously.

The aim is to transfer the knowledge from the human operator to the agent. The knowledge is similar to a walk through tutorial for games. It is a description of how to play a certain game. In a hierarchical task network the knowledge is formalized like a symbolic game engine. That is a software-modul which can predict future game states, e.g. robot-grasp-object -> object-isin-hand Usually the description is based on natural language. Instead of using simple variables in the gameengine like:

bool a,b,c

int d,e,f

the variables have sounding names like “bool object-isin-hand true/false” or “int distance-between-object-and-gripper”. The reason is, that the domain model is not primarily programmed for a machine but as help for the software-engineering-process. Creating a domain model is not a mathematical algorithm like A* but a software-engineering-task like UML and agile development. The result of this step is not a PDDL file or executable code, it is a human-readable paper which is called the specification of the game. The algorithm doesn't learn by itself the game, instead a version control system like git is used to bring the domain model to the next version.

Grounding means to combine tracking control with natural language.[9] The idea is not only to describe a task with “subtask1”, “subtask2” and so on, but with the correct words e.g. “heating the water”, “fill the cup”. It is not possible to describe a domain without using natural language. From a machine perspective perhaps, because all the words have no meaning for the computer, they are only labels. But for maintaining a task model by human engineers they need natural language. That means, a task model is foremost a dictionary and not a mathematical algorithm.

Language model

Under the assumption that every task model is based on natural language the question to investigate is how does the language model will look like for a certain domain? The GIVE challenge is trying to answer this by generating natural language instructions to guide a human for doing a task.[2] The idea is, that on the first hand, a dictionary is coded in computercode and can be executed like a game-engine, and the output of the engine is used to solve a task.

Perhaps an example will make the point clear. In [7, page 6] is on top of the page the map of a game visible. It is a normal maze game, in which the player moves around and can press button. Below the image the pddl description is given, which can be seen as a natural language game engine. It provides commands like “move”, “turn-left” and “manipulate-button”. The pddl description contains of two important aspects:

• natural language words, for example “turn-left” instead of a   simple “action2”

• state-action-pairs, that means by activating an action, the   system is in a new state

The overall system can be seen as a living dictionary. It contains one the first hand, words and action-names, and they can be executed by the user which brings the system to a new state. The pddl file contains knowledge about the domain.

1.2 The GIVE challenge

The term “Generating Instructions in Virtual Environments” (GIVE) is used for describing a programming challenge with the aim to generate natural language for a domain.[5] The output itself is usually produced by a PDDL solver, that means for a given current / goal pair the solver is trying to find a plan through the domain. The solver needs as a precondition the PDDL domain model.

A more colloquial description of the challenge is to compare it with a textadventure game which is enriched by a 3d map on top of the GUI. It is comparable to the early Point&click adventures in the 1990s in which the human-operator has some actions like “go north”, and must reach a certain point in the map while is doing subtasks. The interesting aspect in the GIVE-challenge is, that from a graphical point of view, everything is minimalist instead the idea is the task model and it's potential application to Artificial Intelligence. Another important aspect in the challenge is, that natural language is in the center of focus. That means, the idea is not only to play a game by an agent, but instead the idea is to generate natural language which guides a human who is already capable of understanding English.

From a programming point of view, the GIVE challenge is one of easier tasks. It needs less energy to solve the challenge compared with Starcraft AI or Robocup. The task is not so easy as programming a normal 2d computer game, but it can be mastered by beginners in AI.

1.3 Automatic creating of a pddl file

A domain model consists of natural language. From a technical side, the domain model is stored in a symbolic planning language like PDDL, OPL or ABPL. The first one (PDDL) is a classical language, while the second others have object-oriented features. The easiest way for creating a domain model is program the domain-description by hand. It is the same technique like a textadventure is created. A more sophisticated idea is to create the language model automatically from event logs.[13]

The idea is to record all the event in a section called “agent memory” and then construct out of the relationships the pddl / ABPL description. That means, at the beginning the agent has no domain model, he has to build one from scratch while he gets new experiences. In the literature the term “action model learning” is used. An action model is a symbolic game-engine which can be stored in a PDDL file.

Instead of explaining how to realize such a system, at first we must describe how to evaluate an action model. At first, we need a working symbolic game engine, for example an instance of an textadventure. This game-engine produces a stream of natural language. The user can input text, and the dialogue system gives feedback also in natural language. On the right screen there is an empty prototype. The prototype has the obligation to emulate the working game-engine. That means, the prototype observers the events, stores everything and after a while he is acting in the same way. The goal is to reverse engineer a symbolic game-engine.

1.4 Theorem proving for beginners

In the early history of Artificial Intelligence, theorem proving played an important role. In the context of the STRIPS planning system, such systems were capable to prove mathematical questions. But what is theorem proving exactly? Why it is so hard?

Theorem proving means basically to create a puzzle, for example Rubik's cube, and search for a sequence. The cube has a starting pattern, certain operations are possible and the goal is to bring the system into a goal situation. For example, make all sides clear, or bring only one side into a healthy condition.

Mathematical theorem proving works with the same idea in mind. There is a starting equation, a number of allowed operations and a goal situation. Like in the Rubik's cube example the idea is to search for plan, if such a sequence was found, the theorem was proven. In reality, theorem proving is equal to game-playing. A game is system which has allowed moves and it is up to the player to decide which moves he want's to execute. Automatically theorem proving works surprisingly simple. The so called SAT solver is using brute-force-search and that's all. If the problem is small like in the rubik's cube example, the STRIPS program is successful, in much higher state-space for example “a theorem prover for chess” is much more difficult to realize, because the number of possible plans is higher.

In the historic paper [4] of 1971, Nilsson introduces the so called “frame problem”. This means basically, that the STRIPS language is only a simple planning language and has no object-oriented feature for describing more complex problems. More recent planning languages like “A Better Planning Language” (ABPL) can overcome the frame problem.

Example

From school mathematics there are equations known plus rules which can used onto these equations:

a+4=7

a+4=7 |-4

a=7-4

a=3

The starting situation was an equation, and we have applied an operator to it. After the action, the equation is in a new condition. In the example, we selected the action manually, but it is also possible to formulate the problem in the STRIPS language. Such feature is integrated in most computer-algebra systems. The so called solver is playing around with the equation to fulfill a certain condition.

The “frame problem”

With STRIPS is a powerful planning language available for proving any theorem. The problem is now: how to formulate a robotics-problem in the STRIPS syntax? The question is discussed in the literature as the frame problem, because the assumption is, that frame based aka object-oriented programming is part of the solution.

A more precise formulation of the problem is given under the term “General game playing”. The challenge is here to invent a game from scratch. That means, as input the system gets a plan trace of checkers, or a textadvanture, and the system is able to construct all the game-rules and codes them into the Game description language. The sad news is, that until now “General game playing” didn't work very well. It is not possible to construct real games from scratch. But that is not a real bottleneck, because it is always possible to manually program in Strips, GDL or any other language. It is not necessary to use automatic programming for realizing a robot. 

In reality, the frame problem is equal to a software-crisis. That describes a situation in which a demand for software is there but no sourcecode is available because of many reasons. The software crisis in the area of operating systems was solved with Open Source software, and the software crisis for the special domain of game-playing and planning languages will be solved with Open Science. For example, if programmer A describes in a paper an UML chart, a ontology and executable code for implementing a pick&place robot, than programmer B is able to reproduce the result and use this as a basis for a more sophisticated system.

The frame problem, the grounding problem and the general game playing challenge can all be solved with a better science communication which works manually and is working with Open Access papers and Open Source software.

1.5 Storing domain knowledge in a game-engine

Domain knowledge has to be stored in machine readable form. Most literature questioned how exactly the data-storage should be, for example in the PDDL format, in ontologies or in semantic networks. More important is the question how the result will look like if the domain knowledge is available. It will look like the game-engine of a textadventure. That means, it is possible to send a command to the engine, and the engine will output the future state.

A symbolic game engine which is controlled by natural language is able to predict future states. For example, a command like “grasp apple” results into the output “apple is in hand”. This logical reasoning has to implemented in a part of the software called game engine. A game engine can be programmed in a textadventure markup language, in Javascript and even with ontologies. In the easiest form a textadventure is programmed in Python with object-oriented feature. But in general it is only a minor problem, more important is the information that domain knowledge and a working game-engine is equal.

Let us describe what in the so called ICAPS conference is usually done. In most cases a domain like Blocksworld is converted into a pddl description. But that is not what the inner goal is. The more precise description is, that a textadventure for the blocksworld domain was created, and apart from PDDL this can be done in any other programming language. At the end, a game-engine must be implemented which can be filled with user commands.

But why is a textadventure so important, isn't it possible to write a normal game-engine with a graphical interface? The terms grounding means to connect natural language with actions. Grounding means, that the engine can parse a command like “grasp apple”. Every grounding results into a textadventure, because a textadventure is about the understanding of natural language. The only open question is, how to program such adventure for a certain domain.

Existing textadventure which were programmed since the 1980s contains domain knowledge in a machine readable form. They have a clean interface, it is possible to send a request to it, and the game-engine calculates the follow state. A textadventure can be seen as the inner core of a working robot control system. It is the part in which the domain knowledge is stored.

In the context of Artificial Intelligence the general name for domain knowledge which is stored in a textadventure is “dialogue system”. Dialogue system like TRAINS and FrOz are usually programmed to support the human player. They have a planning feature out of the box, that means, the engine was programmed with the goal to find a path through it by a solver.[1]

1.6 Plan stack in HTN-planning

[10] describes on page 8 the plan-stack of a HTN-planning system. A so called plan stack is a list of high-level commands:

1. task1

2. task2

3. task3

and so forth. The term “stack” is correct but it is a bit misleading, because the datastructure of storing a plan is not very important. Any other data structure for example a SQL-table, a csv-file and so on would also work great. The more important aspect is, that before building the plan stack the programmer needs to know the name of the tasks. In the cited example, the tasks are having to do with the soccer domain. Their names represents elements of the soccer game, for example, “pass-the-ball” or “shoot”. The knowledge is not stored in the HTN-planner directly, but in the domain-model which is used by the HTN-planner.

I would guess that the stack and the HTN-solver are the least important part of the AI-system. That means, to store a list of task-names in a computer-memory is a trivial programming task and can be implemented easily. The bottleneck in Hierarchical task networks is somewhere else. Like i mentioned above it is the domain-model. In general we can say, that the domain model is equal to a high-level game-engine. It is some kind of textadventure. The user has commands which he can send to the game-engine and the engine is executing them. The game-engine has the obligation to predict future game-states. That means, after the command “pass-the-ball”, the game engine changes the position of the ball to the receiver of the ball.

Basically spoken, the domain-model of a HTN-planner is equal to a computergame. Because of it's high-level-nature it is often realized as a textadventure but can have additional graphics to visualize the internal states. Let us go into the details for the Robocup case. A game for playing Robocup can be programmed on many levels. At first it is possible to play the game physical with real robots, while in the 3D Simulation league only a physics engine is used. In the 2D Simulation a different kind of physics engine (perhaps a 2d one) is in the loop, and it is also possible to simplify the engine further to a more abstract domain model, which is working without a realistic engine but only with a idealized physics engine.

For example, it is possible to use the SFML graphic library to program a soccer game which is not very accurate. The game is not realistic but is similar to a Pacman clone. That means, the players have limited actions possibilities and the simulation would look like a Atari 2600 game. The trick with a htn-planner is, to combine different game-engines in layers. For example on top a high-level textadventure, in the middle a graphical representation and on the bottom a 3d realistics physics engine. Optimizing these different layers is the key factor for a successful HTN-planner.

Model acquisition

Surprisingly many papers are discussing the automatic creating of action models for HTN-planning. The idea is to use plan traces and a very complicated algorithm which generates the action model. To be honest, automatic generation isn't working. If the aim is to get a real system for example to play a game, only handcrafted models can be used. Realizing an action model for a HTN-planner has to be done as programming in general. That means, that lots of man years has to be invested, and some kind of version control system is needed. That means, the action model can not be generated autonomously, it has to be programmed by man.

There are many working examples available for example from the gaming-industry or from the Robocup challenge. In all cases the workflow was hand-crafted. That means, a team of 10 programmers has written the documentation, they have painted UML charts and they have implemented the action model in a simulator. The process can be called a “Software engineering task”. Plan traces may be useful but there is no algorithm but only a project which can transform them into a executable action model.

What can be done automatically is to use a given action model with an automatic solver. If it is clear that the task contains the subtasks “pass” and “shoot” and if it is clear, what the follow state is, that an automatic solver is able to generate the best plan. It is the same strategy which is used in computer chess to generate the next move. It is done entirely by the computer and human intervention is not needed.

What is possible, is to use an existing serious game (which has an API) and run on top a HTN-planner. If the game contains the action model, the tasks and the events it is possible to calculate the plan. The programming effort is only minimal in such cases. But, here the programming effort has to be invested by somebody else who has programmed the original game. That means, the action model is not generated from scratch it was programmed to in an external software engineering project.

1.7 Building a simulator for HTN-planning

HTN-Planning itself is easy to understand: a given “action model” is sampled by a solver and the found plan brings the system into the goal state. The more demanding task is to create the action model. Let us describe in detail how does it look like.

On a programming level every “Action model” is realized with an ontology. That means there are some C++ classes which are containing methods and attributes. They can call each other. The purpose of the ontology is to realize a simulator, that is a piece of software which is mimicry the reality. A well known simulator which is used in the Robocup domain is a physics-realistic simulator. It is realized with a dedicated physics engine and calculates what will happen if the player kicks the ball. But a physics-simulation is not enough, in the context of hierarchical task networks, many layers of simulators are combined together. There is a need also for a high-level-simulator, a tactical simulator and so on. All of these software moduls can be realized with ontologies, better known as UML classes. The question is only how to transfer a certain domain for example a dexterous grasping task into a simulator.

Again, let us imagine what the benefits are. Suppose we have a layered simulator for a dexterous grasping task. On the lowlevel it is a physics engine, on the mid-level a simplified 2d game and on the high-level layer a textadventure which can be controlled in natural language. If such a detailed model is available, it is very easy to solve the game. All what the HTN-planner has to do is generate random actions on different levels and search for a certain situation which is called the goal. The only open question is, that for most domains, such a layered simulator isn't available. And without such system, the HTN-planner has nothing to do.

The open question is: how to program for a certain domain, a layered simulator in an object oriented programming language. Programming only a realistic physics engine is not enough, what a HTN-solver needs is a mixture of different simulators because this will speed up the search process. Let us make an example for the Robocup domain.

In the high-level-simulator we can execute a command like “move-to-ball”. After executing the command, the engine places the player direct to the ball. The cpu-consumption for doing so is exactly zero. That means, the game engine simply moves the player position and that is. There is no collision detection, no path planning and no check if the battery is empty. On a second layer, this command is resolved into detail commands which are more realistic and only on the lowlevel layer a realistic 3d physics engine which includes collision detection is needed. Such a layered ontology based simulator can be called the main part of a HTN-planner. It is a useful tool for generating a plan for an agent.

layered abstraction

Because the layer architecture is fundamental for HTN-planning, I want to a give an example. Let us suppose we are again in the Robocup domain. A normal simulator would implement a physics engine in 3D. In HTN-planning this is not enough. The idea is to search for a plan on different abstraction levels and especially on layers which are computation inexpensive. A 3d accurate physics-simulation is very cpu-demanding, it is the worst choice for testing out random plans in it. The better approach is to construct first an artificial game on top of the simulator. We can call this a simplified soccer simulator. It is only 2d based and has no dedicated physics engine. Instead it works like a board game. That means, the pieces on the table can be moved freely without any constraint. If agent #1 should go to a certain place we can manipulate his position directly. That means, the action “move” needs no cpu-consumption instead it is executed directly. On this simplified board game, it is possible to figure out basic strategy. For example, if we want that 3 players are on the same place, we must move all them to that place. The abstract game engine can answer certain question. All of them are abstract nature. It is a game on top of the original game.

Now we can combine both layers together. On top the 2d abstract game with a simplified mechanic and on bottom the elaborated 3d simulator which simulates an accurate physics engine. Before we will ever try out a move in the 3d simulator we are asking first the high-level-layer what the result will be. The overall domain must be implemented in at least 2 layers of different game engines. That is the basic concept of an action model behind a HTN-planner.

The high-level layer didn't replace the former 3d physics engine. An accurate physics engine is great for planning lowlevel actions, for example if we need to know how strong we must kick the ball until he reaches a certain velocity there is no alternative to a physics engine. It gives the exact result back. But, only a small amount of question of an autonomous agent has to deal with this detail question. In many other cases the agent needs advice if he should kick the ball to position A or B, no matter how exactly this can be done. This high-level-decision can't be answered by an accurate physics engine.

In reality, a domain is modelled by different game engines which are arranged in layers. At least 2 layer are needed, but more layers are better. This raises the problem of how exactly the different layer-engines has to be implemented. Manual programming is the only working choice. Because the question is similar to any other software-engineering project. As an input we have a system specification, for example “program a software modul which simulates strategy aspects of a soccer play”, and the result is after some man years working code which fulfills the specification.

The concept of “Action model learning” is discussed sometimes in the literature, but it is only a future vision not a technology which is available today. The hope, that an action model can be derived from plan-traces without handwritten code will be disappointed.

1.8 Combining autonomous and remote-control

It is obvious, that writing a software-package which controls a robot is possible. Because, a robot is a machine which can be driven by commands, and a software can generate these commands. It is only a detail question, how exactly such a program will look like. In real robotics projects this is the bottleneck number one. That means, on a theoretical level it is often clear, what the robot should do, but the users are not good in programming or have not enough time to realize the software itself.

A possible answer is a semi-autonomous control system. The human operator takes first a joystick for controlling an underwater vehicle, and only in the second step the robot is following the demonstration. [11] The system described in the paper is at first hand a teleoperated underwater vehicle. That is according to the definition not a real robot, but it is more a remote controlled toy-boat. The advantage is, that writing the software for a human-in-the-loop simulation is relatively easy. The second part of the project (autonomous control) is postponed to the step #2. That means, even this subproject fail, it is always possible for a human to control the system manually.

The second advantage of this step wise programming is, that a concept like “Learning from demonstration” answers the question, how the Artificial Intelligence will work. The task can be specified under the term tracking. That means, the robot has the obligation to reproduce the human task. Implementing this task in software is not easy, but it is possible. In the above cited paper the authors are using the PDDL language for the high-level-planner and DMPs (parametrized dynamic movement primitive) for the lowlevel part.

But let us go into the details. The boat can be controlled manually. That means the human operator has a joystick and lots of keys he can press, and the boat has a certain task, for example “docking”. The process is the same like playing a computergame, that means the operator must press some keys, the robot reacts and the water in the tank increases the difficulty because the fluid produces disturbances. It needs usually more then one attempts until the human operator has mastered the task.

The strategy of the autonomous system can be sloppy described as Decision support system. That means, the AI is not really capable of controlling the robot, instead it is a support for the human operator. Sometimes the concept is called supervised autonomy, because the human operator is always in the loop and must observe what the robot is doing. How exactly works the system? It is mostly a controller. That is a piece of software which generates control-signal for the robot. The controller consists of a lowlevel and a high-level part. It is similar to a GOAP-planner which is used in computergames for controlling non-player-characters but is integrated in the overall robot-monitoring-system. The basic idea behind a controller is a planning task. That means, from the current situation a plan is generated to bring the system into a goal state. It is the same principle like a chess-engine works. There is a game-tree, different branches and an evaluation criteria. The difference is, that a robot-controller is more complicated then a chess-playing software. It contains more submoduls which are doing the hierarchical planning process.

Another interesting feature of mixed teleoperation is, that from the software-engineering side the project is relatively easy. That means, a teleoperated controlled robot is mostly a hardware problem which is understood very well. If hardware is available like a robotarm, a camera, an object and a joystick all the devices has to be connected and the system is ready. The joystick can be replaced by a data-glove and the manipulator by a larger model. That means, it is not necessary to write complicated control software for the task or have a theoretical understanding of robotics to pickup the ball. The main idea is to postpone the complicated task of writing the software to later state, namely for the Learning from demonstration. It is mostly the result of playing around with the system and try to improve their functionality a bit. Or to make the point clear: it is complicated to fail a telerobotics project. The reason why has to do, that a human-operator is capable of executing nearly all task. Remote controlling a machine is a robust way of interaction with the environment.

Suppose the manual teleoperation works, what is the next step? The next more advanced form is to utilize a pddl planner in the loop. A task model is formulated in the pddl language and this calculates some decision in realtime. Such a system is not a real robot system, because pddl is only a basic form of planning, but it is a good transition from a pure human-controlled system into a semi-autonomous system.

2 Example

2.1 HTN Planner

The difference between a Hierarchical task network and a behavior tree is not easy to understand. Both concepts are about Artificial Intelligence and Game-programming, but in general a HTN-planner is superior. Perhaps a simple example in sourcecode makes sense to grasp the idea.

The figure [fig:Textadventure] shows a compact C++ class which implements a textadventure. The user can send to the engine different commands like “init”, “open-door” and so on. After the command is parsed, the engine changes internal variables. In the concrete example, the user must first open the door until he can enter the room. The C++ class is not a behavior tree which says which commands must be executed in sequence, instead it is a game-engine who accepts commands and prints out the internal state. The user can play around with the game and send different commands to the engine in the hope, that he will reach the goal. It is not the HTN planner itself, but the domain model which can be used by a HTN-planner. The question is: which commands must be executed to bring the system into a goal-state.

class Textadventure {

public:

  std::string door;

  std::string position;

  void action(std::string name) {

    std::cout<

    if (name=="open-door") door="open";

    if (name=="close-door") door="close";

    if (name=="go-in") {

      if (door=="open") 

        position="inside-room";  

    }

    if (name=="go-out") {

      if (door=="open") 

        position="outside-room";  

    }

    if (name=="init") {

      door="close";

      position="outside-room";

    }

    if (name=="show") {

      std::cout<<"* ";

      std::cout<

      std::cout<<"\n";

    }

  }

  Textadventure() {

    action("init");

    action("show");

    action("go-in");

    action("show");

    action("open-door");

    action("show");

    action("go-in");

    action("show");

  }

};

Textadventure visual

The interesting aspect is the hierarchy of actions. On the lower-level the player can open and close the door and on the high-level layer he can enter and leave the room. Let us make a practical example. The game starts with a fresh instance and the agent want's to enter the room. He types in “action("go-in");” but it doesn't work, because the game-engine prevents that the player can direct manipulate his position. Instead there is a build-in game-mechanics, that means on the low-level the player must first open the door until he can execute the high-level “go-in” command.

The problem is not to solve the game automatically, this can be done by a brute-force sampler in under a second. The problem is to describe the domain in a machine-readable form. That means to program the game-engines on the lower-level and on the higher-level. A game-engine is a software-modul which specifies what will happen if the agent executes an action.

2.2 Car physics

Suppose we want to program a car parking controller, what is the best practice method? At first, we need a simulator with a top down physics engine. The idea is not to use a real car, but testing out the controller in a computer-game. A realistic physics engine is also helpful because it allows to detect collisions. But there is only one problem: a working simulator isn't equal to a working controller. A simulator means only, that we can control the car with a joystick, but the aim was to get an autonomous car.

Let us investigate what the problem is. If the car is visible in the simulator we can test out different plans, for example a trajectory for parking. The question is: how does look the trajectory for getting a certain goal? This is usually answered with a brute-force sampling planner, that means we are testing out 1 million trajectories and evaluate what will happen. So we can generate the parking trajectory like a chess engine works. There is only a minor problem. The CPU-consumption would be very high. Even if we are taken a modern efficient physics engine like Box2d or bullet, a normal computer is not able to evaluate more then 100 trajectories in a second. That means, it is not possible for testing out 100 million trajectories, it would take years for doing so.

Car-parking-scene

The answer to the problem is called “hierarchical task network”. It is a planning technique which constructs a layered simulator and planning on different levels. Let us make an example. Figure [fig:Car-parking-scene] contains three scenes of a parking maneuver. The standard programming technique to implement the game is a realistic physics engine, because it is highly accurate. The alternative is to program a simplified physics engine from scratch. This engine doesn't have a collision check or sophisticated force calculation. Instead it works on a symbolic level.

The game starts with the init-keyframe. That means, there is a car and a parking lot. The user has different commands he can enter. The command “u-turn” does not activate a complex AI-controller which is doing the u-turn maneuver with a detailed trajectory. No, “u-turn” means only to change the direction of the car direct. That means, in the game the position of the lamps of the car will be changed to the new position, that is all. If the user enters “u-turn” the game-engine simply flips the car. The next command the user can enter is “parking”. Like in the example before, it is a very basic command, if the user enters “parking” the position of the car is simply changed to the parking lot. That physics engine works in a reduced form, it is similar to a pddl specification.

As a consequence we have a car-parking game, but a very abstract kind of game. Playing around with the game isn't generating the detailed trajectory, but only the subgoals. It is a way of storing knowledge and to enable high-level-planning. Let us now investigate how “parking” works. The user enters two commands: “u-turn”, “parking”. That's all. With the first command he flips his car, and with the second command he moves the car into the lot.

Until now the idea may look a bit useless, because we need a detailed motion controller and not a subgoal generator. But the described abstract game is an important step into this direction. We can use the high-level-game for constructing the low level controller. If we know, what the subgoal is, we can do the planning on the realistic physics engine. The question is not longer: what is the overall trajectory, the question is only “how to realize a u-turn”? That means, the high-level commands are equal to skill primitive. Calculating the correct trajectory for reaching out these skills is easier then planning the complete domain. It is possible to use a realistic physics engine like Box2D for calculating such subgoals.

References

[1] Luciana Benotti, "DRINK ME: Handling actions through planning in a text game adventure", XI ESSLLI Student Session  (2006), pp. 160--172. https://cs.famaf.unc.edu.ar/~luciana/content/papers/files/benotti06.pdf

[2] Donna Byron, Alexander Koller, Kristina Striegnitz, Justine Cassell, Robert Dale, Johanna Moore, and Jon Oberlander, "Report on the first NLG challenge on generating instructions in virtual environments (GIVE)", in Proceedings of the 12th european workshop on natural language generation (, 2009), pp. 165--173. http://www.aclweb.org/anthology/W09-0628

[3] Aaron St Clair, Carl Saldanha, Adrian Boteanu, and Sonia Chernova, "Interactive hierarchical task learning via crowdsourcing for robot adaptability", in Refereed workshop Planning for Human-Robot Interaction: Shared Autonomy and Collaborative Robotics at Robotics: Science and Sys… (, 2016). https://people.csail.mit.edu/cdarpino/RSS2016WorkshopHRcolla/abstracts/RSS16WS_17_InteractiveHierarchicalTask.pdf

[4] Richard E Fikes and Nils J Nilsson, "STRIPS: A new approach to the application of theorem proving to problem solving", Artificial intelligence  2, 3-4 (1971), pp. 189--208. http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/strips.pdf

[5] Andrew Gargett, Konstantina Garoufi, Alexander Koller, and Kristina Striegnitz, "The GIVE-2 Corpus of Giving Instructions in Virtual Environments.", in LREC (, 2010). http://cs.union.edu/~striegnk/papers/striegnitz_conference_lrec_2010.pdf

[6] Andrew Garland and Neal Lesh, "Learning hierarchical task models by demonstration", Mitsubishi Electric Research Laboratory (MERL), USA--(January 2002)  (2003). http://www.merl.com/publications/docs/TR2002-04.pdf

[7] Alexander Koller and Ronald Petrick, "Experiences with planning for natural language generation", Computational Intelligence  27, 1 (2011), pp. 23--40. http://www.coli.uni-saarland.de/~koller/papers/ci-crisp-11.pdf

[8] Miguel Lozano, Steven J Mead, Marc Cavazza, and Fred Charles, "Search-based planning for character animation", in 2nd International Conference on Application and Development of Computer Games (, 2003). https://pdfs.semanticscholar.org/cba3/a6527f7a4e7209b463cc70bc300cda01b171.pdf

[9] Dipendra K Misra, Jaeyong Sung, Kevin Lee, and Ashutosh Saxena, "Tell me dave: Contextsensitive grounding of natural language to mobile manipulation instructions", in in RSS (, 2014). https://www.cs.stanford.edu/people/asaxena/papers/misra_sung_saxena_rss14_tellmedave.pdf

[10] Oliver Obst, Anita Maas, and Joschka Boedecker, "HTN planning for flexible coordination of multiagent team behavior", Fachberichte Informatik  (2005), pp. 3--2005. ftp://ftp.uni-koblenz.de/pub/outgoing/Reports/RR-3-2005.pdf

[11] Narćıs Palomeras, Arnau Carrera, Natàlia Hurtós, George C Karras, Charalampos P Bechlioulis, Michael Cashmore, Daniele Magazze…, "Toward persistent autonomous intervention in a subsea panel", Autonomous Robots  40, 7 (2016), pp. 1279--1306. https://www.researchgate.net/profile/Charalampos_Bechlioulis/publication/283339628_Toward_persistent_autonomous_intervention_in_a_subsea_panel/links/587574d108ae8fce492823bc/Toward-persistent-autonomous-intervention-in-a-subsea-panel.pdf

[12] RM Simpson and W Zhao, "Gipo graphical interface for planning with objects", International Competition on Knowledge Engineering for Planning and Scheduling  (2005), pp. 34--41. https://pdfs.semanticscholar.org/5ef6/d24c8f496963a40b4939b5f3e012c977edca.pdf

[13] Qingxiaoyang Zhu, Vittorio Perera, Mirko Wächter, Tamim Asfour, and Manuela Veloso, "Autonomous narration of humanoid robot kitchen task experience", in Humanoid Robotics (Humanoids), 2017 IEEE-RAS 17th International Conference on (, 2017), pp. 390--397. http://h2t.anthropomatik.kit.edu/pdf/Zhu2017.pdf