With these sampling approaches, we use the , , and relaxed plans. We build the and 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: computed on a unioned single graph , denoted as ``Unioned'' compared to the sampled single graph denoted as ``Single'', and and 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 heuristic is much more effective when computed on versus . This is because the is 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 . 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 and 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 . 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 . Using more possible worlds to compute heuristics is a good idea, but it takes a more efficient substrate to exploit them.