Summary of Methods for Distance Estimation

Since we explore several methods for computing belief state distances on planning graphs, we provide a summary of the choices we must consider, listed in Table 1. Each column is headed with a choice, containing possible options below. The order of the columns reflects the order in which we consider the options.

Table 1: Features for a belief state distance estimation.

In this section we have covered the first two columns which relate to selecting states from belief states for distance computation, as well as aggregating multiple state distances into a belief state distance. We test options for both of these choices in the empirical evaluation.

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.