next up previous
Next: Conclusions Up: Related Work: Representing and Previous: Temporal extent

Planning with Time

In classical planning models, time is treated as relative. That is, the only temporal structuring in a plan, and in reasoning about a plan, is in the ordering between actions. This is most clearly emphasised by the issues that dominated planning research in the late 1980s and early 1990s, when classical planning was mainly characterised by the exploration of partial plan spaces, in planners such as TWEAK [ChapmanChapman1987], SNLP [McAllester RosenblittMcAllester Rosenblitt1991] and UCPOP [Penberthy WeldPenberthy Weld1992]. Partial plans include a collection of actions representing the activity thus far determined to be part of a possible plan and a set of temporal constraints on those actions. The temporal constraints used in a partial plan are all of the form $A < B$ where $A$ and $B$ are time points corresponding to the application of actions.

Classical linear planners [Fikes NilssonFikes Nilsson1971,Russell NorvigRussell Norvig1995] rely on the simple fact that a total ordering on the points at which actions are applied can be trivially embedded into a time line. Again, the duration between actions is not considered. The role of time in planning becomes far more significant once metric time is introduced. With metric time it is possible to associate specific durations with actions, to set deadlines or windows of opportunity. The problems associated with relative time have still to be resolved in a metric time framework, but new problems are introduced. In particular, durations become explicit, so it is necessary to decide what the durations attach to: actions or states. Further, explicit temporal extents make it more important to confront the issue of concurrency in order to best exploit the measured temporal resources available to a planner.

In contrast to the simple ordering constraints required for relative time, metric time requires more powerful constraint management. Most metric time constraint handlers are built around the foundations laid by Dechter, Meiri and Pearl (1991). For example, IxTeT uses extensions of temporal constraint networks [Laborie GhallabLaborie Ghallab1995]. The language that IxTeT uses to represent planning domains is similar to PDDL2.1 as described in this paper, but more expressive because it allows access to time points within the interval of a durative action. This added expressive power is obtained at the cost of increased semantic complexity and, consequently, increased difficulty in the validation of plans. However, there are many similarities between the modelling of discretised durative actions in PDDL2.1 and in IxTeT, and similar modelling conventions are also found in the languages of Sapa [Do KambhampatiDo Kambhampati2001] and Oplan [Drabble TateDrabble Tate1994].

One of the earliest planners to consider the use of metric time was Deviser [VereVere1983], which was developed from NONLIN [TateTate1977]. In Deviser, metric constraints on the times at which actions could be applied and deadlines for the achievements of goals were both expressible and the planner could construct plans respecting metric temporal constraints on the interactions between actions. Cesta and Oddi oddi have explored various developments of temporal constraint network algorithms to achieve efficient implementation for planning and Galipienso and Sanchis galipienso consider extensions to manage disjunctive temporal constraints efficiently, which is a particularly valuable expressive element for plan construction as was observed above, since constraints preventing overlap of intervals translate into disjunctive constraints on time points. HSTS [MuscettolaMuscettola1994] also relies on a temporal constraint manager.

In systems that use continuous real-valued time it is possible to make use of linear constraint solvers to handle temporal constraints. In particular, constraints dictated by the relative placement of actions with durations on a timeline can be approached in this way [Long FoxLong Fox2003a]. An alternative timeline that is often used is a discretised line based on integers. The advantage of this approach is that it is possible to advance time to a next value after considering activity at any given time point. The next modality can be interpreted in a continuous time framework by taking it to mean the state following the next logical change, regardless of the time at which this occurs [Bacchus KabanzaBacchus Kabanza1998]. In planning problems in which no events can occur other than the actions dictated by the planner and no continuous change is modelled, plans are finite structures and therefore change can occur at only a finite number of time points during its execution. This makes it possible to embed the execution of the plan into the integer-valued discrete time line without any loss of expressiveness.

Various researchers have considered the problem of modelling continuous change. Pednault pednaultTimberline proposes explicit description of the functions that govern the continuous change of metric parameters, attached to actions that effect instantaneous change to initiate the processes. However, his approach is not easy to use in describing interacting continuous processes. For example, if water is filling a tank at a constant rate and then an additional water source is added to increase the rate of filling then the action initiating the second process must combine the effects of the two water sources. This means that the second action cannot be described simply in terms of its direct effect on the world -- to increase the rate of flow into the tank -- but with reference to the effects of other actions that have already affected the rate of change of the parameter. Shanahan shanahan also uses this approach, with the consequence that processes are modelled as stopping and then restarting with new trajectories as each interacting action is applied.

In Zeno [Penberthy WeldPenberthy Weld1994], actions have effects that are described in terms of derivatives. This approach makes it easier to describe interacting processes, but complicates the management of processes by making it necessary to solve differential equations. The complication has not deterred other authors from taking this approach: McDermott drewICAPS takes this approach in his process planner.

The introduction of continuous processes into the planning problem represents a considerable complication, even over a model that includes temporal features and supports concurrency. It is an area of active research and the community has not yet agreed on matters of representation, let alone semantics. There remain many open problems for the planning community to address, both in the development of languages and planning algorithms and also in in the development of plan verification tools that can embody a widely accepted semantics.

next up previous
Next: Conclusions Up: Related Work: Representing and Previous: Temporal extent
Derek Long 2003-11-06