Next: Same-World Labelled Mutexes Up: Labelled Uncertainty Graph Heuristics Previous: Labelled Uncertainty Graph Heuristics

### Label Propagation

Like the single graph and multiple graphs, the is based on the [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 , effect , and literal layers. We denote the label of a literal in level as . We can build the for any belief state , and illustrate for the CBTC example. A label is a formula describing a set of states (in ) from which a graph element is (optimistically) reachable. We say a literal is reachable from a set of states, described by , after levels, if . For instance, we can say that arm is reachable after two levels if contains arm and arm), meaning that the models of worlds where arm holds after two levels are a superset of the worlds in our current belief state.

The intuitive definition of the 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 in which it holds, as the conjunction of the literal with . 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.

Initial Literal Layer: The has an initial layer consisting of every literal with a non false ( ) label. In the initial layer the label of each literal is identical to , representing the states of in which 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 for CBTC, shown in Figure 7 (without labels), using = has the initial literal layer:

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

Action Layer: Once the previous literal layer is computed, we construct and label the action layer . contains causative actions from the action set , plus literal persistence. An action is included in if its label is not false (i.e. ). The label of an action at level , is equivalent to the extended label of its execution precondition:

Above, we introduce the notation for extended labels of a formula to denote the worlds of that can reach at level . We say that any propositional formula is reachable from after levels if . 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 at level , is defined:

The zeroth action layer for CBTC is:

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

Effect Layer: The effect layer depends both on the literal layer and action layer . contains an effect if the effect has a non false label (i.e. ). Because both the action and an effect must be applicable in the same world, the label of the effect at level is the conjunction of the label of the associated action with the extended label of the antecedent

The zeroth effect layer for CBTC is:

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 depends on the previous effect layer , and contains only literals with non false labels (i.e. ). An effect contributes to the label of a literal when the effect consequent contains the literal . The label of a literal is the disjunction of the labels of each effect from the previous effect layer that gives the literal:

The first literal layer for CBTC is:

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

We continue to the level one action layer because does not indicate that is reachable from ( arm ). Action layer one is defined:

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 clog. Each Dunk action gets a label identical to its execution precondition label.

The level one effect layer is:

The conditional effects of the Dunk actions in CBTC (Figure 7) have labels that indicate the possible worlds in which they will give arm because their antecedents do not hold in all possible worlds. For example, the conditional effect DunkP1 has the label found by taking the conjunction of the action's label with the antecedent label (inP1) to obtain .

Finally, the level two literal layer:

The labels of the literals for level 2 of CBTC indicate that arm is reachable from because its label is entailed by . The label of arm is found by taking the disjunction of the labels of effects that give it, namely, from the conditional effect of DunkP1 and from the conditional effect of DunkP2, which reduces to . Construction could stop here because entails the label of the goal arm clog) arm clog . 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 , where , that a formula is reachable in steps if . If no such level exists, then is not reachable from . If there is some level , where is reachable from , then the first such is a lower bound on the number of parallel plan steps needed to reach from . 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 with respect to , described shortly.

Next: Same-World Labelled Mutexes Up: Labelled Uncertainty Graph Heuristics Previous: Labelled Uncertainty Graph Heuristics
2006-05-26