WEBVTT

00:02.280 --> 00:08.670
Goal orientated action planning or go for short is an Iowa technique that was devised by Jeff Orkin

00:08.700 --> 00:10.950
of MIT in the early 2000s.

00:10.980 --> 00:16.230
It was successfully applied in the game fear to control the behavior of the NPCs.

00:16.260 --> 00:21.480
If you want to learn more about it, you can read through the research papers available at this address.

00:22.710 --> 00:27.470
GO has all the elements of a finite state machine, but works with them very differently.

00:27.480 --> 00:33.060
For example, the finite state machines, as you've seen before, defined behaviors and conditions to

00:33.060 --> 00:36.240
drive the NPC at fulfilling some goal.

00:36.510 --> 00:41.760
To achieve this with a finite state machine, you could have one massive graph or divided up into smaller

00:41.760 --> 00:42.510
units.

00:42.840 --> 00:48.870
Gopi also uses graphs for its processing but differs from finite state machines in that the actions

00:48.870 --> 00:50.490
and goals are decoupled.

00:50.550 --> 00:56.610
Actions are free elements within the system that are mixed and match to meet goals when they are presented.

00:56.820 --> 01:02.460
Instead of having a set list of actions that need to be performed to achieve a goal, Gopi allows for

01:02.460 --> 01:04.710
numerous solutions to be chosen from.

01:04.890 --> 01:09.730
So instead of a system that looks like this in scope, all the links are removed.

01:09.750 --> 01:15.240
Then when a goal is presented, an appropriate course of action can be chosen from all of the available

01:15.240 --> 01:18.870
tasks based on the state of the agent and the world.

01:18.900 --> 01:24.750
For example, if an agent were asked to kill an enemy and it didn't have a weapon, it could choose

01:24.750 --> 01:25.950
a physical fight.

01:25.980 --> 01:30.570
However, if it did have a weapon, a different set of actions would become available.

01:32.340 --> 01:38.460
Every action in scope has a precondition, and in effect, the precondition is a state that must be

01:38.460 --> 01:40.800
met before the action can take place.

01:40.920 --> 01:46.740
The effect is how the action leaves the state of the agent or the world after it has occurred.

01:47.130 --> 01:52.980
A set of actions forms a kind of puzzle or set of dominoes where the preconditions can be matched with

01:52.980 --> 01:57.540
effects, and the effects match with preconditions to create action chains.

01:58.110 --> 02:00.150
Let's look at an example.

02:00.180 --> 02:01.920
Consider this set of actions.

02:01.920 --> 02:05.430
If you take a close look, you will see they focus on eating.

02:05.490 --> 02:10.770
If you take a closer look, you might be able to see two plans that you could form yourself.

02:11.160 --> 02:14.550
One for ordering pizza and one for baking.

02:14.550 --> 02:19.020
An agent with these actions won't do anything until presented with a goal.

02:19.290 --> 02:21.420
In this case, let's trigger the goal.

02:21.450 --> 02:23.460
Hungry equals false.

02:23.910 --> 02:28.050
The goal is the end state of the agent, not the starting state.

02:28.080 --> 02:34.680
If you think about it, a recurring human goal is to have hungry, equal, false as often as possible.

02:35.100 --> 02:40.740
Plans can generally only occur when the world and or the agent are in a particular state.

02:40.770 --> 02:47.230
For this example, let's add to has ingredients is true and has phone number is true.

02:47.250 --> 02:52.390
The planning stage in scope always works backwards from the goal to see if it is achievable.

02:52.410 --> 02:56.850
It does this by matching the effects with preconditions into a chain.

02:57.030 --> 02:59.940
It works all the way back to the world states.

02:59.970 --> 03:04.440
If it can't find a matching world state at the end, the plan is abandoned.

03:04.470 --> 03:07.900
In this example, there are two possible plans available.

03:07.920 --> 03:11.070
Order a pizza and bake something to eat.

03:11.220 --> 03:13.530
Notice the reuse of the eat action.

03:13.530 --> 03:19.390
It fits into both plans and illustrates how actions can be mixed and matched to form different plans.

03:19.410 --> 03:24.220
As long as the preconditions and effects fit together, any actions can be chained together.

03:24.240 --> 03:28.290
Now that we have two plans that will achieve the goal, which one do we choose?

03:28.410 --> 03:29.070
Simple.

03:29.070 --> 03:30.810
We add a cost to the plans.

03:30.810 --> 03:33.860
We might assign each action a monetary cost.

03:33.870 --> 03:37.060
In this case, the pizza plan works out dearer.

03:37.080 --> 03:43.140
Assuming we already have the ingredients for baking, we might instead opt for a time based cost as

03:43.140 --> 03:43.740
well.

03:43.770 --> 03:49.430
This would make the baking option more costly with costs assigned to each plan.

03:49.440 --> 03:53.580
When there are multiple, the cheapest one can be selected first.

03:53.940 --> 03:59.160
If there are multiple plans with the same lowest cost, then one can be picked at random.

03:59.640 --> 04:06.690
A conceptualization of a system looks like this with actions, goals and world states being fed into

04:06.690 --> 04:07.580
a planner.

04:07.620 --> 04:13.140
The planner chains the actions together according to the goals and starting states to determine which

04:13.140 --> 04:14.610
plans are achievable.

04:14.640 --> 04:20.910
The planner uses the aStar algorithm to find the best plan using the cost values.

04:21.300 --> 04:27.690
Once a plan has been generated, the agent goes about achieving it using a very, very simple, finite

04:27.690 --> 04:33.810
state machine that basically moves the agent to where the action needs to take place and then performs

04:33.810 --> 04:34.680
the action.

04:34.860 --> 04:40.440
The agent works its way along the chain of actions until the goal has been achieved before each action

04:40.440 --> 04:41.100
is performed.

04:41.100 --> 04:43.790
It is always checked to see if it is still valid.

04:43.800 --> 04:47.700
If not, the entire plan is discarded and another one is generated.

04:47.730 --> 04:53.250
The beauty of hope is that more and more actions can be added to the pool available to the agent, and

04:53.250 --> 04:55.830
these will automatically be picked up by the planner.

04:55.860 --> 05:01.860
This means very little extra programming to recognize graphs like the ones in complete set ups of finite

05:01.860 --> 05:06.360
state machines as the graphs are generated on the fly by the planner.

05:06.720 --> 05:13.140
This makes scope a very powerful and flexible option for programming the behaviors of your NPCs.
