July 27, 2019

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.