Notice that we are not computing all state distances between states in BSP and BSi. Each planning graph γ corresponds to a state in BSP , and from each γ we extract a single relaxed plan.

We do not need to enumerate all states in BSi and find a relaxed plan for each. We instead support a set of literals from one constituent of BSi. This constituent is estimated to be the minimum distance state in BSi because it is the first constituent reached in γ.

For CBTC, computing hMG
m−RP (BSG) (Figure 6) finds:
RP1 =
A
RP1 0 = {inP1p, Flush},
E
RP1 0 = {ϕ 0(inP1p), ϕ 0(Flush)},
L
RP1 1 = {inP1,¬clog},
A
RP1 1 = {¬clogp, DunkP1},
E
RP1 1 = {ϕ 0(¬clogp), ϕ 1(DunkP1)},
L
RP1 2 = {¬arm,¬clog}
and RP2 =
A
RP2 0 = {inP2p, Flush},
E
RP2 0 = {ϕ 0(inP2p), ϕ 0(Flush)},
L
RP2 1 = {inP2,¬clog},
A
RP2 1 = {¬clogp, DunkP2},
E
RP2 1 = {ϕ 0(¬clogp), ϕ 1(DunkP2)},
L
RP2 2 = {¬arm,¬clog}.

Each relaxed plan contains two actions and taking the maximum of the two relaxed plan values gives hMG
m−RP (BSG**) = 2**. This aggregation ignores the fact that we must use different Dunk actions each possible world.

Independence Aggregation: We can use the hMG
s−RP heuristic to assume independence among the worlds in our belief state. We extract relaxed plans exactly as described in the previous heuristic and simply use a summation rather than maximization of the relaxed plan costs. Formally:

$$h_{s-R P}^{M G}(B S_{i})=\sum_{\gamma\in\Gamma}\left(\sum_{j=0}^{b_{\gamma}-1}\mid{\mathcal A}_{j}^{R P_{\gamma}}\mid\right)$$

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

For CBTC, if computing hMG
s−RP (BSG), we find the same relaxed plans as in the hMG
m−RP (BSG)
heuristic, but sum their values to get 2 + 2 = 4 as our heuristic. This aggregation ignores the fact that we can use the same Flush action for both possible worlds.

State Overlap Aggregation: We notice that in the two previous heuristics we are either taking a maximization and not accounting for some actions, or taking a summation and possibly accounting for extra actions. We present the hMG
RP U heuristic to balance the measure between positive interaction and independence of worlds. Examining the relaxed plans computed by the two previous heuristics for the CBTC example, we see that the relaxed plans extracted from each graph have some overlap.

Notice, that both A
RP1 0and A
RP2 0contain a Flush action irrespective of which package the bomb is in - showing some positive interaction. Also, A
RP1 1contains DunkP1, and A
RP2 1contains DunkP2