Pddl

IRIS Wiki - Computational Models - Pddl

Planning Background

In Planning the task for the planner is to achieve some objective/goal from some initial state of a world (a snapshot of the world). In order to achieve this task the planner is given: (i) a description of the world in terms of actions that can be performed in it; (ii) a description of a problem/task written in terms of an initial state and a goal. The solution to the task is a plan which consists of a collection of actions that perform that task.

Actions

Actions model the things that can change in the world. They specify what needs to be true in the state before the action is performed and what will be true in the state after it is performed. Note that there will be other aspects of the world that the action has no effect on. As an example, consider a transport planning world which includes an action called (drive truck london edinburgh) that requires that the truck is in london before the action can be performed and that after the action has been performed the resulting state of the world will have the truck in Edinburgh. The action doesn't say anything about the locations of any other trucks since they aren't relevant to the movement of truck.

Variables

An example action written using PDDL syntax is shown below:

(:action DRIVE-TRUCK
    :parameters
       (?t - truck ?from - location ?to - location ?d - driver)
    :precondition
    (and
       (at ?t ?from)
       (driving ?d ?t))
    :effect
    (and
       (not (at ?t ?from))
       (at ?t ?to)))
) 

This features variables: any text that starts with a ? is a variable. The variables of interest for an action are listed as parameters (e.g. ?t - truck) and they can be thought of as containers that can take on a value of an appropriate type (the type follows the variable, so in this example the type of ?t is truck. Part of the job of the planner is to reason about and select appropriate values for the variables in the actions. In the final plan that is output the name of each selected action is given with the values that have been chosen for solving this particular problem.

Problems

A specific problem is specified in terms of an initial state of the world and a goal state. The initial state of the world is required to be a complete snapshot of the world. For example, in the transport planning domain, the initial state would need to include a description of the locations of all objects that we were interested in, such as all trucks and all drivers. The goal state however only needs to be a partial description of a state as long as it describes the desired state of any object we are interested in.

Plans

The job of the planner (a piece of software) is to find a collection of actions, with some orderings between them, that when performed in an appropriate order will result in a state of the world in which the goal is true.

Application to Interactive Storytelling

Planning

Planning has been widely used as the technology of choice for narrative generation in IS since a narrative can be seen as a collection of actions with temporal orderings between them and once a domain model and problem instances have been specified for the story world any planner could be used to generate narratives. However there are still many open research questions to be addressed: both from a planning and an IS perspective. For instance, until recently the focus in much planning research has been to use the cost of plans as a measure of quality (i.e. those with the fewest actions) and clearly this is very important if we are planning the movement of trucks. But in some application areas, such as IS, we need different measures of plan quality. One recent extension to PDDL, which seeks to address this, is the use of constraints and preferences (constraints allow us to specify which things we want to be made true on the way to a goal and preferences are things which are desirable but not essential in the plan).

Examples

Teesside University has produced first versions of Goldfinger, Madame Bovary and The Merchant of Venice which are intended to give a feel for how domains and problems can be modelled using PDDL. To accompany these models please refer to notes on PDDL.

The Goldfinger model includes a [pddl domain file] (and a [domain file] written in a more text like format), a [problem file] and an [example plan] for this problem.

The Bovary model includes a [pddl domain file] (and a [domain file] written in a more text like format), a [problem file] and an [example plan] for this problem.

The Merchant of Venice model includes a [pddl domain file], a [problem file] and an [example plan] for this problem.

References

More information about the latest version of PDDL can be found in:

• Gerevini, A. & Long, D. (2006). Plan Constraints and Preferences in PDDL3: The Language of the Fifth International Planning Competition (2006). [1]

• Gerevini, A. & Long, D. (2005). BNF Description of PDDL3.0. http://www.cs.yale.edu/homes/dvm/papers/pddl-bnf.pdf (URL last accessed Sept. 27 2009).