Goal orientated action planning or go for short is an Iowa technique that was devised by Jeff Orkin
of MIT in the early 2000s.
It was successfully applied in the game fear 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.
GO 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, defined 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 divided up into smaller
units.
Gopi 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 match to meet goals when they are presented.
Instead of having a set list of actions that need to be performed to achieve a goal, Gopi allows for
numerous solutions to be chosen from.
So instead of a system that looks like this in scope, 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 scope has a precondition, and in 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 kind of puzzle or set of dominoes where the preconditions can be matched with
effects, and the effects match 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 two plans that you could form yourself.
One for ordering pizza and one for baking.
An agent with these actions won't do anything until presented with a goal.
In this case, let's trigger the goal.
Hungry equals 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, equal, 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 to has ingredients is true and has phone number is true.
The planning stage in scope 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 two 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 two 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 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 aStar 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 the 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 hope 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 scope a very powerful and flexible option for programming the behaviors of your NPCs.