As in the conformant problem we expand BS10, giving its child a cost of zero and BS10 a cost of one. This changes our best solution at BSI to use DunkP2, and we expand BS20, giving its child a cost of zero and it a cost of one. Then we choose DetectMetal to start the best solution at BSI
because it gives BSI a cost of one, where using either Dunk action would give BSI a cost of two.

We expand the first child of DetectMetal, BS50, with DunkP1 to get:
{inP1 ∧¬inP2 ∧ clog ∧¬arm},
which is a goal state, and DunkP2 to get:
B6 = {BS60} = Progress(BS50,DunkP2) = {inP1 ∧¬inP2 ∧clog ∧ arm}. We then expand the second child, BS51, with DunkP2 to get:
{¬inP1 ∧ inP2 ∧ clog ∧¬arm},
which is also a goal state and DunkP1 to get:
B7 = {BS70} = Progress(BS51,DunkP1) = {¬inP1 ∧ inP2 ∧clog ∧ arm}.

While none of these new belief states are not equivalent to BSG, two of them entail BSG, so we can treat them as terminal by connecting the hyper-edges for these actions to BSG. We choose DunkP1 and DunkP2 as best actions for BS50 and BS51 respectively and set the cost of each node to one. This in turn sets the cost of using DetectMetal for BSI to (1+1)/2 + 1 = 2. We terminate here because this plan has cost equal to the other possible plans starting at BSI and all leaf nodes satisfy the goal. The plan is shown in bold with solid lines in Figure 2.

## 3. Belief State Distance

In both the CAltAlt and **P OND** planners we need to guide search node expansion with heuristics that estimate the plan distance dist(**BS, BS**′) between two belief states BS and BS′. By convention, we assume BS precedes BS′(i.e., in progression BS is a search node and BS′is the goal belief state, or in regression BS is the initial belief state and BS′is a search node). For simplicity, we limit our discussion to progression planning. Since a strong plan (executed in BS) ensures that every state S ∈ M(BS) will transition to some state S
′ ∈ M(BS′), we define the plan distance between BS and BS′as the number of actions needed to transition every state S ∈ M(BS) to a state S
′ ∈ M(BS′). Naturally, in a strong plan, the actions used to transition a state S1 ∈ M(BS)
may affect how we transition another state S2 ∈ M(BS). There is usually some degree of positive or negative interaction between S1 and S2 that can be ignored or captured in estimating plan distance.4In the following we explore how to perform such estimates by using several intuitions from classical planning state distance heuristics.

We start with an example search scenario in Figure 3. There are three belief states BS1 (containing states S11 and S12), BS2 (containing state S21), and BS3 (containing states S31 and S32).

The goal belief state is BS3, and the two progression search nodes are BS1 and BS2. We want to expand the search node with the smallest distance to BS3 by estimating dist(BS1**, BS**3) - denoted by the bold, dashed line - and dist(BS2**, BS**3) - denoted by the bold, solid line. We will assume for now that we have estimates of state distance measures dist(**S, S**′) - denoted by the light dashed and solid lines with numbers. The state distances can be represented as numbers or action sequences. In our example, we will use the following action sequences for illustration: