currently among the best. Yet a foundation for what constitutes a good distance-based heuristic for belief space has not been adequately investigated.

Belief Space Heuristics: Intuitively, it can be argued that the heuristic merit of a belief state depends on at least two factors–the size of the belief state (i.e., the uncertainty in the current state), and the distance of the individual states in the belief state from a destination belief state. The question of course is how to compute these measures and which are most effective. Many approaches estimate belief state distances in terms of individual state to state distances between states in two belief states, but either lack effective state to state distances or ways to aggregate the state distances. For instance the MBP planner (Bertoli et al., 2001b) counts the number of states in the current belief state. This amounts to assuming each state distance has unit cost, and planning for each state can be done independently. The GPT planner (Bonet & Geffner, 2000) measures the state to state distances exactly and takes the maximum distance, assuming the states of the belief state positively interact.

Heuristic Computation Substrates: We characterize several approaches to estimating belief state distance by describing them in terms of underlying state to state distances. The basis of our investigation is in adapting classical planning reachability heuristics to measure state distances and developing state distance aggregation techniques to measure interaction between plans for states in a belief state. We take three fundamental approaches to measure the distance between two belief states. The first approach does not involve aggregating state distance measures, rather we use a classical planning graph to compute a representative state distance. The second retains distinctions between individual states in the belief state by using multiple planning graphs, akin to CGP (Smith
& Weld, 1998), to compute many state distance measures which are then aggregated. The third employs a new planning graph generalization, called the Labelled Uncertainty Graph (LUG), that blends the first two to measure a single distance between two belief states. With each of these techniques we will discuss the types of heuristics that we can compute with special emphasis on relaxed plans. We present several relaxed plan heuristics that differ in terms of how they employ state distance aggregation to make stronger assumptions about how states in a belief state can co-achieve the goal through action sequences that are independent, positively interact, or negatively interact.

Our motivation for the first of the three planning graph techniques for measuring belief state distances is to try a minimal extension to classical planning heuristics to see if they will work for us.

Noticing that our use of classical planning heuristics ignores distinctions between states in a belief state and may provide uninformed heuristics, we move to the second approach where we possibly build exponentially many planning graphs to get a better heuristic. With the multiple planning graphs we extract a heuristic from each graph and aggregate them to get the belief state distance measure. If we assume the states of a belief state are independent, we can aggregate the measures with a summation. Or, if we assume they positively interact we can use a maximization. However, as we will show, relaxed plans give us a unique opportunity to measure both positive interaction and independence among the states by essentially taking the union of several relaxed plans. Moreover, mutexes play a role in measuring negative interactions between states. Despite the utility of having robust ways to aggregate state distances, we are still faced with the exponential blow up in the number of planning graphs needed. Thus, our third approach seeks to retain the ability to measure the interaction of state distances but avoid computing multiple graphs and extracting heuristics from each. The idea is to condense and symbolically represent multiple planning graphs in a single planning graph, called a Labelled Uncertainty Graph (LUG). Loosely speaking, this single graph unions the causal support information present in the multiple graphs and pushes the disjunction,