How to start a robotics project?

Normal software engineering projects are grouped around certain technologies. For example, somebody can use a Linux server together with the PHP language to build a website, or it's possible to create with the C++ language a new computer game. If the programming environment is fixed, it's possible to figure out the details. And the number of options how to create within C++ a game is limited.

The situation in case of robotics project is a bit more difficult. There is no framework available. Sure, some libraries for creating robotics and even some programming language are mentioned in the literature. Sometimes the ROS project is called a quasi standard, and embedded control is often handled with C. But these technologies are not used for creating the AI itself, but they make only if it's already known how to realize the robot.

The better idea to start a robotics project is based on the steps in human computer interaction. A new robotics project is usually started as a manual control system. That means, the human operator gets a joystick and moves the robotarm remote. That is the same what a crane operator is doing. The second step is about reducing the workload for the human operator. The goal is to increase the automation level. In case of a robot arm who grasps objects this is done by automating the step of grasping itself. That means, the human operator controls the arm, but the robot decides when the right moment is there to close the gripper.

In the literature the concept is called shared autonomy. It means, that that some tasks are done by the human and other by the Artificial Intelligence. The human operator controls the movement of the arm, and the vision system detects if an object is in the hand and activates the grasping action. The advantage is, that only subparts of the system gets automated. That means, only the software which executes the grasping action is working autonomously, while the position of the gripper isn't controlled by the software. The overall pipeline can be improved into a fully autonomous system. The next step would be, that the AI controls both: the grasping and the position of the robot hand.

Somebody may argue, that the difference between a teleoperated robot arm and a robot arm who can grasp by itself is small. And indeed, in both cases the human operator is in the loop. That means, he has to move the joystick for doing the task. The advantage is, that the human will recognize the reduced workload. If he doesn't need to press the “grasp” button it's a clear improvement.

Combining GOAP with a vision model

GOAP (Goal oriented action planning) is a well known technique from Game AI to build realistic AI characters. The idea is, that the agent is in a worldstate and has a behavior library in the background. A solver is testing out different behaviors to bring the agent to a goal. GOAP is equal to a automatic textadventure which takes an input worldstate and generates the next behaviors.

To use the concept for real robotics, a vision model is needed which provides the input worldstate. A vision model is in the easiest case a vision cone infront of the agent. This is sometimes describes as spatial grounding in the literature, because it connects pixelcoordinates like “object=(100,100)” to language, e.g. “object isat front”.

GOAP planning for Sokoban

The game of Sokoban consists of a robot, a box and a goal. The robot has to execute some actions which pushes the box to the goal. Instead of creating the overall gametree the better idea is to describe the problem from an abstract perspective. In the GOAP (goal oriented action planning) technique the robot has the following actions:

- movetobox (precondition: robot far from box, effect: robot is at box)

- adjustposatbox (precondition: robot is at box, effect: robot has push position)

- pushbox (precondition: robot has push position, effect: box is at goal)

The planner can generate an action sequence. A sample plan would look like: movetobox, adjustposatbox, pushbox.

This is the basic idea behind GOAP. But perhaps it's possible to somplify the overall pipeline with conditional planning. Conditional planning means to create a more abstract plan which works in different situations.

The main idea behind the GOAP problem solving technique is to transfer a domain into a language. In the Sokoban example, three actions are available plus some world descriptions like “robot is at box”. This new kind of problem is a textadventure, it is played interactively and the visual representation is no longer needed. A pleasant sideeffect is, that the state space was reduced dramatically. Even the Sokoban map has a size of 100x100 fields, the planning space for the solver is reduced to the textadventure.

The open question is, if the problem space can be reduced further. A possible idea would to a use constructive grammar which produces the textadventure. In the literature this is called "procedural grammar". A GOAP model has the syntax:

rulename, if feature then feature

Rule induction

If the GOAP action model is not known in advance it make sense to collect a dataset and try to determine the rules with machine learning algorithm like Decision tree learning algorithm C4.5. At first, we need a vast amount of data:

case id	name	precondition	effect
0	movetobox	robot far from box	robot is at box
1	movetobox	robot far from box	robot is at box
2	adjustposatbox	robot is at box	robot has push position
3	adjustposatbox	robot is at box	robot has push position
4	pushbox	robot has push position	box is at goal
5	pushbox	robot has push position	box is at goal

In the table some cases are recorded. They were acquired from plan traces in a learning from demonstration scenario. To make thinks simple, the precondition / effect variables are the same, that means every action was successful. The idea is to first record all the interaction with the Sokoban game, extract features, group these features into actions and then give the actions a name. The result is GOAP forward model which predicts the outcome of an action in terms of feature values.

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.

The secret behind game AI

Real time strategy games like OpenRA have a built in game AI. But how exactly is this computer generated force working in reality? Sometimes, the principle is described as scripting AI but this definition isn't clear enough. The more elaborated explanation has to do with abstraction. The transition between no AI into an autonomous system is a soft one.

Let us go into the details. A realtime strategy game is usually programmed for the human player in mind. The underlying physics engine provides to the player some actions. For example he can select the units and let them walk to a target position. This abstraction layer can be formalized as grammar. The human player can interact with the game with a controlled vacabulary. He has some actions which are mapped to the GUI and after activating the actions the physics engine is doing something.

This baseline abstraction has nothing to do with an ingame AI but it's supporting the normal game play. It defines the game itself and it's rules. A sideeffect is, that the game AI can use the same layer as the baseline. That means, the AI doesn't move the cursor to a button and clicks with the mouse, but the AI has access to underlying API with all the allowed actions. The only thing what is missing is which of the around 100 actions should be activated next.

A naive approach would be to use a random generator. Such an AI Would become very weak. The more interesting technique is to create a second layer which allows the AI engine to plan the movement. A cpu efficient way in doing so is called GOAP (goal oriented action planning). This is some kind of textadventure which is forming an additional layer on top of the physics engine. In the GOAP model all the actions are available but they can be activated without running the normal physics engine.

Let me give an example. In every Real time strategy game the player can build a powerplant. But why should somebody do so? Because the effect of the action is, that the energy level gets increased. The relationship between the action and the effect can be stored in a textadventure in a compact representation. This allows the planner to execute the action and without a delay he gets the result that the energy level is higher. Or let me give another example.

Formalizing all the allowed actions into a textadventure is equal to building a goal model. It's a headless game which can be played in a much faster time. In this textadventure a complicated game tree can be built. The solver is trying out possible action sequences and he will see the result.

The next step contains the AI itself which is not hard to explain. The solver gets a goal, for example, maximize the energy level and the AI will figure out by it's own which actions are needed. The generated action sequence from the textadvanture is executed in the real time and for the human player a lifelike game AI is visible. Creating the GOAP model from scratch is a bit trickey, but with trial and error it's possible.

From a birds eye perspective the AI contains of a abstract actions which are searched by a solver to fulfill a goal. The resulting action sequences gets executed in the game. The advantage of this technique is, that the amount of needed cpu ressources is low, and the AI can become very strong. Let us go back to the example with the powerplant. If the GOAP model is available it's possoble to send to the planner a high level request. For example a goal can be: maximize the energy level. Another goal is to build as much units as possible. A more general goal would be to increase the overall strength. The interesting point is, that from an algorithm perspective it is very esay to fulfill such goals. Because all the possible actions and the effects are formalized. A game tree can be generated which means, that the solver is testing out an action and determines what the result is. If the solver is doing so many times he can browse through the entire game.

In the AI literature, sometimes it was written that Real time strategy games are hard to solve because the state space is too large. Exactly this is the reason why many abstraction levels are needed to simplify the search process. If the solver would try out random mouse actions it is indeed not possible to figure out the next action. Because after a short amount of time, the possible combinations are endless. But if the game is structured hierarchically and if a goap model is used it's not very hard to build the entire game tree. Sometimes a third layer is used which is called Goal manager. On this layer, a dedicated manager is defining the next goal. The advantage is, that such goal definition can be realized on a very high abstraction level. It's possible to write down the following statement:

if the own base is under attack, play defensive.

else play offensive.

Such high level goals are only possible because the lower layer are available. That means, if the game is working great, the goap model is available and the solver accepts goals, it's possible to build on top of these layers a goal manager which contains of simple if-then-statements.

GOAP AI planning explained step by step

The Goal and action planning system has the same disadvantages like the original STRIPS planner. The algorithm itself works great, but it's complicated to explain. I won't invent the wheel twice but i will explain it more easier. At first, a GOAP tutorial needs two elements:

1. how the solver works

2. how to build the domain model

A GOAP planner contains of low level actions which can be executed on the robot directly, for example the action “left”. And it contains of tasks which doesn't produce an action but result into a goal. Let us take an example. The robot should go to the middle of a map. This goal is defined by sending the goal to the game engine: task(“gotomiddle”)

If the game engine receives the task it will put the robot to the middle by changing it's absolute coordinates. The planner has to figure out which goals are needed in which sequence and then the low level actions are determined. The inner working of such a planner is remarkable easy because it's a graph search algorithm which is traversing the symbolic game tree, and checks out potential paths.

The second important aspect of GOAP is how to create the domain model. Without a model the planner won't work. The domain model is equal to grammar which contains goals in natural language. It's a wordlist which contains detailed description for each entry. Building such a grammar is possible with learning from demonstration. That means, a human operator is observed how he is solving a task, and according to the annotated actions the tasks are identified.

Combining teleoperation with symbolic planning

Every solver is working with a goal in mind. The problem is, that goals are not available in the software itself, because they are referencing to request from the outside. The high level goal is an input which is feed into the planner. The source of the goal is not another module, but the human operator.

If the human operator defines the goal interactively, a semi-autonomous system is the result. An easy to grasp example is an inverse kinematic in which the human operators points to a position on the screen and the robot arms is following the trajectory. The interesting aspect is, that such a robot arm is moving faster than a human can execute the actions. The human needs only to point the mouse to the goal, but the lowlevel actions are determined by the system.

This interaction between human and robot can't be modeled in software. Every goal planner comes to a bottleneck because it's only in parts possible to determine the goals themself. That means, the robot itself doesn't has meaning, he becomes only a tool if a higher instance asks the system to do a certain action. Let us give an example:

A plan is provided to the robot control system, which is a list of waypoints. Why does the robot system should follow the waypoints? Nobody knows, because the plan is given by a human operator. He knows why the plan makes sense, but this knowledge isn't available for the robot. The communication between both separate system needs a shared language. That means, the robot control system should be able to parse the plan and the human operator as well. What the robot can do is to figure out the low level primitives for realizing the plan.

It's the same idea how modern compiled programming languages are working. The compiler needs as input a hello world program. For the compiler the program itself doesn't make sense, but it can convert the sourcecode into binary code.

Essence of GOAP

The problem with most AI paradigm is, that it's hard to grasp it's inner core. Is GOAP an algorithm, a piece of software or a programming language? Unfortunately none of them, and it's much harder to explain the overall concept. I would call it, an extension to a physics engine which provides abstract actions. The user can send a command like “movecenter” to the physics engine, even if the game itself doesn't know of such an action. The physics engine is put into a measurable state and a solver can try to reach this state.

Or to explain it from a different viewpoint. The goap concept means, that a plan notation is invented and grounded into the physics engine. This plan notation allows the human operator to provide a sequence of actions, and the goap planner can try to convert this plan into lowlevel actions. The term goal is equal to a macro action. For example a goal might be “reach waypoint”. It's an option to raise the abstraction level. A plan which contains of only 10 single steps can describe a complex longer sequence of movements in the game. A comparison with functions in a normal programming language make sense. For the programmer it's not important how the “isprim()” function works internally, but it delivers a return value back to the program. GOAP is using the paradigm for structuring the action space of a robot in a game.