In both the CAltAlt and planners we need to guide search node expansion with heuristics that estimate the plan distance between two belief states and . By convention, we assume precedes (i.e., in progression is a search node and is the goal belief state, or in regression is the initial belief state and is a search node). For simplicity, we limit our discussion to progression planning. Since a strong plan (executed in ) ensures that every state will transition to some state , we define the plan distance between and as the number of actions needed to transition every state to a state . Naturally, in a strong plan, the actions used to transition a state may affect how we transition another state . There is usually some degree of positive or negative interaction between and that can be ignored or captured in estimating plan distance.4 In the following we explore how to perform such estimates by using several intuitions from classical planning state distance heuristics.
We start with an example search scenario in Figure 3. There are three belief states (containing states and ), (containing state ), and (containing states and ). The goal belief state is , and the two progression search nodes are and . We want to expand the search node with the smallest distance to by estimating - denoted by the bold, dashed line - and - denoted by the bold, solid line. We will assume for now that we have estimates of state distance measures - 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:
In each sequence there may be several actions in each step. For instance, has and 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 and . We identify four possible options for using state distance estimates to compute the distance between belief states and :
Since it is possible to express a belief state formula with every literal (e.g., using to express the belief state where is true), we assume a reasonably succinct representation, such as a ROBDD . 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 .
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 needs to reach a state in , we should consider the distance for each state in to ``a'' state in . However, we don't necessarily need the distance for every state in to ``every'' state in . 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.