Numeric Change within Discretised Durative Actions

This section explains how continuous change can sometimes be modelled in PDDL2.1 using durative actions with discrete effects. This is achieved by using step functions to describe instantaneous changes at the beginnings or ends of the durations of actions. Appendix A details the language constructs involved.

An example of a durative action, illustrating the use of numeric update operations, is shown in Figure 7.

Figure 7: A simple durative action for boiling a pan of water.

In this example showing a water heating action, the conditions (full ?p) and (onHeatSource ?p) must hold at the start of the interval as well as during the interval. To model this we enter these conditions as both at start and over all constraints. The action achieves as its start effect that the water is heating, and this condition is maintained invariant over the whole interval of the action. This is an example of an operator that achieves its own invariant condition, and draws attention to the fact that over all conditions hold over an interval that is open on the left (as well as on the right).

It should be noted that the actions in Figures 7 and 8 use fixed duration specifications. In the case of the water-boiling example this means that it is impossible to adjust the length of time over which the pan is heated and this has an impact on the context in which the action can be used. In particular, when an assign construct is used to update a numeric value, it is not possible for concurrent activity to affect the same value or else the model will be flawed. Because the water heating example uses an assign construct no concurrent activity should affect the temperature of the water. It is the responsibility of the modeller to ensure that the temperature is neither accessed nor updated during the interval over which the action is executing.

We decided to leave it to the modeller to ensure correct behaviour of the assign construct because we did not want to forbid the modelling of truly discontinuous updates. For example, a durative action that models the deposit of a cheque in a bank account might have a duration of three days, with a discontinuous update to the account balance at the end of that interval -- it would be inappropriate to prevent actions from accessing the balance during the three day period. In general, modelling continuous change with discrete effects is open to various pitfalls. This is the price that is paid for the convenience of not having to specify the details of the continuous processes.

The use of discretised durative actions in combination with numeric (step-function) updates requires care in modelling. In particular, it relies on the notion of conservative resource updating. The updating of resource levels is conservative if the consumption of a resource is modelled as if it happens at the start of a durative action, even though it actually happens continuously over the duration of the action, and production of a resource is modelled as if it happens at the end of the durative action even though, again, it might actually be produced continuously over the interval.

Figure 8: Discretised durative actions for a rover to move between locations and to recharge.

(:durative-action navigate
:parameters (?x - rover ?y - waypoint ?z - waypoint) 
:duration (= ?duration (travel-time ?y ?z))
:condition (and (at start (available ?x)) 
                (at start (at ?x ?y))  
                (at start (>= (energy ?x) 
                            (* (travel-time ?y ?z) (use-rate ?x))))
                (over all (visible ?y ?z))
                (over all (can_traverse ?x ?y ?z)))
:effect (and (at start (decrease (energy ?x) 
                            (* (travel-time ?y ?z) (use-rate ?x)))) 
             (at start (not (at ?x ?y))) 
             (at end (at ?x ?z))))

(:durative-action recharge
:parameters (?x - rover ?w - waypoint)
:duration (= ?duration (recharge-period ?x))
:condition (and (at start (at ?x ?w))
                (at start (in-sun ?w)) 
                (at start (<= (energy ?x) (capacity ?x)))
                (over all (at ?x ?w)))
:effect (at end (increase (energy ?x) (* ?duration (recharge-rate ?x)))))

As an example of a discretised durative action, Figure 8 shows how the action of a rover navigating between two points is modelled. The local precondition of the start of the period is that the rover be at the start location. Local effects include that the rover consumes an appropriate amount of energy and that it is at the destination. The first of these is conservative and therefore immediate, while the second is a logical effect that occurs at the end point. This organisation ensures that no parallel activities will consume energy that has already been committed to the navigation activity. Similarly, the recharge action only makes new charge available at the conclusion of the action, so that charge gained cannot be exploited until after the recharging is complete. The use of conservative updates ensures that a model does not support invalid concurrency.

Figure 9: Using discrete actions to model the production and consumption of a resource. In reality, the recharge activity produces energy continuously and the concurrent dig activity continuously consumes it. The conservative model using step functions requires that the energy consumed by digging must be available at the start of that action, despite not having yet updated the model to show the additional energy accumulated because of the part of the recharge action so far executed. The final energy level is consistent with having used a continuous model.

Figure 9 illustrates how a recharging and a digging action (that consumes energy) would interact under a conservative energy consumption model. This model would allow concurrent actions to consume energy provided they did not consume more energy than was left under the conservative assumption that the dig action consumed all of its demands at the start and the recharge action produced nothing until the end. Note that the example assumes energy constraints but no capacity constraint.

The use of conservative updates is subtle. If there were a capacity constraint on the energy level of the rover then one would need to consider two separate resources: the energy itself and the space available for storage of energy. The dig action would consume energy at the start and only produce space at the end, while the recharge action would consume space at the start and produce charge at the end. Using this combination it would be possible to ensure that plans did not consume either resource before it was available.

Durative actions can have conditional effects. The antecedents and consequents of a conditional effect are temporally annotated so that it is possible to specify that the condition be checked at start or at end, and that the effect be asserted at either of these points. The semantics makes clear that a well-formed durative action with conditional effects cannot require the condition to be checked after the effect has been asserted. Conditional effects arise in all PDDL2.1 variants. We discuss how their occurrence in discretized durative actions is interpreted in Section 8.1.

Figure 10: An example of a problem with a durative action useful for its start effects. The burning match produces the light necessary to pick up the coin.

PDDL2.1 allows the specification of duration inequalities enabling actions to be described in which external factors can be involved in determining their temporal extent. In the match-burning example shown in Figure 10 it can be seen that the effect at the start point is the only one of interest, so a planner would exploit this action for its start rather than its end effect. The duration inequality specifies that the match will burn for no longer than a specified upper bound. The model shows that the match can be put out early if the planner considers it appropriate. We discuss the use of duration inequalities further in Section 5.3.