PDDL+ and Priced Timed Automata

Rasmussen et al. rasmussen describe the components of a Priced Timed Automaton (PTA) as follows. It contains a set of real-valued clocks, $C$, over which constraints can be expressed by a set of clock constraints, $B(C)$. There is a set of actions, $Act$. A PTA is given as a 5-tuple $(L,l_{0},E,I,P)$, where L is a finite set of locations (that is, states), $l_{0}$ is the initial location, $E \in L \times B(C) \times Act \times 2^{C} \times L$, $I : L \rightarrow B(C)$ is a function assigning invariants to locations and $P : (L \cup E) \rightarrow N$ assigns prices to edges and locations. An edge, $E = (l,b,a,r,l^\prime)$ is a transition between locations $l$ and $l^\prime$ using action $a$, which has the jump condition $b$ (over the clocks) and resets the clocks in $r$ to zero. The price function represents a discrete cost for transitions and a continuous cost associated with staying in each location.

For the modelling of arbitrary Priced Timed Automata we define a PDDL+ fragment which we refer to as PDDL+$_{PTA}$. The following definition of this fragment is not unique. Other subsets of PDDL+ exist with the same expressive power, including subsets directly relying on processes and events. By excluding events in this fragment we are trivially guaranteed to have a deterministic language.

The PDDL+$_{PTA}$ fragment uses the standard PDDL+ language features, but subject to the following constraints:

1. Processes may have only logical preconditions and exactly one process must be active in each state except, possibly, one special state, error.
2. Each process must increase all the metric fluents at rate 1, except for one special variable, $c$, which may be increased at any constant rate.
3. Each action may have preconditions that refer to any of the metric fluents except $c$. These preconditions must appear in any of the forms (called clock constraints) conforming to the following: ($\bowtie$ $x_i$ $n$) or ($\bowtie$ (- $x_i$ $x_j$) $m$) where $n,m$ are natural numbers and $\bowtie \in \{<,\leq,=,\geq,>\}$.
4. Each action may reset the value of any metric fluent, other than $c$, to zero. They may increase the value of $c$ by any constant value.
5. The domain may contain events whose precondition may include literals and clock constraints. The effect of every event must be to leave the system in the special state error, from which no further transitions are possible.
6. The plan metric is of the form: (:metric minimize (c)).

These constraints ensure that the state space yielded by a PDDL+$_{PTA}$ description, and its transition behaviour, is equivalent (within a constant multiple encoding size) to a PTA. We cannot demonstrate direct equivalence between PDDL+$_{PTA}$ and PTAs because PDDL+$_{PTA}$ models can be exponentially more compact than the explicit PTA to which it corresponds. This compaction is similar to that which can be obtained by factorising PTA models [DierksDierks2005]. We demonstrate the indirect equivalence of the two languages in Theorem 2.

Definition 28   Indirectly Equivalent Expressiveness Given two languages, $L_1$ and $L_2$, $L_1$ is indirectly equivalent in expressive power to $L_2$ if each sentence, $s_1$, in $L_1$ defines a model, $M_{s_1}$, such that $L_2$ can express $M_{s_1}$ with only a polynomial increase in encoding size (in the size of $M_{s_1}$) and each sentence, $s_2$, of $L_2$ can be expressed in $L_1$ with at most a polynomial increase in the size of the encoding (in the size $s_2$).

We note that this definition is asymmetric: sentences of $L_1$ define models that can be expressed efficiently in $L_2$, but sentences of $L_2$ can be efficiently expressed directly in $L_1$. The sentences of $L_1$ might be compact encodings of their corresponding models and therefore we cannot claim a direct equivalence in expressiveness between $L_1$ and $L_2$. This is intentional and allows us to exploit the PDDL property that it is a compact encoding language for the state spaces and transition behaviours of the planning domains it defines.

Theorem 2   PDDL+$_{PTA}$ has indirectly equivalent expressive power to Priced Timed Automata.

The proof of this theorem can be found in Appendix B.

Lemma 1   A sentence, $s$, of PDDL+ defines a transition system that is at most doubly exponential in the size of $s$.

This is straightforward: the set of literals defined by a PDDL+ problem instance is at most exponential in the number of parameters in the predicate of the highest arity and the state space this defines is at most exponential in the size of the set of literals.

$\Box$

Corollary 1   Reachability in PDDL+$_{PTA}$ is decidable.

This follows from Theorem 2, Lemma 1 and the decidability of PTAs [Larsen, Behrmann, Brinksma, Fehnker, Hune, Pettersson, RomijnLarsen et al.2001].

$\Box$

PDDL+$_{PTA}$ can be extended, while remaining decidable, by allowing additional metric fluents whose (non-continuous) behaviour is constrained according to one of the decidable subsets identified by Helmert helmert, provided that these fluents are distinct from the clock and cost variables.

We can similarly define a language fragment with expressive power equivalent to Initialised Singular Automata. Initialised Singular Automata represent the most expressive form of deterministic automaton with a decidable Reachability problem. Their constraints limit the extent to which we can reason about the dependence of behaviour on temporal and metric quantities.

In an Initialised Singular Automaton continuous change is not restricted to variables of slope 1, in contrast to the clocks of Timed Automata. All variables have finite slope (that is, their rates of change can only take one of a finite set of different values), but must be initialised to a given constant whenever their rates of change are altered. The values of these variables can be referred to in the jump conditions of the automaton.

For the modelling of Initialised Singular Automata we define a PDDL+ fragment which we refer to as PDDL+$_{ISA}$. This fragment contains the same syntactic components as PDDL+$_{PTA}$ but is subject to slightly different constraints:

1. Processes may have only logical preconditions and exactly one process must be active in each state except, possibly, one special state, error.
2. Each process must increase all the metric fluents at constant rates.
3. Each action may have preconditions that refer to any of the metric fluents. These preconditions must appear in any of the forms (called clock constraints): ($\bowtie$ $x_i$ $n$) or ($\bowtie$ (- $x_i$ $x_j$) $m$) where $n,m$ are natural numbers and $\bowtie \in \{<,\leq,=,\geq,>\}$.
4. Each action may reset the value of any metric fluent to any constant natural number value. Any action that causes a transition to a state where a new process is active must also reset all metric fluents whose rates of change are different under the new process.
5. The domain may contain events whose precondition may include literals and clock constraints. The effect of every event must be to leave the system in the special state error, from which no further transitions are possible.

This fragment does not contain a special plan metric: problems in PDDL+$_{ISA}$ are of interest for the plan existence problem.

Theorem 3   PDDL+$_{ISA}$ has indirectly equivalent expressive power to Initialised Singular Automata.

The proof of this result is analogous to Theorem 2. The constraints ensure that the behaviour of Initialised Singular Automata is captured in this language and that the language contains only expressions that can be effectively modelled within Initialised Singular Automata.

It is of interest to review the domains we have considered in this paper, the planetary lander domain and the accelerating vehicle domain, with respect to the modelling power of PDDL+$_{PTA}$ and PDDL+$_{ISA}$. In the first instance, since both domains involve non-linear change, in the power generation and state of charge curves and in the distance travelled by the vehicle when acceleration is non-zero, it is clear that both domains lie outside the modelling power of these constrained languages. It is feasible to consider approximating the non-linear behaviour in some cases. For example, the generation curve might be approximated by a small set of linear functions (with a corresponding loss of opportunities to exploit the margins of the model). The generation curve can be tied to absolute points on the timeline and the values of the points at which the linear functions would be required to meet in order to approximate the original curve can be identified in advance. In order to create a reasonable approximation, the functions would require different slopes (shallow at the start, then steeper and then shallower again, to approximate the first half of the bell curve), which cannot be achieved using PDDL+$_{PTA}$, since this only allows clock variables. PDDL+$_{ISA}$ is powerful enough to express differently sloped linearly changing variables of this kind. Unfortunately, the state of charge curve, even with approximations, is beyond the expressive power of either language. For PDDL+$_{ISA}$ the problem is that there must be a memory of the old state of charge when the slope of the charge curve changes. With PDDL+$_{PTA}$ the cost variable could be used to model the state of charge, since it has the capacity to both be used as a memory and to have different rates of change. However, the cost variable cannot be used in preconditions of any actions, which means that any attempt to model the battery in this way would force a decoupling between the battery state of charge and the actions that use power. A more realistic model of the battery management lies outside the power of PDDL+$_{PTA}$ and PDDL+$_{ISA}$.

However, other interesting problems involving continuous change are perfectly amenable, as Dierks dierks and Behrmann et al. larsen have shown. The Aircraft Landing problem [Beasley, Krishnamoorthy, Sharaiha, AbramsonBeasley et al.2000] can be modelled as a PTA because it has one source of continuous change which can be modelled as a cost variable. In this domain, some number of aircraft must land on a single airport, sometime between an earliest and latest landing time and as close to a target time as possible. The earliest, latest and target times are defined for each aircraft. A cost is associated with the problem and there is a charge associated with landing a plane early or late, where the charge decreases linearly from the earliest landing time towards the target time and increases linearly from the target up to the latest landing time. The behaviour of the aircraft is not dependent on the value of the cost variable, although the quality of a landing schedule is determined by it. The Aircraft Landing problem is an optimisation problem where the quantity being optimized changes continuously over time.

Figure 14: Mapping PDDL fragments to corresponding deterministic automata. PDDL is a family of deterministic languages. However, extension to support temporal, numeric or logical non-determinism would give access to the automata on the right hand side of the figure.

In Figure 14 we present some formal relationships between PDDL+ fragments and classes of hybrid automata. The bottom half of the figure concerns decidable fragments of PDDL+ whilst the top half concerns undecidable fragments. In the figure, DPDDL is the PDDL+ fragment in which fixed duration durative actions are allowed (and no events or processes), restricted to those with no at start effects and NPDDL (non-temporal PDDL) is the fragment in which they do not occur. Initial effects are significant because it is these that make it possible to create domains in which there are problems that can only be solved by exploiting concurrency. The reason for this is that if all effects are restricted to the end points of actions, then it is always possible to find a sequential plan to solve a problem for which there is a concurrent solution. In cases where concurrency is not required to solve a problem, durative actions can be sequentialised and their durations simply summed as discrete end effects. When actions can have initial effects then it is possible for there to be effects that are added at the start of an action and deleted at the end, creating windows of opportunity into which other actions must be fitted concurrently if they are to exploit the effects. Once concurrency matters it is necessary to monitor the passage of time and this requires the power of timed automata. The other language variants we show are as follows:

• DPDDL$_{SE}$ which allows start effects, raising the need for concurrency as explained above.
• DPDDL$_{TT}$, which is DPDDL together with the use of plan metrics using the term total-time: this also requires concurrency since the time required by a plan depends on the extent to which non-interfering actions can be selected to reduce the make-span of the plan.
• DPDDL$_{TT+SE}$ which is DPDDL together with total-time and allowing the use of start effects.
• PDDL+ $_{\char93 t lin}$ is PDDL+ restricted to linear rates of change on all metric fluents. This restriction is insufficient to ensure decidability, but the use of linear rates of change makes it possible to apply linear constraint solvers to the problems. As a consequence, this subset of PDDL+ captures the continuous planning problems to which planning technology has already been applied [Shin DavisShin Davis2005,McDermottMcDermott2003b,Wolfman WeldWolfman Weld1999,Penberthy WeldPenberthy Weld1994] (in the first of these, in particular, the models are actually expressed in PDDL+).

In the bottom half of the figure both NPDDL and DPDDL include metric conditions and effects constrained to occur in decidable combinations as defined by Helmert helmert. Helmert demonstrated that adding (discrete) metric effects and conditions to the propositional PDDL fragment already adds dramatically to the expressive power of the language. In particular, with a quite limited set of (discrete) metric effects and conditions decidability is already lost. However, there are restrictions to the use of metric variables that leave a decidable fragment. In order for the extensions we are discussing to retain decidability we must not, of course, sacrifice it by adopting too rich a set of discrete metric effects or preconditions. This is why in the lower half of the figure we work within these constraints. Our results extend Helmert's by introducing continuous metric change, while demonstrating boundaries that retain decidability. In the top half of the figure these constraints are lifted. The left-hand half of the figure concerns deterministic models: PDDL+ is a language for expressing deterministic domains, so we have restricted our attention to this side. The right-hand half concerns non-deterministic variants of the models considered. We include these only to provide a general context for our results.