Durative Actions with Conditional Effects

We now explain how the mapping described in the previous section is extended to deal with durative actions containing conditional effects.

First, we observe that temporally annotated conditions and effects can be accumulated, because the temporal annotation distributes through logical conjunction. Therefore, we can convert conditional effects so that their conditions are simple conjunctions of at most one at start condition, at most one at end condition and at most one over all condition. It should be noted that we do not allow logical connectives other than conjunction in combining temporally annotated propositions. Allowing other connectives would create significant further complexity in the semantics and create potentially paradoxical opportunities for communication from future states to earlier states. Similarly to conditions, durative action effects can be reduced to a conjunction of at most one at start effect and at most one at end effect. Treatment of conditional effects then divides into three cases. The first case is very straightforward: any effect in a durative action of the form (when (at t p) (at t q)), where the condition and the effect bear the same single temporal annotation, can be transformed into a simple conditional effect of the form (when p q) attached to the start or end simple action according to whether $t$ is start or end. Since this case is straightforward we will not explicitly extend the previous definitions to cope with it. The second case is one in which the condition of a condition effect has at start conditions and the effect has at end effects.

Note that we consider conditional effects in which the effects occur at the start, but with conditions dependent on the state at the end or over the duration of the action, to be meaningless. This is because they reverse the expected behaviour of causality, where cause precedes effect. In any attempt to validate a plan by constructing a trace such reversed causality would be a huge problem, since we could not determine the initial effects of applying a durative action until we had seen what conditions held over the subsequent interval and conclusion of its activity, but, equally, we could not see what the effects of activity during the interval would be without seeing the initial effects of applying the durative action. This paradox is created by the opportunity for an action to change the past.

To handle this second case we need to modify the state after the start of the durative action to ``remember'' whether the start conditions were satisfied and communicate this to the end of the durative action where it can then be simply looked up in the (then) current state to determine whether the conditional effect should be applied. We apply a transformation to conditional effects of the form (when (and (at start ps) (at end pe)) (at end q)) into a conditional effect added to the start simple action, (when ps (M$_{ps}$)), and a conditional effect added to the end simple action, (when (and pe (M$_{ps}$)) q), where M$_{ps}$ is a special new proposition, unique to the particular conditional effect of the particular application of the durative action being transformed. By ensuring that this proposition is unique in this way, there is no possibility of any other action in the plan interfering with it, so it represents an isolated memory of the fact that ps held in the state at which the durative action was started. If a conditional effect does not have at end conditions, the same transformation can be applied, simply ignoring pe in the previous discussion. Figure 15 depicts the transformation of a single durative action, $A$, with a conditional effect, into a collection of level 2 actions, complete with the appropriate ``memory'' proposition (in this case called $P^{*}$).

Figure 15: Conversion of a durative action into non-durative actions and their grounded forms.

The importance of the memory introduced in this transformation is explained in Figures 16 and 17. Figure 16 shows the ambiguity that results from not remembering how a state, on the trajectory of a plan, was reached. The figure illustrates that if one is in a state $(P,Q,\neg R)$ at the point when durative action $A$ (as described in Figure 15) ends, it is impossible to determine from the state alone whether $R$ should be added or not. This is because it is possible to have reached the state $(P,Q,\neg R)$ by at least two different paths, with at least one path having seen $A$ started in a state in which $P$ held and at least one path having seen $A$ started in a state in which $P$ did not hold (using an action, achieve-$P$, with $P$ as its only effect). The state $(P,Q,\neg R)$ does not contain any information to disambiguate which path was used to reach it, and hence cannot determine the correct value of $R$ after $A$ ends.

The third, and final, case is where the durative action has conditional effects of the form:

(when (and (at start ps) (over all pi) (at end pe)) (at end q)).

Again, if the effect has no at start or at end conditions the following transformation can be applied simply ignoring ps or pe as appropriate. In this case we need to construct a transformation that ``remembers'' not only whether ps held in the state at which the durative action is first applied, but also whether pi holds throughout the interval from the start to the end of the durative action. Unlike the invariants of durative actions, these conditions are not required to hold for the plan to be valid, but only determine what effects will occur at the end of the durative action. The idea is to use intervening monitoring actions, rather as we did for invariants in definition 18. This is achieved by adding a further effect to the start action: (M$_{pi}$). Then, the monitoring (simple) actions that are required have no precondition, but a single conditional effect: (when (and (M$_{pi}$) (not pi)) (not (M$_{pi}$))). Once again, M$_{pi}$ is a special new proposition unique to the conditional effect for the application instance of the durative action being transformed. The monitoring actions are added at all the intermediate points that are used for the monitoring actions in Definition 18. The same transformation used in the second case above is required again for the at start condition, ps, so (when ps (M$_{ps}$)) is added as a conditional effect to the start simple action. Finally, we add a conditional effect to the end (simple) action: (when (and (M$_{ps}$) (M$_{pi}$) pe) q).

Figure 16: Flawed state space resulting from failure to record the path traversed when conditional effects span the interval of a durative action. The arc labelled achieve-P indicates the possible application of some action that achieves the proposition P.

The effect of this machinery is to ensure that if the proposition pi becomes false at any time between the start and end of the durative action then M$_{pi}$ will be deleted, but otherwise at the end of the durative action M$_{ps}$ will hold precisely if ps held at the start of the action and M$_{pi}$ will hold precisely if pi has held over the entire duration of the durative action. Therefore, the conditional effect of the end action achieves the intuitively correct behaviour of asserting its conditional effect precisely when the at start condition held at the start of the durative action, the at end condition holds at the end of the durative action and its over all condition has held throughout the duration of the action.

Figure 17: Correct state space showing use of ``memory'' proposition P*. The arc labelled achieve P indicates the possible application of some action that achieves the proposition P.

The addition of these new memory-checking actions means that it is no longer true to claim that the added actions cannot change the state. However, memory propositions are unique to the task of communication for a single action instance, so the effects that memory-checking actions might have on these have no implications for other invariants.