
| Planner   | Search Space   | Search Direction   | Conditional    | Heuristic         | Implementation   |
|-----------|----------------|--------------------|----------------|-------------------|------------------|
| CAltAlt   | Belief Space   | Backward           | Planning Graph | C                 |                  |
| P OND     | Belief Space   | Forward            | √              | Planning Graph    | C                |
| MBP       | Belief Space   | Forward/Backward   | √              | Cardinality       | C                |
| KACMBP    | Belief Space   | Forward            | Cardinality    | C                 |                  |
| CGP       | Planning Graph | Backward           | Planning Graph | Lisp              |                  |
| SGP       | Planning Graph | Backward           | √              | Planning Graph    | Lisp             |
| GPT       | Belief Space   | Forward            | √              | State Space Plans | C                |
| YKA       | Belief Space   | Backward           | √              | Cardinality       | C                |
| CFF       | Belief Space   | Forward            | Planning Graph | C                 |                  |

by sampling worlds used in its construction. However planners are able to exhibit better scalability by considering more worlds through optimizing the representation of the redundant structure as in the LUG. The improvement in scalability is attributed to lowering the cost of heuristic computation, but retaining measures of multiple state distances. The LUG makes a trade-off of using an exponential time algorithm for evaluation of labels instead of building an exponential number of planning graphs. This trade-off is justified by our experiments.

## 7. Empirical Evaluation: Inter-Planner Comparison

We first compare CAltAlt and **P OND** with several planners on our conformant domains, then compare **P OND** with the conditional planners on the conditional domains. Our purpose in this section is to identify the advantages of our techniques over the state of the art planners. We end the section with a discussion of general conclusions drawn from the evaluation.

## 7.1 Conformant Planning

Although this work is aimed at giving a general comparison of heuristics for belief space planning, we also present a comparison of the best heuristics within CAltAlt and **P OND** to some of the other leading approaches to conformant planning. Table 7 lists several features of the evaluated planners, such as their search space, their search direction, whether they are conditional, the type of heuristics, and the implementation language. Note, since each approach uses a different planning representation (BDDs, GraphPlan, etc.), not all of which even use heuristics, it is hard to get a standardized comparison of heuristic effectiveness. Furthermore, not all of the planners use PDDLlike input syntax; MBP, and KACMBP use AR encodings which may give them an advantage in reducing the number of literals and actions. We gave the MBP planners the same grounded and filtered action descriptions that we used in CAltAlt and **P OND**. We also tried, but do not report results, giving the MBP planners the full set of ground actions without filtering irrelevant actions. It appears that the MBP planners do not use any sort of action pre-processing because performance was much worse with the full grounded set of actions. Nevertheless, Table 8 compares MBP, KACMBP,
GPT, CGP, YKA, and CFF with h LUG(DyX−SX)
RP in CAltAlt and h LUG
RP in **P OND** with respect to run time and plan length. MBP: The MBP planner uses a cardinality heuristic that in many cases overestimates plan distances
(as per our implementation with h**card**). MBP uses regression search for conformant plans, but progression search for conditional plans. It is interesting to note that in the more difficult problem