
## A.2 Multiple Planning Graph Heuristics (Mg)

Similar to the various relaxed plan heuristics for the multiple graphs, we can compute a max, sum, or level heuristic on each of the multiple planning graphs and aggregate them with a maximum or summation to respectively measure positive interaction or independence. The reason we cannot aggregate the individual graph heuristics to measure overlap is that they are numbers, not sets of actions. Measuring overlap involves taking the union of heuristics from each graph and the union of numbers is not meaningful like the union of action sets from relaxed plans. Like before, there is no reason to use multiple graphs if there is no state distance aggregation.

## Positive Interaction Aggregation:

- Max The max heuristic hMG
m−max is computed with multiple planning graphs to measure positive interaction in the hMG
m−max heuristic. This heuristic computes the maximum cost clause in κ(BSi) for each graph γ ∈ Γ, similar to how h SG
m−max(BSi) is computed, and takes the maximum. Formally:
h MG
m−max(BSi**) = max**
γ∈Γ
(h γ max(BSi))
The hMG
m−max heuristic considers the minimum cost, relevant literals of a belief state (those that are reachable given a possible world for each graph γ) to get state measures. The maximum is taken because the estimate accounts for the worst (i.e., the plan needed in the most difficult world to achieve the subgoals).

- Sum The sum heuristic that measures positive interaction for multiple planning graphs is hMG
m−sum. It computes the summation of the cost of the clauses in κ(BSi) for each graph γ ∈ Γ and takes the maximum. Formally:
$\square$
$$h_{m-s u m}^{M G}(B S_{i})=\operatorname*{max}_{\gamma\in\Gamma}\left(h_{s u m}^{\gamma}(B S_{i})\right)$$
The heuristic considers the minimum cost, relevant literals of a belief state (those that are reachable given the possible worlds represented for each graph γ) to get state measures. As with hMG
m−max, the maximum is taken to estimate for the most costly world.

- **Level** Similar to hMG
m−max and hMG
m−sum, the hMG
m−**level** heuristic is found by first finding h γ level for each graph γ ∈ Γ to get a state distance measure, and then taking the maximum across the graphs. h γ level(BSi) is computed by taking the minimum among the Sˆ ∈ ˆξ(BSi), of the first level levγ(Sˆ) in the planning graph γ where literals of Sˆ are present with none of them marked mutex. Formally:

$$h_{l e v e l}^{\gamma}(B S_{i})=\operatorname*{min}_{\hat{S}\in\hat{\xi}(B S_{i})}l e v^{\gamma}(\hat{S})$$
and
$$h_{m-l e v e l}^{M G}(B S_{i})=\operatorname*{max}_{\gamma\in\Gamma}(h_{l e v e l}^{\gamma}(B S_{i}))$$

Note that this heuristic is admissible. By the same reasoning as in classical planning, the first level where all the subgoals are present and non-mutex is an underestimate of the true cost of a state. This holds for each of the graphs. Taking the maximum accounts for the most difficult