Next: CAltAlt Up: Planning Graph Heuristics for Previous: Conditional Problems

# Empirical Evaluation: Inter-Heuristic Comparison

We start by comparing the heuristic approaches within our planners. In the next section, we continue by describing how our planners, using the best heuristics, compare against other state of the art approaches. In this section we intend to validate our claims that belief space heuristics that measure overlap perform well across several domains. We further justify using the over multiple planning graphs and applying mutexes to improve heuristics in regression through pruning belief states.

We compare many techniques within CAltAlt and on our conformant planning domains, and in addition we test the heuristics in on the conditional domains. Our performance metrics include the total planning time and the number of search nodes expanded. Additionally, when discussing mutexes we analyze planning graph construction time. We proceed by showing how the heuristics perform in CAltAlt and then how various mutex computation schemes for the can affect performance. Then we present how performs with the different heuristics in both conformant and conditional domains, explore the effect of sampling a proportion of worlds to build , , and graphs, and compare the heuristic estimates in to the optimal plan length to gauge heuristic accuracy. We finish with a summary of important conclusions.

We only compute mutexes in the planning graphs for CAltAlt because the planning graph(s) are only built once in a search episode and mutexes help prune the inconsistent belief states encountered in regression search. We abstain from computing mutexes in because in progression we build new planning graphs for each search node and we want to keep graph computation time low. With the exception of our discussion on sampling worlds to construct the planning graphs, the planning graphs are constructed deterministically. This means that the single graph is the unioned single graph , and the and graphs are built for all possible worlds.

Subsections

Next: CAltAlt Up: Planning Graph Heuristics for Previous: Conditional Problems
2006-05-26