In 1998 Drew McDermott released a Planning Domain Description Language, PDDL [McDermottMcDermott2000,McDermott the AIPS-98 Planning Competition CommitteeMcDermott the AIPS-98 Planning Competition Committee1998], which has since become a community standard for the representation and exchange of planning domain models. Despite some dissatisfaction in the community with some of the features of PDDL the language has enabled considerable progress to be made in planning research because of the ease with which systems sharing the standard can be compared and the enormous increase in availability of shared planning resources. The introduction of PDDL has facilitated the scientific development of planning.
Since 1998 there has been a decisive movement in the research community towards application of planning technology to realistic problems. The propositional puzzle domains of old are no longer considered adequate for demonstrating the utility of a planning system -- modern planners must be able to reason about time and numeric quantities. Although several members of the community have been working on applications of planning to real domains of this nature for some time [Laborie GhallabLaborie Ghallab1995,Ghallab LaruelleGhallab Laruelle1994,MuscettolaMuscettola1994,Drabble TateDrabble Tate1994,WilkinsWilkins1988] there has always been a gap between the modelling requirements of such domains and what can be expressed in PDDL. Application-driven planners come equipped with their own modelling conventions and black arts and, as a consequence, it is difficult to reproduce their results and to make empirical comparisons with other approaches, both of which are essential for scientific progress to be made.
The PDDL language provides the foundation on which an expressive standard can be constructed, enabling the domain models of the applications-driven community to be shared and motivating the development of the planning field towards realistic application. The third International Planning Competition, which took place in 2002, had the objective of closing the gap between planning research and application. As organisers of the third competition the authors therefore took the first step in defining an expressive language capable of modelling a certain class of temporal and resource-intensive planning domains. This had to be done both with an eye to the future and with awareness of the current capabilities of planners (it had to be possible for the language to be used by members of the community, or there would be no competitors). In this paper we describe the resulting language, PDDL2.1, in terms of its syntax, semantics and modelling capabilities.
PDDL2.1 has been designed to be backward compatible with the fragment of PDDL that has been in common usage since 1998. This compatibility supports the development of resources which help to establish a scientific foundation for the field of AI planning. Furthermore, McDermott's original PDDL provides a clean and well-understood basis for development and embodies a number of design principles that we considered it important to retain. PDDL2.1 extends PDDL in principled ways to achieve the additional expressive power following, as far as possible, McDermott's maxim ``physics, not advice'' [McDermottMcDermott2000]. We take this maxim to mean that a language should focus on expressing the physical properties of the world, not advice to the planner about how to search the associated solution spaces. Of course, any model of physical systems makes simplifying assumptions and abstracts behaviours at some level, so no model can be claimed to be purely physics and free of decisions that could influence the use of the model. We do not attempt to make strong judgements about what constitutes advice but try to implement the maxim by keeping the language as simple as possible. We make the following two guarantees of backward compatibility:
An important contribution made in the development of PDDL2.1 is a means by which domain designers can provide alternative objective functions that can be used to judge the value of a plan. The use of numbers in a domain provides a platform for measuring consumption of critical resources and other parameters. An example of a metric that can be modelled is that energy consumption must be minimized. This is very important for many practical applications of planning in which plan quality might be dependent on a number of interacting domain-dependent factors.
The organisation of the paper is as follows. In Section 2 we introduce non-specialist readers to the PDDL domain description language used in the planning research community. This background is given in order to provide the foundations for the numeric and durative extensions made in developing PDDL2.1. The paper then focusses on the specific extensions introduced: numeric expressions and durative actions. In Section 3 we start by explaining the syntax of numeric expressions and their use in action descriptions. We then explain, in Section 4, how metrics can be provided as part of the problem description so that the quality of a plan involving numeric change can be evaluated in terms appropriate to the problem domain. We present the syntax in which metrics are expressed and give examples.
In Section 5 the paper introduces the notion of durative action as a way of modelling the temporal properties of a planning domain. Both discretised and continuous durative actions are considered. The syntax is described and examples of modelling power and limitations are presented in both cases. Having given examples of the syntactic representation of durative actions we present a formal semantics for both discretised and continuous actions and for plans. Sections 6, 7, 8 and 9 provide the details. The semantics gives us a way of tackling the problem of confirming plan validity -- something that becomes an important issue in the face of concurrent activity. In Section 10 we describe the process by which plans were validated in the competition and discuss the complexity of the validation question for PDDL2.1. Finally, Section 11 describes some related work in the temporal reasoning community, in order to put the contributions made by PDDL2.1 into a wider context. A full BNF description of PDDL2.1 can be found in the appendix.
PDDL2.1 was developed for use in the third International Planning Competition in which competing planners demonstrated that many discretized temporal and metric models can now be efficiently handled by both domain-independent planners and those using hand-tailored control rules. For ease of reference in the competition we identified the features of PDDL2.1 with a series of levels of increasing expressive power. Thus, the STRIPS fragment of PDDL2.1 was referred to as level 1, the numeric extensions comprised level 2, the addition of discretised durative actions resulted in level 3, continuous durative actions resulted in level 4 and a final level, level 5, comprised all of the extensions of PDDL2.1 and additional components to support the modelling of spontaneous events and physical processes. Level 5 is not discussed in this paper but details can be found in earlier work by Fox and Long foxlpddl2. The competition focussed on the use of levels 1, 2 and 3 and did not use levels 4 or 5 because the planning technology was not at that stage sufficiently advanced to handle the additional complexities. Despite the fact that level 4 was not used in the competition we devote some discussion to it in this paper. We feel that level 4 presents some important immediate challenges for the planning community that affect the extent to which planning can be applied to real problems.
The purpose of this paper is to provide an overview of the new features introduced in PDDL2.1, discuss the rationale for our language choices and explain some of the issues that have arisen in trying to extend PDDL. Although we have provided the BNF for PDDL2.1 as an appendix, this paper is not intended to be either a language manual or a tutorial on the use of the language. For examples of the use of the language and other relevant materials, readers should consult archived resources currently held at http://www.dur.ac.uk/d.p.long/competition.html.