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 [9]. 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.