Notes on PDDL

Modelling Domains using PDDL

These notes are intended to give some background for those of you who may be unfamiliar with planning and planning terminology.

Planning Background

In Planning the task for the planner is to achieve some objective/goal from some initial state of aworld (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 term 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 need only be a partial description of a state so long as it describes the desired state of any objects that 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.

Planning for Interactive Storytelling

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).

PDDL examples: Goldfinger and Madame Bovary

For both story worlds we've included a domain and problem file written in pddl (with a pddl suffix) and for the domain files there is also a text version thats been translated from the pddl source which we hope is a bit more readable (with a text suffix).

Goldfinger

The domain and problem cover the initial phase of the story (up to the end of card game and golf game when Bond has been threatened off by Goldfinger). In the problem file there is one goal included which is (feeling-of-power goldfinger high) but given that this is already true in the initial state (ie at the outset goldfinger is feeling powerful) no planning needs to be done. In the problem file we have included a number of constraints which force the planner to reason about solving some intermediate goals and in order which reflects the original narrative.

The constraints are:

(always (at m london))
(always (assistant goldfinger jill))

and this requires, for example, that m is always in London and which in turn forces the planner to reason about getting bond to London to be given his mission.

(sometime (seduced bond jill))

This requires that at sometime bond must seduce jill but there is no requirement about the ordering of this relative to other things (other than it is made true at some stage of the plan.

(sometime-after
(got-mission bond) (won-cards bond goldfinger card-game))

This requires that bond gets his mission at some point in the plan before bond wins the game of cards against goldfinger (and that both getting the mission and bond winning cards become true at some point).

Madame Bovary

The Bovary model is also supplied as two files: bovary_domain.pddl and bovary_problem.pddl.