PDDL is an action-centred language, inspired by the well-known STRIPS formulations of planning problems. At its core is a simple standardisation of the syntax for expressing this familiar semantics of actions, using pre- and post-conditions to describe the applicability and effects of actions. The syntax is inspired by Lisp, so much of the structure of a domain description is a Lisp-like list of parenthesised expressions. An early design decision in the language was to separate the descriptions of parameterised actions that characterise domain behaviours from the description of specific objects, initial conditions and goals that characterise a problem instance. Thus, a planning problem is created by the pairing of a domain description with a problem description. The same domain description can be paired with many different problem descriptions to yield different planning problems in the same domain. The parameterisation of actions depends on the use of variables that stand for terms of the problem instance -- they are instantiated to objects from a specific problem instance when an action is grounded for application. The pre- and post-conditions of actions are expressed as logical propositions constructed from predicates and argument terms (objects from a problem instance) and logical connectives.
Although the core of PDDL is a STRIPS formalism, the language extends beyond that. The extended expressive power includes the ability to express a type structure for the objects in a domain, typing the parameters that appear in actions and constraining the types of arguments to predicates, actions with negative preconditions and conditional effects and the use of quantification in expressing both pre- and post-conditions. These extensions are essentially those proposed as ADL [PednaultPednault1989].
Although the original definition of the PDDL syntax was not accompanied by a formal semantics, the language was really a proposal for a standard syntax for a commonly accepted semantics and there was little scope for disagreement about the meaning of the language constructs. Two parts of the original language proposal for which this claim fails are an attempt to offer a standard syntax for describing hierarchical domain descriptions, suitable for HTN planners and the subset of the language concerned with expressing numeric-valued fluents. The former was an ambitious project to construct a syntax in which the entire structure of domains using hierarchical action decompositions could be expressed. In contrast to STRIPS-based planning, the differences between planners using hierarchical decomposition appear to be deeper, with domain descriptions often containing structures that go beyond the description of domain behaviours (for example, SHOP [Nau, Cao, Lotem, Muñoz-AvilaNau et al.1999] often uses mechanisms that represent goal agendas and other solution-oriented structures in a domain encoding). This diversity undermined the efforts at standardisation in hierarchical domain descriptions and this part of the language has never been successfully explored.
The syntax proposed for expressing numeric-valued fluents was not tested in the first use of the language (in the 1998 competition) and, indeed, it underwent revision in the early development of the language. The second competition in 2000 also avoided use of numeric-valued fluents, so a general agreement about the syntax and semantics of the numeric-expressivity of the language remained unnecessary. McDermott's original PDDL provides support for numbers by allowing numeric quantities to be assigned and updated. The syntax of numeric-valued fluents changed between the PDDL manuals 1.1 and 1.2 [McDermott the AIPS-98 Planning Competition CommitteeMcDermott the AIPS-98 Planning Competition Committee1998] and the later AI Magazine article on PDDL [McDermottMcDermott2000]. McDermott presented a version of numeric fluents used in PDDL in the article in AI Magazine drew which could be taken as a definitive statement of the syntax. An example using numeric fluents, presented by McDermott drew, is shown in Figure 1. This action models an action from the well-known jugs-and-water problem, allowing the water in one jug to be emptied into a second jug provided that the space in the second jug is large enough to hold the water in the first. The effect is a discrete update of the values of the current contents of the jugs by an assignment (denoted here by the change token).
 |
Even without the numeric extensions, PDDL is an expressive language, capable of capturing a wide variety of interesting and challenging behaviours. Figure 2 illustrates how PDDL can be used to capture a domain in which a vehicle can move between locations, consuming fuel as it does so.
It can be seen in the example that PDDL includes a syntactic representation of the level of expressivity required in particular domain descriptions through the use of requirements flags. This gives the opportunity for a planning system to gracefully reject attempts to plan with domains that make use of more advanced features of the language than the planner can handle. Syntax checking tools can be used to confirm that the requirements flags are correctly set for a domain and that the types and other features of the language are correctly employed. An example of a problem description to accompany the vehicle domain is shown in Figure 3. The example illustrates that the description of an initial state requires an exhaustive listing of all the (atomic) propositions that hold. Symmetric or transitive relations must be modelled by exhaustive and explicit listing of the propositions that hold. The use of domain axioms to simplify the description of domains that use such relationships has been considered, but remains an untested part of PDDL and therefore an unstable part of the syntax. PDDL domains are not case-sensitive, which is somewhat anachronistic in the light of standard practice in modern programming languages.
In the following sections we review the extensions made to PDDL in its development into PDDL2.1, the version of the language used in the third International Planning Competition.
