\documentclass[11pt,twoside]{article}
\usepackage{theapa}
\usepackage{jair}
%\usepackage{times}
\usepackage{amssymb}
\usepackage{courier}


\usepackage[pdftex]{graphicx}
\newcommand{\eg}{{\it e.g.}}
\newcommand{\ie}{{\it i.e.}}

\newcommand{\ucpop}{\mbox{\sc ucpop}}
\newcommand{\lang}{\mbox{\sc {\sc pddl2.1}}}
\newcommand{\prodigy}{\mbox{\sc prodigy}}
\newcommand{\zeno}{\mbox{\sc zeno}}
\newcommand{\clpr}{\mbox{CLP({$\cal{R}$})}}
\newcommand{\HOLDS}{\mbox{\tt holds-at}}
\newcommand{\VALUE}{\mbox{\tt value-at}}
\newcommand{\strips}{\mbox{\sc strips}}
\newcommand{\adl}{\mbox{\sc adl}}

\newcommand{\?}{\mbox{?}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\ddt}{\mbox{$\frac{d}{dt}\,$}}  %* no strut
\newcommand{\PS}{\mbox{$\prec\!\! S, O, B\!\! \succ$}} % plan state
\newcommand{\SPP}{\mbox{$\prec\!\! {\cal O}, \Sigma, \Omega \!\!\succ$}}
\newcommand{\comment}[1]{}
\newtheorem{defn}{Definition}
\newcommand{\clink}[3]{\mbox{${#1}\!\!\stackrel{#2}{\rightarrow}\!\!{#3}$}}
\newcommand{\hlink}[3]{\mbox{${#1}\!\!\stackrel{#2}{\rightarrow *}\!\!{#3}$}}
\newcommand{\bug} {\mbox{\rule{4mm}{4mm}}}
\newcommand{\Bug}[1]{\mbox{\rule{4mm}{4mm}}\footnote{{\bf BUG:} #1}}
\newcommand{\type}[1]{\mbox{\small {\tt {#1}}}}

\newtheorem{them}{Proposition}
\newtheorem{lemma}[them]{Lemma}
\newtheorem{corol}[them]{Corollary}
\newtheorem{conj}[them]{Conjecture}
\newtheorem{example}{Example}
\newtheorem{Defn}{Definition}

\newcommand{\boxout}[2]{\begin{figure}\begin{center}\fbox{\begin{minipage}{5.5in}\begin{example}\label{#2} #1\end{example}\end{minipage}}\end{center}\end{figure}}

\newcommand{\goal}[1]{\prec\!\!{#1}\!\!\succ}
\newcommand{\PDB}{\mbox {\sc pdb}}
\newcommand{\pdb}{\PDB}


\setcounter{tocdepth}{2}
\setcounter{page}{61}

\def\oom{$^{\tt +}$}
\def\zom{$^*$}
\def\bump{\hspace{1cm}}
\def\req#1{$^{\tt #1}$}
\newenvironment{tabtt}{\begin{tt} \begin{footnotesize} \begin{tabbing}}{\end{tabbing} \end{footnotesize} \end{tt}}
\def\noteme#1{}%{[[#1]]}
\def\notecoauth#1{\ }
\def\notereader#1{[[#1]]}
\def\meta{$\uparrow\uparrow$}
\def\la{\langle}
\def\ra{\rangle}
\newcommand{\checkme}[1]{\mbox{\bf {#1}}}

\jairheading{20}{2003}{61-124}{09/02}{12/03}
\ShortHeadings{{\sc pddl2.1}: Expressing Temporal Planning Domains}
{Fox \& Long}
%\firstpageno{25}


\title{{\sc pddl2.1} : An Extension to {\sc pddl} for Expressing Temporal Planning Domains}
\author{\name Maria Fox \email maria.fox@cis.strath.ac.uk\\
\name Derek Long \email derek.long@cis.strath.ac.uk\\
\addr Department of Computer and Information Sciences\\
University of Strathclyde, Glasgow, UK}
\begin{document}
\maketitle

\begin{abstract}
In recent years research in the planning community has moved increasingly towards application of planners to realistic problems involving both time and many types of resources. For example, interest in planning demonstrated by the space research community has inspired work in  observation scheduling, planetary rover exploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. 

The International Planning Competitions have acted as an important motivating force behind the progress that has been made in planning since 1998. The third competition (held in 2002) set the planning community the challenge of handling time and numeric resources. This necessitated the development of a modelling language capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, {\sc pddl2.1}, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that {\sc pddl2.1} has considerable modelling power~--- exceeding the capabilities of current planning technology~--- and presents a number of important challenges to the research community.  
\end{abstract}

\section{Introduction}

In 1998 Drew McDermott released a Planning Domain Description Language, {\sc pddl}~\cite{drew,pddl}, 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 {\sc 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 {\sc 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~\cite{ixtet,ixtetextra,hsts,oplan,sipe} there has always been a gap between the modelling requirements of such domains and what can be expressed in {\sc 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 {\sc 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, {\sc pddl2.1}, in terms of its syntax, semantics and modelling capabilities. 

{\sc pddl2.1} has been designed to be backward compatible with the fragment of {\sc 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 {\sc pddl} provides a clean and well-understood basis for development and embodies a number of design principles that we considered it important to retain. {\sc pddl2.1} extends {\sc pddl} in principled ways to achieve the additional expressive power following, as far as possible, McDermott's maxim ``physics, not advice''~\cite{drew}. 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:

\begin{enumerate}
\item All existing {\sc pddl} domains (in common usage) are valid {\sc pddl2.1} domains. This is important to enable existing libraries of benchmark problems to remain valid.
\item Valid {\sc pddl} plans are valid {\sc pddl2.1} plans. 
\end{enumerate}

An important contribution made in the development of {\sc 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~\ref{sec-background} we introduce non-specialist readers to the {\sc 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 {\sc pddl2.1}. The paper then focusses on the specific extensions introduced: numeric expressions and durative actions. In Section~\ref{sec-numerics} we start by explaining the syntax of numeric expressions and their use in action descriptions. We then explain, in Section~\ref{sec-metrics},  how {\em 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~\ref{sec-durativeprobs} the paper introduces the notion of {\em 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~\ref{sec-semintro}, \ref{sec-sem2}, \ref{sec-sem3} and \ref{sec-semantics3} 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~\ref{sec-valid} we describe the process by which plans were validated in the competition and discuss the complexity of the validation question for {\sc pddl2.1}. Finally, Section~\ref{sec-relatedwork} describes some related work in the temporal reasoning community, in order to put the contributions made by {\sc pddl2.1} into a wider context. A full {\sc bnf} description of {\sc pddl2.1} can be found in the appendix.

{\sc 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 {\sc pddl2.1} with a series of {\em levels} of increasing expressive power. Thus, the {\sc strips} fragment of {\sc 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 {\sc 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~\citeyear{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 {\sc pddl2.1}, discuss the rationale for our language choices and explain some of the issues that have arisen in trying to extend {\sc pddl}. Although we have provided the {\sc bnf} for {\sc 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 {\small {\tt http://www.dur.ac.uk/d.p.long/competition.html}}.



\input{JAIRpddleg}

\section{Numeric Expressions, Conditions and Effects}
\label{sec-numerics}
One of the first decisions we made in the development of {\sc pddl2.1} was to propose a definitive syntax for the expression of numeric fluents. We based our syntax on the version described in the AI Magazine article~\cite{drew}, with some minor revisions (discussed below). Numeric expressions are constructed, using arithmetic operators, from primitive numeric expressions, which are values associated with tuples of domain objects by domain functions. Using our proposed syntax for expressing numeric assignments and updates we can express the jug-pouring operator originally described in the {\sc pddl1.2} manual and in the AI Magazine article (see Figure~\ref{fig-jugs1}), in {\sc pddl2.1}, as presented in Figure~\ref{fig-jugs3}. 
\begin{figure}
%\include{jugs3}
{\footnotesize
\begin{verbatim}
(define (domain jug-pouring)
   (:requirements :typing :fluents)
   (:types jug)
   (:functions
        (amount ?j - jug)
        (capacity ?j - jug))
   
   (:action pour
       :parameters (?jug1 ?jug2 - jug)
       :precondition (>= (- (capacity ?jug2) (amount ?jug2)) (amount ?jug1))
       :effect (and (assign (amount ?jug1) 0)
                    (increase (amount ?jug2) (amount ?jug1)))
)
\end{verbatim}}
\caption{Pouring water between jugs, {\sc pddl2.1} style.}
\label{fig-jugs3}
\end{figure}
In this example the functions \type{capacity} and \type{amount} associate the jug objects with numeric values corresponding to their capacity and current contents respectively. As can be seen in the example, we have used a prefix syntax for all arithmetic operators, including comparison predicates, in order to simplify parsing. Conditions on numeric expressions are always comparisons between pairs of numeric expressions. Effects can make use of a selection of assignment operations in order to update the values of primitive numeric expressions. These include direct assignment and relative assignments (such as \type{increase} and \type{decrease}). Numbers are not distinguished in their possible roles, so values can represent, for example, quantities of resources, accumulating utility, indices or counters. 

The differences between the {\sc pddl2.1} syntax and the AI Magazine syntax are in the declaration of the functions and in the use of \type{assign} instead of \type{change}. We decided to only allow numeric-valued functions, making the declaration of function return types superfluous. We therefore simplified the language by requiring only the declaration of the function names and argument types, as is required for predicates. We felt that \type{change} was ambiguous when used alongside the operations \type{increase} and \type{decrease} and that \type{assign} would be clearer.

Numeric expressions are not allowed to appear as terms in the language (that is, as arguments to predicates or values of action parameters). There are two justifications for this decision~--- a philosophical one and a pragmatic one. Philosophically we take the view that there are only a finite number of objects in the world. Numbers do not exist as unique and independent objects in the world, but only as values of attributes of objects. Our models are object-oriented in the sense that all actions can be seen as methods that apply to the objects given as their parameters. The object-oriented view does not directly inform the syntax of our representations, but is reflected in the way in which numbers are manipulated only through their relationships with the objects that are identified and named in the initial state. Pragmatically, many current planning approaches rely on being able to instantiate action schemas prior to planning, and this is only feasible if there is a finite number of action instances. The branching of the planner's search space, at choice points corresponding to action selection, is therefore always over finite ranges. The use of numeric fluent variables conflicts with this because they could occur as arguments to any predicate and would not define finite ranges. 

Our decision not to allow numbers to be used as arguments to actions rules out some actions that might seem intuitively reasonable. For example, an action to {\em fly} at a certain altitude might be expected to take the altitude as a number-valued argument. This is only possible in {\sc pddl2.1} if the range of numbers that can be used is finite. From a practical point of view we think that this is unlikely to be an arduous constraint and that the benefits of keeping the logical state space finite compensates for any modelling awkwardness that results. 

Functions in {\sc pddl2.1} are restricted to be of type {\em Object}$^{n}~\rightarrow~{\mathbb {R}}$, for the (finite) collection of objects in a planning instance, {\em Object} and finite function arity $n$. Later extensions of {\sc pddl} might introduce functions of type {\em Object}$^{n}$~$\rightarrow$~{\em Object}, allowing {\em Object} to be extended by the application of functions to other objects. The advantage of this would be to allow objects to be referred to by their relationships to known objects. (For example, \type{(onTopOf~?x)} could be used to refer to the object currently on top of an object instantiating \type{?x}). Unfortunately, such functions present various semantic problems. In particular, the interpretation of quantified preconditions becomes significantly harder, since the collection of objects is no longer necessarily finite, so extensional interpretations are not possible. A further difficulty is the identity problem~--- as objects are manipulated by actions, the functional expressions that refer to them are also affected, but implicitly. For example, as objects are moved, \type{(onTopOf A)} can change without any action manipulating it explicitly. Managing the way in which functional terms map to specific objects in the domain (which might or might not have specific names of their own) appears to introduce considerable complication into the semantics. We believe that it is important to avoid extending {\sc pddl} with elements that are still poorly understood.

\section{Plan Metrics}
\label{sec-metrics}

The adoption of a stable numeric extension to the {\sc pddl} core allowed us to introduce a further extension into {\sc pddl2.1}, namely a new (optional) field within the specification of problems: a plan metric. Plan metrics specify, for the benefit of the planner, the basis on which a plan will be evaluated for a particular problem. The same initial and goal states might yield entirely different optimal plans given different plan metrics. Of course, a planner might not choose to use the metric to guide its development of a solution but just to evaluate a solution {\em post hoc}. This approach might lead to sub-optimal, and possibly even poor quality plans, but it is a pragmatic approach to the handling of metrics which was quite widely used in the competition. This issue is discussed further in the companion paper analysing the results of the 3rd IPC in this issue~\cite{resultspaper}. 

The value \type{total-time} can be used to refer to the temporal span of the entire plan. Other values must all be built from primitive numeric expressions defined within a domain and manipulated by the actions of the domain. As a consequence, plan metrics can only express non-temporal metrics in {\sc pddl2.1} domains using numeric expressions. Any arithmetic expression can be used in the specification of a metric --- there is no requirement that the expression be linear. It is the domain designer's responsibility to ensure that plan metrics are well-defined (for example, do not involve divisions by zero). An example of use of a plan metric is shown in Figure~\ref{fig-planmetric}. 

The implications of having introduced this extension are far-reaching and have already helped to demonstrate some important new challenges for planning systems~--- particularly fully-automated systems. An enriched descriptive power for the evaluation of plans is a crucial extension for the practical use of planners, since it is almost never the case that real plans are evaluated solely by the number of actions they contain. 
\begin{figure}
{\footnotesize
\begin{verbatim}
(define (domain metricVehicle)
 (:requirements :strips :typing :fluents)
 (:types vehicle location)
 (:predicates (at ?v - vehicle ?p - location)
              (accessible ?v - vehicle ?p1 ?p2 - location))
 (:functions  (fuel-level ?v - vehicle)
              (fuel-used ?v - vehicle)
              (fuel-required ?p1 ?p2 - location)
              (total-fuel-used))

 (:action drive
   :parameters (?v - vehicle ?from ?to - location)
   :precondition (and (at ?v ?from)
                      (accessible ?v ?from ?to)
                      (>= (fuel-level ?v) (fuel-required ?from ?to)))
   :effect (and (not (at ?v ?from))
                (at ?v ?to)
                (decrease (fuel-level ?v) (fuel-required ?from ?to))
                (increase (total-fuel-used) (fuel-required ?from ?to))
                (increase (fuel-used ?v) (fuel-required ?from ?to)))
 )
)

(define (problem metricVehicle-example)
 (:domain metricVehicle)
 (:objects 
      truck car - vehicle
      Paris Berlin Rome Madrid - location)
 (:init
      (at truck Rome)
      (at car Paris)
      (= (fuel-level truck) 100)
      (= (fuel-level car) 100)
      (accessible car Paris Berlin)
      (accessible car Berlin Rome)
      (accessible car Rome Madrid)
      (accessible truck Rome Paris)
      (accessible truck Rome Berlin)
      (accessible truck Berlin Paris)
      (= (fuel-required Paris Berlin) 40)
      (= (fuel-required Berlin Rome) 30)
      (= (fuel-required Rome Madrid) 50)
      (= (fuel-required Rome Paris) 35)
      (= (fuel-required Rome Berlin) 40)
      (= (fuel-required Berlin Paris) 40)
      (= (total-fuel-used) 0)
      (= (fuel-used car) 0)
      (= (fuel-used truck) 0)
 )
 (:goal (and (at truck Paris)
             (at car Rome))
 )
 (:metric minimize (total-fuel-used))
)
\end{verbatim}}
\caption{An example of a domain and problem instance describing a plan metric.}
\label{fig-planmetric}
\end{figure}

Metrics are described in the problem description, allowing a modeller to easily explore the effect of different metrics in the construction of solutions to problems for the same domain. In order to define a metric in terms of a specific quantity it is necessary to {\em instrument} that quantity in the domain description. For example, if the metric is defined in terms of overall fuel use a {\em fuel-use} quantity can be initialised to zero in the initial state and then updated every time fuel is consumed. In the domain shown in Figure~\ref{fig-planmetric} it is possible to minimise a linear combination of fuel used by each of the vehicles such as:
\begin{center}
\type{(:metric minimize (+ (* 2 (fuel-used car)) (fuel-used truck)))}
\end{center}
However it is not possible to minimise distance covered since distance is not instrumented. It would be straightforward to instrument it if desired, simply by adding the appropriate initial value and incrementing effects to the domain description. Since actions cause quantities to change, instrumenting a value requires modification of the domain description itself, not just a problem file.

The use of plan metrics is subtle and can have dramatic impact on the plans being sought. Perhaps the simplest case is where all actions increase a metric that must be minimised, or decrease one that must be maximised. This is the case in the example shown in Figure~\ref{fig-planmetric}, where any use of the drive action can only worsen the value of the plan metric (whether we use the metric shown in the figure or the maximising metric described in the last paragraph). This situation might appear to be relatively straightforward: a planner must attempt to use as few actions to solve a problem as possible. In fact, even this case is a little more complex than it appears~--- there can be rival plans in which one uses more actions but has lower overall cost than the other. A more complex case arises when some actions improve the quality metric while others degrade it. For example, if we use the maximising metric but also add a refuel action to the domain then driving will degrade plan quality (by reducing the fuel level of a vehicle) but refuelling will improve plan quality (by increasing the fuel level of a vehicle). In this case, a planner can attempt to use actions to improve the plan quality without those actions actually contributing to achieving the goals. For example, refuelling might not be necessary to get the vehicles to their destinations, but adding refuelling actions would improve the quality of a solution. This process could involve trading off finite and irreplaceable resources for the increased value of the plan. This would be the case if, for example, refuelling a vehicle took fuel from a finite reservoir. Alternatively a domain could allow plans of arbitrarily high value to be constructed by using more and more actions. This would occur in the metric vehicles domain using the maximising vehicle's fuel level metric if refuelling were not constrained, since the domain does not impose a limit on the fuel capacities of the vehicles. 

The case in which plans are constrained by finite availability of resources, is an important and interesting form of the planning problem, but the case in which plans of arbitrarily high utility can be constructed, is obviously an ill-defined problem, since an optimal plan does not exist. It is non-trivial to determine whether a planning problem provided with a metric is ill-defined. In fact, as Helmert shows~\cite{helmert}, the introduction of numeric expressions, even in the constrained way that we have adopted in {\sc pddl2.1}, makes the planning problem undecidable. The problem of finding a collection of actions which does not consume irreplaceable resources and has an overall beneficial impact on a plan metric is at least as hard as the planning problem. Therefore it is clear that determining whether a planning problem is even well-defined is undecidable. This does not make it worthless to consider planning with metrics, of course, but it demonstrates that the modelling problem, as well as the planning problem, becomes even more complex when metrics are introduced. 

One strategy available to planners working with problems subject to plan metrics is to ignore the metric and simply produce a plan to satisfy the logical goals that a problem specifies. In this case, the plan quality will simply be the value, according to the metric, of the plan that happens to be constructed. This strategy is unsophisticated and it is obviously better for a planner to construct a plan guided by the specified metric. How best to use a metric to expedite the search process in a fully-automated planner is still a research issue.


\input{JAIRdiscretedas}
\input{JAIRdurative}


\input{JAIRsemintro}

\input{JAIRsemanticslevel2}


\input{JAIRsemanticslevel3}
\input{JAIRsemantics4}

%\input{JAIRevents}
\input{JAIRvalid}

\input{JAIRtime}

\section{Conclusions}

Recent developments in AI planning research have been leading the community closer to the application of planning technology to realistic problems. This has necessitated the development of a representation language capable of modelling domains with temporal and metric features. The approach we have taken towards the development of such a language is to extend McDermott's {\sc pddl} domain representation standard to support temporal and metric models.

The development of the {\sc pddl} sequence towards greater expressive power is important to the planning community because {\sc pddl} has provided a common foundation for a great deal of recent research effort. The problems involved in modelling the behaviour of domains with both discrete and continuous behaviours have been well explored in the temporal logic and model checking communities but there have been no widely adopted models within the planning community. Our work on {\sc pddl2.1} provides a way of making the relevant developments in these communities accessible to planning. Furthermore, {\sc pddl2.1} begins to bridge the gap between basic research and applications-oriented planning by providing the expressive power necessary to capture real problems.

{\sc pddl2.1} has the expressive power to represent a class of deterministic mixed discrete-continuous domains as planning domains. The language introduces a form of durative action based on three connected parts: the initiation of an interval in which numeric change might occur and its explicit termination by means of an action that produces the state corresponding to the end of the durative interval. This form of action allows the modelling of both discrete and continuous behaviours --- discretized change can be represented by means of step functions, whilst continuous change can be modelled using the $\#t$ variable. The language provides solutions to the critical issues of concurrency, continuous change and temporal extent. The semantics of the language is derived from the familiar state transition semantics of {\sc strips}, extended to interpret invariants holding over intervals in which continuous functions might also be active. Our semantics allows us to interpret more plans than we can efficiently validate. We describe the criteria that a plan must satisfy in order to be practically verifiable. 

This paper has focussed primarily on a discussion of the numeric and discretised temporal features of {\sc pddl2.1}. However, the modelling capability of discretized durative actions is in some respects limited and it is important for the planning community to address the challenges presented by continuous change. Indeed, even using the continuous actions of {\sc pddl2.1} it is not possible to model episodes of change being terminated by spontaneous events in the world rather than by the deliberate choice of the planner. The future goals of the community should include addressing domains that require the continuous actions of {\sc pddl2.1}, then confronting the challenges of planning within more dynamic environments in which intervals of change can be terminated by the world as well as by the deliberate action of the planner. This will constitute an important step towards planning within dynamic and unpredictable environments. 

\section*{Acknowledgements}

We would like to thank the members of the committee for the third International Planning Competition. In particular, discussions with Drew McDermott, Fahiem Bacchus, David Smith and Hector Geffner in turns infuriated, intrigued and delighted us and contributed immeasurably to the strengths of this paper. Many others have offered comments and insights that have allowed us to develop the work we present here. We would like to thank J\"{o}rg Hoffmann, Malte Helmert, Antonio Garrido, Stefan Edelkamp, Nicola Muscettola, Mark Boddy, Keith Golden, Jeremy Frank, Ari J\'{o}nsson, Julie Porteous, Alex Coddington, Stephen Cresswell, Luke Murray, Keith Halsey and Richard Howey for the many helpful discussions we have shared.

\appendix
\include{JAIRbnf}

\bibliographystyle{theapa}
\bibliography{pddlplusdoc}


\end{document}
