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

Working Group on Goal-oriented Action Planning

This group has been slow to coordinate activities, due to heavy work-load commitments of its former coordinator, Ruth Aylett, and of its recently appointed new coordinator, Derek Long. This report summarises the most important elements of the discussion that has been pursued so far and outlines the directions that will be explored in the medium term.

What is Planning?

Most of the discussion of the group has centred on the role of action planning in games, and the problem of defining terms. Planning, actions and goals are all terms that are used by different people in different ways within the group, resulting from the diversity of backgrounds from game developers to academics. Furthermore, the difference between action planning and other techniques for action-selection like FSMs, or decision trees, was not always clear. General agreement has been reached that goals are conditions that an agent desires to bring about and that actions are the means that agents have to achieve these goals. Planning is the problem of assembling a coherent programme of actions to achieve specified goals. In contrast to that, rule based systems, finite state machines, or decision trees represent hard-wired sets of actions and correspond more to reactive, fixed plans to deal with specific situations. Common drawbacks of these techniques are missing 'individualism', too shallow goal hierarchies, repetitive failures, or other obvious FSM-like behaviours. The advantage of goal-oriented action planning over these techniques is the ability to provide more flexible and more diverse behaviours for NPCs, since plans are constructed 'online' from atomic actions and adapted specificially to the current goal.

There are still important open questions in this overall framework: a planner might need to work with abstractions of actions if it is to produce a plan that is robust to possible changes in the world and fast enough to construct. For example, there is little point planning a detailed programme of actions to, say, capture the enemy flag, using actions at the level of move to position X, face direction D, extend right arm and so on, since the opponent will be responding in a way that undermines much of such a plan before it is executed. On the other hand, a plan at an abstract level: deploy decoy move on left flank, deploy strike team in deep penetration around right flank, on signal, send in sprint team with heavy cover in scattered formation and so on, can be robust to responses by the opponent (that is, this plan anticipates certain forms of response and can still be executed regardless of the details of the response, provided that the anticipation is broadly valid).

Execution of a plan is then an interesting challenge in mapping the high-level abstract actions into lower level executable steps. This might be achieved through some sort of mapping to finite-state machine models of execution behaviours.

Talking to Planners

If we assume that the objective of a planner is to put together a coherent programme of actions, there still remain the challenges of communicating to and from the planner. A planner must be told the current state of the world (as it is known by the agent planning) and it must know, or have access to, descriptions of the actions available to the agent at the appropriate level of abstraction for the plan being sought. It must also be told the goals. Generation of goals is non-trivial and there are many questions about why certain goals might be adopted. Once a plan is constructed, communicating the plan to the external executive is also a challenge. There must be means to monitor the execution of a plan and the abstractions will make this harder because it will make it difficult to know when an action is completed - the translation of an abstract action into concrete steps must be flexible enough to account for different possible states of the world. For example, when is the action of deploying a decoy move completed? When some set of team members is in place? Where must they be precisely to count as deployed? Must they have been detected? How can we be sure that they are decoying the opponent?

One language that has been proposed for communicating with a planner is PDDL, used in the academic planning community. There are many reasons why this is probably inappropriate for specialised target domains such as in games, but speed is obviously one crucial issue: there is no way that game time can be spent constructing and parsing PDDL documents. The actions available to an agent in a particular game domain will be hard-wired into the planning system for that game, in order to achieve efficient performance. Of course, there might be a role for PDDL or something like it in game development, to be compiled into dedicated planner machinery for a given domain.

Planning Strategy

Planning in the academic community has traditionally been concerned with the domain-independent taks of constructing programmes of activity from primitive action descriptions, using weak-heuristic search techniques. Much work on planning has also considered more scripted activity such as hierarchical task network style planning (HTN planning). In considering the ways in which planning can play a role in games it is important to question what degree of flexibility is really sought and what form of planning is really necessary. It is important that agents exhibit intelligent goal-directed behaviour, but not necessarily that they are capable of constructing near-optimal plans in all situations. Sensible default behaviours to enter safe states from which deliberation can proceed to identify new plans might be just as effective as an ability to replan from arbitrary initial states.

It is extremely unlikely that heavy-duty computation can be expended in planning, so search intensive approaches are unlikely to find favour. Anytime algorithms might be more promising, but there still needs to be a good performance guarantee for time-to-first-plan. On the other hand, once a plan is in place and an agent is pursuing it, there is likely to be some opportunity to continue to develop and extend the plan. Thus, a good forward-planning strategy is likely to be more promising than a backward-planning strategy, since it will generate actions for execution quickly before completing the entire plan. The combinatorial explosion involved, however, renders this less directed forward-planning approach often infeasible.

Plans for the Future

The group needs to progress these ideas and this will commence with a short term activity to identify concrete scenarios in which planning can play a role, together with a clear description of what would be a useful plan to have constructed in examples of these scenarios. Once the role of plans and planning has been more clearly identified, further activities will be focused on constructing the framework for communication with a planner, with a view to clear separation of the roles of planning, plan-dispatch, plan-execution monitoring and, possibly, replanning.

Group Members

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

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