Logistics has observations to determine if a package at a location exists, and the observation is assumed to be made by a driver or pilot at the particular location. Since there are several drivers and a pilot, different agents make the observations. The information gained by the agents is assumed to be automatically communicated to the others, as the planner is the agent that has all the knowledge.5

## 6. 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 LUG over multiple planning graphs and applying mutexes to improve heuristics in regression through pruning belief states.

We compare many techniques within CAltAlt and **P OND** on our conformant planning domains, and in addition we test the heuristics in **P OND** 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 LUG can affect performance. Then we present how **P OND** performs with the different heuristics in both conformant and conditional domains, explore the effect of sampling a proportion of worlds to build SG1, MG, and LUG graphs, and compare the heuristic estimates in **P OND**
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 **P OND** 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 SGU , and the MG and LUG graphs are built for all possible worlds.

## 6.1 Caltalt

The results for CAltAlt in the conformant Rovers, Logistics, BT, and BTC domains, in terms of total time and number of expanded search nodes, are presented in Table 3. We show the number of expanded nodes because it gives an indication of how well a heuristic guides the planner. The total time captures the amount of time computing the heuristic and searching. A high total time with a high number of search nodes indicates a poor heuristic, and a high total time and low number of search nodes indicates an expensive but informed heuristic.

We do not discuss the Ring and Cube Center domains for CAltAlt because it cannot solve even the smallest instances. Due to implementation details the planner performs very poorly when domains have actions with several conditional effects and hence does not scale. The trouble stems