July 25, 2019

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.