Belief State Distance

In both the CAltAlt and $POND$ planners we need to guide search node expansion with heuristics that estimate the plan distance $dist(BS, BS')$ between two belief states $BS$ and $BS'$ . By convention, we assume $BS$ precedes $BS'$ (i.e., in progression $BS$ is a search node and $BS'$ is the goal belief state, or in regression $BS$ is the initial belief state and $BS'$ is a search node). For simplicity, we limit our discussion to progression planning. Since a strong plan (executed in $BS$ ) ensures that every state $S \in {\cal M}(BS)$ will transition to some state $S' \in {\cal M}(BS')$ , we define the plan distance between $BS$ and $BS'$ as the number of actions needed to transition every state $S \in {\cal M}(BS)$ to a state $S' \in {\cal M}(BS')$ . Naturally, in a strong plan, the actions used to transition a state $S_1 \in {\cal M}(BS)$ may affect how we transition another state $S_2 \in {\cal M}(BS)$ . There is usually some degree of positive or negative interaction between $S_1$ and $S_2$ that can be ignored or captured in estimating plan distance.⁴ In the following we explore how to perform such estimates by using several intuitions from classical planning state distance heuristics.

Figure 3: Conformant Plan Distance Estimation in Belief Space

We start with an example search scenario in Figure 3. There are three belief states $BS_1$ (containing states $S_{11}$ and $S_{12}$ ), $BS_2$ (containing state $S_{21}$ ), and $BS_3$ (containing states $S_{31}$ and $S_{32}$ ). The goal belief state is $BS_3$ , and the two progression search nodes are $BS_1$ and $BS_2$ . We want to expand the search node with the smallest distance to $BS_3$ by estimating $dist(BS_1, BS_3)$ - denoted by the bold, dashed line - and $dist(BS_2, BS_3)$ - denoted by the bold, solid line. We will assume for now that we have estimates of state distance measures $dist(S, S')$ - 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:

$dist(S_{11}, S_{32}): (\{a_1, a_2\}, \{a_5\}, \{a_6, a_7\})$ ,

$dist(S_{12}, S_{31}): (\{a_1, a_7\}, \{a_3\})$ ,

$dist(S_{21}, S_{31}): (\{a_3, a_6\}, \{a_9, a_2, a_1\}, \{a_0, a_8\}, \{a_5\})$ .

In each sequence there may be several actions in each step. For instance, $dist(S_{21}, S_{31})$ has $a_3$ and $a_6$ 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 $BS_1$ and $BS_3$ . We identify four possible options for using state distance estimates to compute the distance between belief states $BS_1$ and $BS_3$ :

• Sample a State Pair: We can sample a single state from $BS_1$ and a single state from $BS_3$ , whose plan distance is used for the belief state distance. For example, we might sample $S_{12}$ from $BS_1$ and $S_{31}$ from $BS_3$ , then define $dist(BS_1, BS_3) = dist(S_{12}, S_{31})$ .

• Aggregate States: We can form aggregate states for $BS_1$ and $BS_3$ 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:

  $$\tilde{S}(BS) = \bigcup\limits_{\substack{l: l \in \hat{S}, \hat{S} \in \hat{\xi}(BS)}} l$$

  
  

  Since it is possible to express a belief state formula with every literal (e.g., using $(q \vee \neg q) \wedge p$ to express the belief state where $p$ 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 $dist(BS_1, BS_3) = dist(\tilde{S}(BS_1), \tilde{S}(BS_3))$ .

  
  
• Choose a Subset of States: We can choose a set of states (e.g., by random sampling) from $BS_1$ and a set of states from $BS_3$ , 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 $S_{11}$ and $S_{12}$ from $BS_1$ and $S_{31}$ from $BS_3$ , compute $dist(S_{11}, S_{31})$ and $dist(S_{12}, S_{31})$ , and then aggregate the state distances to define $dist(BS_1, BS_3)$ .

• Use All States: We can use all states in $BS_1$ and $BS_3$ , 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 $BS_1$ needs to reach a state in $BS_3$ , we should consider the distance for each state in $BS_1$ to ``a'' state in $BS_3$ . However, we don't necessarily need the distance for every state in $BS_1$ to ``every'' state in $BS_3$ . 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.