Introduction

This paper describes PDDL+, an extension of the PDDL [McDermott the AIPS'98 Planning Competition CommitteeMcDermott the AIPS'98 Planning Competition Committee1998,Fox LongFox Long2003,Hoffmann EdelkampHoffmann Edelkamp2005] family of deterministic planning modelling languages. PDDL+ is intended to support the representation of mixed discrete-continuous planning domains. PDDL was developed by McDermott pddl as a standard modelling language for planning domains. It was later extended [Fox LongFox Long2003] to allow temporal structure to be modelled under certain restricting assumptions. The resulting language, PDDL2.1, was further extended to include domain axioms and timed initial literals, resulting in PDDL2.2 [Hoffmann EdelkampHoffmann Edelkamp2005]. In PDDL2.1, durative actions with fixed-length duration and discrete effects can be modelled. A limited capability to model continuous change within the durative action framework is also provided.

PDDL+ provides a more flexible model of continuous change through the use of autonomous processes and events. The modelling of continuous processes has also been considered by McDermott trentopaper, Herrmann and Thielscher handt, Reiter rayr, Shanahan shan, Sandewall sandewall1 and others in the knowledge representation and reasoning communities, as well as by Henzinger henzinger, Rasmussen, Larsen and Subramani rasmussen, Haroud and Faltings falts and others in the real time systems and constraint-reasoning communities.

The most frequently used subset of PDDL2.1 is the fragment modelling discretised change. This is the part used in the 3rd International Planning Competition and used as the basis of PDDL2.2. The continuous modelling constructs of PDDL2.1 have not been adopted by the community at large, partly because they are not considered an attractive or natural way to represent certain kinds of continuous change [McDermottMcDermott2003a,BoddyBoddy2003]. By wrapping up continuous change inside durative actions PDDL2.1 forces episodes of change on a variable to coincide with logical state changes. An important limitation of the continuous durative actions of PDDL2.1 is therefore that the planning agent must take full control over all change in the world, so there can be no change without direct action on the part of the agent.

The key extension that PDDL+ provides is the ability to model the interaction between the agent's behaviour and changes that are initiated by the world. Processes run over time and have a continuous effect on numeric values. They are initiated and terminated either by the direct action of the agent or by events triggered in the world. We refer to this three-part structure as the start-process-stop model. We make a distinction between logical and numeric state, and say that transitions between logical states are instantaneous whilst occupation of a given logical state can endure over time. This approach takes a transition system view of the modelling of change and allows a direct mapping to the languages of the real time systems community where the same modelling approach is used [Yi, Larsen, PetterssonYi et al.1997,HenzingerHenzinger1996].

In this paper we provide a detailed discussion of the features of PDDL+, and the reasons for their addition. We develop a formal semantics for our primitives in terms of a formal mapping between PDDL+ and Henzinger's theory of hybrid automata [HenzingerHenzinger1996]. Henzinger provides the formal semantics of HAs by means of the labelled transition system. We therefore adopt the labelled transition semantics for planning instances by going through this route. We explain what it means for a plan to be valid by showing how a plan can be interpreted as an accepting run through the corresponding labelled transition system.

We note that, under certain constraints, the Plan Existence problem for PDDL+ planning instances (which corresponds to the Reachability problem for the corresponding hybrid automaton) remains decidable. We discuss these constraints and their utility in the modelling of mixed discrete-continuous planning problems.