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 ($SG^1$ ), 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}$ , $h^{MG}_{RPU}$ , 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 $SG^U$ , denoted as ``Unioned'' compared to the sampled single graph $SG^1$ denoted as ``Single'', and $h^{MG}_{RPU}$ 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.

Figure 10: Total Time (hours) for $POND$ to solve all conformant and conditional problems when sampling worlds to use in heuristic computation.

There are two major points to see in Figure 10. First, the $h^{SG}_{RP}$ heuristic is much more effective when computed on $SG^1$ versus $SG^U$ . This is because the $SG^1$ 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 $SG^U$ . 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.