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

Working Group on Goal-oriented Action Planning

The goal of this working group is to create an interface standard specification for real-time Goal-oriented Action Planning (also called AI Planning or Action Planning), such that a computer game can easily call modules providing planning functionality. A planning system takes as input the current state of the world, goals to be satisfied and possible actions to be executed, and generates a plan, which is a valid sequence of actions that, when executed in the current state of the world, satisfies the given goals. We will not go into further details here, however, as the main purpose of this document is an update about our progress.

Our group has made considerable progress within the last year (over 200 messages were posted to our forum), and we are quite close to an actual interface specification. Many discussions are of course still in progress, and we will only briefly touch such matters in the following.

General Approach

A planning domain is initially read in. After this has happened, single planning problems can be cast for solution. The solution of a planning problem is an iterative process in which small amounts of computation time are granted for a revision/improvement of the current solution structures (until a solution is found or the process is aborted). The piecewise computation is necessary because the solution of some planning problems requires substantial time. This time cannot be granted in one step because it would hurt other game systems' real-time performance. The stepwise computation, however, requires that external changes/updates of the world that happen in between single planning iterations can be incorporated during a planning process.

For the use of a planning module, i.e., our interface, the following picture provides a preliminary overview/example of the control flow and functions. The specifications of the functions can be found in Section [Interface Functions]. Note that anything related to the use of plans is not yet included.

The domain definition and other information specific to the concrete planning problem will be represented by XML-like data structures (see comments on OWL in Section [Miscellaneous]). In contrast, specification formats like PDDL use a LISP-like format. We expect, however, that people that use our interfaces will hardly be familiar with LISP.

Glossary

The following definitions show some glossary updates, which may help you to understand the descriptions. However, we recommend to that you skip it for now and only check it if you actually want to look up a term.

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.

Effect
Propositions that will be changed when an action is executed.

Goal
A sub-state of a game environment (attached to a character or the world) that a plan is intended to achieve and that when successfully reached terminates the behavior initiated to achieve it.

HTN
Hierarchical Task Network. A form of planning that decomposes high-level tasks into simpler ones.
More information can be found at: http://www.cs.umd.edu/~nau/cmsc722/notes/chapter11.pdf

PDDL
Planning Domain Definition Language. A standardized action-centered language, inspired by STRIPS and syntactically similar to LISP. Designed as a common way of representing planning problems.
An overview can be found at: http://www-2.cs.cmu.edu/afs/cs/project/jair/pub/volume20/fox03a-html/node2.html
The PDDL2.2 specification can be found at: http://ls5-www.cs.uni-dortmund.de/~edelkamp/ipc-4/DOCS/pddl2.2.ps.gz

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 world state representation that can be modified as the planner evaluates the validity of all possible sequences of actions.

Planning Domain
A planning domain consists of a set of actions. Each action may be executed only if meets its preconditions, and has some particular set of effects on the state of the world.

Planning Iteration
A partial execution of computing a (partial) plan. A planning module might need multiple planning iterations to compute a (partial) plan. The duration or stopping criteria of a single planning iteration can be configured by the user of a planning module. This configuration is not part of our interface but can be done in a module-specific way.

Planning Module
The part of the code that has to compute (partial) plans, i.e., which provides the planning functionality.

Planning Process
A specific planning problem ("threat") in its current solving state, which is worked on.

Planning Problem
A planning problem consists of specific goals and instantiations of plan variables for a planning domain. A planning process can solve such a problem, i.e., produce a valid plan that satisfies the given goals.
Example: The agent has cooking skills and a kitchen (the planning domain). He wants to cook dinner (the goal) and thinks that there is milk in the fridge (an instantiation of a plan variable).

Precondition
Preconditions define aspects of the state of the world which must be true prior to executing the action. For example, a door must be unlocked before it can be opened.

Real World Interface
The actual state of the world in which an agent belongs. This contrasts with the agents view of the world as defined by simulated world interface

Simulated World Interface
An agents view, or interpretation, of the world in which it belongs. This may not be the actual state of the world, as defined by real-world interface. For example, an agent would believe there to be Milk in the fridge if it was unaware that another agent drank it.

 

Interface Functions

In this section, preliminary functions for basic interaction with a planning module are specified. Note that the function definitions are still very much under revision, and that you should not worry about pointers vs. real objects etc. Many functions are also still missing, e.g., to inform the planning module about value updates, or functions for checking validity of a plan. We show this only to give you an approximate idea of our direction.

 

Initialization

  

PlanningModule.loadDomain()

This function presents a planning domain to the planning module and requests it to internally store this domain. An identifier for the domain that was loaded is returned. 


DomainID dID =
  PlanningModule.loadDomain( 
    XMLDomainDefinition dDef );
returns:   DomainID dID
An identifier for the planning domain that was loaded. This identifier can be used in following interactions with the planning module to reference this domain.
XMLDomainDefinition dDef
The definition of the planning domain to be loaded.

Example application: 


XMLDomainDefinition dDef = [structures not yet defined]
DomainID dID = PlanningModule.loadDomain( dDef );

  

PlanningModule.initializePlanningProcess()

Generates and initializes a planning process, which is responsible for solving a specific planning problem. An identifier for the planning process that was generated is returned. 


PlanningProcessID ppID =
  PlanningModule.initializePlanningProcess( 
    DomainID dID , 
    [structures not yet defined] vInit , 
    [structures not yet defined] g );
returns:   PlanningProcessID ppID
An identifier for the planning process that was generated. This identifier can be used in following interactions with the planning module to reference this planning process.
DomainID dID
An identifier of the planning domain that is to be used for the planning process. This identifier has to be generated by calling PlanningModule.loadDomain() before.
[structures not yet defined] vInit
This XML structure initializes specific variables of the planning domain.
[structures not yet defined] g
This XML structure defines the goals that the resulting plan of the planning process should fulfill.

Example application: 


...
DomainID dID = PlanningModule.loadDomain( dDef );
[missing: generation of vInit]
[missing: generation of g]
PlanningProcessID ppID = initializePlanningProcess( dID , vInit , g );

 

Plan Generation

  

PlanningModule.executePlanningIteration()

Instructs the planning module to advance the plan generation for one planning iteration. The time constraints for a planning iteration are dependent on the specific planning module (and might be set by middleware-specific functions). It is returned whether a correct plan was found that satisfies the planning process' goals. If this is not the case, it might be possible to generate a plan by repeatedly calling this function. 


bool planReady =
  PlanningModule.executePlanningIteration( 
    PlanningProcessID ppID );
returns:   bool planReady
If a plan was found that satisfies the planning process' goals, true is returned, and false if a plan could not be generated in this planning iteration.
PlanningProcessID ppID
An identifier of the planning process that is to be advanced. This identifier has to be generated by calling PlanningModule.initializePlanningProcess() before.

Example application: 


...
PlanningProcessID ppID = initializePlanningProcess( dID , vInit , g );
...
bool planReady = false; 
while( myGameModule.stillEnoughTimeForNPCComputations() && !planReady )  
{
  planReady = executePlanningIteration( ppID ); 
}

 

Result Retrieval

  

PlanningModule.retrievePlan()

Retrieves a plan from the planning module. This plan is only available if the planning module has computed a correct plan (see PlanningModule.executePlanningIteration() function). Note that there is no guarantee that a correct plan exists even if PlanningModule.executePlanningIteration() returned true before because there might have been updates on the world state in the meantime. 


XMLPlanStructure plan =
  PlanningModule.retrievePlan( 
    PlanningProcessID ppID );
returns:   XMLPlanStructure plan
Describes the plan that has been computed. The function returns null if the planning process did not result in a correct plan yet.
PlanningProcessID ppID
An identifier of the planning process that has produced the plan. This identifier has to be generated by calling PlanningModule.initializePlanningProcess() before.

Example application: 


...
PlanningProcessID ppID = initializePlanningProcess( dID , vInit , g );
...
bool planReady = false; 
while( myGameModule.stillEnoughTimeForNPCComputations() && !planReady )  
{
  planReady = executePlanningIteration( ppID ); 
}

XMLPlanStructure plan = null;
if ( planReady ) 
{
  plan = PlanningModule.retrievePlan( ppID );
}

 

Cleanup

  

PlanningModule.endPlanningProcess()

Notifies the planning module that a planning process is terminated and all related resources can be released. 


void PlanningModule.endPlanningProcess( 
    PlanningProcessID ppID );
PlanningProcessID ppID
An identifier of the planning process that is being terminated. This identifier will not be valid anymore after the function call.

Example application: 


...
PlanningProcessID ppID = initializePlanningProcess( dID , vInit , g );
...
PlanningModule.endPlanningProcess( ppID );

  

PlanningModule.closePlanningDomain()

Notifies the planning module that a planning domain is not needed anymore and all related resources can be released. Note that all planning processes of this domain have to be ended before (see PlanningModule.endPlanningProcess()). 


void PlanningModule.closePlanningDomain( 
    DomainID dID );
DomainID dID
An identifier of the planning domain that is to be closed. This identifier will not be valid anymore after the function call.

Example application: 


...
DomainID dID = PlanningModule.loadDomain( dDef );
...
PlanningModule.closePlanningDomain( dID );

Miscellaneous

Group Members

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

Further group consultant(s): Richard Evans (Maxis / Electronic Arts)

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