GOAP - A form of AI planner

Game Engine Game Engine Resources
21

The difficulty with using Dijkstra is that it explores all possible path nodes (multiple times), which isn’t particularly performant in all cases. The use of A* merely avoids visiting overly expensive routes (with the appropriate heuristic).

Planning shouldn’t happen that frequently, so theoretically the performance difficulties are found in calculation spikes, rather than framerate-drops. You could look at something like a thread-based planner, because the in/out data can be kept quite simple (though procedural conditions may require some more thought).

I did find that reading the papers wasn’t enough to get a working planner. The A* planner used essentially works backwards from the goal, keeping track of how each action affects the state, until the state of the node equals its goal state. The neighbours for each node are just the actions that have effects that may/may not produce useful results. The heuristic used is the number of unsatisfied state symbols between the goal and current state of a node. There are some peculiarities here, such as the way we check that the path is complete. The main reason for this that we don’t compare goal and current states is because a) we allow preconditions to involve symbols that are also in the action effects dictionary, which isn’t handled, and we don’t check if neighbours of actions actually solve the state, or if they instead diverge.

A* heuristics are different for each task, and the algorithm must be careful to support them. (Or, rather, some people use simplified algorithms if the heuristic is guaranteed not to over-estimate the distance to the goal (e.g the Wikipedia example)).

The Actions used in the planner should avoid running expensive procedural checks, and defer most of the work to subsystems via something like the blackboard. I’m experimenting with a sensory system to allow for the planner to make decisions based upon potentially flawed information (like blind zombies, guessing where the threat is positioned), rather than doing this lookup inside the action explicitly, but it is all a little ill-defined and up-to-you in this field.

Jeff’s articles suggest using a sensory system to run most expensive checks regularly, to avoid latency spikes (instead incurring a regular, predictable cost). You can see what I’m doing with this here https://github.com/agoose77/PyAuthServer/tree/master/game_system/ai

My implementation will be slower than the one used in F.E.A.R, not simply because it’s Python - I allow for different variable types to be used, whilst in the FEAR planner, boolean bitfields are used (which can be optimised for speed). C++ would be faster, if you can allow for this trade-off. Of course, once you support procedural preconditions / effects, it makes sense that most of theg ame allows a C++ API.

22

what about using the same property many ways depending on what the type of data is?

like if type(own[‘target’]) is vector:

or

if type(own[‘target’]) is object:

if type(own[‘target’]) is string:

python has this over C++ right?

so this way, whatever sets the property defines the state ?

23

An aside; It’s more sensible to use isinstance(obj, str) rather than type(obj) is str.

C++ can use objects without types, with raw pointers, but it has to use casts to do so, which are not safe, whereas Python allows for dynamic typing without casts which is, for this function, safer.

However, it’s not particularly relevant here, what I mean by the variable types is that I don’t restrict the values of the effects / preconditions to solely be booleans in a known-size bitfield. This means that an unbounded number of variables can be used, and less data is required in the planner (at a cost to the comparisons).

24

well, I was thinking from a architectural standpoint, you could only call functions that are relevent, instead of proccessing a bunch of switches that are off,

by using a event like
if property is string-----------(plan type 1)

if property is object-----------(plan type 2)

if property is vector------------(plan type 3)

and each function adds a object that tries to accomplish the goal,
on faliure it sets data/type in the planner, whe makes a new plan object?

so the planner only runs if the plan succeeds or fails?

but we don’t have access to types as a property switch right?

what about expression controllers?

but then the logic would proccess the next frame?

can a expression controller call a function?

25

Well if we go so abstract I would instead of “if property is” have “property.do()”.
A class that deals with the type and things itself.

But as agoose said, boolean operations are very fast in c++;
It more about speed as the task is searching an huge (state) space.

26

I had problems actually in blender python, I couldn’t find a function that would return a list of visible objects to the camera … theres a function called “world_to_camera_view” however i had to loop over every object in the scene to clip … i think theres a way of getting all visible objects from bullet … I don’t do much BGE coding, however a visibility frustum test would be excellent for the sensor

otherwise a ray cast and closest hit test would also be a useful sensor, and radar sensors could be used for hearing

27

actually i think view frustum sensors can be made from a frustum shaped mesh collision object set to not interact with the physics world and also to be invisible. Then a ray hit test can tell you if the object is not occluded - these functions apparently use bullet so they would be quite optimal.

For the object planning code, it would be good to have doors and keys, machines with unconnected wires, it would be interesting to implement a deductive reasoning step that associates the finding of a key at random with the need to find a locked or lockable door, for example, and to have a database or internally built python database that contains simple information about object types, like keys, locks, electric cables, weapons, crowbars etc - stating their basic purpose, i.e. interacts with, fires, explodes etc, then the AI could be set up to try to find new solutions to problems - like exploding a door if the key is missing

28

Since my last post, I’ve updated the first post, adding some improvements (see here https://github.com/agoose77/goap)

29

Stick to Python for now. No need to “speed it up” unless there is actually a performance bottleneck.

I don’t do much in these demos, but certainly, the systems that provide information that drives the planner (world state) would be responsible for the sorts of queries like “closest weapon rack”. In the FEAR and Killzone2 games, systems generated “world facts” that contained meta-information like relevance, age of fact, and interest (killzone had an urge-interest system). These systems are as important as the planner, if not more so, as they allow it to perform its queries efficiently.

The planner uses a simple heuristic of h(node)=len(goal_state != current_state), and a g score of g(node)=action.cost. In future, the cost might itself be dynamic and dependent upon world state (though this would need some care).

Once you move to a goal->root approach, and use a depth first search A*, you will improve performance dramatically. The performance of the planner is related to how many actions can satisfy the same world state symbols, i.e how many actions have effects that affect a particular node’s preconditions. If these are relatively small, then the planner won’t become particularly slower - we lookup neighbour candidates from a dictionary by effect-type, so it’s a relatively constant lookup time.