
| State     | State Distance   | Planning   | Mutex        | Mutex     | Heuristic   |
|-----------|------------------|------------|--------------|-----------|-------------|
| Selection | Aggregation      | Graph      | Type         | Worlds    |             |
| Single    | + Interaction    | SG         | None         | Same      | Max         |
| Aggregate | Independence     | MG         | Static       | Intersect | Sum         |
| Subset    | Overlap          | LUG        | Dynamic      | Cross     | Level       |
| All       | - Interaction    | Induced    | Relaxed Plan |           |             |

In the next section we will also expand upon how to aggregate distance measures as well as discuss the remaining columns of Table 1. We will present each type of planning graph: the single planning graph (SG), multiple planning graphs (MG), and the labelled uncertainty graph (LUG).

Within each planning graph we will describe several types of mutex, including static, dynamic, and induced mutexes. Additionally, each type of mutex can be computed with respect to different possible worlds - which means the mutex involves planning graph elements (e.g., actions) when they exist in the same world (i.e., mutexes are only computed within the planning graph for a single state), or across worlds (i.e., mutexes are computed between planning graphs for different states) by two methods (denoted Intersect and Cross). Finally, we can compute many different heuristics on the planning graphs to measure state distances - max, sum, level, and relaxed plan. We focus our discussion on the planning graphs, same-world mutexes, and relaxed plan heuristics in the next section. Cross-world mutexes and the other heuristics are described in appendices.

## 4. Heuristics

This section discusses how we can use planning graph heuristics to measure belief state distances.

We cover several types of planning graphs and the extent to which they can be used to compute various heuristics. We begin with a brief background on planning graphs.

Planning Graphs: Planning graphs serve as the basis for our belief state distance estimation. Planning graphs were initially introduced in GraphPlan (Blum & Furst, 1995) for representing an optimistic, compressed version of the state space progression tree. The compression lies in unioning the literals from every state at subsequent steps from the initial state. The optimism relates to underestimating the number of steps it takes to support sets of literals (by tracking only a subset of the infeasible tuples of literals). GraphPlan searches the compressed progression (or planning graph)
once it achieves the goal literals in a level with no two goal literals marked infeasible. The search tries to find actions to support the top level goal literals, then find actions to support the chosen actions and so on until reaching the first graph level. The basic idea behind using planning graphs for search heuristics is that we can find the first level of a planning graph where a literal in a state appears; the index of this level is a lower bound on the number of actions that are needed to achieve a state with the literal. There are also techniques for estimating the number of actions required to achieve sets of literals. The planning graphs serve as a way to estimate the reachability of state literals and discriminate between the "goodness" of different search states. This work generalizes such literal estimations to belief space search by considering both GraphPlan and CGP style planning graphs plus a new generalization of planning graphs, called the LUG.

Planners such as CGP (Smith & Weld, 1998) and SGP (Weld et al., 1998) adapt the GraphPlan idea of compressing the search space with a planning graph by using multiple planning graphs, one