labels through actions and effects and label subsequent literal layers. Label propagation relies on expressing labels as propositional formulas and using standard propositional logic operations. The end product is a single planning graph with labels on all graph elements; labels indicate which of the explicit multiple graphs (if we were to build them) contain each graph element.

We are trading planning graph structure space for label storage space. Our choice of BDDs to represent labels helps lower the storage requirements on labels. The worst-case complexity of the LUG is equivalent to the MG representation. The LUG's complexity savings is not realized when the projected possible worlds and the relevant actions for each are completely disjoint; however, this does not often appear in practice. The space savings comes in two ways: (1) redundant representation of actions and literals is avoided, and (2) labels that facilitate non-redundant representation are stored as BDDs. A nice feature of the BDD package (Brace, Rudell, & Bryant, 1990) we use is that it efficiently represents many individual BDDs in a shared BDD that leverages common substructure. Hence, in practice the LUG contains the same information as MG with much lower construction and usage costs.

In this section we present construction of the LUG without mutexes, then describe how to introduce mutexes, and finally discuss how to extract relaxed plans.

## 4.4.1 Label Propagation

Like the single graph and multiple graphs, the LUG is based on the **IP P** (Koehler et al., 1997) 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 A, effect E, and literal L layers. We denote the label of a literal l in level k as ℓk(l). We can build the LUG for any belief state BSP , and illustrate BSP = BSI for the CBTC example. A label is a formula describing a set of states (in BSP ) 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 |= ℓk(l). For instance, we can say that ¬arm is reachable after two levels if L2 contains ¬arm and BSI |= ℓ2(¬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 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 BSP in which it holds, as the conjunction of the literal with BSP . 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 LUG has an initial layer consisting of every literal with a non false (⊥)
label. In the initial layer the label ℓ0(l) of each literal l is identical to l∧BSP , representing the states of BSP 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".