next up previous
Next: Related Approaches Up: Durative Actions Previous: Numeric Change within Discretised

Durative Actions with Continuous Effects

The objective of discrete durative actions is to abstract out continuous change and concentrate on the end points of the period over which change takes place. The syntax allows precise specification of the discrete changes at the end points of durative actions. However, when a plan needs to manage continuously changing values, as well as discretely changing ones, the durative action language and semantics need to be more powerful. General durative actions can have continuous as well as discrete effects. These increase, or decrease, some numeric variable according to a specified rate of change over time for that variable. When determining how to achieve a goal a planner must be able to access the values of these continuous quantities at arbitrary points on the time-line of the plan. We use $\char93 $t to refer to the continuously changing time from the start of a durative action during its execution. For example, to express the fact that the fuel level of a plane, $?p$, decreases continuously, as a function of the consumption rate of $?p$, we write:

(decrease (fuel-level ?p) (* $\char93 $t (consumption-rate ?p)))
This is distinctly different from:
(at end (decrease (fuel-level ?p)
(* (flight-time ?a ?b) (consumption-rate ?p))))
because the latter is a single update happening at the end point of the flight action, whilst the former allows the correct calculation of the fuel level of the plane at any point in that interval. The former is a continuous effect, whilst the latter is a discrete one. Continuous effects are not temporally annotated because they can be evaluated at any time during the interval of the action. $\char93 $t is local to each durative action, so that each durative action has access to a purely local ``clock''. Another way to interpret the expression representing continuous change is as a differential equation:

\begin{displaymath}\frac{d}{dt} \mbox{\small {\tt {(fuel-level ?p)}}} = \mbox{\small {\tt {(consumption-rate ?p)}}}\end{displaymath}

We chose to use the $\char93 $t symbol instead of a differential equation because it is possible for two concurrent actions to be simultaneously modifying the same quantity. In that case, the use of differential equations would actually form an inconsistent pair of simultaneous equations, rather than having the intended effect of a combined contribution to the changing value of the quantity. Although all of the expressions describing continuous change take the form of a product of $\char93 $t and some quantity, it is possible to express complex change using them with interdependent concurrent effects. For example, acceleration arises by simply increasing distance using a quantity describing velocity, while at the same time increasing velocity using a quantity describing acceleration. When dependencies between the changing terms include mutual dependencies between terms then the differential equations that arise can lead to continuous change dictated by exponential, logarithmic and exponential functions.

A plan containing continuous durative actions can assign to, consult, and continuously modify the same numeric variables concurrently (see Example 1).

% latex2html id marker 1232
\fbox{\begin{minipage}{5.5in}\begin{example}In the f...
...nt with maintaining the invariant of the fly action.\end{example}\end{minipage}}

Figure 11: A continuous durative action for flying.
\begin{figure}{\footnotesize\begin{verbatim}(:durative-action fly
...:effect (assign (fuel-level ?p) (fuel-capacity ?p)))\end{verbatim}}

In Figures 12 and 14 the discrete and continuous actions for heating a pan of water are presented (this simple model ignores heat loss). The discrete action presented in Figure 12 modifies the version presented in Figure 7 by the use of a duration inequality constraint. Duration inequalities add significant expressive power over duration equalities. Duration constraints that express inequalities are associated with an additional requirements flag because of the extended expressiveness over fixed-duration discrete durative actions.

In both actions, the logical post-condition of the start of the period is that the pan is heating. The conditions that the pan be heating, full and on the heat source are invariant, although the presence of the agent (by the pan) is only a local precondition of the two end-points and is not invariant. In the first action the duration is modelled by expressing the following duration inequality constraint:

(at end (<= ?duration (/ (- 100 (temperature ?p)) (heat-rate))))
and the effect at the end-point of the discrete durative action is that the temperature of the pan is increased by (* ?duration (heat-rate)) (where heat-rate is a domain constant). In the continuous action of Figure 14 the duration constraint is unnecessary since the invariant
(over all (<= (temperature ?p) 100))
is added to ensure that the pan never exceeds boiling.

Figure 12: A discrete durative action for heating a pan of water, using a variable duration.
\begin{figure}{\footnotesize\begin{verbatim}(:durative-action heat-water
:par... (temperature ?p)
(* ?duration (heat-rate)))))

The durative action in Figure 12 models the heating pan in the face of possible concurrent activities affecting the temperature. The duration inequality allows the planner to adapt the duration to take account of other temperature-affecting activity in a way that is not possible when the duration is specified using an equality constraint. The duration constraint ensures that the temperature never exceeds boiling by checking, as a precondition for the updating activity, that the computed temperature increase can be executed without exceeding the boiling point. If this temperature increase would exceed boiling the plan is invalid. The temperature at the end of the interval of execution is computed from the current temperature and the heating rate, together with the duration over which the heating action has been active (see further discussion in Example 2).

% latex2html id marker 1268
\fbox{\begin{minipage}{5.5in}\begin{example}If a pla... choose to exploit them or avoid them accordingly.\end{example}\end{minipage}}

Figure 13: Heating a pan with a discrete durative action, concurrently with another heating activity.

Figure 14: A continuous durative action for heating a pan of water.
\begin{figure}{\small\begin{verbatim}(:durative-action heat-water
(increase (temperature ?p) (*  ...

The use of duration inequalities adds significant expressive power even when using discrete durative actions. For example, the plan depicted in part (a) of Figure 13, which illustrates the use of the water-heating action shown in Figure 12 while concurrently heating the pan with a blowtorch, will be considered valid provided that there is a duration value that satisfies the duration constraint in the water-heating action. This brings us very close to the expressive power available with continuous durative actions because it gives the planner the power to exploit concurrent interacting activities enacting changes on the same numeric valued variable (see Example 3). Attempting to express continuous change using only duration inequalities does not give precisely equivalent behaviour, because the discretisation forces actions that access changing numeric values to be separated, by some small temporal interval, from the actions that change those values in order to resolve their mutual exclusion. In a continuous model this is not necessary because the true value of a numeric variable is available for consultation at any time during the continuous process of change.

% latex2html id marker 1284
\fbox{\begin{minipage}{5.5in}\begin{example}It is po...
...tinuous effects are not localised at a single point.\end{example}\end{minipage}}

In the discrete semantics presented in Section 8 we exploit the fact that the only changes that can occur when a plan is executed are at points corresponding to the times of happenings, so the plan can be checked by looking at the activity focussed in this finite happening sequence. In fact, provided continuous effects are restricted to linear functions of time with only first order effects (which requires that no continuous effects can affect numeric expressions contributing to the rate of change of another numeric valued variable), and invariants are restricted to linear functions of changing quantities, it is still possible to restrict attention to the happening sequence even when using continuous actions.

Non-linear effects and higher-order rates of change create difficulties since it is possible for an invariant to be satisfied at the end points of an interval, without having necessarily been satisfied throughout the interval. In these cases it is no longer sufficient to insert invariant checking actions at fixed mid-points in the happening sequence of a plan in order to validate its behaviour. However, provided that effects are first-order and linear, and invariants are linear in continuously changing values, then, despite the fact that arbitrary time points within action intervals are accessible to the planner, it is only necessary to gain access to numeric values at the start- and end-points of the actions in the plan that refer to them, together with finitely many mid-points for invariant-checking actions. The values are not required at all other points. This is so because continuous durative actions do not support the modelling of exogenous events, so it is not necessary to take into account the exogenous activity of the environment in determining the validity of a plan.

next up previous
Next: Related Approaches Up: Durative Actions Previous: Numeric Change within Discretised
Derek Long 2003-11-06