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.