Empirical Evaluation Conclusions

In our internal comparisons of heuristics within CAltAlt and $POND$ , 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, $POND$ , to scale up in conditional domains, despite the fact that the heuristic computation does not model observation actions.