The Interpretation of Concurrent plans

When time is introduced into the modelling of a domain it is possible for concurrent activity to occur in a plan. Prior to the introduction of time into PDDL all plans were interpreted as sequential -- even Graphplan-concurrent plans were sequenced before being validated -- so concurrency was never an issue. In PDDL2.1 plan validity can depend on exploiting concurrency correctly. Actions can overlap and co-occur, giving rise to questions over the interpretation of synchronous behaviour. We discuss the problems arising in precise synchronization in Section 10. We now explain under what constraints actions can occur concurrently within a plan involving durative actions and numeric conditions and effects.

The key difference, between durative actions in PDDL2.1 and those used by planners prior to the competition, is that we distinguish between the conditions and effects at the start and end points of the durative interval and the invariant conditions that might be specified to hold over the interval. That is, actions can have pre- and postconditions that are local to the two end-points of the action, and a planner can choose to exploit a durative action for effects it has at its start or at its end. Conditions that are invariant are distinguished from pre-conditions, enabling the exploitation of a higher degree of concurrency than is possible if preconditions are not distinguished from invariants, as in TGP [Smith WeldSmith Weld1999], TPSys [Garrido, Onaindía, BarberGarrido et al.2001] and TP4 [Haslum GeffnerHaslum Geffner2001]. We discuss the consequences of these design decisions, together with several examples of durative actions, in the following sections.

It is important to observe that our view of time is point-based rather than interval-based. That is, we see a period of activity in terms of intervals of state separated by time points at which state-changing activities occur. All logical state change occurs instantaneously, at the start or end point of a durative action. Propositions are true over half-open intervals that are closed on the left and open on the right. Activities might change logical state or they might update the values of numeric variables. In the discretised view of time we allow for only a finite number of activities (which we call happenings) between any two time points, although time itself is considered continuous and actions can be scheduled to begin at any time point.

For a plan to be considered valid, no logical condition can be both asserted and negated at the same instant. We impose the further constraint that no logical condition can both be required to hold and be asserted at the same instant. Although this might seem overly strong we claim that a plan cannot be guaranteed to be valid if the instant at which a proposition is required is exactly the instant at which it is asserted. We require that, for an action with precondition $P$ to start at time $t$, there must be a half open interval immediately preceding $t$ in which $P$ holds. This is mathematically inconsistent with $P$ being asserted at the instant at which it is required. We are conservative in our view of the validity of simultaneous update of and access to a state proposition. For example, if we have two instantaneous actions, $A$ and $B$, where $A$ has precondition $P$ and effects (not $P$) and $Q$, while $B$ has precondition $P \vee Q$ and effect $R$, we consider that an attempt to apply $A$ and $B$ simultaneously in a state in which $P$ holds is ill-defined. The reason is that, although $A$ switches the state from one in which $P$ holds into one in which $Q$ holds so one might suppose the precondition of $B$ to be secure, $A$ is an abstraction of a model in which the values of $P$ and $Q$ are changing and, we argue, any reliance on their values at this point of change is unstable. We adopt a rule we call no moving targets, by which we mean that no two actions can simultaneously make use of a value if one of the two is accessing the value to update it -- the value is a moving target for the other action to access. This rule creates a behaviour for propositions in a planning state that is very much like the behaviour of variables in shared memory protected by a mutex lock (such as those in POSIX threads), with a difference between read and write access to the variable.

Validity also requires that no numeric value be accessed and updated simultaneously at the start or end point of a durative action. In the case of discretised durative actions, all numeric change is modelled in terms of step functions so numeric values can be accessed, or updated, during the interval of another durative action acting on that value (we provide examples in the following section) provided that any updates are consistent with all invariant properties dependent on the value. In the case of continuous durative actions, values can be simultaneously accessed and updated during the continuous process of change occurring in the interval of an action. In both the discretised and continuous cases we allow multiple simultaneous updates provided the update operations are commutative.

In order to implement the mutual exclusion relation we require non-zero-separation between mutually exclusive action end points. In our view, when end points are non-conflicting they can be treated as though it is possible to execute them simultaneously even though precise synchronicity cannot be achieved in the world. However, when end points are mutually exclusive the planner should buffer the co-occurrence of these points by explicitly separating them. In this way we ensure that the concurrency in the plan is at least plausible in the world.

Planners can exploit considerable concurrency in a domain by ensuring only that conflicting start and end points of actions are separated by a non-zero amount. A detailed specification of the mutual exclusion relation of PDDL2.1 is given in Section 8. We further discuss the implications of non-zero separation in Section 10.