Related Approaches

Time is an important numerically varying quantity. The simplest way to reason about time is to adopt a black box durative action model in which change happens at the ends of their durative intervals. This is the approach taken in the language used by TGP [Smith WeldSmith Weld1999], for example, in which durative actions encapsulate continuous change so that the correct values of any affected variables are guaranteed only at the end points of the implied intervals. All of the logical and numeric effects of a durative action are enacted at the end of the action and are undefined during the interval of its execution. All undeleted preconditions must remain true throughout the interval. There is no syntactic distinction between preconditions and invariant conditions in this action representation. A simplistic way of ensuring correct action application is to prevent concurrent actions that refer to the same facts, but this excludes many intuitively valid plans.

A more sophisticated approach allows preconditions to be annotated with time points, or intervals, so that the requirement that a condition be true at some point, or over some interval, within the duration of the action can be expressed. This is the approach taken in Sapa [Do KambhampatiDo Kambhampati2001]. For example, using such an annotated precondition it would be possible to express the requirement that some chemical additive be added within two minutes of the start of a tank-filling action. If effects can also be specified to occur at arbitrary points within the duration of the action then it is possible to express effects that occur before the end of the specified duration. It is also possible to distinguish between conditions that are local to specific points in the duration of the action and those that are invariant throughout the action.

Allowing reference to finitely many time points between the start and end of actions makes the language more complex without adding to its expressive power. Where time points are strictly scheduled relative to the start of the action the effect can be achieved through the use of a sequence of linked durative actions. We decided to keep PDDL2.1 simple by restricting access to only the end points of actions.

In TLPlan [Bacchus AdyBacchus Ady2001] a similar, but more constrained, approach is adopted in which actions are applied instantaneously but can have delayed effects. The delays for effects can be arbitrary and different for each effect. However, invariants cannot be specified because the preconditions are checked at the instant of application and subsequent delayed effects are separated from the action which initiated them.

Several planners have been developed to use networks of temporal constraints [Ghallab LaruelleGhallab Laruelle1994,Jonsson, Morris, Muscettola, RajanJonsson et al.2000,El-Kholy RichardsEl-Kholy Richards1996] to handle temporal structure in planning problems. Efficient algorithms exist for handling such constraints [Dechter, Meiri, PearlDechter et al.1991] which make them practical for managing large networks. The domain models constructed using PDDL2.1 certainly lend themselves to treatment by similar techniques, but are not constrained to be handled in this way.