Goal-Orientated Action Planning (or GOAP for short) is an A.I. technique that was devised by Jeff Orkin of
MIT in the early 2000s.
It was successfully applied in the game
F.E.A.R. to control the behavior of the NPCs.
If you want to learn more about it, you can read through the research papers available at this address.
GOAP has all the elements of a Finite State Machine but works with them very differently.
For example, the Finite State Machines (as you've seen before)
define behaviors and conditions to drive the NPC at fulfilling some goal. To achieve this with a Finite
State Machine,
you could have one massive graph or divide it up into smaller units.
GOAP also uses graphs for its processing but differs from Finite State Machines in that the actions
and goals are decoupled.
Actions are 'free elements' within the system that are mixed and matched to meet goals
when they are presented. Instead of having a set list of actions that need to be performed to achieve
a goal, GOAP allows for numerous solutions to be chosen from.
So instead of a system that looks like this, in GOAP, all the links are removed. Then when a goal is presented,
an appropriate course of action can be chosen from all of the available tasks based on the state of the
agent and the world.
For example, if an agent were asked to kill an enemy and it DIDN'T have a weapon, it could choose a physical
fight.
However, if it DID have a weapon, a different set of actions would become available. Every action in GOAP
has a 'Precondition' and an 'Effect'. The Precondition is a state that must be met before the action can
take place.
The Effect is how the action leaves the state of the agent (or the world) after it has occurred. A set
of actions forms a puzzle/set of dominoes where the Preconditions can be matched with Effects
and the Effects matched with Preconditions to create 'Action Chains'.
Let's look at an example.
Consider this set of actions.
If you take a close look, you will see they focus on eating.
If you take a closer look, you might be able to see 2 plans that you could form yourself (1 for ordering
pizza and 1 for baking). An agent
with these actions won't do anything until presented with a goal.
In this case lets trigger the goal 'Hungry = false'.
The goal is the 'end state' of the agent NOT the 'starting state'.
If you think about it, a recurring human goal is to have 'Hungry = false' as often as possible.
Plans can generally only occur when the world and/or the agent are in a particular state.
For this example, let's add 2...'hasIngredients = true' and 'hasPhoneNumber = true'.
The planning stage in GOAP
always works backwards from the goal, to see if it is achievable.
It does this by matching the Effects with Preconditions into a chain.
It works all the way back to the World States.
If it can't find a matching World State at the end, the plan is abandoned.
In this example, there are 2 possible plans available.
'Order a pizza' and 'Bake something to eat'.
Notice the reuse of the 'Eat' action.
It fits into both plans and illustrates how actions can be mixed-and-matched to form different plans.
As long as the Preconditions and Effects fit together, any actions can be chained together.
Now that we have 2 plans that will achieve the goal,
which one do we choose?
Simple! We add a cost to the plans. We might assign each action a monetary cost.
In this case, the pizza plan
works out dearer, assuming we already have the ingredients for baking.
We might instead opt for a time-based cost as well.
This would make the baking option more costly. With costs assigned to each plan, when there are multiple,
the cheapest one can be selected first. If there are multiple plans with the same lowest cost, then one
can be picked at random. A conceptualization of a GOAP system looks like this, with Actions, Goals and
World States being fed into a Planner.
The Planner chains the Actions together according to the Goals and starting States, to determine which
plans are achievable.
The Planner uses the A* algorithm to find the best plan using the cost values.
Once a plan has been generated, the agent goes about achieving it using a very, very simple Finite State
Machine that basically moves the agent to where the action needs to take place and then performs the
action.
The agent works its way along the chain of actions until a goal has been achieved. Before each action
is performed,
it is always checked to see if it is still valid. If not, the entire plan is discarded and another one
is generated.
The beauty of GOAP is that more and more actions can be added to the pool available to the agent and
these will automatically be picked up by the Planner.
This means very little extra programming to recognize graphs like the ones in complete set-ups of
Finite State Machines, as the graphs are generated on-the-fly by the Planner.
This makes GOAP a very powerful and flexible option for programming the behaviors of your NPCs.