The Semantics of Continuous Durative Actions

The introduction of continuous durative actions complicates the semantics. It is no longer possible to handle invariants by insertion of simple actions between other happenings in a plan to test their continued satisfaction. In fact, continuous effects can, in principle, cause an invariant to be satisfied over some parts of an interval and not over others. Ignoring invariants for a moment, updates to numeric values caused by continuous effects can be applied as discrete updates at time points within the interval over which they apply. These updates behave slightly differently to the discrete updates we have seen in durative actions with discrete effects, since it is possible for a continuous update to affect a variable that is concurrently affected by a discrete update, or examined by a precondition, without creating an inconsistency. For example, if the water heating action in Figure 14 is applied with the concurrent addition of an egg to the pan with a precondition that the temperature of the water is between 90 and 95 degrees then the value of the temperature can be examined at the moment of application of the action adding the egg. This is because the temperature change is actually happening over the interval between the start of the heating and the point at which the egg is added, rather than as a discrete update at the point the egg is added. The temperature is not actually changed at the instant of the addition of the egg.

In this section we summarise the semantics for continuous actions. Where the semantics for discrete durative actions is defined in terms of the familiar state-transition semantics, the continuous semantics introduces a different formulation.

Definition 21   A Continuous Durative Action A continuous effect is an effect expression that includes the symbol $\char93$t. A continuous durative action is a durative action with at least one continuous effect.

Definition 22   Continuous Update Function Let $C$ be a set of ground continuous effects for a planning instance, $I$, and $St = (t,S,{\bf X})$ be a state. The continuous update function defined by $C$ for state $St$ is the function $f_{C} : {\mathbb{R}} \rightarrow {\mathbb{R}}^n$, where $n$ is dim$_{I}$, such that:

$$\frac{df_{C}}{dt} = g$$

and

$$f_{C}(0) = {\bf X}$$

where $g$ is the update function generated for an action $a$ with:

$$NP_{a} = \{ \, \mbox{\small {\tt {(<op> P Q)}}} \, \vert \, \mbox{\small {\tt {(<op> P (* $\char93 $t Q))}}} \in C\}$$

Definition 22 shows how the continuous effects of several continuous durative actions can be combined to create a single system of simultaneous differential equations whose solution, given an appropriate starting point, defines the evolution of the continuously varying values.

Definition 23   Induced Continuous Plan Let $I$ be a planning instance that includes continuous durative actions and $P$ be a plan for $I$. The induced continuous plan for $P$ is a triple, $(S,Invs,Cts)$, where $S$ is $simplify(P)$, $Invs$ is the set of invariant constraints:

$$Invs = \{ (Q,t,t+d) \, \vert \, (t,a[d]) \in P \, \mbox{and} ... ...mall {\tt {(over all Q)}}} \, \mbox{is an invariant for} \, A\}$$

Let $t_{i}$ and $t_{i+1}$ be two consecutive times in the happening sequence for $simplify(P)$. The set of active continuous effects over $(t_{i},t_{i+1})$ is:

$$\{ Q \, \vert \, (t,a[d]) \in P, (t_{i},t_{i+1}) \subseteq [t,t+d] \, \mbox{and $Q$\ is a continuous effect of $a$}\}$$

and $Cts$ is the set of systems of continuous effects:

$$Cts = \{ (C,t_{i},t_{i+1}) \, \vert \, C \, \mbox{is the set of active continuous effects over $(t_{i},t_{i+1})$}\}$$

The components of a continuous plan separate out the invariant conditions and continuous effects from the rest of the simple plan in order to allow correct application of the continuous updates and to allow confirmation that the invariants hold in the face of the continuous effects.

Definition 24   Trace Let $I$ be a planning instance that includes continuous durative actions, $P$ be a plan for $I$, $(SP,Inv,Cts)$ be the induced continuous plan for $P$, $\{t_{i}\}_{i=0...k}$ be the happening sequence for $S$ and $S_{0}$ be the initial state for $I$. The trace for $P$ is the sequence of states $\{S_{i}\}_{i=0...k+1}$ defined as follows:

• If there is no element $(C,t_{i},t_{i+1}) \in Cts$ then $S_{i+1}$ is the state resulting from applying the happening at $t_{i}$ in the simple plan $SP$ to the state $S_{i}$.
• If $(C,t_{i},t_{i+1}) \in Cts$ then let $T_{i}$ be the the state formed by substituting $f(t_{i+1}-t_{i})$ for the numeric part of state $S_{i}$, where $f$ is the continuous update function defined by $C$ for state $S_{i}$. Then $S_{i+1}$ is the state resulting from applying the happening at $t_{i}$ in the simple plan $SP$ to the state $T_{i}$. If $f$ is undefined for any element in $Cts$ then so is the trace.

Definition 24 defines a trace in a similar fashion to the traces for simple plans and plans with durative actions. The key difference is the need to apply the continuous updates. These are handled by solving the systems of simultaneous differential equations across each interval in which they are active and then applying the result to update the numeric values across that interval. Of course, this is easier to describe than it is to do, since solving arbitrary simultaneous differential equations algorithmically is not generally possible. Under certain constraints this semantics can be implemented in order to confirm the validity of a plan automatically.

Definition 25   Invariant Safe Let $I$ be a planning instance that includes continuous durative actions, $P$ be a plan for $I$, $(S,Inv,Cts)$ be the induced continuous plan for $P$ and $\{S_{i}\}_{i=0...k+1}$ be the trace for $P$. For each $(C,t_{i},t_{i+1}) \in Cts$ let $f_{i}$ be the continuous update function defined by $C$ for $S_{i}$. $P$ is invariant safe if, for each $f_i$ that is defined and for each $(Q,t,u) \in Inv$ such that $[(t_{i},t_{i+1})] = I \subseteq (t,u)$, then $\forall x \in I$, ${\mathbb{N}um}(s,Q)(f_{i}(x))$ where $s$ is the logical state in $S_{i}$.

In this definition, the symbols $[(..)]$ are used to mean that the interval $I$ can be closed or open at either end.

From a semantic point of view, invariants must be checked at every point in the interval over which they apply. When the interval contains only finitely many discrete changes then the obligation can be met by considering only the finite number of points at which change occurs (a fact that is exploited for discrete durative action plan semantics in Definition 18). When there is continuous change the obligation is much harder to meet. In practice, the invariants can be checked by examining the possible roots of the function describing continuous change, but finding those roots can be very difficult in general. Again, suitable constraints on the forms of differential equations expressed in a domain can make the validation problem tractable.

The last two definitions simply assemble the components to arrive at analogous definitions to those for executability and validity of simple plans and plans with durative actions.

Definition 26   Executability of a Plan A plan $P$ containing continuous durative actions, for planning instance $I$, with induced continuous plan $(S,Invs,Cts)$. $P$ is executable if the trace for $P$ is defined, $\{S_{i}\}_{i=0...k+1}$, and it is invariant safe.

Definition 27   Plan Validity A plan $P$ containing durative actions, for planning instance $I$ is valid if it is executable, with trace $\{S_{i}\}_{i=0...k+1}$ and $S_{k+1}$ satisfies the goal in $I$.