PDDL2.1 Core Definitions

In this appendix we present the definitions from [Fox LongFox Long2003] that are most relevant to this paper, for ease of reference. For detailed discussions of these definitions and their relationships see the original source.

Core 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.

Core 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},{\vec{x}})$ where ${\vec{x}}$ is the vector of values in ${\mathbb{R}}_{\perp}$ corresponding to the initial assignments given by $Init_{numeric}$ (treating unspecified values as $\perp$).

Core 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.

Core 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 $\mathcal{ N}(p)$. Numeric effects are normalised by first converting them into assignment propositions. Primed primitive numeric expressions are replaced with their corresponding primed literals. ${\vec{X}}$ is used to represent the vector $\langle X_{1} \ldots X_{n} \rangle$.

Core 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.

Core 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 PNE 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$}$$\}$

Core 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.

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

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

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

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

Core 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}$, Num$(s,p)$, as follows:

Num$$(s,p)({\vec{x}})$$   iff$$\quad s \models \mathcal{ N}(p)[{\vec{X}} := {\vec{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,{\vec{x}})$ if Num $(s,p)(\vec{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.

Core 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$.