The previous section showed that UA has a potential advantage over TO because it can better exploit certain ordering heuristics. We now examine the practical effects of incorporating one such heuristic into UA and TO.
First, we note that ordering heuristics only make sense for some search strategies. In particular, for breadth-first search, heuristics do not improve the efficiency of the search in a meaningful way (except possibly at the last level). Indeed, we need not consider any search strategy in which TO and UA are ``synchronized'', as defined earlier, since ordering heuristics do not significantly affect the relative performance of UA and TO under such strategies. Thus, we begin by considering a standard search strategy that is not synchronized: depth-first search.
Figure 10: Depth first search with and without min-goals
We use the min-goals heuristic as the basis for our experimental
investigation, since it is commonly employed, but presumably we could
choose any heuristic that meets the criterion set forth in the
previous section. Figure 10 shows the impact of min-goals
on the behavior of UA and TO under depth-first search. Although
the heuristic biases the order in which the two planners' search
spaces are explored ( cf.
(Rosenbloom, Lee, & Unruh, 1993), it appears
that its effect is largely independent of the
partial-order/total-order distinction, since both planners are
improved by a similar percentage. For example, under depth-first
search on the problems with solutions at depth six, UA improved 88%
and TO improved 87%. Thus, there is no obvious evidence for any
extra advantage for UA, as one might have expected from our analysis
in the previous section. On the other hand, this does not contradict
our theory, it simply means that the potential heuristic advantage was
not significant enough to show up. In other domains, the advantage
might manifest itself more significantly. After all, it is certainly
possible to design problems in which the advantage is significant, as
our example in Figure 9 illustrates. Our results
simply illustrate that in our blocksworld domain, making intelligent
ordering decisions produces a negligible advantage for UA, in
contrast to the significant effect due to search space compression
(discussed previously).
While the min-goals heuristic did not seem to help UA more than TO, the results are nevertheless interesting, since the heuristic had a very significant effect on the performance of both planners, so much so that TO with min-goals outperforms UA without min-goals. While the effectiveness of min-goals is domain dependent, we find it interesting that in these experiments, the use of min-goals makes more difference than the use of partial orders. After all, the blocksworld originally helped motivate the development of partial-order planning and most subsequent planning systems have employed partial orders. While not deeply surprising, this result does help reinforce what we already know: more attention should be paid to specific planning heuristics such as min-goals.
Figure 11: Iterative sampling & iterative broadening, both with min-goals
In our analysis of search space compression in
Section 7, we described a ``distribution
insensitive'' search strategy called iterative sampling and showed
that under iterative sampling UA and TO perform similarly,
although their performance is worse than it is under depth-first
search. If we combine min-goals with iterative sampling, we find that
this produces a much more powerful strategy, but one in which TO and
still perform about equally. For simplicity, our implementation
of iterative sampling uses min-goals as a pruning heuristic; at each
choice point, it explores only those plan extensions with the fewest
goals. This strategy is powerful, although
incomplete. Because of this incompleteness, we
note there was one problem we removed from our sample set because
iterative sampling with min-goals would never terminate on this
problem. With this caveat in mind, we turn to the results in
Figure 11, which when compared against Figure 10,
show that the performance of both UA and TO with iterative
sampling was, in general, significantly better than their performance
under depth-first search. (Note that the graphs in Figures
10 and 11 have very different scales.) Our results
clearly illustrate the utility of the planning bias
introduced by min-goals in our blocksworld
domain, since on 43 of our 44 problems, a solution exists in the very
small subspace preferred by min-goals.
These experiments do not show any advantage for UA as compared with TO under the heuristic, which is consistent with our conclusions above. However, this could equally well be because min-goals was so powerful, leading to solutions so quickly, that smaller influences were obscured.
The dramatic success of combining min-goals with iterative sampling led us to consider another search strategy, iterative broadening, which combines the best aspects of depth-first search and iterative sampling. This more sophisticated search strategy initially behaves like iterative sampling, but evolves into depth-first search as the breadth-cutoff increases Langley, 1992). Assuming that the solution is within the specified depth bound, iterative broadening is complete. In its early stages iterative broadening is distribution-insensitive; in its later stages it behaves like depth-first search and, thus, becomes increasingly sensitive to solution distribution. As one would expect from our iterative sampling experiments, with iterative broadening, solutions were found very early on, as shown in Figure 11. Thus, it is not surprising that UA and TO performed similarly under iterative broadening.
We should point out that the results presented in this subsection are only illustrative, since they deal with only a single domain and with a single heuristic. Nevertheless, our experiments do illustrate how the various properties we have identified in this paper can interact.