

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

are very accurate in many domains, but suffer in Ring and Cube Center because they can be costly to compute.

## 6.6 Inter-Heuristic Conclusions

Our findings fall into two main categories: one, what are effective estimates for belief state distances in terms of state to state distances, and two, how we can exploit planning graphs to support the computation of these distance measures.

In comparing ways to aggregate state distance measures to compute belief state distances, we found that measuring no interaction as in single graph heuristics tends to poorly guide planners, measuring independence and positive interaction of worlds works well in specific domains, and measuring overlap (i.e. a combination of positive interaction and independence) tends to work well in a large variety of instances. By studying the accuracy of our heuristics we found that in some cases the most accurate were not the most effective. We did however find that the most accurate did best over the most cases.

Comparing graph structures that provide the basis for belief state distance measures, we found that the heuristics extracted from the single graph fail to systematically account for the independence or positive interaction among different possible worlds. Despite this lack in the distance measure, single graphs can still identify some structure in domains like Rovers and Logistics. To more accurately reflect belief state distances, multiple graphs reason about reachability for each world independently. This accuracy comes at the cost of computing a lot of redundant MG structure and is limiting in instances with large belief states. We can reduce the cost of the MG structure