

![0_image_0.png](0_image_0.png)

In the graph for the first possible world, ¬arm comes in only through DunkP1 at level 2. In the graph for the second world, ¬arm comes in only through DunkP2 at level 2. Thus, the multiple graphs show which actions in the different worlds contribute to support the same literal.

A single planning graph is sufficient if we do not aggregate state measures, so in the following we consider how to compute the achievement cost of a belief state with multiple graphs by aggregating state distances.

Positive Interaction Aggregation: Similar to GPT (Bonet & Geffner, 2000), we can use the worstcase world to represent the cost of the belief state BSi by using the hMG
m−RP heuristic. The difference with GPT is that we compute a heuristic on planning graphs, where they compute plans in state space. With this heuristic we account for the number of actions used in a given world, but assume positive interaction across all possible worlds.

The hMG
m−RP heuristic is computed by finding a relaxed plan RPγ on each planning graph γ ∈ Γ,
exactly as done on the single graph with h SG
RP . The difference is that unlike the single graph relaxed plan SGU , but like SG1, the initial levels of the planning graphs are states, so each relaxed plan will reflect all the support needed in the world corresponding to γ. Formally:

$$h_{m-R P}^{M G}(B S_{i})=\operatorname*{max}_{\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.