The previous sections have compared TO and UA in terms of relative search space size and relative time cost per node. The extra processing time required by UA for each node would appear to be justified since its search space may contain exponentially fewer nodes. However, to complete our analysis, we must consider the number of nodes actually visited by each algorithm under a given search strategy.
For breadth-first search, the analysis is straightforward. After
completing the search to a particular depth, both planners will have
explored their entire trees up to that depth.
Both UA and TO find a
solution at the same depth due to the correspondence between their
search trees. Thus, the degree to which UA will outperform TO,
under breadth-first, depends solely on the ``expansion factor'' under
, i.e., on the number of linearizations of UA's plans.
We can formalize this analysis as follows. For a node U in
, we denote the number of steps in the plan at U by
, and the number of edges in U by 
. Then for each node
U that UA generates, UA incurs time cost 
;
whereas, TO incurs time cost 
, where 
is the number of linearizations
of the plan at node U. Therefore, the ratio of the total time costs
of TO and UA is as follows, where 
denotes the subtree considered by UA under breadth-first search.
The analysis of breadth-first search is so simple because this search strategy preserves the correspondence between the two planners' search spaces. In breadth-first search, the two planners are synchronized after exhaustively exploring each level, so that TO has explored (exactly) the linearizations of the plans explored by UA. For any other search strategy which similarly preserves the correspondence, such as iterative deepening, a similar analysis can be carried out.
The cost comparison is not so clear-cut for depth-first search, since
the correspondence is not guaranteed to be preserved. It is easy to
see that, under depth-first search, TO does not necessarily
explore all linearizations of the plans explored by UA. This is
not simply because the planners nondeterministically choose which
child to expand. There is a deeper reason: the correspondence does not preserve the subtree structure of the search space. For
a plan U in , the corresponding linearizations in
may be spread throughout 
. Therefore, it
is unlikely that corresponding plans will be considered in the same
order by depth-first search. Nevertheless, even though the two
planners are not synchronized, we might expect that, on average, UA
will explore fewer nodes because the size of is less
than or equal to the size of .
Figure 6: UA and TO Performance Comparison under Depth-First Search
Empirically, we have observed that UA does tend to outperform TO
under depth-first search, as illustrated by the experimental results
in Figure 6. The first graph compares the mean number of
nodes explored by UA and TO on 44 randomly generated
blocksworld problems; the second graph compares the mean planning time for UA and TO on the same problems and demonstrates that
the extra time cost per node for UA is relatively insignificant.
The problems are partitioned into 4 sets of 11 problems each,
according to minimal solution ``length'' (i.e., the number of
steps in the plan). For each problem, both planners were given a
depth-limit equal to the length of the shortest
solution. Since the
planners make nondeterministic choices, 25 trials were conducted for
each problem. The source code and data required to reproduce these
experiments can be found in
Online Appendix 1.
As we pointed out, one plausible explanation for the observed dominance of UA is that TO's search tree is at least as large as UA's search tree. In fact, in the above experiments we often observed that TO's search tree was typically much larger. However, the full story is more interesting. Search tree size alone is not sufficient to explain UA's dominance; in particular, the density and distribution of solutions play an important role.
The solution density of a search tree is the proportion of nodes that
are solutions.
If the solution density for TO's search tree is greater than that for
UA's search tree, then TO might outperform UA under depth-first
search even though TO's search tree is actually larger. For
example, it might be the case that all UA solution plans are
completely unordered and that the plans at the remaining leaves of
- the failed plans - are totally ordered. In
this case, each UA solution plan corresponds to an exponential
number of TO solution plans, and each UA failed plan corresponds
to a single TO failed plan. The converse is also possible: the
solution density of UA's search tree might be greater than that of
TO's search tree, thus favoring UA over TO under depth-first
search. For example, there might be a single totally ordered solution
plan in UA's search tree and a large number of highly unordered
failed plans. Since each of these failed UA plans would correspond
to a large number of TO failed plans, the solution density for TO
would be considerably lower.
For our blocksworld problems, we found that the solution densities of
the two planners' trees does not differ greatly, at least not in such
a way that would explain our performance results. We saw no tendency
for to have a higher solution density than
. For example, for the 11 problems with solutions at
depth six, the average solution density for TO exceeded that of UA
on 7 out of the 12 problems. This is not particularly surprising
since we see no a priori reason to suppose that the solution
densities of the two planners should differ greatly.
Figure 7: Uniform solution distribution, with solution density 0.25
Since solution density is insufficient to explain UA's dominance on
our blocksworld experiments when using depth-first search, we need to
look elsewhere for an explanation. We hypothesize that the distribution of solutions provides an explanation. We note that if
the solution plans are distributed perfectly uniformly (i.e., at
even intervals) among the leaves of the search tree, and if the
solution densities are similar, then both planners can be expected to
search a similar number of leaves, as illustrated by the schematic
search tree in Figure 7. Consequently, we can explain
the observed dominance of UA over TO by hypothesizing that
solutions are not uniformly distributed; that is, solutions tend
to cluster. To see this, suppose that is smaller than
but the two trees have the same solution density. If
the solutions are clustered, as in Figure 8, then
depth-first search can be expected to produce solutions more quickly
for than for . The hypothesis that solutions tend to be clustered
seems reasonable since it is easy to construct problems where a
``wrong decision'' near the top of the search tree can lead to an
entire subtree that is devoid of solutions.
Figure 8: Non-uniform solution distribution, with solution density 0.25
One way to test our hypothesis is to compare UA and TO using a randomized search strategy, a type of Monte Carlo algorithm, that we refer to as ``iterative sampling'' ( cf. Minton et al., 1992; Langley, 1992; Chen, 1989; Crawford & Baker, 1994) The iterative sampling strategy explores randomly chosen paths in the search tree until a solution is found. A path is selected by traversing the tree from the root to a leaf, choosing randomly at each branch point. If the leaf is a solution then search terminates; if not, the search process returns to the root and selects another path. The same path may be examined more than once since no memory is maintained between iterations.
In contrast to depth-first search, iterative sampling is relatively
insensitive to the distribution of solutions. Therefore, the advantage
of UA over TO should disappear if our hypothesis is correct. In
our experiments, we did find that when UA and TO both use
iterative sampling, they expand approximately the same number of nodes
on our set of blocksworld problems. (For both planners, performance with iterative
sampling was worse than with depth-first search.) The fact that there
is no difference between UA and TO under iterative sampling, but
that there is a difference under depth-first search, suggests
that solutions are indeed non-uniformly distributed. Furthermore, this
result shows that UA is not necessarily superior to TO; the search
strategy that is employed makes a dramatic difference.
Although our blocksworld domain may be atypical, we conjecture that our results are of general relevance. Specifically, for distribution-sensitive search strategies like depth-first search, one can expect that UA will tend to outperform TO. For distribution-insensitive strategies, such as iterative sampling, non-uniform distributions will have no effect. We note that while iterative sampling is a rather simplistic strategy, there are more sophisticated search strategies, such as iterative broadening (Ginsberg & Harvey, 1992), that are also relatively distribution insensitive. We further explore such strategies in Section 8.2.