next up previous
Next: Concurrency Up: Related Work: Representing and Previous: Related Work: Representing and

Continuous change

Several temporal reasoning frameworks began with consideration of discrete change and, later, were extended to handle continuous change. For example, Shanahan shanahan extended the event calculus of Kowalski and Sergot eventcalc to enable the modelling of continuous change. This process of extension mirrors the situation faced in extending PDDL, where a system modelling discrete change already existed. It is, therefore, interesting to compare the use of PDDL2.1 with the use of systems such as the extended event calculus.

In his sink-filling example Shanahan shanahan discusses the issues of termination of events (self-termination and termination by other events), identification of the level of water in the sink during the filling process and the effect on the rate of change in the level of water in a sink when it is being filled from two sources simultaneously. The behaviour of the filling process and its effects on the state of the sink over time are modelled as axioms which would allow an inference engine to predict the state of the sink at points during the execution of the process.

PDDL2.1 allows the representation of the complex interactions that arise when a sink is filled from multiple independently controlled water sources by means of concurrent durative actions with continuous effects that encapsulate the initiation of the filling process, from a single water source, the change in the level of water in the sink and the termination of the process when the water source is turned off. This model is robust, since it easily accommodates multiple water sources, simply modifying the rate of flow appropriately by commutative updates. Since the actions have additive effects and the model provides the rate at which water enters the tank from a source, it is possible to compute the level of water in the sink at any point in the filling interval at which a concurrent action might consult the level. In contrast to Shanahan's extension to the event calculus, this approach does not require that the filling process be (at least from the point of view of the logical axiomatisation) terminated and restarted at a new rate when a water source is opened or closed, since the process simply remains active throughout. The change in rate of filling is then reflected in a piecewise-linear profile for the depth of water in the sink, just as it is in Shanahan's model.

It is not possible to model the multiple water sources situation if the filling process is completely encapsulated within a discretized durative action. In the discretized action the true level of water is not accessible during the filling process but only at its end or its start. Step-function behaviour only coarsely approximates true behaviour, so the consequence is that complex interactions cannot be properly modelled.

One of the important consequences of continuous behaviour is the triggering of events. In Shanahan's extensions this is achieved through the axiomatisation of causal relationships -- events are not distinguished syntactically from actions, but only by the fact that their happening is axiomatically the consequence of certain conditions. In PDDL2.1 some events (such as the flooding of the sink if the filling continues after its capacity has been reached) can be modelled by using a combination of conditional effects and duration inequalities. However, not all events can be modelled in this way, since it is not always possible to predict when spontaneous events will occur. PDDL2.1 could be extended to allow the expression of causal axioms, but an alternative approach is to modify the language to enable the representation of events within the action-oriented tradition. This can be achieved by breaking up continuous durative actions into their instantaneous start and end points and the processes they encapsulate. This would enable the execution of a process to be initiated by a start action and ended by an instantaneous state transition that is either an action under the control of the planner or an event. A simple extension to the language is needed to distinguish actions from events and to prevent the planner from deliberately selecting an event. We refer to this approach as the start-process-stop model, and we have extended PDDL2.1 to support it [Fox LongFox Long2002]. The resulting language, PDDL+, is more difficult to plan with than PDDL2.1, and there are still open questions, concerning the complexity of the plan validation problem for this language, which remain topics for future work.


next up previous
Next: Concurrency Up: Related Work: Representing and Previous: Related Work: Representing and
Derek Long 2003-11-06