
## 7.3 Empirical Evaluation Conclusions

In our internal comparisons of heuristics within CAltAlt and **P OND**, as well as external comparisons with several state of the art conformant and conditional planners we have learned many interesting lessons about heuristics for planning in belief space.

- Distance based heuristics for belief space search help control conformant and conditional plan length because, as opposed to cardinality, the heuristics model desirable plan quality metrics.

- Planning graph heuristics for belief space search scale better than planning graph search and admissible heuristic search techniques.

- Of the planning graph heuristics presented, relaxed plans that take into account the overlap of individual plans between states of the source and destination belief states are the most accurate and tend to perform well across many domains.

- The LUG is an effective planning graph for both regression and progression search heuristics.

- In regression search, planning graphs that maintain only same-world mutexes provide the best trade-off between graph construction cost and heuristic informedness.

- Sampling possible worlds to construct planning graphs does reduce computational cost, but considering more worlds by exploiting planning graph structure common to possible worlds
(as in the LUG), can be more efficient and informed.

- The LUG heuristics help our conditional planner, **P OND**, to scale up in conditional domains, despite the fact that the heuristic computation does not model observation actions.

## 8. Related Work & Discussion

We discuss connections with several related works that involve heuristics and/or conditional planning in the first half of this section. In the second part of the section we discuss how we can extend our work to directly handle non-deterministic outcomes of actions in heuristic computation.

## 8.1 Related Work

Much interest in conformant and conditional planning can be traced to CGP (Smith & Weld, 1998), a conformant version of GraphPlan (Blum & Furst, 1995), and SGP (Weld et al., 1998), the analogous conditional version of GraphPlan. Here the graph search is conducted on several planning graphs, each constructed from one of the possible initial states. More recent work on C-plan (Castellini et al., 2001) and Frag-Plan (Kurien et al., 2002) generalize the CGP approach by ordering the searches in the different worlds such that the plan for the hardest to satisfy world is found first, and is then extended to the other worlds. Although C**AltAlt** and **P OND** utilize planning graphs similar to CGP and Frag-plan it only uses them to compute reachability estimates. The search itself is conducted in the space of belief states.

Another strand of work models conformant and conditional planning as a search in the space of belief states. This started with Genesereth and Nourbakhsh (1993), who concentrated on formulating a set of admissible pruning conditions for controlling search. There were no heuristics for choosing among unpruned nodes. GPT (Bonet & Geffner, 2000) extended this idea to consider a