We have now covered the key questions we set out to address: what are the relative effects of alternative search-control strategies on search-space size, and, in particular, how can we reconcile the apparently conflicting approaches of LCFR and ZLIFO? We concluded that LCFR-DSep combines the main advantages for reducing search-space size of these two strategies, namely LCFR's use of a least-cost selection mechanism, at least for forced flaws, with ZLIFO's use of separable-threat delay. A final question concerns the price one has to pay to use LCFR-DSep--or for that matter, any of the alternative strategies. To achieve a reduction in search-space size, is it necessary to spend vastly more time in processing? Or do these strategies pay for themselves?
To answer these questions, we collected timing data on all our
experiments. Figures 
and gives
this data for the basic problems, for both the experiments run with
the node limit and those run with the time limit. (As
detailed in Appendix A, the results for the experiments with the node
limit and the time limit were very similar.)
Because we saw
little influence of precondition ordering on the basic problems, we
analyze only the data for the default precondition ordering.
We show one graph with all the
strategies, and another that includes only the ``leading strategies'',
to make it possible to see the distinctions among them.
The timing data show that LCFR-DSep does, by and large, pay for its own overhead on the basic problems by generating smaller search spaces (and therefore having to process fewer nodes). When run with a time limit, LCFR-DSep's time performance is almost identical with ZLIFO's, despite the fact that repair cost computations are more expensive than the stack-popping of a LIFO strategy. When run with a node limit, LCFR-DSep does show worse time performance than ZLIFO in aggregate, but still performs markedly better than most of the other strategies. The change in relative performance results from the cases in which both strategies fail at the node limit: LCFR-DSep takes longer to generate 10,000 nodes.
Another interesting observation is that DSep-LC has the best time performance of all on the basic problem set. This should perhaps not be a surprise, because DSep-LC closely approximates LCFR-DSep. It differs primarily in its preference for nonseparable threats, which in any case will tend to have low repair costs. Whenever a node includes a nonseparable threat, DSep-LC can quickly select that threat, without having to compute repair costs. This speed advantage outweighs the cost of processing the extra nodes it sometimes generates.
Figures - provide the timing data for the
Trains and Tileworld domains.
Here there are no real surprises. The
computation times taken parallel quite closely the size of the search
spaces generated. The strategies that generate the smallest search
spaces are also the fastest.
With the Trains problems, we again
see the DSep-LC can serve as a good approximation technique for
LCFR-DSep. Although it generates more nodes than LCFR-DSep, it is
somewhat faster.
