State Distance Assumptions

When we choose to compute multiple state distances between two belief states $BS$ and $BS'$ , whether by considering all states or sampling subsets, not all of the state distances are important. For a given state in $BS$ we do not need to know the distance to every state in $BS'$ because each state in $BS$ need only transition to one state in $BS'$ . There are two assumptions that we can make about the states reached in $BS'$ 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 $S \in {\cal M}(BS)$ can reach the closest of the later states $S' \in {\cal M}(BS')$ . With this assumption we compute distance as:

  $dist(BS, BS') = \bigtriangledown_{S\in {\cal M}(BS)} \min\limits_{S' \in {\cal M}(BS')} dist(S, S')$ .

• We can assume that all of the earlier states $S \in {\cal M}(BS)$ reach the same later state $S' \in {\cal M}(BS')$ , where the aggregate distance is minimum. With this assumption we compute distance as:

  $dist(BS, BS') = \min\limits_{S' \in {\cal M}(BS')} \bigtriangledown_{S\in {\cal M}(BS)} dist(S, S')$ ,

where $\bigtriangledown$ 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 $BS$ the closest state in $BS'$ , so that we do not enumerate the states $S'$ 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 $\hat{S}' \in \hat{\xi}(BS')$ rather than actual states. Also, because we only consider constituents of $BS'$ , when we discuss sampling belief states to include in distance computation we only sample from $BS$ . We can also avoid the explicit aggregation $\bigtriangledown$ by using the $LUG$ , but describe several choices for $\bigtriangledown$ to understand implicit assumptions made by the heuristics computed on the $LUG$ .