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 structure and is limiting in instances with large belief states. We can reduce the cost of the structure by sampling worlds used in its construction. However planners are able to exhibit better scalability by considering more worlds through optimizing the representation of the redundant structure as in the . The improvement in scalability is attributed to lowering the cost of heuristic computation, but retaining measures of multiple state distances. The makes a trade-off of using an exponential time algorithm for evaluation of labels instead of building an exponential number of planning graphs. This trade-off is justified by our experiments.