Semantics of a Simple Plan

A simple plan, in PDDL2.1, is a sequence of timed actions, where a timed action has the following syntactic form:

$$t:(action \, p_{1} \ldots p_{n})$$

In this notation $t$ is a positive rational number in floating point syntax and the expression $($action  $p_{1} \ldots p_{n})$ is the name and actual parameters of the action to be executed at that point in time. In more complex plans simple and durative actions, with or without numeric-valued effects or preconditions, can co-occur -- the semantics of such plans is discussed in Section 8. No special separators are required to separate timed actions in the sequence and the actions are not required to be presented in time-sorted order. It is possible for multiple actions to be given the same time stamp, indicating that they should be executed concurrently. It should be emphasised that the earliest point at which activity occurs within a plan must be strictly after time 0. This constraint follows from the decision to make the initial state be the state existing at time 0, together with the decision, in the semantics, that actions have their effects in the interval that is closed on the left, starting at the time when the action is applied, while preconditions are tested in the interval that is open on the right that precedes the action.

In order to retain compatibility with the output of current planners the following concession is made: if the plan is presented as a sequence of actions with no time points, then it is inferred that the first action is applied at time 1 and the succeeding actions apply in sequence at integral time points one unit apart.

A simple plan is a slight generalisation of the more familiar STRIPS-style classical plan, since actions are labelled with the time at which they are to be executed.

Definition 11   Simple Plan A simple plan, $SP$, for a planning instance, $I$, consists of a finite collection of timed simple actions which are pairs $(t,a)$, where $t$ is a rational-valued time and $a$ is an action name.

The happening sequence, $\{t_{i}\}_{i=0\ldots k}$ for $SP$ is the ordered sequence of times in the set of times appearing in the timed simple actions in $SP$. All $t_{i}$ must be greater than $0$. It is possible for the sequence to be empty (an empty plan).

The happening at time $t$, $E_{t}$, where $t$ is in the happening sequence of $SP$, is the set of (simple) action names that appear in timed simple actions associated with the time $t$ in $SP$.

A plan thus consists of a sequence of happenings, each being a set of action names applied concurrently at a specific time, the sequence being ordered in time. The times at which these happenings occur forms the happening sequence. It should be noted that action names are ambiguous when action schemas contain conditional effects -- the consequence of flattening is to have split these actions into multiple actions with identical names, differentiated by their preconditions. However, at most one of each set of actions with identical names can be applicable in a given logical state, since the precondition of each action in such a set will necessarily be inconsistent with the precondition of any other action in the set, due to the way in which the conditional effects are distributed between the pairs of action schemas they induce.

In order to handle concurrent actions we need to define the situations in which the effects of those actions are consistent with one another. This issue was first discussed in Section 5.1. The mutual exclusion rule for PDDL2.1 is an extension of the idea of action mutex conditions for GraphPlan [Blum FurstBlum Furst1995]. The extension handles two extra features: the extended expressive power of the language (to include arbitrary propositional connectives) and the introduction of numeric expressions. We make a very conservative condition for actions to be executed concurrently, which ensures that there is no possibility of interaction. This rules out cases where intuition might suppose that concurrency is possible. For example, the actions:

  (:action a
    :precondition (or p q)
    :effect (r))
  
  (:action b
    :precondition (p)
    :effect (and (not p) (s)))

could, one might suppose, be executed simultaneously in a state in which both $p$ and $q$ hold. The following definition asserts, however, that the two actions are mutex. The reason we have chosen such a constrained definition is because checking for mutex actions must be tractable and handling the case implied by this example would appear to require checking the consequence of interleaving preconditions and effects in all possible orderings. The condition on primitive numeric expressions has already been discussed -- it determines that the update effects can be executed concurrently and that they do not affect values which are then tested by preconditions (regardless of whether the results of those tests matter to the satisfaction of their enclosing proposition). This is the rule of no moving targets: no concurrent actions can affect the parts of the state relevant to the precondition tests of other actions in the set, regardless of whether those effects might be harmful or not. It might be considered odd that the preconditions of one action cannot refer to literals in the add effects of a concurrent action. We require this because preconditions can be negative, in which case their interaction with add effects is analogous to the interaction between positive preconditions and delete effects. The no moving targets rule makes the cost of determining whether a set of actions can be applied concurrently polynomial in the size of the set of actions and their pre- and post-conditions.

Definition 12   Mutex Actions Two grounded actions, $a$ and $b$ are non-interfering if

$$\begin{array}{c} GPre_{a} \cap (Add_{b} \cup Del_{b}) = GPre_... ...L_{a} \cap L_{b} \subseteq L^{*}_{a} \cup L^{*}_{b} \end{array}$$

If two actions are not non-interfering they are mutex.

The last clause of this definition asserts that concurrent actions can only update the same values if they both do so by additive assignment effects.

We are now ready to define the conditions under which a simple plan is valid. We can separate the executability of a plan from whether it actually achieves the intended goal. We will say that a plan is valid if it is executable and achieves the final goal. Executability is defined in terms of the sequence of states that the plan induces by sequentially executing the happenings that it defines.

Definition 13   Happening Execution Given a state, $(t,s,{\bf x})$ and a happening, $H$, the activity for $H$ is the set of grounded actions

$$A_{H} = \{a \vert \mbox{the name for $a$\ is in $H$, $a$\ is ... ...d} \,\, Pre_{a} \,\, \mbox{is satisfied in}\,\, (t,s,{\bf x})\}$$

The result of executing a happening, $H$, associated with time $t_{H}$, in a state $(t,s,{\bf x})$ is undefined if $\vert A_{H}\vert \not= \vert H\vert$ or if any pair of actions in $A_{H}$ is mutex. Otherwise, it is the state $(t_{H},s',{\bf x'})$ where

$$s' = (s \setminus \bigcup_{a \in A_{H}} Del_{a}) \cup \bigcup_{a \in A_{H}} Add_{a}$$

and ${\bf x'}$ is the result of applying the composition of the functions $\{$NPF $_{a} \, \vert \, a \in A_{H}\}$ to x.

Since the functions $\{$NPF $_{a} \, \vert \, a \in A_{H}\}$ must affect different primitive numeric expressions, except where they represent additive assignment effects, these functions will commute and therefore the order in which the functions are applied is irrelevant. Therefore, the value of ${\bf x'}$ is well-defined in this last definition. The requirement that the activity for a happening must have the same number of elements as the happening itself is simply a constraint that ensures that each action name in the happening leads to a valid action that is applicable in the appropriate state. We have already seen that conditional effects induce the construction of families of grounded actions, but that at most one of each family can be applicable in a state. If none of them is applicable for a given name, then this must mean that the precondition is unsatisfied, regardless of the conditional effects. In this case, we are asserting that the attempt to apply the action has undefined interpretation.

Definition 14   Executability A simple plan, $SP$, for a planning instance, $I$, is executable if it defines a happening sequence, $\{t_{i}\}_{i=0\ldots k}$, and there is a sequence of states, $\{S_{i}\}_{i=0\ldots k+1}$ such that $S_{0}$ is the initial state for the planning instance and for each $i = 0\ldots k$, $S_{i+1}$ is the result of executing the happening at time $t_{i}$ in $SP$.

The state $S_{k+1}$ is called the final state produced by $SP$ and the state sequence $\{S_{i}\}_{i=0\ldots k+1}$ is called the trace of $SP$. Note that an executable plan produces a unique trace.

Definition 15   Validity of a Simple Plan A simple plan (for a planning instance, $I$) is valid if it is executable and produces a final state $S$, such that the goal specification for $I$ is satisfied in $S$.