PDDL2.1

PDDL -- the Planning Domain Definition Language -- is the standard language for the encoding of planning domains. The original version of the language was developed by Drew McDermott, with the help of the 1998 Planning Competition committee. Fahiem Bacchus selected a subset of the original language as the language for the 2000 competition. Maria Fox and Derek Long then extended the competition language to allow for numerical variables, and concurrent execution of durational actions (original PDDL already featured a form of numerical variables, which was however never put to use). The 2002 competition language, PDDL2.1, had the following features:

PDDL2.1 is separated into different levels of expressivity. Level 1 is ADL planning, level 2 adds numeric constructs, level 3 adds durational actions. (There is also a fourth level featuring continuous effects, but this has not been put to use in IPC-3, and will not be put to use in IPC-4.)

PDDL2.2

PDDL2.1 (more precisely, the first three levels of PDDL2.1) forms the basis for the IPC-4 language, called PDDL2.2. Like PDDL2.1, PDDL2.2 is divided into three levels corresponding to ADL, numeric, and durational planning. On top of the PDDL2.1 language features, two new, relatively moderate, constructs are added: derived predicates, and timed initial literals. A few explanatory words on these constructs are said below. A document describing the new language features, including a full BNF for PDDL2.2, can be downloaded here. PDDL2.2 was created in a discussion with the IPC-4 organizing committee, and at this point we would like to thank all the committee members for their valuabe contributions. The reason why the language extensions beyond PDDL2.1 are relatively moderate is that everybody on the committee felt that Fox and Long's PDDL extensions still posed a serious challenge to the community.

Derived Predicates

Derived predicates have been implemented in several planning systems in the past, including e.g. UCPOP. They are predicates that are not affected by any of the actions available to the planner. Instead, the predicate's truth values are derived by a set of rules of the form if formula(x) then predicate(x). The semantics are, roughly, that an instance of a derived predicate (a derived predicate whose arguments are instantiated with constants; a fact, for short) is TRUE iff it can be derived using the available rules. An example for a derived predicate is an ``above'' predicate in the Blocksworld, which can be derived by the following rule:

if on(x,y) OR (exists z: on(x,z) AND above(z,y)) then above(x,y)

Note that the ``above'' predicate captures a transitive closure (that of ``on''). This (expressing transitive closures) is also what derived predicates are used for in IPC-4.

Under the name ``axioms'', derived predicates were a part of the original PDDL language defined by McDermott for the first planning competition, but they have never been put to use in a competition benchmark (we use the name ``derived predicates'' instead of ``axioms'' in order to avoid confusion with safety conditions). Derived predicates combine two key aspects that make them a useful language extension:

Timed Initial Literals

Timed initial literals are a syntactically very simple way of expressing a certain restricted form of exogenous events: facts that will become TRUE or FALSE at time points that are known to the planner in advance, independently of the actions that the planner chooses to execute. Timed initial literals are thus deterministic unconditional exogenous events. Syntactically, we simply allow the initial state to specify -- beside the usual facts that are true at time point 0 -- literals that will become true at time points greater than 0. For example:

(:init (at 9 (shop-open)) (at 20 (not (shop-open))))

Timed initial literals are practically very relevant: in the real world, deterministic unconditional exogenous events are very common, typically in the form of time windows (within which a shop has opened, within which humans work, within which traffic is slow, within which there is daylight, within which a seminar room is occupied, within which nobody answers their mail because they are all at conferences, etc.).