our belief state to only those states that can reach the goal through those actions. Thus in regression the size of belief states decreases, but in progression remains constant.

The performance of **P OND** in the conditional domains exhibits similar trends to the conformant domains, with a few exceptions. Like the conformant domains, the MG relaxed plans tend to outperform the SG relaxed plan, but the LUG relaxed plan does best overall. Unlike the conformant domains, The hMG
m−RP performs much better in BTS and BTCS over BT and BTC partly because the conditional plans have a lower average cost. The h**card** heuristic does better in BTS and BTCS
over BT and BTC because the belief states actually decrease in size when they are partitioned by sensory actions.

## 6.4 Sampling Worlds

Our evaluations to this point have considered the effectiveness of different heuristics, each computed with respect to all possible worlds of a belief state. While we would like to use as many of the possible worlds as we can, we can reduce computation cost and hopefully still get reasonable heuristics by considering a subset of the worlds. Our scheme for considering subsets of worlds in the heuristics is to sample a single world (SG1), or sample a given percentage of the worlds and build multiple graphs, or the LUG.

With these sampling approaches, we use the h SG
RP , hMG
RP U , and h LUG
RP relaxed plans. We build the MG and LUG for 10%, 30%, 50%, 70%, and 90% of the worlds in each belief state, sampled randomly. In Figure 10, we show the total time taken (ms) to solve every problem in our test set (79 problems over 10 domains). Each unsolved problem contributed 20 minutes to the total time.

For comparison we show the previously mentioned heuristics: h SG
RP computed on a unioned single graph SGU , denoted as "Unioned" compared to the sampled single graph SG1 denoted as "Single",
and hMG
RP U and h LUG
RP computed for all worlds denoted as "100%". The total time for any heuristic that samples worlds is averaged over ten runs.

There are two major points to see in Figure 10. First, the h SG
RP heuristic is much more effective when computed on SG1 versus SGU . This is because the SG1is less optimistic. It builds a planning graph for a real world state, as opposed to the union of literals in all possible world states, as in SGU . Respecting state boundaries and considering only a single state is better than ignoring state boundaries to naively consider all possible states. However, as we have seen with the MG
and LUG heuristics, respecting state boundaries and considering several states can be much better, bringing us to the second point.

We see very different performance when using more possible worlds to build multiple graphs compared to the LUG. We are better off using fewer worlds if we have to build multiple graphs because they can become very costly as the number of worlds increases. In contrast, performance improves with more possible worlds when we use the LUG. Using more possible worlds to compute heuristics is a good idea, but it takes a more efficient substrate to exploit them.

## 6.5 Accuracy

The heuristics that account for overlap in the possible worlds should be more accurate than the heuristics that make an assumption of full positive interaction or full independence. To check our intuitions, we compare the heuristic estimates for the distance between the initial belief state and the goal belief state for all the heuristics used in conformant problems solved by **P OND**. Figure 11 shows the ratio of the heuristic estimate for h(BSI ) to the optimal serial plan length h
∗(BSI ) in