For the modelling of arbitrary Priced Timed Automata we define a PDDL+ fragment which we refer to as PDDL+. 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+ fragment uses the standard PDDL+ language features, but subject to the following constraints:
These constraints ensure that the state space yielded by a PDDL+ description, and its transition behaviour, is equivalent (within a constant multiple encoding size) to a PTA. We cannot demonstrate direct equivalence between PDDL+ and PTAs because PDDL+ 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.
We note that this definition is asymmetric: sentences of define models that can be expressed efficiently in , but sentences of can be efficiently expressed directly in . The sentences of might be compact encodings of their corresponding models and therefore we cannot claim a direct equivalence in expressiveness between and . 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.
The proof of this theorem can be found in Appendix B.
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.
This follows from Theorem 2, Lemma 1 and the decidability of PTAs [Larsen, Behrmann, Brinksma, Fehnker, Hune, Pettersson, RomijnLarsen et al.2001].
PDDL+ 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+. This fragment contains the same syntactic components as PDDL+ but is subject to slightly different constraints:
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+ and PDDL+. 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+, since this only allows clock variables. PDDL+ 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+ 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+ 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+ and PDDL+.
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.
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:
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.
Derek Long 2006-10-09