Related Formalisms

A number of representational formalisms have been proposed for expressing temporal and metric activity in planning. The closest recent counterpart to PDDL+ is the modelling language, Opt, of the Optop planner [McDermottMcDermott2004]. This language was developed independently, by Drew McDermott, at the same time as PDDL+ was first proposed, and some of the similarities between Opt and PDDL+ are due to discussions between the developers of the two languages at the time. Opt is a PDDL-like dialect which was strongly influenced by the work of McDermott and other authors on the PDDL family of languages. Opt supports autonomous processes which run when their preconditions are satisfied and are not under the control of the planner. Unlike PDDL+, Opt does not contain explicit events - these are embedded inside processes which run for as long as their preconditions remain true. Opt also retains durative actions as an alternative to the explicit modelling of continuous change and models timed initial literals and derived predicates. A planner, Optop, was developed by McDermott [McDermottMcDermott2005] for the subset of Opt that models linear continuous change. Planners already exist for handling interesting subsets of PDDL+, both directly [Shin DavisShin Davis2005] and indirectly [DierksDierks2005]. In the later case, the language of the PTA solver UPPAAL-cora [Behrmann, Larsen, RasmussenBehrmann et al.2005] is used, which has modelling power equivalent to that of PDDL+$_{PTA}$.

The semantics of Opt processes is given in terms of infinitely many situations occurring within a finite time, each associated with different fluent values of the continuously changing variables. Opt and PDDL+ are fundamentally related to Reiter's work on continuous dynamics in the situation calculus [ReiterReiter2001]. McDermott developed a situation calculus semantics for Opt, whereas we have constructed an explicit relationship between PDDL+ and the theory of Hybrid Automata in order to make explicit the relationship between PDDL+ planning and control theory. A similar relationship is drawn in the CIRCA architecture [Musliner, Durfee, ShinMusliner et al.1993], which integrates planning with real time control using probabilistic timed automata.

The qualitative reasoning community have proposed hybrid state-based models of dynamic physical systems [ForbusForbus1984,de Kleer Brownde Kleer Brown1984,KuipersKuipers1984]. Kuipers kuipers considers the qualitative simulation of physical systems described in terms of continuously varying parameters. He proposes a qualitative representation of the differential equations governing the behaviour of a system, expressed as systems of constraints over the key parameters describing the state of the system at discrete points in time. This representation supports commonsense reasoning about the evolution of physical systems about which quantitative reasoning would be computationally prohibitive.

Other formalisms have been developed within the fields of planning and reasoning about action and change. Temporal and resource management are provided in HSTS and Europa [Frank JónssonFrank Jónsson2003,Jónsson, Morris, Muscettola, Rajan, SmithJónsson et al.2000], IxTeT [Laborie GhallabLaborie Ghallab1995], CIRCA [Musliner, Durfee, ShinMusliner et al.1993], LPSAT [Wolfman WeldWolfman Weld1999], Zeno [Penberthy WeldPenberthy Weld1994] and HAO* [Benazera, Brafman, Meuleau, Mausam, HansenBenazera et al.2005] to mention only a few such systems in the planning literature. For the most part, these systems are plan-generation systems using representation languages that support the restricted modelling of continuous change and metric time. By contrast, PDDL+ proposes an unrestricted representation language, and its semantics, without describing specific search algorithms for the construction of plans. Finding efficient algorithms for reasoning with PDDL+ domains is a separate topic, in which there has already been progress [Shin DavisShin Davis2005,DierksDierks2005,McDermottMcDermott2004] as mentioned above. Of course, the demands of practical planning restrict how ambitious one can be in using PDDL+ to model real planning applications, but this is not a reason to impose artificial restrictions on the expressiveness of the language.

The key objective of HSTS (Heuristic Scheduling Testbed System) [MuscettolaMuscettola1993] is to maintain as much flexibility as possible in the development of a plan, so that the plan can be robustly executed in the face of unexpected events in the environment. HSTS embodies the close integration of planning and scheduling, enabling the representation of complex resource-intensive planning problems as dynamic constraint satisfaction problems (DCSP). In DDL, the Domain Description Language of HSTS, A distinction is made between domain attributes (ie: the components of the domain that can exhibit behaviours) and their states, with the activity of each attribute represented on a separate time line. No distinction is made between states and actions: actions are added to the time lines by inserting tokens representing predicates holding over flexible intervals of time. Each token is associated with a set of compatibilities which explain how they are constrained with respect to activities on the same and other time lines. Compatibilities express relations very similar to the TIMELOGIC constructs of Allen and Koomen [Allen KoomenAllen Koomen1983]. Choices in the development of the plan are explored through a heuristic search and inconsistencies in the DCSPs representing the corresponding partial plans result in pruning.

Events of the kind provided by PDDL+ are expressed as disjuncts in the compatibility constraints associated with the actions that produce them. For example, the action of opening a water source to fill a tank would be expressed as a token constrained to meet either the event of flooding or an interval in which the water source is closed. Then, whether the tank floods or not depends on how long the interval of filling lasts, and the flooding event can be avoided by expressing the constraint that it end before the water level exceeds the tank capacity. The process by which the water level increases while the tank is filling is expressed using sequence compatibilities, which allow variables to take arbitrarily many contiguous values from a sequence during an interval. The actual water level at the end of the interval can be identified, using linear programming techniques, as one of the values in this sequence. The notion of procedural reasoning [Frank, Jönsson, MorrisFrank et al.2000] has been introduced into the framework to support efficient reasoning with rates of change on continuous variables and their interactions within a plan.

HSTS therefore supports the representation of the interaction between actions, processes and events and their exploitation in the development of flexible plan/schedules. In this respect, DDL is somewhat more expressive than PDDL+ because of the flexibility in its temporal database. Allowing intervals to last any amount of time between a specified lower and upper bound introduces bounded temporal flexibility into the reasoning framework.

IxTeT [Laborie GhallabLaborie Ghallab1995] is a partial order causal link planner that uses a task representation very similar to that of discrete durative actions in PDDL2.1. A key difference is that PDDL2.1 discrete durative actions are restricted to the representation of step function change at the start and end points of the interval, whilst IxTeT tasks can have effects at any specified point during the interval. This allows piecewise continuous change to be represented. Continuous change cannot be modelled (except by means of very small intervals in the piecewise representation of the appropriate function). Furthermore, the durative actions of IxTeT are not of fixed duration -- they can endure any amount of time within a specified interval. Thus, IxTeT also models bounded temporal flexibility and is able to construct flexible plans. IxTeT continues the traditions of POCL planning [McAllester RosenblittMcAllester Rosenblitt1991,Penberthy WeldPenberthy Weld1992] in which a plan is built up as a partially ordered graph of activities with complex flexible temporal constraints. A Simple Temporal Network [Dechter, Meiri, PearlDechter et al.1991] is used to determine the consistency of a given temporal constraint set. STNs, also used in HSTS, are a powerful technique for temporal reasoning but are restricted to reasoning about discrete time points.

There is an important difference between modelling the continuous process of change and computing the values of continuous-valued variables during planning. In some systems, continuous change is explicitly modelled, so that trajectories can be constructed for the variables throughout the timeline of a plan. In other systems, the continuous processes that determine the behaviour of metric variables are implicit, but the values of these variables are available, through some computation, at certain times along their trajectories.

Zeno [Penberthy WeldPenberthy Weld1994] uses an explicit representation of processes as differential equations and solves them to determine whether the temporal and metric constraints of a problem are met in any partial plan (and to identify the values of continuous-valued resources when action preconditions require them). LPSAT [Wolfman WeldWolfman Weld1999] also uses an explicit model of the processes that govern continuous change (although its use of linear constraint solving limits it to linear processes). A different approach, in which the processes are not explicitly modelled, can be seen in HAO* [Benazera, Brafman, Meuleau, Mausam, HansenBenazera et al.2005]. Here, although continuous-valued resources are modelled, the way in which they change over time is not. The different possible metric outcomes of an action are discretised and associated with probabilities. Plan construction can be seen in terms of policy construction within a hybrid MDP framework. Time can be managed in the same way as any other metric resource (a certain action will take $t$ time units with probability $1-p$) so there is no need to model the passage of time directly. Whilst the time-dependent nature of the metric effects of actions can be captured in this way, actions cannot interact with the passage of time in order to exploit or control episodes of continuous change.