Next: Temporal extent Up: Related Work: Representing and Previous: Continuous change

## Concurrency

The opportunity for concurrent activities complicates several aspects of temporal reasoning. Firstly, it is necessary to account for which actions can be concurrent and secondly it is necessary to describe how concurrent activities interact in their effects on the world.

In most formalisms the first of these points is achieved by relying on the underlying logic to deliver an inconsistency when an attempt is made to apply two incompatible actions simultaneously. For example, the axioms of the event calculus will yield the simultaneous truth and falsity of a fluent if incompatible actions are applied simultaneously and consequently yield an inconsistency. Unfortunately, recognising inconsistency is, in general, undecidable, for a sufficiently expressive language. In PDDL2.1 we adopt a solution that exploits the restricted form of the action-centred formalism, defining the circumstances in which two actions could lead to inconsistency and rejecting the simultaneous application of such actions. We favour a conservative restriction on compatibility of actions (the no moving targets rule), in order to support efficient determination of incompatibility, rather than a more permissive but elusive ruling. An alternative approach, adopted by Bacchus in TLplan bacchusconcurrency, for example, is to allow multiple actions to occur at the same instant, but nevertheless to be executed in sequence. We find this solution counter-intuitive and, more importantly, consider that it would be impossible to use a plan of this sort as an instruction to an executive -- no executive could be equipped to execute actions simultaneously and yet in a specified order. Our view is that if the order of execution matters then the executive must ensure that the actions are sequenced and can only do so within the limitations of its capability to measure time and react to its passing.

Shanahan shanahantutorial discusses Gelfond's gelfond example of the soup bowl in which the problem concerns raising a soup bowl without spilling the soup. Two actions, lift left and lift right, can be applied to the bowl. If either is applied on its own the soup will spill, but, it is argued, if they are applied simultaneously then the bowl is raised from the table and no soup spills. Shanahan considers this example within the event calculus, where he uses an explicit assertion of the interaction between the lift left and lift right actions to ensure that the spillage effect is cancelled when the pair is executed together. The assumption is that the two actions can be executed at precisely the same moment and that the reasoner can rely on the successful simultaneity in order to exploit the effect.

In PDDL2.1 we take the view that precise simultaneity is outside the control of any physical executive. A plan is interpreted as an instruction to some executive system and we hold that no executive system is capable of measuring time and controlling its activity at arbitrarily fine degrees of accuracy. In particular, it is not possible for an executive to ensure that two actions that must be independently initiated are executed simultaneously. If a plan were to rely on such precision in measurement then, we claim, it could not be executed with any reliable expectation of success and should not, therefore, be considered a valid plan.

PDDL2.1 supports the modelling of the soup bowl situation in the following way. Two durative actions, lift left and lift right, both independently initiate tilting intervals which, when complete, will result in spillage of the soup if their effects have not been counteracted. Provided that the two lift actions start within an appropriate tolerance of one another the tilting will be corrected and the spillage avoided without the need to model cancellation of effects. We argue that an executive can execute the two actions to within a fine but non-zero tolerance of one another, and can therefore successfully lift the bowl. The event calculus model presented by Shanahan insists on precise synchronization of the two actions, incorrectly allowing it to be inferred that the soup will be spilled even if the time that elapses between the two lifts is actually small enough to allow for correction of the tilting of the bowl. Worse, Shanahan's axioms would allow lack of precise synchronization to be exploited to achieve spillage, using an amount of time smaller than that correctly describing the physical situation being modelled.

If one considers it unnecessary to model the precise interaction between the two lifts, one has the alternative in PDDL2.1 to abstract out the interaction and see the soup-bowl lifting action as a single discretized action that achieves the successful raising of the bowl.

Next: Temporal extent Up: Related Work: Representing and Previous: Continuous change
Derek Long 2003-11-06