The belief state distances are dist(BS1, BS3) = max(min(14, 5), min(3, **7)) = 5** and dist(BS2, BS3) = max(min(8, **10)) = 8**. In this case we prefer BS1 to BS2. If each state distance is admissible and we do not sample from belief states, then assuming positive interaction is also admissible.

- Independence of States: Independence assumes that each state in BS requires actions that are different from all other states in BS in order to reach a state in BS′. Previously, we found there was positive interaction in the action sequences to transition S11 to S32 and S12 to S31 because they shared actions a1 and a7. There is also some independence in these sequences because the first contains a2, a5, and a6, where the second contains a3. Again, we do not need to know the action sequences to assume independence because we define the aggregation ▽
as a summation of numerical state distances:
dist(BS, BS′) = P
$$\sum_{S\in{\mathcal{M}}(B S)}\operatorname*{lim}_{S^{\prime}\in{\mathcal{M}}(B S^{\prime})}\operatorname{e}$$

min
dist(**S, S**′).

In our example, dist(BS1, BS3) = min(14, 5) + min(3, **7) = 8**, and dist(BS2, BS3) = min(8, **10) = 8**. In this case we have no preference over BS1 and BS2.

We notice that using the cardinality of a belief state |M(BS)| to measure dist(**BS, BS**′) is a special case of assuming state independence, where ∀S, S′dist(S, S′**) = 1**. If we use cardinality to measure distance in our example, then we have dist(BS1, BS3) = |M(BS1)| = 2, and dist(BS2, BS3) = |M(BS2)| = 1. With cardinality we prefer BS2 over BS1 because we have better knowledge in BS2.

- Overlap of States: Overlap assumes that there is both positive interaction and independence between the actions used by states in BS to reach a state in BS′. The intuition is that some actions can often be used for multiple states in BS simultaneously and we should count these actions only once. For example, when we computed dist(BS1**, BS**3) by assuming positive interaction, we noticed that the action sequences for dist(S11, S32) and dist(S12, S31) both used a1 and a7. When we aggregate these sequences we would like to count a1 and a7 each only once because they potentially overlap. However, truly combining the action sequences for maximal overlap is a plan merging problem (Kambhampati, Ihrig, & Srivastava, 1996),
which can be as difficult as planning. Since our ultimate intent is to compute heuristics, we take a very simple approach to merging action sequences. We introduce a plan merging operator ⋒ for ▽ that picks a step at which we align the sequences and then unions the aligned steps. We use the size of the resulting action sequence to measure belief state distance:
dist(BS, BS′) = ⋒S∈M(BS) min S′∈M(BS′)
dist(**S, S**′).

Depending on the type of search, we define ⋒ differently. We assume that sequences used in progression search start at the same time and those used in regression end at the same time. Thus, in progression all sequences are aligned at the first step before we union steps, and in regression all sequences are aligned at the last step before the union.

For example, in progression dist(S11, S32) ⋒ dist(S12, S31) = ({a1, a2}, {a5}, {a6, a7}) ⋒
({a1, a7}, {a3}) = ({a1, a2, a7}, {a5, a3}, {a6, a7}) because we align the sequences at their first steps, then union each step. Notice that this resulting sequence has seven actions, giving