The aggregation function plays an important role in how we measure the distance between belief states. When we compute more than one state distance measure, either exhaustively or by sampling a subset (as previously mentioned), we must combine the measures by some means, denoted . There is a range of options for taking the state distances and aggregating them into a belief state distance. We discuss several assumptions associated with potential measures:

- Positive Interaction of States: Positive interaction
assumes that the most difficult state in
requires actions
that will help transition all other states in
to some state
in
. In our example, this means that we assume the actions used
to transition
to
will help us transition
to
(assuming each state in
transitions to the closest state in
).
Inspecting the action sequences, we see they positively interact because both need actions
and
. We do not need to know the action sequences to assume
positive interaction because we define the aggregation
as a maximization
of numerical state distances:
.

The belief state distances are and . In this case we prefer to . 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
requires actions that are different from all other states in
in order to reach a state in
. Previously, we found there was positive interaction in the action sequences
to transition
to
and
to
because they shared actions
and
.
There is also some independence in these sequences
because the first contains
, and
, where the second contains
. 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:
.

In our example, , and . In this case we have no preference over and .

We notice that using the cardinality of a belief state to measure is a special case of assuming state independence, where . If we use cardinality to measure distance in our example, then we have , and . With cardinality we prefer over because we have better knowledge in .

- Overlap of States: Overlap assumes that there is both
positive interaction and independence between the actions used by states in
to reach a state in
. The intuition is that some actions can
often be used for multiple states in
simultaneously and we
should count these actions only once. For example, when we computed
by assuming
positive interaction, we noticed that the action sequences for
and
both used
and
. When we aggregate these sequences we would
like to count
and
each only once because they potentially overlap.
However, truly combining the action sequences for maximal overlap is a plan merging
problem [19], 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:
.

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 because we align the sequences at their first steps, then union each step. Notice that this resulting sequence has seven actions, giving , whereas defining as maximum gave a distance of five and as summation gave a distance of eight. Compared with overlap, positive interaction tends to under estimate distance, and independence tends to over estimate distance. As we will see during our empirical evaluation (in Section 6.5), accounting for overlap provides more accurate distance measures for many conformant planning domains.

- Negative Interaction of States: Negative interaction
between states can appear in our example if transitioning state
to
state
makes it more difficult (or even
impossible) to transition state
to state
. This could happen if
performing action
for
conflicts with action
for
. We can say that
cannot reach
if all possible action sequences
that start in
and
, respectively, and end in any
negatively interact.
There are two ways negative interactions play a role in belief state distances. Negative interactions can allow us to prove it is impossible for a belief state to reach a belief state , meaning , or they can potentially increase the distance by a finite amount. We use only the first, more extreme, notion of negative interaction by computing ``cross-world'' mutexes [30] to prune belief states from the search. If we cannot prune a belief state, then we use one of the aforementioned techniques to aggregate state distances. As such, we do not provide a concrete definition for to measure negative interaction.

While we do not explore ways to adjust the distance measure for negative interactions, we mention some possibilities. Like work in classical planning [23], we can penalize the distance measure to reflect additional cost associated with serializing conflicting actions. Additionally in conditional planning, conflicting actions can be conditioned on observations so that they do not execute in the same plan branch. A distance measure that uses observations would reflect the added cost of obtaining observations, as well as the change in cost associated with introducing plan branches (e.g., measuring average branch cost).

The above techniques for belief state distance estimation in terms of state distances provide the basis for our use of multiple planning graphs. We will show in the empirical evaluation that these measures affect planner performance very differently across standard conformant and conditional planning domains. While it can be quite costly to compute several state distance measures, understanding how to aggregate state distances sets the foundation for techniques we develop in the . As we have already mentioned, the conveniently allows us to implicitly aggregate state distances to directly measure belief state distance.