The Semantics of a Planning Instance

In the following we present the semantics of a planning instance in stages in order to facilitate understanding. We begin with the definition of a uniprocess planning instance and an event-free uniprocess planning instance. We then introduce the general concept of a planning instance. These definitions rely on the concept of relevance of actions, events and processes, which we now present.

The following definition uses the interpretation of preconditions defined in Core Definition 9. This core definition explains how, given a proposition $P$ and a logical state $s$, the truth of the proposition is determined. $Num(s,P)$ is a predicate over the PNEs in the domain. As explained in Core Definition 9, to determine the truth of a proposition in a state, with respect to a vector of numeric values $\vec{x}$, the formal numeric parameters of the proposition are substituted with the values in $\vec{x}$ and the resulting proposition is evaluated in the logical state. The purpose of Definition 7 is to identify actions, events or processes that could be applicable in a given logical state, if the values of the metric fluents are appropriate to satisfy their preconditions.

Definition 7   Relevance of Actions, Events and Processes A ground action $a$ (event $e$, or process $p$) of a planning instance $I$ of dimension $n$, is relevant in the logical state $s$ if there is some value $\vec{x} \in \mathbb{R}^n$ such that $Num(s,Pre_a)(\vec{x})$ ( $Num(s,Pre_e)(\vec{x})$ or $Num(s,Pre_p)(\vec{x})$, respectively).

$\mathcal{P}_s$ ( $\mathcal{E}_s$) is the set of all ground processes (events) that are relevant in state $s$.

In general, an action, event or process that is relevant in a particular (logical) state might not actually become applicable, since the valuations of the numeric state that arise while the system is in the logical state might not include any of those that satisfy the preconditions of the corresponding transition.

In the construction of a HA, in the mappings described below, the vertices of its control graph are subsets of ground atoms and are therefore equivalent to logical states. We use the variable $v$ to denote a vertex and $\mathcal{P}_v$ ( $\mathcal{E}_v$) to denote the processes (events) relevant in the corresponding logical state.

In any given logical state a subset of the relevant processes will be active, according to the precise valuation of the metric fluents in the current state. We first consider the restricted case in which no more than one active process affects the value of each variable at any time, which we call a uniprocess planning instance. The proposition unary-context-flow($i$,$\pi$), defined below, is used to describe the effects on the $i$th variable of the process $\pi$, when it is active. We later extend this definition to the concurrent case in which multiple processes may contribute to the behaviour of a variable.

Definition 8   Uniprocess Planning Instance A planning instance is a uniprocess planning instance if, for each metric variable, $X_i$, the set of processes that can affect the value of $X_i$ relevant in state $v$, denoted $\mathcal{P}_v\vert _{X_i}$, contains processes whose preconditions are pairwise mutually exclusive. That is, for $\pi_1, \pi_2 \in \mathcal{P}_v\vert _{X_i}$ ( $\pi_1 \not= \pi_2$) there is no numeric state such that $\mathcal{ N}(Pre_{\pi_1}) \wedge \mathcal{N}(Pre_{\pi_2})$.

Definition 9   Unary-context-flow If $v$ is a logical state for a uniprocess planning instance $I$ of dimension $n$ and $\pi \in \mathcal{P}_v\vert _{X_i}$ then the unary-context-flow proposition is defined as follows. Let the effect of $\pi$ on $X_i$ take the form (increase $X_i$ (* #t $Q_i$)) for some expression $Q_i$.

$$\mbox{unary-context-flow$_{v}$}$$$$(i,\pi) = (\mathcal{ N}(Pre_{\pi}) \rightarrow \dot{X}_i = Q_i)$$

We begin by presenting the semantics of a event-free uniprocess planning instance -- that is, a uniprocess planning instance that contains no events. We then extend our definition to include events, and present the semantics of a uniprocess planning instance. Finally we introduce concurrent process effects and the definition of the semantics of a planning instance.

Definition 10   Semantics of an Event-free Uniprocess Planning Instance An event-free uniprocess planning instance, $I = (Dom,Prob)$, is interpreted as a Hybrid Automaton, $H_I$, as follows:

• Variables. The variables of $H_I$ are $X = \{X_{1}, \ldots , X_{n}\}$, where $n$ is the dimension of the planning problem.
• Control Graph. The set of vertices $V$ is formed from all subsets of the ground atoms of the planning instance. The set of edges in $E$ contains an edge $e$ between $v$ and $v'$ iff there is an action, $a$, relevant in $v$ and:
  $$v' = (v - Del_{a}) \cup Add_{a}$$
  The action $a$ is associated with the edge $e$.
• Initial, invariant and flow conditions. The vertex labelling function init is defined as:
  $$init(v) = \left\{ \begin{array}{ll} false & \mbox{if $v \neq... ...{ N}(Init_{numeric})\}} & \mbox{otherwise} \end{array} \right.$$
  The vertex labelling function inv is the proposition True.

  The vertex labelling function flow is defined:

  $$flow(v) = (\bigwedge_{i=1}^{n} \big\{ \bigwedge_{\pi \in \mathcal{ P}_{v}\vert _{X_i}}$$   $$\mbox{unary-context-flow$_{v}$}$$$$(i,\pi) \wedge (\bigwedge_{\pi \in \mathcal{P}_{v}\vert _{X_i}} \neg \mathcal{N}(Pre_{\pi}) \rightarrow \dot{X}_i = 0) \big\} )$$

• Jump conditions. The edge labelling function jump is defined as follows. Given an edge $e$ from vertex $v$, associated with an action $a$:
  $$jump(e) = \mathcal{ N}(Pre_{a}) \wedge UF_{a}(X) = X^\prime$$
  where $UF_a$ is the updating function for action $a$, as defined in Core Definition 8 which specifies the relationship that must hold between the valuations of the PNEs before and after the application of an action.
• H-events. $\Sigma$ is the set of all names of all ground actions. The edge labelling function $hevent : E \rightarrow \Sigma$ assigns to each edge the name of the action associated with the edge.

The flow condition states that, for each variable, if the precondition of one of the processes that could affect it is true then that process defines its rate of change (through the unary-context-flow proposition), or else, if none of the process preconditions is satisfied then the rate of change of that variable is zero.

To illustrate this construction we now present a simple example. The planetary lander domain requires events and so cannot be used as an example of the event-free model. Consider the PDDL+ domain containing just the following actions and process:

(:action startEngine
 :precondition (stopped)
 :effect (and (not (stopped))
              (running))
)

(:action accelerate
 :precondition (running)
 :effect (increase (a) 1)
)

(:action decelerate
 :precondition (running)
 :effect (decrease (a) 1)
)

(:action stop
 :precondition (and (= (v) 0) (running))
 :effect (and (not (running))
              (stopped)
              (assign (a) 0))
)

(:process moving
 :precondition (running)
 :effect (and (increase (d) (* #t (v)))
              (increase (v) (* #t (a))))
)

The translation process described in Definition 10 leads to the hybrid automaton shown in Figure 10. As can be seen, there are two vertices, corresponding to the logical states $\{$stopped$\}$ and $\{$running$\}$. The four actions translate into edges, each edge linking a vertex in which an action is relevant to one in which its logical effects have been enacted. The metric effects of actions are encoded in the jump conditions associated with an edge, using the convention that the primed versions of the variables refer to the state following the transition. Note that variables that are not explicitly affected by an action are constrained to take the same value after the transition as they did before the transition: this is the metric equivalent of the STRIPS assumption. The stop action has a metric precondition and this is expressed in the jump condition of the transition, requiring that the velocity variable, $v$, be zero for this transition.

Figure 10: A hybrid automaton constructed by the translation of an event-free uniprocess planning instance. We ignore the init function, which simply asserts the appropriate initial state for a particular problem instance.

In the stopped state no process can affect the variables, so the flow conditions simply assert that the variables have a zero rate of change. In the running state the moving process is relevant -- indeed, since it has no other preconditions, it is active whenever the system is in this state. The effect of this process is expressed in the flow conditions for that state which show that the distance variable, $d$, changes as the value of velocity, $v$, which changes in turn as the value of acceleration, $a$. These constraints create a system of differential equations describing the simultaneous effects of velocity and acceleration on the system.

We now consider the case in which events are included but there can only be one process active on any one fluent at any one time.

In planning domains it is important to distinguish between state changes that are deliberately planned, called actions, and those, called events, that are brought about spontaneously in the world. There is no such distinction in the HA, where all control switches are called events. This distinction complicates the relationship between plans and traces, because plans contain only the control switches that correspond to actions. Any events triggered by the evolution of the domain under the influence of planned actions must be inferred and added to the sequence of actions in order to arrive at the corresponding traces.

Henzinger et al. henzingerdecides discuss the use of $\epsilon$-moves, which are transitions that are not labelled with a corresponding control-switch, but with the special label $\epsilon$. The significance of these transitions is that they do not appear in traces. A trace that corresponds to an accepting run using $\epsilon$-moves will contain only those transitions that are labelled with elements from $\Sigma$. Where $\epsilon$-moves appear between time transitions, the lengths of these transitions can be accumulated into a single transition in the corresponding trace. The purpose of these silent transitions is that they allow special book-keeping transitions to be inserted into automata that can be used to simulate automata with syntactically richer constraints, allowing various reducibility results to be demonstrated. The convenient aspect of the $\epsilon$-moves is that they do not affect traces when they are transferred from the original automata to the simulations.

In PDDL+, events are similar to $\epsilon$-moves in that they do not appear explicitly in plans. However, in contrast to $\epsilon$-moves, applicable events are always forced to occur before any actions may be applied in a state.

When extending event-free planning instances to include events we require a mechanism for capturing the fact that events occur at the instant at which they are triggered by the world, and not at the convenience of the planner. No time must be allowed to pass between the satisfaction of event preconditions and the triggering of the event. In our semantic models we use a variable to measure the amount of time that elapses between the preconditions of an event becoming true and the event triggering. Obviously this quantity, which we call time-slip, must be 0 in any valid planning instance. In the HA that we construct we associate an invariant with each vertex in the control graph to enforce this requirement. It might appear that a simpler way to handle events would be to simply assert that an invariant condition for each state is that the preconditions of all events are false, while each event is represented by an outgoing transition with a jump condition specifying the precondition of the corresponding event. However, it is not possible for a jump condition on a transition to be inconsistent with the invariant of the state it leaves since both must hold simultaneously at the time at which the transition is made.

The variable used to monitor time-slip for a planning instance of dimension $n$ is the variable $X_{n+1}$. This variable operates as a clock tracking the passage of time once an event becomes applicable. We define the time-slippage proposition to switch the clock on whenever the preconditions of any event become true in any state. When no event is applicable the clock is switched off.

Definition 11   Time-slippage For a planning instance of dimension $n$ the variable $X_{n+1}$ is called the time-slip variable and time-slippage is defined as follows.

$$\mbox{time-slippage($\mathcal{ R}$)}$$$$= (\dot{X}_{n+1} = 0 \vee \dot{X}_{n+1} = 1) \wedge (\bigvee_{e \in \mathcal{ R}} \mathcal{ N}(Pre_{e}) \rightarrow \dot{X}_{n+1} = 1)$$

where $\mathcal{ R}$ is a set of ground events.

The use of time-slip allows us to model PDDL+ domains directly in Hybrid Automata in a standard form. An alternative would be to introduce a modified definition of Hybrid Automata that makes explicit distinction between controllable and uncontrollable transitions (actions and events respectively) and then require that uncontrollable transitions should always occur immediately when their jump conditions are satisfied. This approach would lead to an essentially equivalent formalism, but would complicate the opportunity to draw on the existing body of research into Hybrid Automata, which is why we have followed the time-slip approach.

The interpretation of a Uniprocess Planning Instance extends the interpretation of the Event-free Uniprocess Planning Instance. The added components are underlined for ease of comparison.

Definition 12   Semantics of a Uniprocess Planning Instance A unary process planning instance $I = (Dom,Prob)$ is interpreted as a Hybrid Automaton, $H_I$, as follows:

• Variables. The variables of $H_I$ are $X = \{X_{1}, \ldots , X_{n+1}\}$, where $n$ is the dimension of the planning problem. The $n+1th$ variable is a special control variable used to measure time-slip.
• Control Graph. The set of vertices $V$ is formed from all subsets of the ground atoms of the planning instance. The set of edges in $E$ contains an edge $e$ between $v$ and $v'$ iff there is an action or event, $a$, relevant in $v$ and:
  $$v' = (v - Del_{a}) \cup Add_{a}$$
  The action or event $a$ is associated with the edge $e$.
• Initial, invariant and flow conditions. The vertex labelling function init is defined as:
  $$init(v) = \left\{ \begin{array}{ll} false & \mbox{if $v \neq... ...{ N}(Init_{numeric})\}} & \mbox{otherwise} \end{array} \right.$$
  The vertex labelling function inv is the simple proposition that ensures time-slip is zero.
  $$\underline{inv(v) = (X_{n+1} = 0)}$$

  The vertex labelling function flow is defined:

  $$\begin{array}{ll} flow(v) = (\bigwedge_{i=1}^{n} & \big\{ \bi... ...line{\wedge \mbox{time-slippage($\mathcal{E}_v$)}}) \end{array}$$

• Jump conditions. The edge labelling function jump is defined as follows. Given an edge $e$ from vertex $v$, associated with an action $a$:
  $$jump(e) = \mathcal{ N}(Pre_{a}) \wedge UF_{a}(X) = X^\prime \wedge \underline{\bigwedge_{ev \in \mathcal{E}_v} \neg \mathcal{ N}(Pre_{ev})}$$

  Given an edge $e$ from vertex $v$, associated with an event $ev$:

  $$jump(e) = \mathcal{N}(Pre_{ev}) \wedge UF_{ev}(X) = X^\prime$$
  where $UF_{a}$ ($UF_{ev}$) is the updating function for action $a$ (event $ev$) respectively.

• H-events. $\Sigma$ is the set of all names of all ground actions and events. The edge labelling function $hevent : E \rightarrow \Sigma$ assigns to each edge the name of the action or event associated with the edge.

In this case, the flow condition says the same thing as for the event-free uniprocess planning instance, but with the additional constraint that whenever the precondition of an event is satisfied, the time-slip variable must increase at rate $1$ (and may increase at rate zero otherwise). Since the invariant condition for every state insists that the time-slip variable is never greater than 0, a valid trace for this machine cannot rest in a state for any period of time once the preconditions of an event become true. It can also be seen that the jump condition for action transitions asserts that all event preconditions must be false. This ensures that events are always applied before action transitions are permitted. We now extend the preceding simple example domain to include an event, to illustrate the construction described in Definition 12:

(:event engineExplode
 :parameters ()
 :precondition (and (running) (>= (a) 1) (>= (v) 100))
 :effect (and (not (running)) (assign (a) 0) (engineBlown))
)

The corresponding machine is shown in Figure 11. The structure of this machine is similar to the previous example, but includes an extra state, reachable by an event transition. The addition of an event also requires the addition of the time-slip variable, $T$. The behaviour of this variable is controlled, in particular, by a new flow constraint in the running state that ensures that if the event precondition becomes true then the time-slip starts to increase as soon as any time passes. The addition of this variable and its control also propagates into the jump and flow conditions of the other states.

Figure 11: A hybrid automaton constructed by the translation of a uniprocess planning instance.

Finally we consider the case in which concurrent process effects occur and must be combined. This is the general case to which we refer in the rest of this paper.

In any given logical state a subset of the relevant processes will be active, according to the precise valuation of the metric fluents in the current state. The proposition context-flow(i,$\Pi$) asserts that the rate of change of the $i$th variable is defined by precisely those processes in $\Pi$, provided that they (and only they) are all active, and is not affected by any other process. The following definition explains how the contributions to the rate of change of a variable by several different concurrent processes are combined (see also Section 4.2). This simply involves summing the contributions that are active at an instant. Here we assume without loss of generality that contributions are increasing effects. Decreasing effects are handled by simply negating the contributions made by these effects.

Definition 13   Combined Concurrent Effects Given a finite set of process effects, $E = e_1 \ldots e_k$, where $e_i$ is of the form (increase $P_i$ (* $\char93$t $Q_i$)), the combined concurrent effect of $E$ on the PNE $P$, called $C(P,E)$, is defined to be

$$\sum \{Q_i \vert i = 1,\ldots k, P = P_i\}$$

Given a set of processes, $\Pi$, the combined concurrent effect of $\Pi$ on the PNE $P$, denoted $C(P,\Pi)$, is $C(P,E)$, where $E$ is the set of all the effects of processes in $\Pi$.

It will be noted that if $E$ contains no processes that affect a specific variable, $P$, then $C(P,E) = 0$.

Definition 14   Context-flow If $v$ is a logical state for a planning instance $I$ of dimension $n$ and $\Pi$ is a subset of $\mathcal{P}_v$, then the context-flow proposition is defined as follows.

$$\mbox{context-flow$_{v}$}$$$$(i,\Pi) = (\bigwedge_{p \in \Pi} \mathcal{ N}(Pre_{p}) \wedge \bi... ...\setminus \Pi} \neg \mathcal{ N}(Pre_{p})) \rightarrow \dot{X}_{i} = C(X_i,\Pi)$$

where $1 \leq i \leq n$.

If $\Pi$ is empty then the context flow proposition asserts that $\dot{X}_i = 0$ for each $i$.

The interpretation of a Planning Instance extends the interpretation of a Uniprocess Planning Instance. Again, the added components are underlined for convenience.

Definition 15   Semantics of a Planning Instance A planning instance $I = (Dom,Prob)$ is interpreted as a Hybrid Automaton, $H_I$, as follows:

• Variables. The variables of $H_I$ are $X = \{X_{1}, \ldots , X_{n+1}\}$, where $n$ is the dimension of the planning problem. The $n+1th$ variable is a special control variable used to measure time-slip .
• Control Graph. The set of vertices $V$ is formed from all subsets of the ground atoms of the planning instance. The set of edges in $E$ contains an edge $e$ between $v$ and $v'$ iff there is an action or event, $a$, relevant in $v$ and:
  $$v' = (v - Del_{a}) \cup Add_{a}$$
  The action or event $a$ is associated with the edge $e$.
• Initial, invariant and flow conditions. The vertex labelling function init is defined as:
  $$init(v) = \left\{ \begin{array}{ll} false & \mbox{if $v \neq... ...{ N}(Init_{numeric})\}} & \mbox{otherwise} \end{array} \right.$$
  The vertex labelling function inv is the simple proposition that ensures time-slip is zero.
  $$inv(v) = (X_{n+1} = 0)$$

  The vertex labelling function flow is defined:

  $$flow(v) = (\bigwedge_{i=1}^{n} \bigwedge_{\Pi \in \mathbb{P}(\mathcal{ P}_{v})}$$   $$\mbox{\underline{context-flow$_{v}$}}$$$$(i,\Pi)) \wedge$$   $$\mbox{time-slippage($\mathcal{E}_v$)}$$

• Jump conditions. The edge labelling function jump is defined as follows. Given an edge $e$ from vertex $v$, associated with an action $a$:
  $$jump(e) = \mathcal{ N}(Pre_{a}) \wedge UF_{a}(X) = X^\prime \wedge \bigwedge_{ev \in \mathcal{E}_v} \neg \mathcal{ N}(Pre_{ev})$$

  Given an edge $e$ from vertex $v$, associated with an event $ev$:

  $$jump(e) = \mathcal{N}(Pre_{ev}) \wedge UF_{ev}(X) = X^\prime$$

• H-events. $\Sigma$ is the set of all names of all ground actions and events. The edge labelling function $hevent : E \rightarrow \Sigma$ assigns to each edge the name of the action or event associated with the edge.

The final conjunct in the jump definition for actions ensures that the state cannot be left by an action if there is an event the preconditions of which are satisfied. It is possible for more than one event to be simultaneously applicable in the same state. This is discussed further in Section 6.4.

As an illustration of this final extension in the sequence of definitions, we now add one further process to the preceding example:

(:process windResistance
 :parameters ()
 :precondition (and (running) (>= (v) 50))
 :effect (decrease (v) (* #t (* 0.1 (* (- (v) 50) (- (v) 50)))))
)

This process causes the vehicle to be slowed by a wind resistance that becomes effective from 50mph, and is proportional to the square of the speed excess over 50mph. This leads to the flow constraint in the running state having two new clauses that replace the original constraint on the rate of change of velocity. These new clauses are shown in the second box out on the right of Figure 12. As can be observed, the velocity of the vehicle is now governed by two different differential equations, according to whether $v < 50$ or $v \geq 50$. These equations are:

$$\begin{array}{ll} \frac{dv}{dt} = a, & \mbox{if $v < 50$}\\ ... ...dv}{dt} = a - 0.1 (v-50)^2, & \mbox{if $v \geq 50$} \end{array}$$

The solution to the first is: $v = at + v_0$ where $v_0$ is the velocity at the point when the equation first applies (and $t$ is measured from this point). The solution to the second is:

$$v = \frac{c_0 (\sqrt{10a} - 50) e^{- c_1 t} + 50 + \sqrt{10a}}{1 - c_0 e^{- c_1 t}}$$

where $c_1 = \frac{\sqrt{10a}}{5}$ and $c_0$ is a constant determined by the initial value of the velocity when the process first applies (and, again, $t$ is then measured from that point). As is shown by the this example, the simple differential equations that can be expressed in PDDL+ can lead to complex expressions. Of course, there is a significant difference between the provision of a semantics for this expressiveness and finding a planning algorithm that can manage it -- in this paper we are concerned only with the former. We anticipate that planning will require sensible constraints on the extent to which the expressive power of PDDL+ is exploited.

Figure 12: A hybrid automaton constructed by the translation of a planning instance.

The definition of the semantics of a planning instance is constructed around a basic framework of the discrete state space model of the domain. This follows a familiar discrete planning model semantics. The continuous dimensions of the model are constructed to ensure that the Hybrid Automaton will always start in an initial state consistent with the planning instance (modelled by the init labelling function). The state invariants ensure that no time-slip occurs in the model and that, therefore, events always occur once their preconditions are satisfied. It will be noted that since the negation of the event preconditions is added to all jump conditions for other exiting transitions, it will be impossible for a state to be exited in any other way than by the triggered event. Finally, flow models the effect on the real values of all of the active processes in a state. The flow function assigns a proposition to each state that determines a piece-wise continuous behaviour for each of the real values in the planning domain. The function is piece-wise differentiable, with only a finite number of segments within any finite interval. The reason for this is that it is possible for the behaviour of a metric fluent undergoing continuous change to affect the precondition of a process and cause the continuous change in itself or of other metric fluents to change. Such a change cannot cause discontinuity in the value of the metric fluents themselves, but it can cause discontinuity in the derivatives. The consequence of this is that the time interval between two successive actions or events might include a finite sequence of distinct periods of continuous change. As will be seen in the following section, this requires that an acceptable trace describing such behaviour will explicitly subdivide the interval into a sequence of subintervals in each of which the continuous change is governed by a stable set of differential equations.