When we choose to compute multiple state distances between two belief states and , whether by considering all states or sampling subsets, not all of the state distances are important. For a given state in we do not need to know the distance to every state in because each state in need only transition to one state in . There are two assumptions that we can make about the states reached in which help us define two different belief state distance measures in terms of aggregate state distances:

- We can optimistically assume that each of the
earlier states
can reach the closest of the
later states
. With this assumption we compute
distance as:
.

- We can assume that all of the earlier states
reach the
same later state
, where the aggregate distance is
minimum. With this assumption we compute distance as:
,

where represents an aggregation technique (several of which we will discuss shortly).

Throughout the rest of the paper we use the first definition for belief state distance because it is relatively robust and easy to compute. Its only drawback is that it treats the earlier states in a more independent fashion, but is flexible in allowing earlier states to transition to different later states. The second definition measures more dependencies of the earlier states, but restricts them to reach the same later state. While the second may sometimes be more accurate, it is misinformed in cases where all earlier states cannot reach the same later state (i.e., the measure would be infinite). We do not pursue the second method because it may return distance measures that are infinite when they are in fact finite.

As we will see in Section 4, when we discuss computing these measures with planning graphs, we can implicitly find for each state in the closest state in , so that we do not enumerate the states in the minimization term of the first belief state distance (above). Part of the reason we can do this is that we compute distance in terms of constituents rather than actual states. Also, because we only consider constituents of , when we discuss sampling belief states to include in distance computation we only sample from . We can also avoid the explicit aggregation by using the , but describe several choices for to understand implicit assumptions made by the heuristics computed on the .