Label Propagation

Like the single graph and multiple graphs, the $LUG$ is based on the $IPP$ [20] planning graph. We extend the single graph to capture multiple world causal support, as present in multiple graphs, by adding labels to the elements of the action ${\cal A}$ , effect ${\cal E}$ , and literal ${\cal L}$ layers. We denote the label of a literal $l$ in level $k$ as $\ell_k(l)$ . We can build the $LUG$ for any belief state $BS_P$ , and illustrate $BS_P = BS_I$ for the CBTC example. A label is a formula describing a set of states (in $BS_P$ ) from which a graph element is (optimistically) reachable. We say a literal $l$ is reachable from a set of states, described by $BS$ , after $k$ levels, if $BS \models \ell_k(l)$ . For instance, we can say that $\neg$ arm is reachable after two levels if ${\cal L}_2$ contains $\neg$ arm and $BS_I \models \ell_2(\neg$ arm), meaning that the models of worlds where $\neg$ arm holds after two levels are a superset of the worlds in our current belief state.

The intuitive definition of the $LUG$ is a planning graph skeleton, that represents causal relations, over which we propagate labels to indicate specific possible world support. We show the skeleton for CBTC in Figure 7. Constructing the graph skeleton largely follows traditional planning graph semantics, and label propagation relies on a few simple rules. Each initial layer literal is labelled, to indicate the worlds of $BS_P$ in which it holds, as the conjunction of the literal with $BS_P$ . An action is labelled, to indicate all worlds where its execution preconditions can be co-achieved, as the conjunction of the labels of its execution preconditions. An effect is labelled, to indicate all worlds where its antecedent literals and its action's execution preconditions can be co-achieved, as the conjunction of the labels of its antecedent literals and the label of its associated action. Finally, literals are labelled, to indicate all worlds where they are given as an effect, as the disjunction over all labels of effects in the previous level that affect the literal. In the following we describe label propagation in more detail and work through the CBTC example.

Figure 7: The $LUG$ skeleton for CBTC, with no mutexes. The relaxed plan for $h^{LUG}_{RP}$ is shown in bold.

Initial Literal Layer: The $LUG$ has an initial layer consisting of every literal with a non false ($\perp$ ) label. In the initial layer the label $\ell_0(l)$ of each literal $l$ is identical to $l \wedge BS_P$ , representing the states of $BS_P$ in which $l$ holds. The labels for the initial layer literals are propagated through actions and effects to label the next literal layer, as we will describe shortly. We continue propagation until no label of any literal changes between layers, a condition referred to as ``level off''.

The $LUG$ for CBTC, shown in Figure 7 (without labels), using $BS_P$ =$BS_I$ has the initial literal layer:

$$\begin{array}{l} {\cal L}_0 = \{{\tt inP1}, \neg {\tt inP2},... ...\ \ell_0({\tt clog}) = \ell_0({\tt arm}) = BS_P \end{array}$$

Notice that inP1 and inP2 have labels indicating the respective initial states in which they hold, and clog and arm have $BS_P$ as their label because they hold in all states in $BS_P$ .

Action Layer: Once the previous literal layer ${\cal L}_k$ is computed, we construct and label the action layer ${\cal A}_k$ . ${{\cal A}}_k$ contains causative actions from the action set $A$ , plus literal persistence. An action is included in ${{\cal A}}_k$ if its label is not false (i.e. $\ell_k(a) \not= \perp$ ). The label of an action at level $k$ , is equivalent to the extended label of its execution precondition:

$$\ell_k(a) = \ell^*_k(\rho^e(a))$$

Above, we introduce the notation for extended labels $\ell_k^*(f)$ of a formula $f$ to denote the worlds of $BS_P$ that can reach $f$ at level $k$ . We say that any propositional formula $f$ is reachable from $BS$ after $k$ levels if $BS_i \models \ell^*_k(f)$ . Since we only have labels for literals, we substitute the labels of literals for the literals in a formula to get the extended label of the formula. The extended label of a propositional formula $f$ at level $k$ , is defined:

$$\begin{array}{c} \ell^*_k(f \wedge f') = \ell^*_k(f) \wedge ... ...*_k(\perp) = \perp,\ \ell^*_k(l) = \ell_k(l)\ \end{array}$$

The zeroth action layer for CBTC is:

$$\begin{array}{l} {{\cal A}}_0 = \{{\tt Flush}, {\tt inP1}_p,... ... \ell_0({\tt clog}_p) = \ell_0({\tt arm}_p) = BS_P \end{array}$$

Each literal persistence has a label identical to the label of the corresponding literal from the previous literal layer. The Flush action has $BS_P$ as its label because it is always applicable.

Effect Layer: The effect layer ${{\cal E}}_k$ depends both on the literal layer ${\cal L}_k$ and action layer ${\cal A}_k$ . ${{\cal E}}_k$ contains an effect $\varphi^j(a)$ if the effect has a non false label (i.e. $\ell_k(\varphi^j(a)) \not= \perp$ ). Because both the action and an effect must be applicable in the same world, the label of the effect at level $k$ is the conjunction of the label of the associated action with the extended label of the antecedent

$$\ell_k(\varphi^j(a)) = \ell_k(a) \wedge \ell^*_k(\rho^j(a))$$

The zeroth effect layer for CBTC is:

$$\begin{array}{l} {{\cal E}}_0 = \{\varphi^0({\tt Flush}), \v... ...clog}_p)) = \ell_0(\varphi^0({\tt arm}_p)) = BS_P \end{array}$$

Again, like the action layer, the unconditional effect of each literal persistence has a label identical to the corresponding literal in the previous literal layer. The unconditional effect of Flush has a label identical to the label of Flush.

Literal Layer: The literal layer ${\cal L}_k$ depends on the previous effect layer ${\cal E}_{k-1}$ , and contains only literals with non false labels (i.e. $\ell_k(l) \not= \perp$ ). An effect $\varphi^j(a) \in {\cal E}_{k-1}$ contributes to the label of a literal $l$ when the effect consequent contains the literal $l$ . The label of a literal is the disjunction of the labels of each effect from the previous effect layer that gives the literal:

$$\ell_{k}(l) = \bigvee_{\substack{\varphi^j(a): l \in \varepsilon^{j}(a),\ \varphi^j(a) \in {\cal E}_{k-1}}} \ell_{k-1}(\varphi^j(a))$$

The first literal layer for CBTC is:

$$\begin{array}{l} {\cal L}_1 = \{ {\tt inP1}, \neg {\tt inP2}... ...) = \ell_1({\tt clog}) = \ell_1({\tt arm}) = BS_P \end{array}$$

This literal layer is identical to the initial literal layer, except that $\neg$ clog goes from having a false label (i.e. not existing in the layer) to having the label $BS_P$ .

We continue to the level one action layer because ${\cal L}_1$ does not indicate that $BS_G$ is reachable from $BS_P$ ($\neg$ arm $\not\in {\cal L}_1$ ). Action layer one is defined:

$$\begin{array}{l} {{\cal A}}_1 = \{ {\tt DunkP1}, {\tt DunkP2... ...({\tt arm}_p) = \ell_1(\neg {\tt clog}_p) = BS_P \end{array}$$

This action layer is similar to the level zero action layer. It adds both Dunk actions because they are now executable. We also add the persistence for $\neg$ clog. Each Dunk action gets a label identical to its execution precondition label.

The level one effect layer is:

$$\begin{array}{l} {{\cal E}}_1 = \{\varphi^0({\tt DunkP1}), \... ...p)) = \ell_1(\varphi^0(\neg {\tt clog}_p)) = BS_P \end{array}$$

The conditional effects of the Dunk actions in CBTC (Figure 7) have labels that indicate the possible worlds in which they will give $\neg$ arm because their antecedents do not hold in all possible worlds. For example, the conditional effect $\varphi^1($ DunkP1$)$ has the label found by taking the conjunction of the action's label $BS_P$ with the antecedent label $\ell^*_1$ (inP1) to obtain $({\tt arm} \wedge {\tt clog} \wedge {\tt inP1} \wedge \neg {\tt inP2})$ .

Finally, the level two literal layer:

$$\begin{array}{l} {\cal L}_2 = \{ {\tt inP1}, \neg {\tt inP2}... ...\ell_2({\tt arm}) = \ell_2(\neg {\tt arm}) = BS_P \end{array}$$

The labels of the literals for level 2 of CBTC indicate that $\neg$ arm is reachable from $BS_P$ because its label is entailed by $BS_P$ . The label of $\neg$ arm is found by taking the disjunction of the labels of effects that give it, namely, $({\tt arm} \wedge {\tt clog} \wedge {\tt inP1} \wedge \neg {\tt inP2})$ from the conditional effect of DunkP1 and $({\tt arm} \wedge {\tt clog} \wedge \neg {\tt inP1} \wedge {\tt inP2})$ from the conditional effect of DunkP2, which reduces to $BS_P$ . Construction could stop here because $BS_P$ entails the label of the goal $\ell^{*}_k(\neg$ arm $\wedge \neg$ clog) $= \ell_k(\neg$ arm $) \wedge \ell_k(\neg$ clog $) = BS_P \wedge BS_P = BS_P$ . However, level off occurs at the next level because there is no change in the labels of the literals.

When level off occurs at level three in our example, we can say that for any $BS$ , where $BS \models BS_P$ , that a formula $f$ is reachable in $k$ steps if $BS \models \ell^*_k(f)$ . If no such level $k$ exists, then $f$ is not reachable from $BS$ . If there is some level $k$ , where $f$ is reachable from $BS$ , then the first such $k$ is a lower bound on the number of parallel plan steps needed to reach $f$ from $BS$ . This lower bound is similar to the classical planning max heuristic [23]. We can provide a more informed heuristic by extracting a relaxed plan to support $f$ with respect to $BS$ , described shortly.