In both the C*AltAlt* and
planners we need to guide search
node expansion with heuristics that estimate the plan distance
between two belief states
and
. By
convention, we assume
precedes
(i.e., in progression
is a search node and
is the goal belief state, or in
regression
is the initial belief state and
is a search
node). For simplicity, we limit our discussion to progression
planning. Since a strong plan (executed in
) ensures that every
state
will transition to some state
, we define the plan distance between
and
as the number of actions needed to transition every state
to a state
. Naturally, in a
strong plan, the actions used to transition a state
may affect how we transition another state
. There is usually some degree of positive or negative
interaction between
and
that can be ignored or captured
in estimating plan distance.^{4}
In 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 (containing states and ), (containing state ), and (containing states and ). The goal belief state is , and the two progression search nodes are and . We want to expand the search node with the smallest distance to by estimating - denoted by the bold, dashed line - and - denoted by the bold, solid line. We will assume for now that we have estimates of state distance measures - 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:

,

,

.

In each sequence there may be several actions in each step. For instance, has and 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
[5,23,18], and
we would like to apply it to estimate the plan distance between two
belief states, say
and
. We identify four possible
options for using state distance estimates to compute the distance
between belief states
and
:

- Sample a State Pair: We can sample a single state from
and a single state
from
, whose plan distance is used for the belief state
distance. For example, we might sample
from
and
from
, then define
.
- Aggregate States: We can form aggregate states for
and
and measure their plan distance. An aggregate state is the union of the literals
needed to express a belief state formula, which we define as:

Since it is possible to express a belief state formula with every literal (e.g., using to express the belief state where is true), we assume a reasonably succinct representation, such as a ROBDD [8]. It is quite possible the aggregate states are inconsistent, but many classical planning techniques (such as planning graphs) do not require consistent states. For example, with aggregate states we would compute the belief state distance .

- Choose a Subset of States: We can choose a set of states
(e.g., by random sampling)
from
and a set of states from
, and then compute state
distances for all pairs of states from the sets. Upon computing all state distances, we can
aggregate the state distances (as we will describe shortly). For example, we might sample
both
and
from
and
from
,
compute
and
, and
then aggregate the state distances to define
.
- Use All States: We can use all states in and , and, similar to sampling a subset of states (above), we can compute all distances for state pairs and aggregate the distances.

The former two options for computing belief state distance are reasonably straightforward, given the existing work in classical planning. In the latter two options we compute multiple state distances. With multiple state distances there are two details which require consideration in order to obtain a belief state distance measure. In the following we treat belief states as if they contain all states because they can be appropriately replaced with the subset of chosen states.

The first issue is that some of the state distances may not be needed. Since each state in needs to reach a state in , we should consider the distance for each state in to ``a'' state in . However, we don't necessarily need the distance for every state in to ``every'' state in . We will explore assumptions about which state distances need to be computed in Section 3.1.

The second issue, which arises after computing the state distances, is that we need to aggregate the state distances into a belief state distance. We notice that the popular state distance estimates used in classical planning typically measure aggregate costs of state features (literals). Since we are planning in belief space, we wish to estimate belief state distance with the aggregate cost of belief state features (states). In Section 3.2, we will examine several choices for aggregating state distances and discuss how each captures different types of state interaction. In Section 3.3, we conclude with a summary of the choices we make in order to compute belief state distances.