

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

dist(S11, S32) : ({a1, a2}, {a5}, {a6, a7}),

$$\pm241$$

dist(S12, S31) : ({a1, a7}, {a3}),

$$S_{31}\,$$

dist(S21, S31) : ({a3, a6}, {a9, a2, a1}, {a0, a8}, {a5}).

In each sequence there may be several actions in each step. For instance, dist(S21, S31) has a3 and a6 in its first step, and there are a total of eight actions in the sequence - meaning the distance is eight. Notice that our example includes several state distance estimates, which can be found with classical planning techniques. There are many ways that we can use similar ideas to estimate belief state distance once we have addressed the issue of belief states containing several states.

Selecting States for Distance Estimation: There exists a considerable body of literature on estimating the plan distance between states in classical planning (Bonet & Geffner, 1999; Nguyen, Kambhampati, & Nigenda, 2002; Hoffmann & Nebel, 2001), and we would like to apply it to estimate the plan distance between two belief states, say BS1 and BS3. We identify four possible options for using state distance estimates to compute the distance between belief states BS1 and BS3:

- Sample a State Pair: We can sample a single state from BS1 and a single state from BS3, whose plan distance is used for the belief state distance. For example, we might sample S12 from BS1 and S31 from BS3, then define dist(BS1, BS3) = dist(S12, S31).

- Aggregate States: We can form aggregate states for BS1 and BS3 and measure their plan distance. An aggregate state is the union of the literals needed to express a belief state formula,