WEBVTT

0
00:10.140 --> 00:16.620
Goal-Orientated Action Planning (or GOAP for short) is an A.I. technique that was devised by Jeff Orkin of

1
00:16.620 --> 00:18.870
MIT in the early 2000s.

2
00:18.870 --> 00:20.860
It was successfully applied in the game

3
00:20.860 --> 00:23.970
F.E.A.R. to control the behavior of the NPCs.

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

5
00:30.480 --> 00:35.400
GOAP has all the elements of a Finite State Machine but works with them very differently.

6
00:35.400 --> 00:39.000
For example, the Finite State Machines (as you've seen before)

7
00:39.030 --> 00:45.690
define behaviors and conditions to drive the NPC at fulfilling some goal. To achieve this with a Finite

8
00:45.690 --> 00:46.430
State Machine,

9
00:46.440 --> 00:50.730
you could have one massive graph or divide it up into smaller units.

10
00:50.790 --> 00:56.580
GOAP also uses graphs for its processing but differs from Finite State Machines in that the actions

11
00:56.580 --> 00:58.280
and goals are decoupled.

12
00:58.530 --> 01:03.080
Actions are 'free elements' within the system that are mixed and matched to meet goals

13
01:03.150 --> 01:08.580
when they are presented. Instead of having a set list of actions that need to be performed to achieve

14
01:08.580 --> 01:12.810
a goal, GOAP allows for numerous solutions to be chosen from.

15
01:12.840 --> 01:19.320
So instead of a system that looks like this, in GOAP, all the links are removed. Then when a goal is presented,

16
01:19.380 --> 01:25.050
an appropriate course of action can be chosen from all of the available tasks based on the state of the

17
01:25.050 --> 01:26.850
agent and the world.

18
01:26.850 --> 01:33.030
For example, if an agent were asked to kill an enemy and it DIDN'T have a weapon, it could choose a physical

19
01:33.030 --> 01:33.930
fight.

20
01:33.930 --> 01:41.510
However, if it DID have a weapon, a different set of actions would become available. Every action in GOAP

21
01:41.610 --> 01:47.460
has a 'Precondition' and an 'Effect'. The Precondition is a state that must be met before the action can

22
01:47.460 --> 01:48.750
take place.

23
01:48.780 --> 01:55.290
The Effect is how the action leaves the state of the agent (or the world) after it has occurred. A set

24
01:55.290 --> 02:01.290
of actions forms a puzzle/set of dominoes where the Preconditions can be matched with Effects

25
02:01.410 --> 02:06.030
and the Effects matched with Preconditions to create 'Action Chains'.

26
02:06.030 --> 02:07.910
Let's look at an example.

27
02:08.100 --> 02:09.690
Consider this set of actions.

28
02:09.750 --> 02:13.310
If you take a close look, you will see they focus on eating.

29
02:13.440 --> 02:19.890
If you take a closer look, you might be able to see 2 plans that you could form yourself (1 for ordering

30
02:19.890 --> 02:23.160
pizza and 1 for baking). An agent

31
02:23.160 --> 02:27.150
with these actions won't do anything until presented with a goal.

32
02:27.180 --> 02:31.750
In this case lets trigger the goal 'Hungry = false'.

33
02:31.800 --> 02:35.960
The goal is the 'end state' of the agent NOT the 'starting state'.

34
02:35.970 --> 02:42.960
If you think about it, a recurring human goal is to have 'Hungry = false' as often as possible.

35
02:42.990 --> 02:48.690
Plans can generally only occur when the world and/or the agent are in a particular state.

36
02:48.690 --> 02:55.090
For this example, let's add 2...'hasIngredients = true' and 'hasPhoneNumber = true'.

37
02:55.110 --> 02:56.460
The planning stage in GOAP

38
02:56.520 --> 03:00.300
always works backwards from the goal, to see if it is achievable.

39
03:00.300 --> 03:04.950
It does this by matching the Effects with Preconditions into a chain.

40
03:04.980 --> 03:07.770
It works all the way back to the World States.

41
03:07.770 --> 03:12.430
If it can't find a matching World State at the end, the plan is abandoned.

42
03:12.450 --> 03:15.810
In this example, there are 2 possible plans available.

43
03:15.810 --> 03:18.940
'Order a pizza' and 'Bake something to eat'.

44
03:19.020 --> 03:21.280
Notice the reuse of the 'Eat' action.

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

46
03:27.270 --> 03:32.000
As long as the Preconditions and Effects fit together, any actions can be chained together.

47
03:32.160 --> 03:34.550
Now that we have 2 plans that will achieve the goal,

48
03:34.560 --> 03:36.250
which one do we choose?

49
03:36.330 --> 03:41.730
Simple! We add a cost to the plans. We might assign each action a monetary cost.

50
03:41.730 --> 03:43.510
In this case, the pizza plan

51
03:43.530 --> 03:47.750
works out dearer, assuming we already have the ingredients for baking.

52
03:48.030 --> 03:51.690
We might instead opt for a time-based cost as well.

53
03:51.690 --> 03:58.660
This would make the baking option more costly. With costs assigned to each plan, when there are multiple,

54
03:58.740 --> 04:05.400
the cheapest one can be selected first. If there are multiple plans with the same lowest cost, then one

55
04:05.400 --> 04:12.690
can be picked at random. A conceptualization of a GOAP system looks like this, with Actions, Goals and

56
04:12.690 --> 04:15.310
World States being fed into a Planner.

57
04:15.600 --> 04:20.880
The Planner chains the Actions together according to the Goals and starting States, to determine which

58
04:20.880 --> 04:22.520
plans are achievable.

59
04:22.590 --> 04:28.770
The Planner uses the A* algorithm to find the best plan using the cost values.

60
04:29.190 --> 04:35.670
Once a plan has been generated, the agent goes about achieving it using a very, very simple Finite State

61
04:35.670 --> 04:41.670
Machine that basically moves the agent to where the action needs to take place and then performs the

62
04:41.670 --> 04:42.780
action.

63
04:42.780 --> 04:48.180
The agent works its way along the chain of actions until a goal has been achieved. Before each action

64
04:48.180 --> 04:48.890
is performed,

65
04:48.900 --> 04:54.600
it is always checked to see if it is still valid. If not, the entire plan is discarded and another one

66
04:54.600 --> 04:55.650
is generated.

67
04:55.650 --> 05:00.990
The beauty of GOAP is that more and more actions can be added to the pool available to the agent and

68
05:00.990 --> 05:03.720
these will automatically be picked up by the Planner.

69
05:03.720 --> 05:09.570
This means very little extra programming to recognize graphs like the ones in complete set-ups of

70
05:09.570 --> 05:14.610
Finite State Machines, as the graphs are generated on-the-fly by the Planner.

71
05:14.610 --> 05:21.010
This makes GOAP a very powerful and flexible option for programming the behaviors of your NPCs.