A simple plan, in PDDL2.1, is a sequence of timed actions, where a timed action has the following syntactic form:
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.
The happening sequence, for is the ordered sequence of times in the set of times appearing in the timed simple actions in . All must be greater than . It is possible for the sequence to be empty (an empty plan).
The happening at time , , where is in the happening sequence of , is the set of (simple) action names that appear in timed simple actions associated with the time in .
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 and 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.
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.
The result of executing a happening, , associated with time , in a state is undefined if
or if any pair of actions in is mutex. Otherwise, it is the state
Since the functions NPF 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 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.
The state is called the final state produced by and the state sequence is called the trace of . Note that an executable plan produces a unique trace.