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.

Definition 1   Simple Planning Instance A simple planning instance is defined to be a pair

$$I = (Dom,Prob)$$

where $Dom = (Fs,Rs,As,arity)$ is a 4-tuple consisting of (finite sets of) function symbols, relation symbols, actions (non-durative), and a function $arity$ mapping all of these symbols to their respective arities. $Prob = (Os,Init,G)$ is a triple consisting of the objects in the domain, the initial state specification and the goal state specification.

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

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

$Init$ consists of two parts: $Init_{logical}$ is a set of literals formed from the atoms in $Atms$. $Init_{numeric}$ 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.

$As$ 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 $Os$ 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.

Definition 2   Logical States and States Given the finite collection of atoms for a planning instance $I$, $Atms_{I}$, a logical state is a subset of $Atms_{I}$. For a planning instance with dimension $dim$, a state is a tuple in $({\mathbb{R}},{\mathbb{P}}(Atms_{I}),{\mathbb{R}}_{\perp}^{dim})$ where ${\mathbb{R}}_{\perp} = {\mathbb{R}} \cup \{\perp\}$ and $\perp$ denotes the undefined value. The first value is the time of the state, the second is the logical state and the third value is the vector of the $dim$ values of the $dim$ primitive numeric expressions in the planning instance.

The initial state for a planning instance is $(0,Init_{logical},{\bf x})$ where x is the vector of values in ${\mathbb{R}}_{\perp}$ corresponding to the initial assignments given by $Init_{numeric}$ (treating unspecified values as $\perp$).

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.

Definition 3   Assignment Proposition The syntactic form of a numeric effect consists of an assignment operator (assign, increase, decrease, scale-up or scale-down), one primitive numeric expression, referred to as the lvalue, and a numeric expression (which is an arithmetic expression whose terms are numbers and primitive numeric expressions), referred to as the rvalue.

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 $f(p) = p+q$, we write it as the proposition $(= \, p' \, (+ \, p \, \, q))$. 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.

Definition 4   Normalisation Let $I$ be a planning instance of dimension $dim_{I}$ and let

$$index_{I}~:~PNEs_{I}~\rightarrow~\{1,\ldots~,dim\}$$

be an (instance-dependent) correspondence between the primitive numeric expressions and integer indices into the elements of a vector of $dim_{I}$ real values, $\mathbb{R}_{\perp}^{dim_{I}}$.

The normalised form of a ground proposition, $p$, in $I$ is defined to be the result of substituting for each primitive numeric expression $f$ in $p$, the literal $X_{index_{I}(f)}$. The normalised form of $p$ will be referred to as ${\cal N}(p)$. 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 $\langle X_{1} \ldots X_{n} \rangle$.

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.

Definition 5   Flattening Actions Given a planning instance, $I$, containing an action schema $A \in As_{I}$, the set of action schemas $flatten(A)$, is defined to be the set $S$, initially containing $A$ and constructed as follows:

• While $S$ contains an action schema, $X$, with a conditional effect, (when P Q), create two new schemas which are copies of $X$, 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 $S$.
• While $S$ contains an action schema, $X$, with a formula containing a quantifier, replace $X$ with a version in which the quantified formula ( $Q$ ( $var_{1} \ldots var_{k}$ ) P) in $X$ is replaced with the conjunction (if the quantifier, $Q$, is forall) or disjunction (if $Q$ is exists) of the propositions formed by substituting objects in $I$ for each variable in $var_{1} \ldots var_{k}$ 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:

Definition 6   Ground Action Given a planning instance, $I$, containing an action schema $A \in As_{I}$, the set of ground actions for $A$, $GA_{A}$, is defined to be the set of all the structures, $a$, formed by substituting objects for each of the schema variables in each schema, $X$, in $flatten(A)$ where the components of $a$ are:

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

The following sets of primitive numeric expressions are defined for each ground action, $a~\in~GA_{A}$:

• $L_{a} = \{ f \vert \mbox{$f$\ appears as an lvalue in $a$}\}$
• $R_{a} = \{ f \vert \mbox{$f$\ is a primitive numeric expression in an rvalue in $a$\ or appears in $Pre_{a}$}\}$
• $L^{*}_{a} = \{ f \vert \mbox{$f$\ appears as an lvalue in an additive assignment effect in $a$}\}$

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:

(or (clear ?x) (>= (room-in ?y) (space-for ?z)))

might be a precondition of an action. In order to handle such conditions, we need to check whether they are satisfied given not only the current logical state, but also the current values of the domain numeric expressions. The inclusion of a numeric component in the state makes it necessary to ensure the correct substitution of the numeric values for the expressions used in the action precondition. This is achieved using the normalisation process from Definition 4 in Definition 9. In contrast, the postcondition of an action cannot contain interlocked numeric and logical effects, so it is possible to separate the effects into the distinct numeric and logical components.

Definition 7   Valid Ground Action Let $a$ be a ground action. $a$ is valid if no primitive numeric expression appears as an lvalue in more than one simple assignment effect, or in more than one different type of assignment effect.

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.

Definition 8   Updating Function Let $a$ be a valid ground action. The updating function for $a$ is the composition of the set of functions:

$$\{\mbox{\em NPF}_{p}~:~{\mathbb{R}}_{\perp}^{dim} \rightarrow~{\mathbb{R}}_{\perp}^{dim} \, \vert \, p \in NP_{a} \}$$

such that NPF $_{p}({\bf x}) = {\bf x'}$ where for each primitive numeric expression $x'_{i}$ that does not appear as an lvalue in ${\cal N}(p)$, $x'_{i} = x_{i}$ and ${\cal N}(p)[{\bf X'} := {\bf x'}, {\bf X} := {\bf x}]$ is satisfied.

The notation ${\cal N}(p)[{\bf X'} := {\bf x'}, {\bf X} := {\bf x}]$ should be read as the result of normalising $p$ and then substituting the vector of actual values ${\bf x'}$ for the parameters ${\bf X'}$ and actual values ${\bf x}$ for formal parameters ${\bf X}$.

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.

Definition 9   Satisfaction of Propositions Given a logical state, $s$, a ground propositional formula of PDDL2.1, $p$, defines a predicate on ${\mathbb{R}}_{\perp}^{dim}$, $\mbox{Num}(s,p)$, as follows:

$$\mbox{Num}(s,p)({\bf x}) \quad \mbox{iff} \quad s \models {\cal N}(p)[{\bf X} := {\bf x}]$$

where $s \models q$ means that $q$ is true under the interpretation in which each atom, $a$, that is not a numeric comparison, is assigned true iff $a \in s$, each numeric comparison is interpreted using standard equality and ordering for reals and logical connectives are given their usual interpretations. $p$ is satisfied in a state $(t,s,{\bf X})$ if Num$(s,p)(\bf X)$.

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

Definition 10   Applicability of an Action Let $a$ be a ground action. $a$ is applicable in a state $s$ if the $Pre_{a}$ is satisfied in $s$.