- showing some independence. If we take the layer-wise union of the two relaxed plans, we would get a unioned relaxed plan:
RPU =
A
RPU
0 = {inP1p, Flush},

$\mathcal{E}_{0}^{RP_{U}}=\{\varphi^{0}(\text{inP1}_{p}),\,\varphi^{0}(\text{inP2}_{p}),\,\varphi^{0}(\text{Flush})\},$  $\mathcal{L}_{1}^{RP_{U}}=\{\text{inP1},\,\text{inP2},\,\neg\text{clog}\},$  $\mathcal{A}_{1}^{RP_{U}}=\{\neg\text{clog}_{p},\,\text{DunkP1},\,\text{DunkP2}\},$  $\mathcal{E}_{1}^{RP_{U}}=\{\varphi^{0}(\neg\text{clog}_{p}),\,\varphi^{1}(\text{DunkP1}),\,\varphi^{1}(\text{DunkP2})\},$  $\mathcal{L}_{2}^{RP_{U}}=\{\neg\text{arm},\,\neg\text{clog}\}.$
$$\mathbf{a}\int\mathbf{\Phi},$$
This relaxed plans accounts for the actions that are the same between possible worlds and the actions that differ. Notice that Flush appears only once in layer zero and the Dunk actions both appear in layer one.

In order to get the union of relaxed plans, we extract relaxed plans from each γ ∈ Γ, as in the two previous heuristics. Then if we are computing heuristics for regression search, we start at the last level (and repeat for each level) by taking the union of the sets of actions for each relaxed plan at each level into another relaxed plan. The relaxed plans are *end-aligned*, hence the unioning of levels proceeds from the last layer of each relaxed plan to create the last layer of the RPU relaxed plan, then the second to last layer for each relaxed plan is unioned and so on. In progression search, the relaxed plans are *start-aligned* to reflect that they all start at the same time, whereas in regression we assume they all end at the same time. The summation of the number of actions of each action level in the unioned relaxed plan is used as the heuristic value. Formally:

$$h_{R P U}^{M G}(B S_{i})=\sum_{j=0}^{b-1}\mid{\mathcal A}_{j}^{R P_{U}}\mid$$

where b is the greatest level bγ where a constituent of BSG was first reachable.

For CBTC, we just found RPU , so counting the number of actions gives us a heuristic value of hMG
RP U (BSG**) = 3**.

## 4.4 Labelled Uncertainty Graph Heuristics (Lug)

The multiple graph technique has the advantage of heuristics that can aggregate the costs of multiple worlds, but the disadvantage of computing some redundant information in different graphs (c.f.

Figure 6) and using every graph to compute heuristics (c.f hMG
RP U ). Our next approach addresses these limitations by condensing the multiple planning graphs to a single planning graph, called a labelled uncertainty graph (LUG). The idea is to implicitly represent multiple planning graphs by collapsing the graph connectivity into one planning graph, but use annotations, called labels (ℓ), to retain information about multiple worlds. While we could construct the LUG by generating each of the multiple graphs and taking their union, instead we define a direct construction procedure.

We start in a manner similar to the unioned single planning graph (SGU ) by constructing an initial layer of all literals in our source belief state. The difference with the LUG is that we can prevent loss of information about multiple worlds by keeping a label for each literal the records which of the worlds is relevant. As we will discuss, we use a few simple techniques to propagate the