Navigation: Overview >> Working Group on Goal-oriented Action Planning

Working Group on Goal-oriented Action Planning

The goals of the Goal-orient Action Planning (GOAP) working group are somewhat different than those of the other groups due to the fact that GOAP is not a commonly used AI technique in today's games. Our group believes that the benefits of applying a GOAP architecture to games make it superior to more common techniques such as Finite State Machines (FSM) and Rule-based Systems (RBS). We are attempting to design an interface that will be appealing to game developers who have not previously employed a GOAP architecture, and extensible to others who would like more advanced features.

We think that GOAP addresses important issues that game developers are facing as the scale of game development increases. Specifically, we think the benefits are:

Goals

We have been focusing on our requirements specification, keeping the following long-term goals in mind:

This year, we have taken steps to arrive at a common understanding of what we mean by GOAP, and determine the simplest set of interface requirements that would be useful to game developers. The minimal interface will be useful to the maximum number of developers. Once more developers are using GOAP, the interface can be extended with more advanced features. These are the steps we have taken:

Concepts and Terminology

In order to nail down the requirements of our GOAP interface, we first needed to define some terms. In particular, we needed to define Goal, Action, and Plan. Our definitions are similar to those found in PDDL (a current planning technology standard for modeling planning tasks in academia). We define these terms as follows:

Goal: A goal is anything that an agent needs to satisfy. Satisfaction is defined by variables that must be true, or that should have a given value, for the state of the world in which to consider the planning task complete. An agent may try to satisfy the single most relevant goal, or multiple goals at once.

Action: An action is an atomic behavior that contributes to the satisfaction of a goal or multiple goals. Actions have a variable number of effects and preconditions. Effects define how executing the action will change the state of the world. Preconditions define aspects of the state of the world that must be true prior to executing this action.

Plan: A plan is a valid sequence of actions that, when executed in the current state of the world, satisfies some goal or multiple goals. A sequence of actions is valid if each action's preconditions are met at the time of execution. The planner attempts to find an optimal plan, according some cost metric per action. The planning process cannot manipulate the actual state of the world. Instead the planner operates on a copy of the word state representation that can be modified as the planner evaluates the validity of all possible sequences of actions.

Examples

Once we defined our terms, we found it useful to put the pieces together into an example of how planning could truly be used in a current, commercial game. Our first example describes a situation common in any action games. We later decided that using the Sims as a standard example provides us with a wider range of planning opportunities.

Action game example:
Let's say we have an agent that wanders around repairing things when no threat is present, and fires a weapon when a threat is in view. The agent needs to holster his weapon while repairing things, and draw his weapon to fire.

The agent has 2 Goals:
GoalRepairObject
GoalKillEnemy

There are 5 available Actions: 

1) ActionFixObject
PreConditions: kKey_AtObject = Variable
kKey_Armed = FALSE
Effects: kKey_FixedObject = Variable

2) ActionGotoObject
PreConditions: None
Effects: kKey_AtObject = Variable

3) ActionHolsterWeapon
PreConditions: kKey_Armed = TRUE
Effect: kKey_Armed = FALSE

4) ActionDrawWeapon
PreConditions: kKey_Armed = FALSE
Effect: kKey_Armed = TRUE

5) ActionFireWeapon
PreConditions: kKey_Armed = TRUE
Effect: kKey_TargetDead = TRUE

Goal: GoalRepairObject
If the agent is aware of an object that needs repair, GoalRepairObject returns some positive value for its current relevance. Otherwise, it returns 0.0

If GoalRepairObject activates, the agent needs to satisfy the WorldState: kKey_FixedObject = ObjectID
where ObjectID is the ID of the object that needs repair.

The Goal now tries to formulate a plan that satisfies this WorldState. This is what the Goal WorldState looks like at each step in the planner:

Start Planning:
Goal: kKey_FixedObject = ObjectID

Apply: ActionFixObject
Goal: kKey_FixedObject = ObjectID (SOLVED)
kKey_AtObject = ObjectID
kKey_Armed = FALSE

Apply: ActionHolsterWeapon
Goal: kKey_FixedObject = ObjectID (SOLVED)
kKey_AtObject = ObjectID
kKey_Armed = FALSE (SOLVED)

Apply: ActionGotoObject
Goal: kKey_FixedObject = ObjectID (SOLVED)
kKey_AtObject = ObjectID (SOLVED)
kKey_Armed = FALSE (SOLVED)

So, the planner has found a sequence of actions that takes the WorldState from the true current WorldState to the solved Goal WorldState. The sequence of action to satisfy the Goal is:
ActionGotoObject
ActionHolsterWeapon
ActionFixObject

Once this Plan is validated, the agent begins to execute it. When an Action activates, it runs a virtual ActivateAction() that could do anything. Usually it sets the agent's state to animate or navigate. When an Action completes, it applies its Effects to the real WorldState of the agent.

When GoalRepairObject is satisfied, it deactivates. If the agent is aware of anything else to fix, it reactivates and plans again.

Goal: GoalKillEnemy
If the agent can see an enemy, GoalKillEnemy returns some positive value for its current relevance. Otherwise, it returns 0.0

If GoalKillEnemy activates, the agent needs to satisfy the WorldState:

kKey_TargetDead = TRUE

This is what the Goal WorldState looks like at each step in the planner:

Start Planning:
Goal: kKey_TargetDead = TRUE

Apply: ActionFireWeapon
Goal: kKey_TargetDead = TRUE (SOLVED)
kKey_Armed = TRUE

Apply: ActionDrawWeapon
Goal: kKey_TargetDead = TRUE (SOLVED)
kKey_Armed = TRUE (SOLVED)

The planner has found a sequence of actions that takes the WorldState from the true current WorldState to the solved Goal WorldState. The sequence of action to satisfy the Goal is:
ActionFireWeapon
ActionDrawWeapon

The Sims example:

  1. The player has a set of numerical characteristics. These may change on their own, and this rate may change over time.
  2. There are Objects. Some Objects may be carried (there is a 'carryable' flag). Some Objects may contain other objects (you can ask an object if it will accept another).
  3. There are six primitive actions:
    1. Movement actions (move to an object),
    2. Purchase actions (buy an object),
    3. Discard actions (remove an object from the game),
    4. Use actions (each object may have more than one 'use' action available),
    5. Pick-up action (hold a carryable object, removing it from an existing object)
    6. f. Put-down action (place a held object in another object). Each action has a duration (e.g. movement has a distance to move, purchasing is instant in the Sims world), and a target object.
  4. Using an object can alter the properties of a character in a well defined way. It can also alter the object, or the contents of the object (e.g. using a cooker containing a chicken produces a cooked chicken).
  5. Objects may appear and disappear at specific times (e.g. the car to take you to work can only be 'used' while it is outside).

Goals in the example are given as a combination of: Personal Characteristic ranges to achieve

Mapping the ontology of the Sims:

This approach allows both a graphical and command-line implementation. It would allow the problem to be scaled from very simple (few objects and use actions) to very complex (playing the whole Sims game). It would be very simple to code up the game interface (a hundred lines of code or so). The Goals are then satisfied by formulating a sequence of Actions (purchase, use, move, etc). If all of an Agents attributes are values between 0 and 100, a Goal might be to get Hunger below 15, or get Relaxation above 75. Everything else is just a means to an end.

For example, if an Agent wants Hunger to fall below 15, he could either:
Go to the store, buy food, and cook it
- OR -
Get another Agent to fall in love with him, and cook for him!

Agents could plan for both the short and long term. Short term, buying food and eating works well, but long term reading books to get a better job to afford a maid will supply the Agent with food more regularly in the long term.

Requirements Specification

Below is our most recent iteration of the requirements specification.

GOAP Requirements Document v0.4
===============================
We would like to define an Application Programming Interface that:

1. Supports planning for real-time behavior of agents in a game.
1.1 Supports specifying a set of Goals per agent.
1.2 Supports specifying a set of Actions per type of agent.
1.3 Provides a means of generating a complete or partial plan given some symbolic Goal(s) to satisfy.
1.4 Supports specifying an Initial State per agent (what s/he knows about the world at planning time) 
1.5 Supports specifying planning resource constraints (e.g. memory, execution time).
1.6 Supports specifying domain resource constraints (e.g. money, game world time).
1.7 Supports specifying a cost metric to optimize (e.g. money, game world time, enjoyment)
1.8 Supports specifying a partially ordered set/s of Actions to be performed as a plan.

2. Supports defining a Goal in terms of some state of satisfaction.
2.1 Supports symbolic representation of the satisfaction state.

3. Supports defining an Action in terms of the Action's preconditions and effects.
3.1 Supports symbolic preconditions for the planner.
3.2 Supports contextual preconditions that depend on real-time game world requirements.
3.3 Supports symbolic effects for the planner.
3.4 Supports contextual side-effects that affect the game world.
3.5 Supports associating a set of cost metrics with the execution of an Action.
3.6 Supports specifying a duration for the execution of an Action.

4. Supports querying the status of the current plan.
4.1 Supports querying to determine if a plan is complete.
4.2 Supports querying to determine is a plan is still valid.
4.3 Supports querying the validation of an Action during execution.
4.4 Supports querying for the completion of an Action's execution.

Future Extensions:
- Specification of heuristics for Action and Goal selection.
- Associating probabilities with selection of Actions.
- Specification of Goal selection interface.
- Querying to determine if a plan is interruptible.

Appendix: Design Decisions

In the process of fleshing out the requirements for our interface, we determined that we were really looking at three separate systems:

  1. A goal selection interface that weighs up relevance, probabilities, and so on, and decides which goal to plan towards.
  2. A planner that takes a goal and plans a series of actions to achieve it.
  3. An action interface for carrying out, interrupting, and timing actions that characters can carry out.

This separation allows a good deal of modularity, which we feel will be essential to the interface's adoption. However, incorporating all of these systems into our initial interface adds complexity, and forces some design decisions that may not please all developers equally. We decided to focus our first version of the interface on (2), and leave (1) and (3) out for now.

In addition, there are various extensions that we decided to omit initially:

Links and References

Group Members

Current members of the working group on goal-oriented action planning:

Navigation: Overview >> Working Group on Goal-oriented Action Planning