Our first two analyses were essentially aimed at replicating earlier results from the literature, namely the LCFR results and the ZLIFO results. We next address the question of how to square these results with one another.

Recall that LCFR and ZLIFO differ in two key respects. First, LCFR treats all flaws uniformly, while ZLIFO distinguishes among flaw types, giving highest preference to nonseparable threats, medium preference to open conditions, and lowest preference to separable threats. Second, while LCFR uniformly makes least-cost selections, ZLIFO uses a LIFO strategy secondary to its flaw-type preferences (but after giving preference to forced open conditions). The comparisons made in Section suggest that the use of a LIFO strategy for unforced flaws should at best make little difference in search-space size, and may possibly lead to to the generation of larger search spaces. On the other hand, the first difference presents an obvious place to look for a relative advantage for ZLIFO. After all, what ZLIFO is doing is delaying separable threats, and Peot and Smith demonstrated the effectiveness of that approach in their DSep strategy.

Peot and Smith's proof that DSep will never generate a larger search space than UCPOP does not transfer to LCFR. There are planning problems for which LCFR will generate a smaller search space than DSep. Their proof relies on the fact that, in DSep, open conditions will be selected in the same order, regardless of when threats are selected. But the selection of a threat in LCFR can influence the repair cost of an open condition (e.g., by promoting an action so that it is no longer available as a potential establisher for some condition), and this in turn can affect the order in which the remaining open conditions are selected.

Nonetheless, despite the fact that one can't *guarantee* that
delaying separable threats will lead to a reduction in search-space
size, the motivation behind DSep is still appealing: separable threats
may often simply disappear during subsequent planning, which will
naturally lead to a reduction in search-space size. For this reason,
we implemented a slightly modified version of LCFR, which we called
LCFR-DSep, in which separable threats are delayed. Note that it is
relatively easy to do this in the UCPOP system, which provides a
switch, the *dsep* switch, which when turned on will automatically
delay the repair of all separable threats. As defined earlier in Table
, the definition of LCFR-DSep is:

**LCFR-DSep** {n.o}LC/{s}LC

On the basic problems, LCFR-DSep proved to have the smallest average node-count
%-overrun of on the basic problems of *all* of the strategies
tested. Moreover, this was true even when we reversed the order in
which the preconditions of an operator were added to the open list.
Figure gives the average node-count %-overruns for both the
unmodified UCPOP v.4 (labeled ``default'') and the modified version in
which we reversed the precondition ordering (labeled ``reverse'').
Reversing the ordering does not effect the conclusion that LCFR-DSep
generates the smallest search spaces for these problems; in fact, in
general it had very little affect on the relative performance of the
strategies at all. The only notable exception, which we mentioned
earlier, is that the relative performance of LCFR and DUnf-Gen flips.

For more detailed comparison, we plot node counts on the basic
problems for LCFR, ZLIFO, and the Separable-Threat Delay strategies in
Figure
. For ease of comparison, we again show the data
sorted by the difference between LCFR and ZLIFO's node counts. The
problems near the left-hand side of the graph are, again, those for
which LCFR generated a smaller search space than ZLIFO; the problems
near the right are those for which it generated a larger search space.
As can be seen, LCFR-DSep nearly always does as well as, or better
than LCFR. It does much better than ZLIFO on the problems that LCFR
is good at. And it also does *much* better than LCFR on the
problems that ZLIFO is good at. However, ZLIFO still outperforms
LCFR-DSep on this latter class of problems.

Another view of the data is given in Figure , the log-log scatter plot for the basic problems, for all the strategies we studied. This time we have highlighted LCFR-DSep's performance. Although there are some problems for which it does not produce a minimal search space, its performance on the individual problems is actually quite good, consistent with its good aggregate performance.

At least for the basic problems, augmenting the simple LCFR strategy with a delay of separable threats reduces the search space as expected. This in turn suggests that when LCFR generates a larger search space than ZLIFO, that is due in large part to the fact that it does not delay separable threats. ZLIFO's primary advantage relative to LCFR seems not to be its use of a LIFO strategy for unforced threats, but rather its separable-threat delay component. Combining separable-threat delay with a least-cost approach yields a strategy that tends to generate smaller search spaces than either strategy by itself for the basic problem set. However, analysis of the Trains and Tileworld problem sets reveals the situation to be a little more complicated than the comparison of the basic problems would suggest, as we discuss in the next section.

Wed Jun 25 17:40:58 EDT 1997