Conclusion

With the intent of establishing a basis for belief state distance estimates, we have:

• Discussed how heuristic measures can aggregate state distance measures to capture positive interaction, negative interaction, independence, and overlap.

• Shown how to compute such heuristic measures on planning graphs and provided empirical comparisons of these measures.

• Found that exploiting planning graph structure to reduce the cost of considering more possible states of a belief state is preferable to sampling a subset of the states for the heuristics.

• Shown that a labelled uncertainty graph can capture the same support information as multiple graphs, and reduces the cost of heuristic computation.

• Shown that the labelled uncertainty graph is very useful for conformant planning and, without considering observational actions and knowledge, can perform well in conditional planning.

Our intent in this work was to provide a formal basis for measuring the distance between belief states in terms of underlying state distances. We investigated several ways to aggregate the state distances to reflect various assumptions about the interaction of state to state trajectories. The best of these measures turned out to measure both positive interaction and independence, what we call overlap. We saw that planners using this notion of overlap tend to do well across a large variety of domains and tend to have more accurate heuristics.

We've also shown that planning with a Labelled Uncertainty planning Graph $LUG$ , a condensed version of the multiple graphs is useful for encoding conformant reachability information. Our main innovation is the idea of ``labels" - labels are attached to all literals, actions, effect relations, and mutexes to indicate the set of worlds in which those respective elements hold. Our experimental results show that the $LUG$ can outperform the multiple graph approach. In comparison to other approaches, we've also been able to demonstrate the utility of structured reachability heuristics in controlling plan length and boosting scalability for both conformant and conditional planning.

We intend to investigate three additions to this work. The first, is to incorporate sensing and knowledge into the heuristics. We already have some promising results without using these features in the planning graphs, but hope that they will help the approaches scale even better on conditional problems. The second addition will be to consider heuristics for stochastic planning problems. The major challenges here are to associate probabilities with labels to indicate the likelihood of each possible world and integrate reasoning about probabilistic action effects.

Lastly, we have recently extended the $LUG$ within the framework of state agnostic planning graphs [13], and hope to improve the technique. A state agnostic planning graph is essentially a multiple source planning graph, where by analogy a conventional planning graph has a single source. Planning graphs are already multiple destination, so in our generalization the state agnostic planning graph allows us to compute the distance measure between any pair of states or belief states. The $LUG$ seeks to avoid redundancy across the multiple planning graphs built for states in the same belief state. We extended this notion to avoid redundancy in planning graphs built for every belief state. We have shown that the state agnostic $LUG$ ($SLUG$ ) which is built once per search episode (as opposed to a $LUG$ at each node) can reduce heuristic computation cost without sacrificing informedness.