
## Appendix A. Additional Heuristics

For completeness, we present some additional heuristics adapted from classical planning to reason about belief state distances in each type of planning graph. Many of these heuristics appeared in our previous work (Bryce & Kambhampati, 2004). We show how to compute the max, sum, and level heuristics on the single graph SG, multiple graphs MG, and the labelled uncertainty graph LUG.

While these heuristics tend to be less effective than the relaxed plan heuristics, we provide them as reference. As with Section 4, we describe the heuristics in terms of regression search.

## A.1 Single Planning Graph Heuristics (Sg)

Like, the relaxed plan for the single unmodified planning graph, we cannot aggregate state distances because all notion of separate states is lost in forming the initial literal layer, thus we only compute heuristics that do not aggregate state distances.

## No State Aggregation:

- Max In classical planning, the maximum cost literal is used to get a max heuristic, but we use formulas to describe our belief states, so we take the maximum cost clause as the cost of the belief state to find the max heuristic h SG
max. The maximum cost clause of the belief state, with respect to a single planning graph, is:

$$h_{m a x}^{S G}(B S_{i})=\operatorname*{max}_{C\in\kappa(B S_{i})}c o s t(C)$$

$$\mathbf{\Sigma}_{\star}^{\star}$$
where the cost of a clause is:
$$c o s t(C)=\operatorname*{min}_{l\in C}\operatorname*{min}_{k:l\in{\mathcal{L}}_{k}}k$$

Here we find the cheapest literal as the cost of each clause to find the maximum cost clause.

This is an underestimate of the closest state to our current belief state.

- Sum Like the classical planning sum heuristic, we can take the sum h SG
sum of the costs of the clauses in our belief state to estimate our belief state distance

$$h_{s u m}^{S G}(B S_{i})=\sum_{C\in\kappa(B S_{i})}c o s t(C)$$

This heuristic takes the summation of costs of literals in the closest estimated state in the belief state, and is inadmissible because there may be a single action that will support every clause, and we could count it once for each clause.

- **Level** When we have mutexes on the planning graph, we can compute a level heuristic h SG level
(without mutexes the level heuristic is equivalent to the max heuristic). The level heuristic maintains the admissibility of the max heuristic but improves the lower bound by considering what level of the planning graph all literals in a constituent are non-pairwise mutex. The level heuristic 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 pairwise mutex. Formally:

$$h_{l e v e l}^{S G}(B S_{i})=\operatorname*{min}_{\hat{S}\in\hat{\xi}(B S_{i})}\;l e v(\hat{S})$$
