The Semantics of Durative Actions

Plans with durative actions with discrete effects can be given a semantics in terms of the semantics of simple plans. Handling durative actions that have continuous effects is more complex -- we discuss this further in Section 9.

Durative actions appearing in a plan must be given with an additional field indicating the duration. This is given with the syntax:

$$t:(action \, p_{1} \ldots p_{n})\, [d]$$

where $d$ is a rational valued duration, written in floating point syntax.

Durative actions are introduced into the framework we have defined so far by generalising Definition 1 to include durative action schemas. The definition of the grounded action must now be extended to define the form of grounded durative actions. However, this definition can be given in such a way that we associate with each durative action two simple (non-durative) actions, corresponding to the end points of the durative action. These simple actions can, together, simulate almost all of the behaviour of the durative action. The only aspects that are not captured in this pair of simple actions are the duration of the durative action and the invariants that must hold over that duration. These two elements can, however, be simply handled in a minor extension to the semantics of simple plans, and this is the approach we adopt. By taking this route we avoid any difficulties in establishing the effects of interactions between durative actions -- this is all handled by the semantics for the concurrent activity within a simple plan. As we will see, one difficulty in this account is the handling of durative actions with conditional effects that contain conditions and effects that are associated with different times or conditions that must hold over the entire duration of the action. Since these cases complicate the semantics we will postpone treatment of them until the next section and begin with durative actions without conditional effects.

The mapping from durative actions to non-durative actions has the important consequence that the mutex relation implied between non-durative actions is (advantageously) weaker than the strong mutex relation used in, for example, TGP [Smith WeldSmith Weld1999]. Two durative actions can be applied concurrently provided that the end-points of one action do not interact either with the end-points (if simultaneous) or the invariants of the other action.

Definition 16   Grounded Durative Actions Durative actions are grounded in the same way as simple actions (see Definition 6), by replacing their formal parameters with constants from the planning instance and expanding quantified propositions. The definition of durative actions requires that the condition be a conjunction of temporally annotated propositions. Each temporally annotated proposition is of the form (at start p), (at end p) or (over all p), where $p$ is an unannotated proposition. Similarly, the effects of a durative action (without continuous or conditional effects) are a conjunction of temporally annotated simple effects.

The duration field of $DA$ defines a conjunction of propositions that can be separated into $DC^{DA}_{start}$ and $DC^{DA}_{end}$, the duration conditions for the start and end of $DA$, with terms being arithmetic expressions and ?duration. The separation is conducted in the obvious way, placing at start conditions into $DC^{DA}_{start}$ and at end conditions into $DC^{DA}_{end}$.

Each grounded durative action, $DA$, with no continuous effects and no conditional effects defines two parameterised simple actions $DA_{start}$ and $DA_{end}$, where the parameter is the ?duration value, and a single additional simple action $DA_{inv}$, as follows.

$DA_{start}$ ($DA_{end}$) has precondition equal to the conjunction of the set of all propositions, $p$, such that (at start p) ((at end p)) is a condition of $DA$, together with $DC^{DA}_{start}$ ($DC^{DA}_{end}$), and effect equal to the conjunction of all the simple effects, $e$, such that (at start e) ((at end e)) is an effect of $DA$ (respectively).

$DA_{inv}$, is defined to be the simple action with precondition equal to the conjunction of all propositions, $p$, such that (over all p) is a condition of $DA$. It has an empty effect.

Every conjunct in the condition of $DA$ contributes to the precondition of precisely one of $DA_{start}$, $DA_{end}$ or $DA_{inv}$. Every conjunct in the effect of $DA$ contributes to the effect of precisely one of $DA_{start}$ or $DA_{end}$. For convenience, $DA_{start}$ ($DA_{end}$, $DA_{inv}$) will be used to refer to both the entire (respective) simple action and also to just its name.

The actions $DA_{start}$ and $DA_{end}$ are parameterised by ?duration and this parameter must be substituted with the correct duration value in order to arrive at the two simple actions corresponding to the start and end of a durative action.

Definition 17   Plans A plan, $P$, with durative actions, for a planning instance, $I$, consists of a finite collection of timed actions which are pairs, each either of the form $(t,a)$, where $t$ is a rational-valued time and $a$ is a simple action name - an action schema name together with the constants instantiating the arguments of the schema, or of the form $(t,a[t'])$, where $t$ is a rational-valued time, $a$ is a durative action name and $t'$ is a non-negative rational-valued duration.

Definition 18   Induced Simple Plan If $P$ is a plan then the happening sequence for $P$ is $\{t_{i}\}_{i=0\ldots k}$, the ordered sequence of time points formed from the set of times¹

$$\{ t \, \vert \, (t,a) \in P \, \mbox{or} \, (t,a[t']) \in P \, \mbox{or} \, (t-t',a[t']) \in P\}$$

The induced simple plan for a plan $P$, simplify$(P)$, is the set of pairs defined as follows:

• $(t,a)$ for each $(t,a) \in P$ where $a$ is a simple (non-durative) action name.
• $(t,a_{start}[{\bf ?duration} := t'])$ and $(t+t',a_{end}[{\bf ?duration} := t'])$ (these expressions are simple timed actions - the square brackets denote substitution of $t'$ for ?duration in this case) for all pairs $(t,a[t']) \in P$, where $a$ is a durative action name.
• $((t_{i}+t_{i+1})/2,a_{inv})$ for each pair $(t,a[t']) \in P$ and for each $i$ such that $t \leq t_{i} < t+t'$, where $t_{i}$ and $t_{i+1}$ are in the happening sequence for $P$.

The process of transforming a plan into a simple plan involves introducing actions to represent the end points of the intervals over which the durative actions in the plan are applicable. Duration constraints convert into simple preconditions on start or end actions, requiring the substitution of a numeric value for the ?duration field to complete the conversion into simple actions. The complication to this process is that invariants cannot be associated with the end points, but must be checked throughout the interval. This is achieved by adding to the simple plan a collection of special actions responsible for checking the invariants. These actions are added between each pair of happenings in the original plan lying between the start and end point of the durative action. Because the semantics of simple plans requires that the preconditions of actions in the plan be satisfied, even though they might have no effects, the consequence of putting these monitoring actions into the simple plan is to ensure that the original plan is judged valid only if the invariants remain true, firstly, after the start of the durative action and, subsequently, after each happening that occurs throughout the duration of the durative action. One possibility is to make these monitoring actions occur at the same times as the updating actions, but this would require values to be accessed at the same time as they might be being updated, violating the no moving targets rule. In order to avoid this problem the monitoring actions are interleaved with the updating actions by inserting them midway between pairs of successive happenings in the interval over which each durative action is executed. Only happenings in the original plan need be considered when carrying out this insertion, since the invariant-checking actions themselves cannot have any effect on the states in which they are checked.

Alternative treatments of invariants are possible, but an important advantage of the approach we have taken is that the semantics rests, finally, on a state-transition model in a form that is familiar to the planning community. That is, plans can be seen as recipes for state-transition sequences, with each state-transition being a function from the current state of the world to the next. However, durative actions complicate this picture because they rely on a commitment, once a durative action has been started, to follow it through to completion. That commitment involves some sort of communication across the duration of the plan. The communication can be managed by structures outside the plan, that examine the trace, or by artificial modification of the plan itself to ensure that states carry extra information from the start to the end of the durative action. The latter approach has the disadvantage that as durative actions become more complex the artificial components that must be added to the plan become more intrusive. This is particularly apparent in the treatment of conditional effects that require conditions tested at the start of a durative action, or across its duration, but effects that are triggered at the end, since these cases require some sort of ``memory'' in the state to remember the status of the tested conditions from the start of the durative action to the end point. These memory conditions allow us to avoid embedding an entire execution history in a state by substituting an ad hoc memory of the history for just those propositions and at just those times it is required. The management of conditional effects of this form, in the mapping from durative actions to simple actions, is discussed further in Section 8.1.

We can now conclude the definitions supporting the validity of a plan with durative actions.

Definition 19   Executability of a Plan A plan, $P$ (for a planning instance), is executable if the induced simple plan for $P$, simplify$(P)$ is executable, producing the trace $\{S_{i} = (t_{i},s_{i},{\bf v}_{i})\}_{i=0 \ldots k}$.

Definition 20   Validity of a Plan A plan, $P$ (for a planning instance), is valid if it is executable and if the goal specification is satisfied in the final state produced by its induced simple plan.