next up previous
Next: The Interpretation of Concurrent Up: PDDL2.1 : An Extension Previous: Plan Metrics

Durative Actions

Most recent work on temporal planning [Smith WeldSmith Weld1999,Bacchus KabanzaBacchus Kabanza2000,Do KambhampatiDo Kambhampati2001] has been based on various forms of durative action. In order to facilitate participation in the competition we therefore developed two forms of durative action allowing the specification only of restricted forms of timed conditions and effects in their description. Although constrained in certain ways, these durative actions are, nevertheless, more expressive than many of the proposals previously explored, particularly in the way that they allow concurrency to be exploited. The two forms are discretised durative actions and continuous durative actions.

Both forms rely on a basic durative action structure consisting of the logical changes caused by application of the action. We always consider logical change to be instantaneous, therefore the continuous aspects of a continuous durative action refer only to how numeric values change over the interval of the action. Figure 6 depicts a basic durative action, load-truck, in which there is no numeric change.

Figure 6: A durative action for loading a truck. We assume no capacity constraints.
\begin{figure}{\footnotesize\begin{verbatim}(:durative-action load-truck
... (not (at ?o ?l)))
(at end (not (holding ?c ?o)))

The modelling of temporal relationships in a discretised durative action is done by means of temporally annotated conditions and effects. All conditions and effects of durative actions must be temporally annotated. The annotation of a condition makes explicit whether the associated proposition must hold at the start of the interval (the point at which the action is applied), the end of the interval (the point at which the final effects of the action are asserted) or over the interval from the start to the end (invariant over the duration of the action). The annotation of an effect makes explicit whether the effect is immediate (it happens at the start of the interval) or delayed (it happens at the end of the interval). No other time points are accessible, so all discrete activity takes place at the identified start and end points of the actions in the plan.

Invariant conditions in a durative action are required to hold over an interval that is open at both ends (starting and ending at the end points of the action). These are expressed using the over all construct seen in Figures 6 and 8. If one wants to specify that a fact $p$ holds in the closed interval over the duration of a durative action, then three conditions are required: (at start p), (over all p) and (at end p).

We considered adopting the convention that over all constraints should apply to the start and end points as well as the open interval inside the durative action, but decided against this because it would then be impossible to express conditions that are actually only required to hold over this open interval. Examples of actions in which conditions are invariant only over the open interval include the action of loading a truck. The truck must remain at the loading location throughout the loading interval, but it can start to move away simultaneously with the loading being completed. The reason is that the start of the drive action is non-mutex with the end of the load so there is a reasonable interpretation of any plan in which driving starts at the instant that loading is completed. Actions that affect an invariant condition (such as the location of the truck) can be executed simultaneously with the end point of a durative action only if the invariant is not constrained to hold true at the end point itself. This highlights an important difference between (over all) and (over all and at end). If a condition is required as an end precondition as well as an invariant condition the meaning is that any action that affects the invariant must start after the end of the action requiring that invariant. For example, if we make (at truck location) an end precondition of the load operator as well as an invariant, the consequence is that the truck cannot drive away until after the instant at which the load has completed.

Note that, in our definition of the load-truck action in Figure 6, we have chosen to make the condition (holding ?c ?o) be a start effect and an end precondition but not an invariant condition. This means that the crane could temporarily cease to hold the cargo at some time during the interval, as long as it is holding the cargo in time to deposit it at the end of the loading interval. This makes the action quite flexible, enabling the exploitation of concurrent uses of the crane where applicable.

The load-truck example shows how logical change can be wrapped up into durative actions that encapsulate much of the detail involved in achieving an effect by a sequence of connected activities. Naturally it would be useful to be able to combine such actions concurrently within a plan. In the next section we consider the extent to which concurrency is allowed and the ways in which concurrent plans are interpreted.

next up previous
Next: The Interpretation of Concurrent Up: PDDL2.1 : An Extension Previous: Plan Metrics
Derek Long 2003-11-06