The Semantics of Simple Plans

The semantics we define in this section extends the essential core of Lifschitz' STRIPS semantics lif to handle temporally situated actions, possibly occurring simultaneously, with numeric and conditional effects.

where is a 4-tuple consisting of (finite sets of)

The *primitive numeric expressions* of a planning instance, , are the terms constructed from the function symbols of the domain applied to (an appropriate number of) objects drawn from . The *dimension* of the planning instance, , is the number of distinct primitive numeric expressions that can be constructed in the instance.

The *atoms* of the planning instance, , are the (finitely many) expressions formed by applying the relation symbols in to the objects in (respecting arities).

consists of two parts: is a set of literals formed from the atoms in . is a set of propositions asserting the initial values of a subset of the primitive numeric expressions of the domain. These assertions each assign to a single primitive numeric expression a constant real value. The goal condition is a proposition that can include both atoms formed from the relation symbols and objects of the planning instance and numeric propositions between primitive numeric expressions and numbers.

is a collection of action schemas (non-durative actions) each expressed in the syntax of PDDL. The primitive numeric expression schemas and atom schemas used in these action schemas are formed from the function symbols and relation symbols (used with appropriate arities) defined in the domain applied to objects in and the schema variables.

The semantics shows how instantiated action schemas can be interpreted as state transitions, in a similar way to the familiar state transition semantics defined by Lifschitz. An important difference is that states can no longer be seen as simply sets of propositions, but must also account for the numeric expressions appearing in the planning instance and the time at which the state holds. This is achieved by extending the notion of state.

The initial state for a planning instance is
where **x** is the vector of values in
corresponding to the initial assignments given by
(treating unspecified values as ).

Undefined values are included in the numeric ranges because there are domains in which some terms start undefined but can nevertheless be initialised and exploited by actions.

To interpret actions as state transition functions it is necessary to achieve two steps. Firstly, since (in PDDL2.1) plans are only ever constructed from fully instantiated action schemas, the process by which instantiation affects the constructs of an action schema must be defined and, secondly, the machinery that links primitive numeric expressions to elements of the vector of real values in a state and that allows interpretation of the numeric updating behaviours in action effects must be defined. Since the mechanisms that support the second of these steps also affect the process in the first, the treatment of numeric effects is described first.

The *assignment proposition* corresponding to a numeric effect is formed by replacing the assignment operator with its equivalent arithmetic operation (that is `(increase p q)` becomes `(= p (+ p q))` and so on) and then annotating the lvalue with a ``prime''.

A numeric effect in which the assignment operator is either `increase` or `decrease` is called an *additive assignment effect*, one in which the operator is either `scale-up` or `scale-down` is called a *scaling assignment effect* and all others are called *simple assignment effects*.

A numeric effect defines a function of the numeric values in the state to which an action is applied determining the value of a primitive numeric expression in the resulting state. For the convenience of a uniform treatment of numeric expressions appearing in pre- and post-conditions, we transform the functions into propositions that assert the equality of the post-condition value and the expression that is intended to define it. That is, rather than writing an effect `(increase p q)` as a function , we write it as the proposition
. The ``priming'' distinguishes the postcondition value of a primitive numeric expression from its precondition value (a convention commonly adopted in describing state transition effects on numeric values). The binding of the primitive numeric expressions to their values in states is defined in the following definition.

be an (instance-dependent) correspondence between the primitive numeric expressions and integer indices into the elements of a vector of real values, .

The normalised form of a ground proposition, , in is defined to be the result of substituting for each primitive numeric expression in , the literal
. The normalised form of will be referred to as . Numeric effects are normalised by first converting them into assignment propositions. Primed primitive numeric expressions are replaced with their corresponding primed literals. **X** is used to represent the vector
.

In Definition 4, the replacement of primitive numeric expressions with indexed literals allows convenient and consistent substitution of the vector of actual parameters for the vector of literals **X** appearing in a state.

With the machinery supporting treatment of numeric expressions complete, it is now possible to consider the process of instantiating action schemas. This process is managed in two steps. The first step is to remove constructs that we treat as syntactic sugar in the definition of a domain. These are conditional effects and quantified formulae. We handle both of these by direct syntactic transformations of each action schema into a set of action schemas considered to be equivalent. The transformation is similar to that described by Gazen and Knoblock gazen. Although it would be possible to give a semantic interpretation of the application of conditional effects directly, the transformation allows us to significantly simplify the question of what actions can be performed concurrently.

- While contains an action schema, , with a conditional effect,
`(when P Q)`, create two new schemas which are copies of , but without this conditional effect, and conjoin the condition`P`to the precondition of one copy and`Q`to the effects of that copy, and conjoin`(not P)`to the precondition of the other copy. Add the modified copies to . - While contains an action schema, , with a formula containing a quantifier, replace with a version in which the quantified formula
`(``(``) P)`in is replaced with the conjunction (if the quantifier, , is`forall`) or disjunction (if is`exists`) of the propositions formed by substituting objects in for each variable in in`P`in all possible ways.

These steps are repeated until neither step is applicable.

Once flattened, actions can be grounded by the usual substitution of objects for parameters:

*Name*is the name from the action schema, , together with the values substituted for the parameters of in forming .*Pre*, the*precondition*of , is the propositional precondition of . The set of ground atoms that appear in*Pre*is referred to as*GPre*.*Add*, the*positive postcondition*of , is the set of ground atoms that are asserted as positive literals in the effect of .*Del*, the*negative postcondition*of ,is the set of ground atoms that are asserted as negative literals in the effect of .*NP*, the*numeric postcondition*of , is the set of all assignment propositions corresponding to the numeric effects of .

The following sets of primitive numeric expressions are defined for each ground action, :

Some comment is appropriate on the last definition: an action precondition might be considered to have two parts -- its logical part and its numeric expression-dependent part. Unfortunately, these can be interdependent. For example:

Definition 7 ensures that an action does not attempt inconsistent updates on a numeric value. Unlike logical effects of an action which cannot conflict, it is possible to write a syntactic definition of an action in which the effects are inconsistent, for example by assigning two different values to the same primitive numeric expression.

such that

The notation should be read as the result of normalising and then substituting the vector of actual values for the parameters and actual values for formal parameters .

Definition 8 defines the function describing the update effects of an action. The function ensures that all of the reals in the vector describing the numeric state remain unchanged if they are not affected by the action (this is the numeric-state equivalent of the persistence achieved for propositions by the STRIPS assumption). For other values in the vector, the normalisation process is used to substitute the correctly indexed vector elements for the primitive numeric expressions appearing as lvalues (which are the primed vector elements corresponding to values in the post-action state) and rvalues (the unprimed values appearing in the pre-action state). The tests that must be satisfied in order to ensure correct behaviour of the functions in the composition simply confirm that the arithmetic on the rvalues is correctly applied to arrive at the lvalues. The requirement that the action be valid ensures that the composition of the functions in Definition 8 is well-defined, since all of the functions in the set commute, so the composition can be carried out in any order.

The various sets of primitive numeric expressions defined in the Definition 6 allow us to conveniently express the conditions under which two concurrent actions might interfere with one another. In particular, we are concerned not to allow concurrent assignment to the same primitive numeric expression, or concurrent assignment and inspection. We *do* allow concurrent increase or decrease of a primitive numeric expression. To allow this we will have to apply collections of concurrent updating functions to the primitive numeric expressions. This can be allowed provided that the functions commute. Additive assignments do commute, but other updating operations cannot be guaranteed to do so, except if they do not affect the same primitive numeric expressions or rely on primitive numeric expressions that are affected by other concurrent assignment propositions. It would be possible to make a similar exception for scaling effects, but additive assignment effects have a particularly important role in durative actions that is not shared by scaling effects, so for simplicity we allow concurrent updates only with these effects. We use the three sets of primitive numeric expressions to determine whether we are in a safe situation or not. Within a single action it is possible for the rvalues and lvalues to intersect. That is, an action can update primitive numeric expressions using current values of primitive numeric expressions that are also updated by the same action. All rvalues will have the values they take in the state prior to execution and all lvalues will supply the new values for the state that follows.

where means that is true under the interpretation in which each atom, , that is not a numeric comparison, is assigned true iff , each numeric comparison is interpreted using standard equality and ordering for reals and logical connectives are given their usual interpretations. is

Comparisons involving , including direct equality between two values are all undefined, so that enclosing propositions are also undefined and not satisfied in any state.