\documentstyle[jair,twoside,11pt,theapa]{article}
\input epsf %% at top of file

\jairheading{6}{1997}{223-262}{2/97}{6/97}


\ShortHeadings{Flaw Selection Strategies}{Pollack, Joslin, \& Paolucci}

\newtheorem{definition}{Definition}

\newcommand{\pref}[3]{\mbox{$\{\hbox{#1}\}_{\hbox{#2}} \hbox{#3} $}}
\newcommand{\spref}[2]{\mbox{$\{\hbox{#1}\} \hbox{#2} $}}

\setcounter{page}{223}

\begin{document}

\title{Flaw Selection Strategies For Partial-Order Planning}

\author{\name Martha E. Pollack \email pollack@cs.pitt.edu\\
\addr Department of Computer Science and Intelligent Systems
Program,\\ University of Pittsburgh, Pittsburgh, PA 15260 USA
\AND
\name David Joslin \email joslin@cirl.uoregon.edu\\
\addr Computational Intelligence Research Laboratory,\\
University of Oregon, Eugene, OR   97403 USA
\AND
\name Massimo Paolucci \email paolucci@pitt.edu\\
\addr Intelligent Systems Program,\\
University of Pittsburgh, Pittsburgh, PA   15260 USA}


\maketitle

\begin{abstract} 

Several recent studies have compared the relative efficiency of
alternative flaw selection strategies for partial-order causal link
(POCL) planning.  We review this literature, and present new
experimental results that generalize the earlier work and explain some
of the discrepancies in it.  In particular, we describe the Least-Cost
Flaw Repair (LCFR) strategy developed and analyzed by Joslin and Pollack
\citeyear{JosPol94}, and compare it with other strategies,
including Gerevini and Schubert's \citeyear{GerSchu96} ZLIFO
strategy.  LCFR and ZLIFO make very different, and apparently
conflicting claims about the most effective way to reduce search-space
size in POCL planning.  We resolve this conflict, arguing that much of
the benefit that Gerevini and Schubert ascribe to the LIFO component
of their ZLIFO strategy is better attributed to other causes.  We show
that for many problems, a strategy that combines least-cost flaw
selection with the delay of separable threats will be effective in
reducing search-space size, and will do so without excessive
computational overhead.  Although such a strategy thus provides a good
default, we also show that certain domain characteristics may reduce
its effectiveness.

\end{abstract}

\section{Introduction}
\label{introduction}

Much of the current research in plan generation centers on
partial-order causal link (POCL) algorithms, which descend from
McAllester and Rosenblitt's \citeyear{SNLP} SNLP algorithm.  POCL
planning involves searching through a space of partial plans, where
the successors of a node representing partial plan $P$ are refinements
of $P$.  As with any search problem, POCL planning requires effective
search control strategies.

In POCL planning, search control has two components.  The first, {\em
node selection}, involves choosing which partial plan to refine next.
Once a partial plan has been selected for refinement, the planner must
then perform {\em flaw selection,} which involves choosing either a
threat to resolve or an open condition to establish.

Over the past few years, several studies have compared the relative
efficiency of alternative flaw selection strategies for POCL planning
and their extensions
\cite{PeotSmith93a,JosPol94,SriHow95,GerSchu96,WillHanks96}.
These studies have been motivated at least in part by a tension
between the attractive formal properties of the POCL algorithms, and
the limitations in putting them to practical use that result from
their relatively poor performance.  To date, the POCL algorithms
cannot match the efficiency of the so-called industrial-strength
planners such as SIPE \cite{Wilkins88,WilkDesim94} and O-Plan
\cite{CurrieTate91,OPlan2-94a}.  Flaw selection strategy has been
shown to have a significant effect on the efficiency of POCL planning
algorithms, and thus researchers have viewed the design of improved
flaw selection strategies as one means of making POCL planning
algorithms more practical.

In this paper, we review the literature on flaw selection strategies,
and present new experimental results that generalize the earlier work
and explain some of the discrepancies in it.  In particular, we
describe the Least-Cost Flaw Repair (LCFR) strategy developed and
analyzed by Joslin and Pollack \citeyear{JosPol94}, and compare it with
other strategies, including Gerevini and Schubert's ZLIFO strategy
\citeyear{GerSchu96}.  LCFR and ZLIFO make very different, and apparently
conflicting claims about the most effective way to reduce search-space
size in POCL planning.  We resolve this conflict, arguing that much of
the benefit that Gerevini and Schubert ascribe to the LIFO component
of their ZLIFO strategy is better attributed to other causes.  We show
that for many problems, a strategy that combines least-cost flaw
selection with the delay of separable threats will be effective 
in reducing search-space size, and will do so without excessive
computational overhead.  Although such a strategy thus provides a
good default, we also show that certain domain characteristics may
reduce its effectiveness.

\section{Background}
\label{background}

\subsection{Node and Flaw Selection}

Although the main ideas of POCL planning have been in the literature
for more than two decades, serious efforts at comparing alternative
plan generation algorithms have been relatively recent.  What made
these comparisons possible was the development of a set of clear
algorithms with provable formal properties, notably TWEAK
\cite{Chapman87}, and SNLP \cite{SNLP}.  These algorithms
were not intended to add functionality to known planning methods, but
rather to capture the essential elements of these known methods in a
readily analyzable fashion.

In analyzing POCL algorithms, researchers have found it useful to
decouple the search control strategy from the underlying plan
refinement process.  Figure \ref{pocl-alg} is a generic POCL
algorithm, in which we highlight the two search
decisions.\footnote{Various versions of this well-known algorithm have
appeared in the literature \cite{Weld94,Russell95,KamKnoYang95}.  The
version we give corresponds most directly to that given by Williamson
and Hanks
\citeyear{WillHanks96}.}  Following convention, we use {\bf
CHOOSE} to indicate that node selection is a backtracking point, and
{\bf SELECT} to indicate that flaw selection is not.  A given
node may not lead to a solution, and so it may be necessary to backtrack and
consider alternative nodes.  On the other hand, if a node does lead to
a solution, that solution will be found regardless of the order in
which its flaws are selected.  See Weld's \citeyear{Weld94} tutorial paper
for more discussion of this difference.


\begin{figure}
\begin{tabbing}
abc \= def \= ghi \= jkl \= \kill {\bf POCL} ({\em init,goal})\\ \>
{\em dummy-plan} $\leftarrow$ make-skeletal-plan({\em init,goal}).\\
\> {\em nodes} $\leftarrow$ \{ {\em dummy-plan} \}.\\ \> While {\em
nodes} is not empty do:\\ \> \> {\bf CHOOSE (and remove) a partial plan {\em P}
from {\em nodes}.  (Node Selection)}\\ \> \> If {\em P} has no flaws\\
\> \> \> then return {\em P}\\ \> \> \> else do:\\ \> \> \> \> {\bf
SELECT a flaw from {\em P}.  (Flaw Selection)}\\ \> \> \> \> Add all
refinements of {\em P} to {\em nodes}.\\ \> Return failure (because
{\em nodes} has become empty without a flaw-free plan being found.)\\
\end{tabbing}
\caption{The Basic POCL Planning Algorithm}
\label{pocl-alg}
\end{figure}

The generic algorithm sketched in the figure must be supplemented with
search strategies that implement the {\bf CHOOSE} and {\bf SELECT}
operators.  Most POCL algorithms perform node selection using a
best-first ranking that computes some function of the number of steps
(denoted $S$), open conditions ($OC$), and unsafe conditions ($UC$,
{\em i.e.}, threats) in the partial plan.  Gerevini and Schubert
\citeyear{GerSchu96} have argued that, in general, only steps and
open conditions should be included in the ranking function, and we
adopt that strategy in our experiments, except where otherwise
indicated.

Having chosen a node, a POCL planning algorithm must then select a
flaw---open condition or threat---within that node to repair.  Open
conditions are repaired by {\em establishment}, which consists either
in adding a new step that has a unifying condition as an effect (along
with a causal link from that new step to the condition), or else in
simply adding a new causal link from an existing step with a unifying
effect.  We use the term {\em repair cost} to denote the number
of possible ways to repair a flaw.

For an open condition $o$, the repair cost $R(o)$ is $I + S + N$,
where
\begin{verse}
$I =$ the number of conditions in the initial state that unify with
$o$ given the current binding constraints,\\ $S =$ the number of
conditions in the effects of existing plan steps that unify with $o$
given the current binding constraints, counting only existing plan
steps that are not constrained to occur after the step associated with
$o$, and \\ $N =$ the number of conditions in the effects of operators
in the library that unify with $o$ given the current binding
constraints.\\
\end{verse}
Note that over time, the repair cost for an open condition that is not
resolved may either increase, as new steps that might achieve the
condition are added to the plan, or decrease, as steps already in the
plan are constrained by temporal ordering or variable binding so that
they can no longer achieve the condition.

In considering the cost of threat repair, it is useful to distinguish
between {\em nonseparable} and {\em separable} threats.  Nonseparable
threats consist of a step $S_1$ with effect $E$, and a causal link
$\prec S_2, F, S_3 \succ$, where $E$ and $F$ are complementary
literals that necessarily unify: either they are complementary ground
literals ($E \equiv \neg F$), or else they are complementary literals
where each of $E$'s variables is identical with, or forced by a
binding constraint to be equivalent to the variable in the same
position in $F$ (e.g., $E = p(x,y)$ and $F = \neg p(x,z)$, where there
is currently a binding constraint that $y = z$).\footnote{An
alternative approach also treats cases in which $E \equiv F$ as
threats; this is required to make the planner {\em systematic}, i.e.,
guaranteed never to generate the same node more than once
\cite{SNLP}.}

Nonseparable threats can be repaired in at most two ways: by {\em
promoting} $S_1$, requiring it to occur after $S_3$, or by {\em
demoting} it, requiring it to occur before $S_2$.  Of course, already
existing temporal ordering constraints may block one or both or these
repair options, which is why there are {\em at most} two possible
repairs.\footnote{Conditional planners make use of an additional
method of threat resolution---confrontation---but we ignore that
within this paper \cite{PeotSmith92,Etzioni92}.  Joslin
\citeyear{dj-diss} provides a detailed account of generalizing the
treatment of flaws to other types of planning decisions.}
Over time, the repair cost for an unresolved
nonseparable threat can only decrease.

A separable threat consists of a step $S_1$ with an effect $E$, and a
causal link $\prec S_2, F, S_3 \succ$, where $E$ and $F$ are
complementary literals  that {\em can} be
unified, but where such a unification is
not forced (e.g., where $E=p(x)$ and $F=p(y)$ and there does not
exist a binding constraint $x=y$).
In such circumstances, the threat may
disappear if a subsequent variable binding blocks the unification.
(A nonseparable threat may also disappear if a subsequent ordering
constraint has the effect of imposing promotion or demotion.)  The
repair cost for a separable threat may be higher than that for an
nonseparable threat: not only can promotion and demotion be used, but
so can {\em separation}, which involves forcing a variable binding
that blocks the unification.  Separation can introduce one repair for
each unbound variable in the threat. For example, if the effect
$P(x,y,z)$ threatens $\prec S_2, \neg P(t,u,v), S_3 \succ$, there are
three possible repairs: $x \neq t$, $y \neq u$, and $z \neq v$.  As
with nonseparable threats, the repair cost for a separable threat that
remains unresolved can
only decrease over time.

\subsection{Notation}

The flaw selection strategies that have been discussed in the
literature typically have been given idiosyncratic names (e.g., DUnf,
LCFR, ZLIFO).  It is useful, in comparing them, to have a precise
unifying notation.  We therefore specify a flaw strategy as a
sequence of preferences.  A strategy begins by attempting to find a
flaw that satisfies its first preference; if it is unable
to do so, it then looks for a flaw that satisfies the second
preference; and so on.  To ensure that a POCL algorithm using the
strategy is complete, the sequence of preferences must be exhaustive:
every flaw must satisfy {\em some} preference.  If a flaw satisfies
more than one preference in a strategy, we assume that the first match
is what counts.

In principle, a preference could identify any feature of a flaw.  In
practice, however, flaw selection strategies have only made use of a
small number of features: the type of a flaw (open condition, nonseparable
threat, or separable threat), the number of ways it can be repaired,
and the time at which it was introduced into the plan.  Often, more
than one flaw will have a given feature, in which case a tie-breaking
strategy may be specified for choosing among the relevant flaws.  

We therefore describe a preference using the following notation
\begin{center}
\pref{{\em flaw types}}{{\em repair cost range}}{{\em tie-breaking
strategy}}
\end{center}
which indicates a preference for any flaw $f$ of the specified
type or types, provided that the repair cost for $f$ falls within the
range of values specified.  (If there are no restrictions on repair
cost, we omit the {\em repair cost range}.)
If more than one flaw meets
these criteria, then the tie-breaking strategy is applied to select among
them.  

We abbreviate flaw type as ``o'' (for open condition), ``n'' (for
nonseparable threat), and ``s'' (for separable threat).  We also use
abbreviations for common tie-breaking strategies, e.g., ``LC'' (least
(repair) cost), ``LIFO'' and ``R'' (Random).  In the case of
LC, if a choice
must be made between flaws that have the same repair cost,
LIFO selection is used.

Thus, for example
\begin{center}
\pref{n}{0-1}{R}
\end{center}
specifies a preference for nonseparable threats with a repair cost of zero
or one; if more than one flaw meets these conditions, a
random selection will be made among them.  
We use the term {\em forced} to describe flaws with
repair cost of one or less.  

An example of a 
complete flaw selection strategy is then:
\begin{center}
\pref{n}{0-1}{R}   {\bf /  } \spref{o}{LIFO}   {\bf /  } \spref{n,s}{R}
\end{center}
This strategy would begin by looking for a forced nonseparable threat;
if more than one flaw meets this criterion, the strategy
would select randomly among them.  If
there are no forced nonseparable threats, it would then look for an open
condition, with any repair cost, using a LIFO scheme to select
among them.  Finally, if there are neither forced nonseparable threats
nor open conditions, it would randomly select either an unforced
nonseparable threat or a separable threat.

While we have
distinguished between flaw type and maximum repair cost, on the one
hand, and tie-breaking strategy, on the other, it is easy to
describe strategies that use something other than flaw type as the
main criterion for selection. For
example, a pure LIFO selection strategy would be encoded as follows.
(Henceforth, we give the name of a strategy in boldface preceding
the specification.)
\begin{center}
{\bf LIFO}\hspace*{.25in}\spref{o,n,s}{LIFO}
\end{center}

\section{Flaw Selection Strategies}
\label{lit}

We begin by reviewing the flaw selection strategies that have been
proposed and studied in the literature to date.

\subsection{Threat Preference and Delay}

The original SNLP algorithm \cite{SNLP} adopted a flaw selection
strategy in which threats are resolved before open conditions, and
early versions of the widely used UCPOP planning system \cite{UCPOP}
did the same.\footnote{In the current version of UCPOP
(v.4), the flaw selection strategy that is run by default is the DSep
strategy, discussed just below. For historical reasons, we maintain
the name DSep for that strategy, and use UCPOP for the older default
strategy.} SNLP does not specify a principle for selecting among
multiple threats or multiple opens; UCPOP used LIFO for this purpose.
Employing the notation above, we can describe the basic UCPOP strategy
as:
\begin{center}
{\bf UCPOP}\hspace*{.25in} \spref{n,s}{LIFO} {\bf / } \spref{o}{LIFO}
\end{center}

The first study of alternative flaw selection strategies was done by
Peot and Smith \citeyear{PeotSmith93a}, who relaxed the requirement that
threats always be resolved before open conditions, and examined
several strategies for delaying the resolution of some threats.  They
analyzed five different strategies for delaying the repair of threats;
of these, two are provably superior: DSep and DUnf.

DSep (Delay Separable Threats) was motivated by the observation that
sometimes separable threats can simply disappear in the planning
process as blocking variable bindings are introduced.  As we pointed
out earlier, nonseparable threats may also ``disappear'', but
typically this is less frequent.  Moreover, if the resolution of {\em
all} threats---separable and nonseparable---were delayed, then
nonseparable threats would only disappear early as a side effect of
step reuse, making their disappearance even less frequent.

The DSep strategy therefore defers the repair of all separable threats
until the very end of the planning process.  However, like UCPOP, it
continues to give preference to nonseparable threats:
\begin{center}
{\bf DSep}\hspace*{.25in} \spref{n}{LIFO} {\bf / } \spref{o}{LIFO}
{\bf / } \spref{s}{LIFO}
\end{center}
Actually, Peot and Smith do not specify a tie-breaking strategy for
choosing among multiple threats; we have here indicated this as
LIFO\@.  They explored three different tie-breaking strategies for
selecting open conditions (FIFO, LIFO, and least-cost); here we list
LIFO, but one can also specify the alternatives:
\begin{center}
{\bf DSep-LC}\hspace*{.25in} \spref{n}{LIFO} {\bf / } \spref{o}{LC}
{\bf / } \spref{s}{LIFO}\\
{\bf DSep-FIFO}\hspace*{.25in}\spref{n}{LIFO} {\bf / } \spref{o}{FIFO}
{\bf / }
\spref{s}{LIFO}\\
\end{center}
Peot and Smith prove that the search space generated by a POCL planner
using DSep will never be larger than the search space generated using
the UCPOP strategy.  This result holds when the tie-breaking strategy
for open conditions is LIFO or FIFO, but not LC, a point we will
return to later in the paper.

Peot and Smith's second successful strategy is DUnf (Delay Unforced
Threats).  It makes use of the notion of forced flaws.  As we stated
earlier, a flaw is forced if there is at most one possible way to
repair it.  The DUnf strategy delays the repair of all unforced
threats:
\begin{center}
{\bf DUnf}\hspace*{.25in} \pref{n,s}{0}{LIFO} {\bf / }
\pref{n,s}{1}{LIFO}  {\bf / } \spref{o}{LIFO}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO}
\end{center}
We can define DUnf-LC and DUnf-FIFO in a manner analogous to that used
for DSep-LC and DSep-FIFO:
\begin{center}
{\bf DUnf-LC}\hspace*{.25in} \pref{n,s}{0}{LIFO} {\bf / }
\pref{n,s}{1}{LIFO} {\bf /} \spref{o}{LC}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO}\\
{\bf DUnf-FIFO}\hspace*{.25in} \pref{n,s}{0}{LIFO} {\bf / }
\pref{n,s}{1}{LIFO} {\bf /} \spref{o}{FIFO}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO}
\end{center}

Peot and Smith proved that the DUnf strategy would never generate a
larger search space than either of the remaining two strategies that
they examined.  They also proved that that DSep and
DUnf are incomparable: there exist planning problems for which DSep
generates a smaller search space than DUnf, and other problems for
which the reverse is true.

Peot and Smith support their theoretical results on DSep and DUnf with
experiments showing that, at least for the domains they examined,
these strategies can result in significant decrease in search-space
size.  The decrease in search is correlated with the difficulty of the
problem, and consequently, as the problems get more difficult, these
strategies reduce search time as well as space.  That is, on large
enough problems, they ``pay for'' their own overhead.

In follow-on work, Peot and Smith \citeyear{SmithPeot94a} describe a
strategy called DMin, which generates smaller search spaces than both
DSep and DUnf.  DMin combines a process of pruning dead-end nodes with
the process of flaw selection.  It gives preference to forced threats.
If there are no forced threats, it checks to see whether {\em all} the
remaining nonseparable threats could be repaired simultaneously.  If
so, it leaves them as threats, and selects an open condition to
repair; if there are no open conditions, then presumably it selects a
remaining unforced threat to repair.  On the other hand, if it is
impossible to repair all the unforced, nonseparable threats, then the
node is a dead end, and can be pruned from the search space.  Note
that some dead-end nodes can be recognized immediately, even without
doing the complete consistency checking of DMin.  This is because an
unrepairable flaw cannot subsequently become repairable, hence, any
node containing a flaw with repair cost of zero is a dead end.
Consequently, all flaw selection strategies should give highest
priority to such flaws \cite{JosPol96,dj-diss}.


\subsection{Least-Cost Flaw Repair}
\label{lcfr}

Peot and Smith's work provided the foundation for our subsequent
exploration of the least-cost flaw repair (LCFR) strategy
\cite{JosPol94}. We hypothesized that the power of the DUnf strategy
might come not from its relative ordering of threats and open conditions,
but instead from the fact that DUnf has the effect of imposing a
partial preference for least-cost flaw selection.  DUnf will always
prefer a forced threat, which, by definition has a repair cost of at
most one; thus, in cases in which there is a forced threat, DUnf will
make a low-cost selection.  What about cases in which there are no
forced threats?  Then DUnf will have to select among open conditions,
assuming there are any.  If our hypothesis is correct, a version of
DUnf that makes {\em this} selection using a least-cost strategy
(i.e., DUnf-LC) ought to perform better than a version that uses one
of the other strategies (i.e., bare DUnf or DUnf-FIFO).  In fact, if
it is the selection of low-cost repairs that is causing the
search-space reduction, then the idea of treating threat resolution
differently from open condition establishment ought to be abandoned.
Instead, a strategy that always selects the flaw with minimal repair
cost, regardless of whether it is a threat or an open condition, ought
to show the best performance.  This is the Least-Cost Flaw Repair
(LCFR) strategy:\footnote{The LCFR strategy is similar to the
branch-1/branch-n search heuristics included in the O-Plan system
\cite{CurrieTate91}.  The contribution of our original work on this topic was
to isolate this strategy and examine it in detail.}
\begin{center}
{\bf LCFR}\hspace*{.25in} \spref{o,n,s}{LC}
\end{center}

There are strong similarities between LCFR and certain heuristics that
have been proposed and studied in the literature on constraint
satisfaction problems (CSPs).  This is perhaps not surprising, given
that flaw selection in POCL planning corresponds in some fairly strong
ways to variable selection in constraint programming.  Flaws in a POCL
planner represent decisions that are yet to be made, and that must be
made before the plan will be complete; unbound variables play a
similar role in constraint satisfaction problems (CSPs).\footnote{When
planning problems are cast as CSPs in the planner Descartes
\cite{JosPol96,dj-diss}, this correspondence is even more direct.}
Although there exist a number of heuristics for selecting a variable
to branch on in solving a CSP \cite{Kumar92}, one well-known heuristic
that is often quite effective is the {\em fail first principle}, which
picks the variable that is the ``most constrained'' when selecting a
variable to branch on.  A simple and common implementation of the fail
first principle selects the variable with the smallest domain
\cite{Tsang93}.

The intuition behind the fail first principle is that one should prune
dead-end regions of the search as early as possible.  The unbound
variables that are most tightly constrained are likely to be points at
which the current partial solution is most ``brittle'' in some sense,
and by branching on those variables we hope to find a contradiction
(if one exists) quickly.  Similarly, LCFR can be thought of as
selecting the ``most constrained'' flaws, resulting in better pruning.

A similar heuristic has also been adopted in recent work on
controlling search in hierarchical task network (HTN) planning, in the
Dynamic Variable Commitment Strategy (DVCS).  DVCS, like LCFR, is
based on a minimal-branching heuristic.  Experimental analyses
demonstrate that DVCS generally produces a well-focused search
\cite{Tsuneto96}.

Our own initial experimental results, presented in Joslin and Pollack
\citeyear{JosPol94}, similarly supported the
hypothesis that a uniform least-cost flaw repair strategy could be
highly effective in reducing the size of the search space in POCL
planning.  In those experiments, we compared LCFR against four other
strategies: UCPOP, DUnf, and DUnf-LC, as defined above, and a new
strategy, UCPOP-LC which we previously called LCOS \cite{JosPol94}:
\begin{center}
{\bf UCPOP-LC}\hspace*{.25in} \spref{n,s}{LIFO}   {\bf /  } \spref{o}{LC}
\end{center}
We included UCPOP-LC to help verify that search-space reduction
results from a preference for flaws with minimal repair costs.  If this
is true, then UCPOP-LC ought to generate a smaller search space then
DUnf, even though it does not delay any threats.  Our results were as
expected.  UCPOP and DUnf, which do not do least-cost selection of open
conditions, generated the largest search spaces; UCPOP-LC generated
significantly smaller spaces; and DUnf-LC and LCFR generated the
smallest spaces.

At the same time, we observed that LCFR incurred an unwieldy overhead,
often taking longer to solve a problem than UCPOP, despite the fact
that it was searching far fewer nodes.  In part this was due a
particularly inefficient implementation of LCFR that we were using,
but in part it resulted from the fact that computing repair costs is
bound to take more time than simply popping a stack (as in a LIFO
strategy), or finding a flaw of a particular type (as in a strategy
that prefers threats).  We therefore explored approximation
strategies, which reduce the overhead of flaw selection by accepting
some inaccuracy in the repair cost calculation.  For example, we
developed the ``Quick LCFR'' (or QLCFR) strategy, which calculates the
repair cost of any flaw only once, when that flaw is first
encountered.  In any successor node in which the flaw remains
unresolved, QLCFR assumes that its repair cost has not changed.  Our
experiments with QLCFR showed it to be a promising means of making a
least-cost approach sufficiently fast to pay for its own overhead.
Additional approximation strategies were studied by Srinivasan and
Howe \citeyear{SriHow95}, who experimented with three variations of LCFR,
along with a fourth, novel strategy that moves some of the control
burden to the user.


\subsection{Threat Delays Revisited}

Recently, Gerevini and Schubert \citeyear{GerSchu96} have revived the idea
that a flaw selection strategy should treat open conditions and
threats differently, and have suggested that LIFO should be used as
the tie-breaking strategy for deciding among open conditions.  They
combine these ideas in their ZLIFO strategy:
\begin{center}
{\bf ZLIFO}\hspace*{.25in} \spref{n}{LIFO}   {\bf /  } \pref{o}{0}{LIFO}   {\bf /  }
\pref{o}{1}{New}   {\bf /  } \pref{o}{2-$\infty$}{LIFO}   {\bf /  } \spref{s}{LIFO}
\end{center}
The ZLIFO strategy gives highest priority to nonseparable threats, and
then to forced open conditions.  If there are neither nonseparable
threats nor forced open conditions, ZLIFO will select an open
condition using LIFO\@.  It defers all separable threats to the end of
the planning process.  The name ZLIFO is intended to summarize the
overall strategy.  The ``Z'' stands for ``zero-commitment'',
indicating that preference is given to forced open conditions: in
repairing these, the planner is not making any commitment beyond what
{\em must} be made if the node is ultimately to be refined into a
complete plan.  The ``LIFO'' indicates the strategy used for selecting
among unforced open conditions.

For open conditions with a repair cost of exactly one, the ZLIFO
strategy uses a tie-breaking strategy here called ``New''.  It prefers
the repair of an open condition that can only be established by
introducing a new action over the repair of an open condition that can
only be established by using an element of the start state.  Gerevini
and Schubert state that this preference ``gave improvements in the
context of Russell's tire changing domain \ldots without significant
deterioration of performance in other domains'' \citeyear[p.
104]{GerSchu96}.  However the difference was apparently not dramatic,
and Gerevini believes this to be an implementation detail, though is
open to the possibility that further study might show this preference
to be significant \cite{Gerevini-mail}.

Gerevini and Schubert make three primary claims about ZLIFO:
\begin{enumerate}
\item A POCL planner using ZLIFO will tend to generate a smaller
search space than one using a pure LIFO strategy.
\item The reduction in search space using ZLIFO, relative to LIFO, is
correlated with the complexity of the planning problem (where complexity is
measured by the number of nodes generated by the pure LIFO strategy).
\item ZLIFO performs comparably with LCFR on relatively easy problems,
and generates a smaller search space on harder problems.
\end{enumerate}

The first two claims are consistent with what we found in the earlier
LCFR studies.  While a LIFO strategy pays no attention to repair
costs, ZLIFO does, at least indirectly, both in its initial preference
for nonseparable threats, which have a repair cost of no more than
two, and in its secondary preference for forced opens.

The third claim is harder to square with our earlier LCFR study, in
which the LIFO-based strategies, such as UCPOP and DUnf, generated much
larger search spaces than the least-cost based strategies. 
What explains ZLIFO's performance?  Gerevini and Schubert answer this
question as follows:
\begin{quotation}
Based on experience with search processes
in AI in general, [a LIFO] strategy has much to recommend it, as a
simple default.  In the first place, its overhead cost is low compared
to strategies that use heuristic evaluation or lookahead to prioritize
goals.  As well, it will tend to maintain focus on the achievement of
a particular higher level goal by regression \ldots rather than
attempting to achieve multiple goals in a breadth-first fashion.  [p. 103]
\end{quotation}
Their point about overhead is an important one.  ZLIFO is a relatively
inexpensive control strategy, and a competing strategy that does a
better job of pruning the search space may end up paying excessive
overhead.  But it is the second point that addresses the question we
are asking here, namely, how ZLIFO could produce {\em smaller} search
spaces.  Gerevini and Schubert go on to say that:
\begin{quotation}
[m]aintaining focus on a single goal should be advantageous at least
when some of the goals to be achieved are independent.  For instance,
suppose that two goals G1 and G2 can both be achieved in various ways,
but choosing a particular method of achieving G1 does not rule out any
of the methods of achieving G2.  Then if we maintain focus on G1
until it is solved, before attempting G2, the total cost of solving
both goals will just be the sum of the costs of solving them
independently.  But if we switch back and forth, and solutions of both
goals involve searches that encounter many dead ends, the combined
cost can be much larger.  This is because we will tend to search any
unsolvable subtree of the G1 search tree repeatedly, in combination
with various alternatives in the G2 search tree \ldots. [p. 103]
\end{quotation}
This is certainly a plausible explanation.   A key remaining question, of
course, is the extent to which this explanation carries over to the
many planning problems that involve interacting goals.

\section{Experimental Comparison of Flaw Selection Strategies}
\label{exper}

As discussed in the previous section, several different proposals
have been made in the literature about how best to reduce the size of
the search space during POCL planning.  These include:
\begin{itemize}
\item giving preference to threats over open conditions;
\item giving preference only to certain kinds of threats (either separable or
forced threats), and delaying other threats until after all open
conditions have been resolved;
\item giving preference to flaws that have minimal repair cost;
\item giving preference to the most recently introduced flaws.
\end{itemize}
Moreover, different strategies have combined these preference schemes in
different ways, and apparently conflicting claims have been made
about the effects of these preferences on search-space size.

To resolve these conflicts, we performed experimental
comparisons of POCL planners using a variety of flaw selection
strategies.  We gave particular attention to the comparison of LCFR
and ZLIFO, because of the their apparently conflicting claims.  LCFR
generates its search space treating all flaws uniformly, using a
least-cost approach to choose among them.  ZLIFO distinguishes between
flaw types (non-separable threats, open conditions, and separable
threats), and uses a modified LIFO approach to select among the flaws in each
class.  The original LCFR studies would have led us to predict that
ZLIFO would generate larger search spaces than did LCFR, but Gerevini
and Schubert found just the opposite to be true.  We aimed, then, to
explain this discrepancy.

Our principal focus was on search-space size, for two reasons.  First,
the puzzle raised by LCFR and ZLIFO is one of space, not time.  As we
mentioned earlier, it is easy to see why ZLIFO would be faster than
LCFR, even on a per node basis.  A least-cost strategy must compute
repair costs, while ZLIFO need only pop a stack containing the right
type of flaws.  The puzzle for us was not why ZLIFO was faster, but
why it generated smaller search spaces.  Second, we believe that
understanding the effect of search control strategies on search-space
size can lead to development of approximation techniques that produce
speed-up as well; the QLCFR strategy \cite{JosPol94} and Srinivasan
and Howe's strategies
\citeyear{SriHow95} are examples of this.

However, a secondary goal was to analyze the time requirements of the
strategies we compared, and we therefore collected timing data for all
our experiments.  As we discuss in Section \ref{time}, the strategy
that tends to generate the smallest search space achieves enough of a
reduction to pay for its own overhead, by and large.


\subsection{Experimental Design}

To conduct our comparison, we implemented a set of flaw selection
strategies in UCPOP v.4.\footnote{Note that the experiments in both
our earlier LCFR paper \cite{JosPol94} and Gerevini and Schubert's
\citeyear{GerSchu96} ZLIFO paper were run using an earlier version
(v.2) of UCPOP\@.  As a result, the number of nodes produced in our
experiments sometimes differs from what is reported in these other two
papers.  This appears to be largely due to the fact that UCPOP v.4
puts the elements of a new set of open conditions onto the flaw list
in the reverse order of the way in which UCPOP v.2 does
\cite{Gerevini-mail}.  As discussed below in Sections
\ref{lz}--\ref{domaind}, we studied the influence of this ordering
change by also collecting data using a modified version of UCPOP v.4
in which we reversed the order of conditions entered in the open list.
While the resulting numbers are similar to those previously published,
they are not identical, leading us to conclude that
there are additional subtle differences between v.2 and v.4.
However, because {\em all} the experiments on which we report here
were run using the same version of UCPOP, we believe this to be a fair
comparison of the strategies.} Table
\ref{the-strats} lists the strategies that we implemented.  Except for
LCFR-DSep and DUnf-Gen, which are discussed later, all the implemented
strategies were described in Section \ref{lit}.


\begin{table}
\begin{tabular}{|l|l|}
\hline
UCPOP & \spref{n,s}{LIFO} {\bf / } \spref{o}{LIFO} \\
\hline
UCPOP-LC & \spref{n,s}{LIFO}   {\bf /  } \spref{o}{LC}\\
\hline
DSep & \spref{n}{LIFO} {\bf / } \spref{o}{LIFO} {\bf / }
\spref{s}{LIFO} \\
\hline
DSep-LC & \spref{n}{LIFO} {\bf / } \spref{o}{LC} {\bf /} \spref{s}{LIFO} \\
\hline
DUnf & \pref{n,s}{0}{LIFO} {\bf / } \pref{n,s}{1}{LIFO}  {\bf / }
\spref{o}{LIFO}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO} \\
\hline
DUnf-LC & \pref{n,s}{0}{LIFO} {\bf / } \pref{n,s}{1}{LIFO} {\bf /}
\spref{o}{LC}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO} \\
\hline
DUnf-Gen &  \pref  {n,s,o}{0}{LIFO} {\bf / } \pref{n,s,o}{1}{LIFO}
{\bf / } \pref{n,s,o}{2-$\infty$}{LIFO}\\
\hline
LCFR & \spref{o,n,s}{LC} \\
\hline
LCFR-DSep & \spref{n,o}{LC} {\bf /} \spref{s} {LC} \\
\hline
ZLIFO & \spref{n}{LIFO}   {\bf /  } \pref{o}{0}{LIFO}   {\bf /  } \pref{o}{1}{New}   {\bf /  } \pref{o}{2-$\infty$}{LIFO}   {\bf /  } \spref{s}{LIFO} \\
\hline
\end{tabular}
\caption{Implemented Flaw Selection Strategies}
\label{the-strats}
\end{table}

We tested all the strategies on three problem sets, also used in our
earlier work
\cite{JosPol94} and in Gerevini and Schubert's \citeyear{GerSchu96}:
\begin{enumerate}
\item {\em The Basic Problems},  33 problems taken from the test suite
distributed with the UCPOP system.  These include problems from a
variety of domains, including the blocks world, the Monkeys and
Bananas problem, Pednault's  \citeyear{Pednault88}
briefcase-and-office problem, Russell's \citeyear{Russell92} tire changing world,
etc.  
\item {\em The Trains Problems}, three problems taken from the TRAINS
transportation domain \cite{Allenetal95}.
\item {\em The Tileworld Problems}, seven problems taken from the
Tileworld domain \cite{AAAI90}.
\end{enumerate}

We ran each strategy on each problem twice.  The first time, we
imposed a node limit, of 10,000 nodes for the basic problems, and of
100,000 nodes for the Trains and Tileworld problems.  The second time,
we imposed a time limit, of 100 seconds for the basic problems, and of
1000 seconds for the Trains and Tileworld problems.  

Gerevini and Schubert experimented with several different node
selection strategies for the Trains and Tileworld domains, so to
facilitate comparison we also used the same node selection strategies
as they did.  For the basic problems, we used $S+OC$.

In reporting our results, we make use not only of raw counts of nodes
generated and computation time in seconds taken, but we also compute
a measure of how badly a strategy performed on a given problem or set
of problems.  We call this measure \%-overrun, and compute it as
follows.  Let $m$ be the minimum node count on a given problem for {\em
any} of the strategies we tested, and let $c$ be the node count for a
particular strategy $S$.  Then 
\begin{center} 
\%-overrun$(S) =[(c-m)/m]*100$ 
\end{center} 
Thus, for example, if the best strategy on
a given problem generated 100 nodes, then a strategy that generated
200 nodes would have a 100
\%-overrun on that problem.  The strategy that does best on a given
problem will have a \%-overrun of 0 on that problem.  In Section
\ref{time}, we make use of similarly computed \%-overruns for
computation time.  

If a strategy hit the node limit, we set $c$ to the relevant node
limit (10,000 or 100,000) to compute its node-count
\%-overrun.\footnote{Because of the way in which UCPOP completes its
basic iteration, it sometimes will go somewhat beyond the specified
node limit before terminating the run.  In such cases, we used the node
limit value, rather than the actual number of nodes generated, in our
computation of \%-overrun.} Similarly, if a strategy hit the time
limit, we used the relevant time limit (100 or 1000) to compute the
computation-time
\%-overrun. 

Online Appendix A provides the raw data---node counts and
computation-time taken---for all the experiments we conducted; it also
includes computed \%-overruns.

In conducting experiments such as these, one has to set either a node-
or time limit cutoff for each strategy/problem pair.  However, there
is always a danger that these cutoffs unfairly bias the data, if the
limits are set in such a way that certain strategies that fail would
instead have succeeded were the limits increased slightly.  We have
carefully analyzed our data to help eliminate the possibility of such a
bias; details are given in Appendix A.



\subsection{The Value of Least-Cost Selection}
\label{lc-value}

Having described our overall experimental design, we now turn to the
analysis of the results.  To begin, we sought to re-establish the
claims we originally made in our earlier work.  Specifically, we wanted
first to reconfirm, using a larger data set, that least-cost flaw
selection is an effective technique for reducing the size of the
search space generated by a POCL planner.  We therefore ran an
experiment in which we compared the the node counts for the five
strategies we had earlier studied---LCFR, DUnf, DUnf-LC, UCPOP, and
UCPOP-LC---plus one new one, DUnf-Gen, explained below.

The results of this experiment are shown in Figures \ref{table1} and
\ref{graph1}.  The former is a log-log scatter plot, showing the
performance of each of the six strategies on the 33 problems in the
basic set.
The problems were sorted by the minimal number of nodes generated on
them by any of the six strategies.
Thus, the left-hand side of
the graph includes the problems that at least one of the six strategies
found to be relatively easy, while the right-hand side has the
problems that were hard for all six strategies.
We omitted problems that none of the six strategies were
able to solve.  The actual number of nodes generated by each strategy
is plotted on the Y-axis, against the minimal number of nodes for that
problem, on the X-axis. LCFR's performance is highlighted with a line
connecting its data points.
This graph shows that, in general, LCFR generates 
small search spaces on this problem set, relative to the other
strategies in this class.  There were only six problems for
which LCFR was not within 10\% of the minimum.  Three of these are in
the Get-Paid/Uget-Paid class of problems---including two of the
``hardest'' problems (UGet-Paid3 and UGet-Paid4).  We discuss this
class of problems more in Section \ref{domaind}.

An alternative view of the data is given in Figure \ref{graph1}, which
shows the aggregate performance of the six strategies, i.e., 
the average of their node-count \%-overrun on the basic problems.  As
can be seen, LCFR has the smallest average \%-overrun.

Figures \ref{table3} and
\ref{graph3} present similar views of the data for the Tileworld
domain, while Figure \ref{table2} gives the data for the Trains problems.
On the Trains domain, these six strategies were only able to solve the
easiest problem (Trains1), so we simply show the actual node counts in
Figure \ref{table2}.   We have omitted two data points,
because they were so extreme that their inclusion on the graph made it
impossible to see the differences among the other strategies:  
LCFR and DUnf-Gen with $S+OC+UC$ node selection took 28,218, and
35,483 nodes, respectively, to solve the problem.

For the Tileworld and Trains problems, we observed the same sorts of
interactions between node and flaw selection strategies as were seen
by Gerevini and Schubert.  Specifically, LCFR performs relatively
poorly with $S+OC$ on the Tileworld problems, and it performs very
poorly with $S+OC+UC$ on the Trains problems.
However, when paired with the other node-selection
strategies, LCFR produces the smallest search spaces of any strategies
in this class.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph1.eps}}
\caption{Basic Problems:  Node Counts for Strategies without
Forced-Flaw Delay}
\label{table1}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph1.eps}}
\caption{Basic Problems:  Aggregate Performance for Strategies without
Forced-Flaw Delay}
\label{graph1}
\end{figure}




\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph3.eps}}
\caption{Tileworld Problems:  Node Counts for Strategies without
Forced-Flaw Delay}
\label{table3}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph3.eps}}
\caption{Tileworld Problems:  Aggregate Performance for Strategies without
Forced-Flaw Delay}
\label{graph3}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{newgraph2.eps}}
\caption{Trains 1:  Node Counts for Strategies without
Forced-Flaw Delay}
\label{table2}
\end{figure}


In sum, LCFR does tend to produce smaller search spaces than the other
strategies in this class.   But a question remains.  LCFR uses a
least-cost strategy, and a side effect of this is that it will prefer
forced flaws, since forced flaws are low-cost flaws.  It is therefore
conceivable that LCFR's performance is mostly or even fully due to its
preference for forced flaws, and not (or not greatly) influenced by
its use of a least-cost strategy for unforced flaws.  This same
hypothesis could explain why DUnf-LC consistently outperforms DUnf,
and why UCPOP-LC consistently outperforms UCPOP\@.

It was to address this issue that we included DUnf-Gen in our
experiment.  DUnf-Gen is a simple strategy that prefers forced flaws
of any kind, and otherwise uses a LIFO regime.  We would expect
DUnf-Gen and LCFR to perform similarly, since they frequently make the
same decision.  Specifically, they will both select the same flaw in
any node in which there is a forced flaw; they will differ when there
are only unforced flaws, with DUnf-Gen selecting a most recently
introduced flaw and LCFR selecting a least-cost flaw.

In practice, DUnf-Gen's performance closely mimicked that of LCFR's.
On the basic problem set it did only marginally worse than LCFR\@.  In
fact, it does marginally {\em better} when we reverse the order in
which the planner adds the preconditions of each new step to the open
list (see Section \ref{valsep}).  LCFR does somewhat better than
DUnf-Gen on both the Trains and Tileworld problems, and this is true
regardless of the order in which the preconditions were added to the
open list, but the extent to which it does better varies.

Thus, the data is inconclusive about the value of using a least-cost
strategy for unforced flaws.  LCFR clearly benefits from selecting
forced flaws early (as a side effect of preferring least-cost flaws),
but it {\em may} not matter whether it continues to use a least-cost
strategy for the unforced flaws.  If indeed it is generally sufficient
to use a least-cost strategy only for forced flaws, then ZLIFO's
performance is somewhat less puzzling, since ZLIFO also prefers forced
flaws.  However the puzzle is not completely resolved.  After all,
DUnf-Gen, like ZLIFO, prefers forced flaws and and then makes
LIFO-based decisions about unforced flaws, and while its performance
is not clearly inferior to LCFR's, neither is it clearly superior.
Even if the use of LIFO for unforced flaws does not obviously increase
the search-space, neither does it appear to decrease it.


\subsection{Comparing LCFR and ZLIFO}
\label{lz}

We next turn to a direct comparison of LCFR and ZLIFO\@.  Gerevini
and Schubert compared these strategies on only a few problems.  To get
a more complete picture of the performance of both LCFR and ZLIFO, we
ran them both on all the problems from our three problem sets.  

The data for the basic problem set is shown in Figure \ref{table4}.
We have sorted the problems by the difference between the node counts
produced by LCFR and ZLIFO\@. Thus, problems near the left-hand side
of the graph are those for which LCFR generated a smaller search
space, while problems near the right-hand side are the ones on which
ZLIFO had a space advantage.  We omit problems which neither strategy
could solve.

As can be seen, on some problems (notably R-Test2, Move-Boxes, and
Monkey-Test2), LCFR generates a much smaller search space than ZLIFO,
while on other problems (notably Get-Paid4, Hanoi, Uget-Paid4, and
Uget-Paid3), ZLIFO generates a much smaller search space.  These are
problems on which LCFR also did worse than the
strategies mentioned above in Section \ref{lc-value}.

As we noted earlier, one of the major changes between UCPOP v.2 and
v.4 is that v.4 puts the elements of a new set of open conditions onto
the flaw list in the reverse order from that of v.2.
This ordering may make a difference, particularly for LIFO-based
strategies.  Indeed, other researchers have suggested that one reason
a LIFO-based strategy may perform well is because it can exploit the
decisions made by the system designers in writing the domain
operators, since it is in some sense natural to list the most
constraining preconditions of an operator first \cite{WillHanks96}.
We therefore also collected data for a modified version of UCPOP, in
which the preconditions for each step are entered onto the open
condition in the reverse of the order in which they would normally be
entered.  We discuss the results of this modification in more detail
in the next two sections, but for now, we simply present the node
counts for LCFR and ZLIFO with the reversed precondition insertion, in
Figure \ref{table5}.  As can be seen, there are a few problems on
which reversing the precondition ordering has a significant effect
(notably FIXB and MonkeyTest2), but by and large LCFR and ZLIFO showed
the same relative performance.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph4.eps}}
\caption{Basic Problems:  Node Counts for LCFR and ZLIFO}
\label{table4}
\end{figure}



\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph5.eps}}
\caption{Basic Problems:  Node Counts for LCFR and ZLIFO with
Reversed Precondition Insertion}
\label{table5}
\end{figure}

For the problems in the basic set, it is difficult to discern an
obvious pattern of performance.  In contrast to what Gerevini and
Schubert suggest, there does not seem to be a clear correlation
between the difficulty of the problem, measured in terms of nodes
generated, and the relative performance of LCFR and ZLIFO\@.  (In
fact, it is a little difficult to determine which strategy's
node-count should serve as the measure of difficulty.)  On the other
hand, it is true that in the aggregate, ZLIFO generates smaller search
spaces than LCFR on the basic problems.  With the default precondition
ordering, ZLIFO obtains an average \%-overrun of 212.62, while LCFR
obtains 647.57.  With reverse ordering, ZLIFO's average \%-overrun is
244.24, while LCFR's is 914.87.  The fact that LCFR's relative
performance is worse when the preconditions are entered in the reverse
direction results primarily from its failure on MonkeyTest2 in the
reverse direction.

The Trains data is scant. 
Neither LCFR nor ZLIFO can solve the hardest problem,
Trains3, regardless of whether the preconditions are entered in the
default or the reverse order.  (In fact, none of the strategies we studied were able to
solve Trains3.)
But, at least when the preconditions are entered in the default order, ZLIFO can solve
Trains2, and LCFR cannot. With reverse precondition insertion, neither
strategy can solve Trains2.
The data are shown in Figure \ref{table7a}.  Note that LCFR's
performance is essentially the same for both node-selection strategies shown.

Finally, the Tileworld data, for the default order of precondition
insertion, is shown in Figure \ref{table8a}.  Here is the only place
in which LCFR clearly generates smaller search spaces than ZLIFO.  We
have not also plotted the data for reverse precondition insertion,
because most of the strategies are not affected by this change.  There
is however, one very notable exception: with reversed insertion, ZLIFO
(with $S+OC+.1UC+F$) does much better---indeed, it does as well as
LCFR\@.  We return to the influence of precondition ordering on the
Tileworld problems in
Section \ref{domaind}.

For now, however, it is enough to observe that our experiments show
that ZLIFO does tend to generate smaller search spaces than LCFR\@.
It does so on the basic problem set, regardless of the order of
precondition insertion, it does so on Trains for one ordering (and
does no worse than LCFR on the other ordering), and it does as well as
LCFR for the Tileworld problems when the preconditions are inserted in
the reverse order.  The only exception is the Tileworld problem set
when the preconditions are inserted in default order: there LCFR does
better.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph6.eps}}
\caption{Trains Problems:  Node Counts for LCFR and ZLIFO}
\label{table7a}
\end{figure}


\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph7.eps}}
\caption{Tileworld Problems:  Node Counts for LCFR and ZLIFO}
\label{table8a}
\end{figure}



\subsection{The Value of Separable-Threat Delay}
\label{valsep}

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 \ref{lc-value} 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 {\em 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 {\em dsep} switch, which when turned on will automatically
delay the repair of all separable threats.  As defined earlier in Table
\ref{the-strats}, the definition of LCFR-DSep is:
\begin{center}
{\bf LCFR-DSep}\hspace*{.25in} \spref{n,o}{LC} {\bf /} \spref{s} {LC} 
\end{center}
Our hypothesis was that if ZLIFO's reduction in search-space size were
largely due to its incorporating a DSep approach, then LCFR-DSep ought
to be ``the best of both worlds'', combining the advantages of LCFR's
least-cost approach with the advantages of a DSep approach.

On the basic problems, LCFR-DSep proved to have the smallest average node-count
\%-overrun of on the basic problems of {\em 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 \ref{graph5} 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.


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph5.eps}}
\caption{Basic Problems:  Aggregate Performance for all Strategies}
\label{graph5}
\end{figure}

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph8.eps}}
\caption{Basic Problems:  Node Counts for LCFR, ZLIFO, and DSep Strategies}
\label{table9}
\end{figure}

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph9.eps}}
\caption{Basic Problems:  Node Counts for all Strategies}
\label{table9a}
\end{figure}

For more detailed comparison, we plot node counts on the basic
problems for LCFR, ZLIFO, and the Separable-Threat Delay strategies in
Figure
\ref{table9}.  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 {\em 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 \ref{table9a}, 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.

\subsection{The Need for Domain Information}
\label{domaind}

The Tileworld and Trains domains problems challenge overly simple
conclusions we might draw from the basic problem sets.  We consider
each set of problems in turn.

\subsubsection{The Tileworld Problems}

The Tileworld domain involves a grid with tiles and holes, and the
goal is to fill each hole with a tile.  This goal can be achieved with
a {\bf fill} operator, which has two preconditions: the agent must be
at the hole, and it must be holding a tile.  In our encoding, an agent
can hold up to four tiles at a time.  The {\bf go} operator is used to
achieve the (sub)goal of being at a hole, while the {\bf pickup}
operator is used to achieve the (sub)goal of holding a tile.  In the
normal way, {\bf go} has a precondition of being at some location,
namely whatever location the agent will move from.  {\bf Pickup} has a
precondition of being at the location of some tile.  The problems in
the Tileworld problem set differ from one another in the number of
holes that the agent must fill: each problem adds another hole.

Figures \ref{graph6} gives the log-log plot for the various strategies
on the Tileworld problems, when the preconditions were entered in the
default order.  Note that LCFR ($S+OC+UC$) is the strategy
highlighted.  Three other strategies were almost indistinguishable
from LCFR ($S+OC+UC$), namely, LCFR ($S+OC+.1UC+F$), DUnf-Gen
($S+OC+UC$) and DUnf-Gen($S+OC+.1UC+F$).  All the other strategies
performed worse.  This can more easily be seen in Figure \ref{graph8},
which gives the aggregate performance for the leading strategies:
those that were able to solve all seven Tileworld problems.  In fact,
these leading
strategies were able to solve the seven Tileworld problems
without generating more than 1800 nodes for any problem.  In contrast,
the remaining strategies failed on at least one, and up to four, of
the seven problems, given the limit of 100,000 nodes generated.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph10.eps}}
\caption{Tileworld Problems: Node Counts for All Strategies}
\label{graph6}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph6.eps}}
\caption{Tileworld Problems:  Aggregate Performance for Leading 
Strategies}
\label{graph8}
\end{figure}


What was originally surprising to us is that on the Tileworld
problems, delaying separable threats actually seems to hurt
performance.  The strategies that did best were those like LCFR and
DUnf-Gen that do {\em not} delay separable threats.  LCFR-DSep, ZLIFO,
DSep-LC, and DSep all generated larger search spaces, in contrast to
what we would have predicted given the experiments on the basic
problem set.

To understand this result, we looked in detail at the planning trace
for these problems.  What that revealed is that for the Tileworld
domain, the early resolution of separable threats has an important
advantage: it imposes what turns out to be the correct temporal
ordering between the steps of going to up a tile (to pick it up), and
carrying it to a hole.  Virtually all the strategies create subplans
like the one shown in Figure \ref{tw-pp}.   The goals involve filling
holes, so the planners insert steps to go to and pick up a tile, and
to go to the hole.  At this point, there are two separable threats:
(1) the effect of going to the hole, $\neg at(X)$, threatens the link
between going to the tile and picking it up ($at(Z)$), and (2) the
effect of going to the tile, $\neg at(W)$, threatens the link between
going to the hole and filling it ($at(Y)$).  Both threats are
separable, because $X$ and $W$ will be unbound; the planner does not
yet know where it will be traveling from.  But there is only one valid
temporal ordering that will resolve these threats: going to the tile
must precede picking up the tile, which in turn must precede going to
the hole.  Once this temporal ordering is determined, further planning
goes smoothly.

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{twpp.eps}}
\caption{Typical Partial Plan for the Tileworld Domain}
\label{tw-pp}
\end{figure}

In contrast, if this ordering decision is not made, the planner can
often ``get lost'', attempting to find plans in which it goes
from some location to the hole and then from the hole to the tile.
There are many ways to attempt this, because there are many different
tiles to select, and many different locations to move among.  The
planner may try many of these alternatives before determining that
there is a fundamental inconsistency in these plans, and that they are
destined to fail.  The larger the number of holes to be filled, the worse
the situation becomes.

Sometimes the planner may make the right decision about temporal
ordering even if it has deferred separable threats.  When faced with
the partial plan in Figure \ref{tw-pp}, if the planner does not select
a threat, it will select from among several open conditions.  It can
attempt to establish the precondition of going to the hole ($at(X)$)
by reusing the effect of going to the tile ($at(Z)$), or it can do the
reverse, and attempt to establish the precondition of going to the
tile ($at(W)$) by reusing the effect of going to the hole ($at(X)$).
Of course, the first solution is the right one, and includes the
critical temporal ordering constraint, while the second will
eventually fail.

The order in which the open conditions are selected will determine
which of these two choices the planner makes.  When preconditions are
entered in the default order, planners that delay separable threats
end up making the latter, problematic choice.  In contrast, when the
preconditions are entered in the reverse order, the planners make what
turns out to be the correct choice.  Thus, for the experiments in
which we reversed precondition insertion, we see a different pattern
of performance, as shown in Figures
\ref{table11}--\ref{graph9}.\footnote{To preserve readability, in
Figure \ref{graph9},
we have used ``(1)''
to denote $S+OC$, ``(2)'' for $S+OC+UC$, and ``(3)'' for
$S+OC+UC+.1F$.}

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph11.eps}}
\caption{Tileworld Problems:  Node Counts with Reversed Precondition
Insertion}
\label{table11}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph9.eps}}
\caption{Tileworld Problems:  Aggregate Performance for all Strategies
with Reversed Precondition Insertion}
\label{graph9}
\end{figure}


When the preconditions are entered in the reverse order, a larger
number of strategies perform well, solving all the problems.  In
particular, with $S+OC+.1UC+F$ node-selection, the performance of
LCFR, DUnf-Gen, ZLIFO, and LCFR-DSep is virtually indistinguishable.
It is important to note that the leading strategies that do not delay
separable threats---LCFR and DUnf-Gen---are not affected much by the
reversal of precondition insertion for the Tileworld problems; in
fact, LCFR's performance is identical in both cases.  In contrast, the
strategies that use separable-threat delay---LCFR-DSep, ZLIFO, and
DSep-LC---all perform much better when we reverse precondition
insertion.  This is explained by our analysis above.

In sum, what is most important for the Tileworld domain is for the
planner to recognize, as early as possible, that there are certain
required temporal orderings between some of the steps in any successful
plan.  Every successful plan will involve going to a tile before going
to a hole, although there is flexibility in the order in which
multiple holes are visited, and in the interleaving of picking up
tiles and dropping them in holes.  For the strategies we studied,
there were two different methods that led to this temporal constraint
being added to the plan.  It was added when the planner selected a
separable threat to resolve, and it was added when it selected one
particular precondition to resolve before another.


\subsubsection{The Trains and Get-Paid Problems}

The Trains domain present a somewhat different variation on our
original conclusions.  The Trains domain involves a set of locations
and objects, and the goal is to transport various objects from
specific starting locations to specified destinations.  Gerevini and
Schubert studied three Trains problems.  All of our strategies failed
to successfully complete the hardest of these (Trains3) within either
the 100,000 node or the 1000 second limit.   Moreover, many of them
also failed on the second hardest (Trains2).
Caution must 
therefore be taken in interpreting the results, as there are a limited
number of data points.


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{newgraph12.eps}}
\caption{Trains Problems:  Node Counts}
\label{table12}
\end{figure}

Figure \ref{table12} gives the node counts for the Trains domain, with
preconditions inserted in the default order.  We
only show the strategies that were able to solve both Trains1 and Trains2.
These  results are
closer to what we would have predicted from the basic problem set than
were the results with the Tileworld.  In particular, LCFR-DSep does
very well, generating much smaller search spaces than LCFR\@.
However, it does slightly worse than ZLIFO\@.  Recall that we saw the
same pattern of performance on a subset of the basic problems,
specifically on the Get-Paid/Uget-Paid problems.  There, LCFR-DSep
again improved on LCFR, but did not generate as small search spaces as
ZLIFO\@.  It turns out that there are similar factors influencing both
sets of problems, and it is instructive to consider in some detail the
planning done by ZLIFO and LCFR-DSep for the Get-Paid/Uget-Paid
problems to understand what is occurring.

Like the Trains domain problems, the Get-Paid/Uget-Paid problems
involve moving particular objects to specified locations.  
In the Get-Paid/Uget-Paid domain there are three objects: a paycheck, a
dictionary, and a briefcase.  As generally formulated, in the initial
state all three are at home, and the paycheck is in the briefcase.
The goal is to deposit the paycheck at the bank, bring the dictionary
to work, and have the briefcase at home.  Both the dictionary and the
paycheck can be moved only in the briefcase.  For a human, the
solution to this problem is obvious.  The dictionary must be put into
the briefcase, and it must then be carried to work, where the
dictionary is taken out.  The briefcase must then be carried home.  In
addition, a stop must be made at the bank, either on the way to work
or on the way home, at which point the paycheck must be taken out of
the briefcase and deposited.

ZLIFO and LCFR-DSep take different paths in solving this problem.
ZLIFO begins by forming plans to get the paycheck to the bank and the
dictionary to work.  These goals are selected first because they are
forced: there is only one way to get the paycheck to the bank (carry
it there), and similarly only one way to get the dictionary to the office
(carry it there).  In contrast, there are two possible ways to
get the briefcase home: either by leaving it there (i.e., reusing the
initial state) or by carrying it there from somewhere else (i.e.,
adding a new step).  The LIFO mechanism then proceeds to complete the
plans for achieving the goals of getting the paycheck to the bank and
the dictionary to work, before beginning to work on the remaining
goal, of getting the briefcase home.  At this point, that goal is easy
to solve.   All that is needed is to plan a route home from wherever the
briefcase is at the end of these two errands.

LCFR-DSep, like ZLIFO, begins by selecting the forced goals of getting
the dictionary to the office and getting the paycheck to the bank.
However, instead of next completing the plans for these goals,
LCFR-DSep continues to greedily select least-cost flaws, and thus
begins to work on achieving the goal of getting the briefcase home.
Unfortunately, at this point it is not clear where the briefcase needs
to be moved home {\em from}, and hence LCFR-DSep begins to engage in a
lengthy process of ``guessing'' where the briefcase will be at the end
of the other tasks, before it has planned for those
tasks.\footnote{The difficulty that LCFR-DSep encounters by greedily
picking low-cost flaws might be reduced by doing a lookahead of
several planning steps, to determine a more accurate repair cost.
This is the approach taken in the branch-n mechanism in O-Plan
\cite{CurrieTate91}.  Significant overhead can be involved 
in such a strategy, however.}

The key decision for the Get-Paid/Uget-Paid domain---and, as it turns
out, for the Trains domain---is related to, but subtly different from
the key decision in the Tileworld domain.  For Get-Paid/Uget-Paid and
Trains, the key insight for the planner is again that there is an
important temporal ordering between goals.  The goal of getting the
briefcase home is going to have to be achieved after the goal of
taking the dictionary to work.  However, recognition of this
constraint is not affected by separable-threat delay, as it was for
the Tileworld.  Instead, what happens in these domains is that a
higher-cost flaw interacts with a lower-cost one, causing the latter
to become fully constrained.

It is tempting to think that here finally is a case in which a
LIFO-based strategy is advantageous.  After all, for this example, by
completely determining what you will do to achieve one goal, you make
it much easier to know how to solve the another goal.  But the use of
ZLIFO (or an alternative LIFO-based strategy) does not guarantee that
the interactions between high- and lower-cost flaws will be exploited.
In particular if the interactions are among two or more unforced
flaws, then the order of the goals in the agenda can lead ZLIFO to
make an inefficient choice.  Thus, when we modified the problem so
that the briefcase was at work in the initial state, ZLIFO and
LCFR-DSep both solved the problem very quickly (178 nodes for ZLIFO
and 157 for LCFR-DSep).  Note that this modification removes the
problematic interaction between a low-cost and a high-cost flaw.

Finally, note that the effectiveness of the LIFO strategies is again
heavily dependent on the the order in which preconditions are entered
onto the open list.  Figure \ref{table13} gives the node counts for
the Trains domain with reverse precondition insertion.  We once again 
plot only the strategies that can solve both Trains 1 and 
Trains2.  In this case, there
are only two such strategies:
LCFR-DSep and DSep-LC.
The strategies that rely on
LIFO for open-condition selection, ZLIFO, DSep, DUnf-Gen, and UCPOP,
all do significantly worse than they did when the preconditions were
in the correct order.  To the extent that LIFO helps in such domains,
it appears to be because of its ability to exploit the 
decisions made by the system designers in writing the domain
operators, as suggested by Williamson and Hanks
\citeyear{WillHanks96}. 

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{newgraph13.eps}}
\caption{Trains Problems:  Node Counts with Reversed Precondition
Insertion}
\label{table13}
\end{figure}


\subsection{Computation Time}
\label{time}

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 \ref{graph12} and \ref{graph13} 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.

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph12.eps}}
\caption{Basic Problems: Aggregate Computation Time Performance for Leading Strategies}
\label{graph12}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph13.eps}}
\caption{Basic Problems:  Aggregate Computation Time Performance}
\label{graph13}
\end{figure}

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 \ref{graph14}--\ref{graph17} provide the timing data for the
Trains and Tileworld domains.\footnote{We have omitted the strategies
that did very poorly, performing worse {\em
both} on the node- and time-limit experiments than did any of the
strategies graphed. Note that we ran the reverse-order
experiments only with a node limit.} 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.\footnote{In interpreting the Trains timing data, it
is important to note that some of the strategies shown---notably UCPOP,
UCPOP-LC, and Dunf, failed to solve Trains2 within either the node or
the time limit.}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph14.eps}}
\caption{Tileworld Problems:  Aggregate Computation Time Performance
for Leading Strategies}
\label{graph14}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph15.eps}}
\caption{Tileworld Problems:  Aggregate Computation Time Performance
for Leading Strategies with Reversed Precondition Insertion}
\label{graph15}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph16.eps}}
\caption{Trains Problems:  Aggregate Computation Time Performance for
Leading Strategies}
\label{graph16}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph17.eps}}
\caption{Trains Problems:  Aggregate Computation Time Performance for
Leading Strategies with Reversed Precondition Insertion}
\label{graph17}
\end{figure}


\section{Conclusion}

In this paper, we have synthesized much of the previous work on flaw
selection for partial-order causal link planning, showing how earlier
studies relate to one another, and have developed a
concise notation for describing alternative flaw selection strategies.

We also presented the results of a series of experiments aimed at
clarifying the effects of alternative search-control preferences on
search-space size.  In particular, we aimed at explaining the
comparative performance of the LCFR and ZLIFO strategies.  We showed
that neither of these flaw selection strategies consistently generates
smaller search spaces, but that by combining LCFR's least-cost
approach with the delay of separable threats that is included in the
ZLIFO strategy, we obtain a strategy---LCFR-DSep---whose space
performance was nearly always as good as the better of LCFR or ZLIFO
on a given problem.  We therefore concluded that much of ZLIFO's
advantage relative to LCFR is due to its delay of separable threats
rather than to its use of a LIFO strategy.  Although we were unable to
resolve the question of whether least-cost selection is required for
unforced, as well as forced flaws, we found no evidence that a LIFO
strategy for unforced flaws was better.  On the other hand,
separable-threat delay is clearly advantageous.  An open question is
exactly why it is so advantageous.  We have conducted preliminary
experiments that suggest that much of the search-space reduction that
results from delaying separable threats can also be achieved by making
separation systematic, something that UCPOP v.4 does not do.  

We also considered the question of computation time, and showed that
often LCFR-DSep only requires computation time comparable to that of
ZLIFO\@.  LCFR-DSep can therefore be seen as paying for its own
computational overhead by its search-space reduction.  Moreover, Peot
and Smith's DSep-LC provides a good approximation of LCFR-DSep:
although it produces somewhat larger search spaces, it does so more
quickly.

These conclusions, however, are tempered by the fact that for certain
clusters of problems, our combined strategy, LCFR-DSep, does not
generate minimal search spaces.  As we saw, for the Tileworld
problems, what is most important is to recognize the need for a
particular temporal ordering among plan steps, and this recognition
can be obtained by resolving separable threats early.  For the Trains
and Get-Paid/Uget-Paid domains, what matters most is recognizing that a
particular effect can in fact only be achieved in one way, and this is
only recognized when a particular flaw is selected---a flaw which
happens generally not to be the least cost flaw available.  The lesson
to be learned from these sets of problems is that although we now
understand the reasons that LCFR and ZLIFO perform the way they do,
and how to combine the best features of both to create good default
strategies for POCL planning, it is clear that domain-dependent
characteristics such as those we identified in the Trains and
Tileworld domains must still be taken into account in settling on a
flaw selection strategy for any domain.


\section*{Acknowledgments}

Martha Pollack's work on this project has been supported by the Air
Force Office of Scientific Research (F49620-96-1-0403) and an NSF
Young Investigator's Award (IRI-9258392).  David Joslin has been
supported by Rome Labs (RL)ARPA (F30602-95-1-0023) and an NSF CISE
Postdoctoral Research award (CDA-9625755).  Massimo Paolucci has been
supported by the Office of Naval Research, Cognitive and Neural
Sciences Division (N00014-91-J-1694).

We are very grateful to Alfonso Gerevini for providing us with the
code he used in his earlier study, and allowing us to use it in our
experiments.  We would also like to thank Arthur Nunes and Yazmine
DeLeon, who assisted us in carrying out experiments done in the
preliminary stages of this work.  Finally, we thank Alfonso Gerevini,
Len Schubert, Michael Wellman, and the anonymous reviewers for their
helpful comments on this work.


\section*{Appendix A:  Ruling Out Ceiling Effects}
\label{ceiling}

For the data collected using a node limit, we examined all the
problems in which at least one of the strategies hit the node
limit.
Table \ref{table14} gives the {\em second worst} node count for
all such problems.  It shows that, for all the basic problems in which at
least one strategy failed, and at least one other succeeded, the 
second-worst strategy generally created fewer than 7000 nodes.

Similarly, for the Trains
and Tileworld problems, in all such cases except TW3, the second-worst
strategy took fewer than 50,000 nodes (and in TW3 it took 89,790).
Recall that the node limit for the basic problems was 10,000 nodes,
while for the Trains and Tileworld problems it was 100,000 nodes.  It
is thus clear that the strategies that hit the node limit are doing
substantially worse than the strategies that succeed.  Even if they
were to succeed by increasing the node limit slightly, their
comparative performance would still be poor.  

Thus, by using the node limits we imposed, we are not making any
strategies look worse than they actually are.  On the other hand, in
computing \%-overrun, we may be making some strategies look better
than they actually are, because we use a value of 10,000 (or 100,000)
nodes generated when a strategy hits the limit, and the actual number
of nodes it might take, if run to completion, could be significantly
higher.  This is why, in our analyses, we considered both the absolute
performance of strategies on individual problems, and their aggregate
performance, as measured by average \%-overrun.

\begin{figure}
\epsfxsize=280pt
\centerline{\epsffile{table14.eps}}
\caption{Second-Worst Node Counts on Problems with Failing Strategies}
\label{table14}
\end{figure}

We also compared the experiments that were run with a time limit and
those that were run with a node limit.  For the basic problem set, the
time limit of 100 seconds was high enough that, in most cases,
strategies could compute significantly more nodes than they could with
the node cutoff.  Nonetheless, the results were almost identical.  In
nearly all cases, if a strategy failed with the node cutoff, it also
failed with the time limit cutoff.  There were only four
exceptions to this: \begin{enumerate} 
\item Hanoi:  With the 10,000 nodes limit, DSep fails, while with the
100 second time limit, it succeeds, taking 46,946 nodes.
\item Uget-Paid3: With the
10,000 node limit, UCPOP-LC fails, while with the 100 second time
limit, it succeeds, taking 37,951 nodes.  \item Uget-Paid4: With the
10,000 node limit, UCPOP-LC fails, while with 100 second time limit,
it succeeds, taking 23,885 nodes.  \item Fixit: With the 10,000 nodes
limit, DSep-LC, UCPOP-LC, and ZLIFO fail, while with the 100 second
time limit, they succeed in 12,732, 13,510, and 20,301 nodes
respectively.  All the other strategies fail to solve this problem
under either limit.  \end{enumerate}

There was a similarly strong correspondence between the results we
obtained on the Trains and Tileworld problems using a node limit and a
time limit.  In a few cases, a strategy that was able to succeed
within the 100,000 node limit was {\em not} able to succeed within the
1,000 second time limit.   The nature of these problems is that the
computation time per node can be very great.  Specifically,
\begin{enumerate} 

\item On TW3, DUnf succeeded in 56,296 nodes when
run with a node limit, but failed with the 1,000 second time limit.
\item On TW4, LCFR-DSep (with an S+OC node-selection strategy)
succeeded in 69,843 nodes, but failed on the time limit.  \item On
TW5, LCFR-DSep (with an S+OC+UC node-selection strategy) succeeded in
49,024, but failed on the limit.  \item On TW6, LCFR (with an S+OC
node-selection strategy) succeeded in 4,506 nodes, but failed with the
time limit.  \end{enumerate} In only one case did a strategy fail
under the node limit but succeed within the time limit:
\begin{enumerate} \item On
TW3, DSep (with an S+OC node-selection strategy) failed with a 100,000
node limit, but succeeded with 134,951 nodes using a 100 second time
limit.  Note that this is significantly worse than the second worst
strategy, which solved this problem generating 89,790 nodes.  
\end{enumerate}

Given this close correspondence between the experiments with node and
time limits, we collected only node-limit data for the experiments in
which we reversed the precondition insertion.

\newpage

\bibliography{complete}
\bibliographystyle{theapa}  




\end{document}




=========================================================

(3)  Latex source (with figures omitted):


\documentstyle[jair,twoside,11pt,theapa]{article}
\input epsf %% at top of file

\jairheading{6}{1997}{223-262}{2/97}{6/97}


\ShortHeadings{Flaw Selection Strategies}{Pollack, Joslin, \& Paolucci}

\newtheorem{definition}{Definition}

\newcommand{\pref}[3]{\mbox{$\{\hbox{#1}\}_{\hbox{#2}} \hbox{#3} $}}
\newcommand{\spref}[2]{\mbox{$\{\hbox{#1}\} \hbox{#2} $}}

\setcounter{page}{223}

\begin{document}

\title{Flaw Selection Strategies For Partial-Order Planning}

\author{\name Martha E. Pollack \email pollack@cs.pitt.edu\\
\addr Department of Computer Science and Intelligent Systems
Program,\\ University of Pittsburgh, Pittsburgh, PA 15260 USA
\AND
\name David Joslin \email joslin@cirl.uoregon.edu\\
\addr Computational Intelligence Research Laboratory,\\
University of Oregon, Eugene, OR   97403 USA
\AND
\name Massimo Paolucci \email paolucci@pitt.edu\\
\addr Intelligent Systems Program,\\
University of Pittsburgh, Pittsburgh, PA   15260 USA}


\maketitle

\begin{abstract} 

Several recent studies have compared the relative efficiency of
alternative flaw selection strategies for partial-order causal link
(POCL) planning.  We review this literature, and present new
experimental results that generalize the earlier work and explain some
of the discrepancies in it.  In particular, we describe the Least-Cost
Flaw Repair (LCFR) strategy developed and analyzed by Joslin and Pollack
\citeyear{JosPol94}, and compare it with other strategies,
including Gerevini and Schubert's \citeyear{GerSchu96} ZLIFO
strategy.  LCFR and ZLIFO make very different, and apparently
conflicting claims about the most effective way to reduce search-space
size in POCL planning.  We resolve this conflict, arguing that much of
the benefit that Gerevini and Schubert ascribe to the LIFO component
of their ZLIFO strategy is better attributed to other causes.  We show
that for many problems, a strategy that combines least-cost flaw
selection with the delay of separable threats will be effective in
reducing search-space size, and will do so without excessive
computational overhead.  Although such a strategy thus provides a good
default, we also show that certain domain characteristics may reduce
its effectiveness.

\end{abstract}

\section{Introduction}
\label{introduction}

Much of the current research in plan generation centers on
partial-order causal link (POCL) algorithms, which descend from
McAllester and Rosenblitt's \citeyear{SNLP} SNLP algorithm.  POCL
planning involves searching through a space of partial plans, where
the successors of a node representing partial plan $P$ are refinements
of $P$.  As with any search problem, POCL planning requires effective
search control strategies.

In POCL planning, search control has two components.  The first, {\em
node selection}, involves choosing which partial plan to refine next.
Once a partial plan has been selected for refinement, the planner must
then perform {\em flaw selection,} which involves choosing either a
threat to resolve or an open condition to establish.

Over the past few years, several studies have compared the relative
efficiency of alternative flaw selection strategies for POCL planning
and their extensions
\cite{PeotSmith93a,JosPol94,SriHow95,GerSchu96,WillHanks96}.
These studies have been motivated at least in part by a tension
between the attractive formal properties of the POCL algorithms, and
the limitations in putting them to practical use that result from
their relatively poor performance.  To date, the POCL algorithms
cannot match the efficiency of the so-called industrial-strength
planners such as SIPE \cite{Wilkins88,WilkDesim94} and O-Plan
\cite{CurrieTate91,OPlan2-94a}.  Flaw selection strategy has been
shown to have a significant effect on the efficiency of POCL planning
algorithms, and thus researchers have viewed the design of improved
flaw selection strategies as one means of making POCL planning
algorithms more practical.

In this paper, we review the literature on flaw selection strategies,
and present new experimental results that generalize the earlier work
and explain some of the discrepancies in it.  In particular, we
describe the Least-Cost Flaw Repair (LCFR) strategy developed and
analyzed by Joslin and Pollack \citeyear{JosPol94}, and compare it with
other strategies, including Gerevini and Schubert's ZLIFO strategy
\citeyear{GerSchu96}.  LCFR and ZLIFO make very different, and apparently
conflicting claims about the most effective way to reduce search-space
size in POCL planning.  We resolve this conflict, arguing that much of
the benefit that Gerevini and Schubert ascribe to the LIFO component
of their ZLIFO strategy is better attributed to other causes.  We show
that for many problems, a strategy that combines least-cost flaw
selection with the delay of separable threats will be effective 
in reducing search-space size, and will do so without excessive
computational overhead.  Although such a strategy thus provides a
good default, we also show that certain domain characteristics may
reduce its effectiveness.

\section{Background}
\label{background}

\subsection{Node and Flaw Selection}

Although the main ideas of POCL planning have been in the literature
for more than two decades, serious efforts at comparing alternative
plan generation algorithms have been relatively recent.  What made
these comparisons possible was the development of a set of clear
algorithms with provable formal properties, notably TWEAK
\cite{Chapman87}, and SNLP \cite{SNLP}.  These algorithms
were not intended to add functionality to known planning methods, but
rather to capture the essential elements of these known methods in a
readily analyzable fashion.

In analyzing POCL algorithms, researchers have found it useful to
decouple the search control strategy from the underlying plan
refinement process.  Figure \ref{pocl-alg} is a generic POCL
algorithm, in which we highlight the two search
decisions.\footnote{Various versions of this well-known algorithm have
appeared in the literature \cite{Weld94,Russell95,KamKnoYang95}.  The
version we give corresponds most directly to that given by Williamson
and Hanks
\citeyear{WillHanks96}.}  Following convention, we use {\bf
CHOOSE} to indicate that node selection is a backtracking point, and
{\bf SELECT} to indicate that flaw selection is not.  A given
node may not lead to a solution, and so it may be necessary to backtrack and
consider alternative nodes.  On the other hand, if a node does lead to
a solution, that solution will be found regardless of the order in
which its flaws are selected.  See Weld's \citeyear{Weld94} tutorial paper
for more discussion of this difference.


\begin{figure}
\begin{tabbing}
abc \= def \= ghi \= jkl \= \kill {\bf POCL} ({\em init,goal})\\ \>
{\em dummy-plan} $\leftarrow$ make-skeletal-plan({\em init,goal}).\\
\> {\em nodes} $\leftarrow$ \{ {\em dummy-plan} \}.\\ \> While {\em
nodes} is not empty do:\\ \> \> {\bf CHOOSE (and remove) a partial plan {\em P}
from {\em nodes}.  (Node Selection)}\\ \> \> If {\em P} has no flaws\\
\> \> \> then return {\em P}\\ \> \> \> else do:\\ \> \> \> \> {\bf
SELECT a flaw from {\em P}.  (Flaw Selection)}\\ \> \> \> \> Add all
refinements of {\em P} to {\em nodes}.\\ \> Return failure (because
{\em nodes} has become empty without a flaw-free plan being found.)\\
\end{tabbing}
\caption{The Basic POCL Planning Algorithm}
\label{pocl-alg}
\end{figure}

The generic algorithm sketched in the figure must be supplemented with
search strategies that implement the {\bf CHOOSE} and {\bf SELECT}
operators.  Most POCL algorithms perform node selection using a
best-first ranking that computes some function of the number of steps
(denoted $S$), open conditions ($OC$), and unsafe conditions ($UC$,
{\em i.e.}, threats) in the partial plan.  Gerevini and Schubert
\citeyear{GerSchu96} have argued that, in general, only steps and
open conditions should be included in the ranking function, and we
adopt that strategy in our experiments, except where otherwise
indicated.

Having chosen a node, a POCL planning algorithm must then select a
flaw---open condition or threat---within that node to repair.  Open
conditions are repaired by {\em establishment}, which consists either
in adding a new step that has a unifying condition as an effect (along
with a causal link from that new step to the condition), or else in
simply adding a new causal link from an existing step with a unifying
effect.  We use the term {\em repair cost} to denote the number
of possible ways to repair a flaw.

For an open condition $o$, the repair cost $R(o)$ is $I + S + N$,
where
\begin{verse}
$I =$ the number of conditions in the initial state that unify with
$o$ given the current binding constraints,\\ $S =$ the number of
conditions in the effects of existing plan steps that unify with $o$
given the current binding constraints, counting only existing plan
steps that are not constrained to occur after the step associated with
$o$, and \\ $N =$ the number of conditions in the effects of operators
in the library that unify with $o$ given the current binding
constraints.\\
\end{verse}
Note that over time, the repair cost for an open condition that is not
resolved may either increase, as new steps that might achieve the
condition are added to the plan, or decrease, as steps already in the
plan are constrained by temporal ordering or variable binding so that
they can no longer achieve the condition.

In considering the cost of threat repair, it is useful to distinguish
between {\em nonseparable} and {\em separable} threats.  Nonseparable
threats consist of a step $S_1$ with effect $E$, and a causal link
$\prec S_2, F, S_3 \succ$, where $E$ and $F$ are complementary
literals that necessarily unify: either they are complementary ground
literals ($E \equiv \neg F$), or else they are complementary literals
where each of $E$'s variables is identical with, or forced by a
binding constraint to be equivalent to the variable in the same
position in $F$ (e.g., $E = p(x,y)$ and $F = \neg p(x,z)$, where there
is currently a binding constraint that $y = z$).\footnote{An
alternative approach also treats cases in which $E \equiv F$ as
threats; this is required to make the planner {\em systematic}, i.e.,
guaranteed never to generate the same node more than once
\cite{SNLP}.}

Nonseparable threats can be repaired in at most two ways: by {\em
promoting} $S_1$, requiring it to occur after $S_3$, or by {\em
demoting} it, requiring it to occur before $S_2$.  Of course, already
existing temporal ordering constraints may block one or both or these
repair options, which is why there are {\em at most} two possible
repairs.\footnote{Conditional planners make use of an additional
method of threat resolution---confrontation---but we ignore that
within this paper \cite{PeotSmith92,Etzioni92}.  Joslin
\citeyear{dj-diss} provides a detailed account of generalizing the
treatment of flaws to other types of planning decisions.}
Over time, the repair cost for an unresolved
nonseparable threat can only decrease.

A separable threat consists of a step $S_1$ with an effect $E$, and a
causal link $\prec S_2, F, S_3 \succ$, where $E$ and $F$ are
complementary literals  that {\em can} be
unified, but where such a unification is
not forced (e.g., where $E=p(x)$ and $F=p(y)$ and there does not
exist a binding constraint $x=y$).
In such circumstances, the threat may
disappear if a subsequent variable binding blocks the unification.
(A nonseparable threat may also disappear if a subsequent ordering
constraint has the effect of imposing promotion or demotion.)  The
repair cost for a separable threat may be higher than that for an
nonseparable threat: not only can promotion and demotion be used, but
so can {\em separation}, which involves forcing a variable binding
that blocks the unification.  Separation can introduce one repair for
each unbound variable in the threat. For example, if the effect
$P(x,y,z)$ threatens $\prec S_2, \neg P(t,u,v), S_3 \succ$, there are
three possible repairs: $x \neq t$, $y \neq u$, and $z \neq v$.  As
with nonseparable threats, the repair cost for a separable threat that
remains unresolved can
only decrease over time.

\subsection{Notation}

The flaw selection strategies that have been discussed in the
literature typically have been given idiosyncratic names (e.g., DUnf,
LCFR, ZLIFO).  It is useful, in comparing them, to have a precise
unifying notation.  We therefore specify a flaw strategy as a
sequence of preferences.  A strategy begins by attempting to find a
flaw that satisfies its first preference; if it is unable
to do so, it then looks for a flaw that satisfies the second
preference; and so on.  To ensure that a POCL algorithm using the
strategy is complete, the sequence of preferences must be exhaustive:
every flaw must satisfy {\em some} preference.  If a flaw satisfies
more than one preference in a strategy, we assume that the first match
is what counts.

In principle, a preference could identify any feature of a flaw.  In
practice, however, flaw selection strategies have only made use of a
small number of features: the type of a flaw (open condition, nonseparable
threat, or separable threat), the number of ways it can be repaired,
and the time at which it was introduced into the plan.  Often, more
than one flaw will have a given feature, in which case a tie-breaking
strategy may be specified for choosing among the relevant flaws.  

We therefore describe a preference using the following notation
\begin{center}
\pref{{\em flaw types}}{{\em repair cost range}}{{\em tie-breaking
strategy}}
\end{center}
which indicates a preference for any flaw $f$ of the specified
type or types, provided that the repair cost for $f$ falls within the
range of values specified.  (If there are no restrictions on repair
cost, we omit the {\em repair cost range}.)
If more than one flaw meets
these criteria, then the tie-breaking strategy is applied to select among
them.  

We abbreviate flaw type as ``o'' (for open condition), ``n'' (for
nonseparable threat), and ``s'' (for separable threat).  We also use
abbreviations for common tie-breaking strategies, e.g., ``LC'' (least
(repair) cost), ``LIFO'' and ``R'' (Random).  In the case of
LC, if a choice
must be made between flaws that have the same repair cost,
LIFO selection is used.

Thus, for example
\begin{center}
\pref{n}{0-1}{R}
\end{center}
specifies a preference for nonseparable threats with a repair cost of zero
or one; if more than one flaw meets these conditions, a
random selection will be made among them.  
We use the term {\em forced} to describe flaws with
repair cost of one or less.  

An example of a 
complete flaw selection strategy is then:
\begin{center}
\pref{n}{0-1}{R}   {\bf /  } \spref{o}{LIFO}   {\bf /  } \spref{n,s}{R}
\end{center}
This strategy would begin by looking for a forced nonseparable threat;
if more than one flaw meets this criterion, the strategy
would select randomly among them.  If
there are no forced nonseparable threats, it would then look for an open
condition, with any repair cost, using a LIFO scheme to select
among them.  Finally, if there are neither forced nonseparable threats
nor open conditions, it would randomly select either an unforced
nonseparable threat or a separable threat.

While we have
distinguished between flaw type and maximum repair cost, on the one
hand, and tie-breaking strategy, on the other, it is easy to
describe strategies that use something other than flaw type as the
main criterion for selection. For
example, a pure LIFO selection strategy would be encoded as follows.
(Henceforth, we give the name of a strategy in boldface preceding
the specification.)
\begin{center}
{\bf LIFO}\hspace*{.25in}\spref{o,n,s}{LIFO}
\end{center}

\section{Flaw Selection Strategies}
\label{lit}

We begin by reviewing the flaw selection strategies that have been
proposed and studied in the literature to date.

\subsection{Threat Preference and Delay}

The original SNLP algorithm \cite{SNLP} adopted a flaw selection
strategy in which threats are resolved before open conditions, and
early versions of the widely used UCPOP planning system \cite{UCPOP}
did the same.\footnote{In the current version of UCPOP
(v.4), the flaw selection strategy that is run by default is the DSep
strategy, discussed just below. For historical reasons, we maintain
the name DSep for that strategy, and use UCPOP for the older default
strategy.} SNLP does not specify a principle for selecting among
multiple threats or multiple opens; UCPOP used LIFO for this purpose.
Employing the notation above, we can describe the basic UCPOP strategy
as:
\begin{center}
{\bf UCPOP}\hspace*{.25in} \spref{n,s}{LIFO} {\bf / } \spref{o}{LIFO}
\end{center}

The first study of alternative flaw selection strategies was done by
Peot and Smith \citeyear{PeotSmith93a}, who relaxed the requirement that
threats always be resolved before open conditions, and examined
several strategies for delaying the resolution of some threats.  They
analyzed five different strategies for delaying the repair of threats;
of these, two are provably superior: DSep and DUnf.

DSep (Delay Separable Threats) was motivated by the observation that
sometimes separable threats can simply disappear in the planning
process as blocking variable bindings are introduced.  As we pointed
out earlier, nonseparable threats may also ``disappear'', but
typically this is less frequent.  Moreover, if the resolution of {\em
all} threats---separable and nonseparable---were delayed, then
nonseparable threats would only disappear early as a side effect of
step reuse, making their disappearance even less frequent.

The DSep strategy therefore defers the repair of all separable threats
until the very end of the planning process.  However, like UCPOP, it
continues to give preference to nonseparable threats:
\begin{center}
{\bf DSep}\hspace*{.25in} \spref{n}{LIFO} {\bf / } \spref{o}{LIFO}
{\bf / } \spref{s}{LIFO}
\end{center}
Actually, Peot and Smith do not specify a tie-breaking strategy for
choosing among multiple threats; we have here indicated this as
LIFO\@.  They explored three different tie-breaking strategies for
selecting open conditions (FIFO, LIFO, and least-cost); here we list
LIFO, but one can also specify the alternatives:
\begin{center}
{\bf DSep-LC}\hspace*{.25in} \spref{n}{LIFO} {\bf / } \spref{o}{LC}
{\bf / } \spref{s}{LIFO}\\
{\bf DSep-FIFO}\hspace*{.25in}\spref{n}{LIFO} {\bf / } \spref{o}{FIFO}
{\bf / }
\spref{s}{LIFO}\\
\end{center}
Peot and Smith prove that the search space generated by a POCL planner
using DSep will never be larger than the search space generated using
the UCPOP strategy.  This result holds when the tie-breaking strategy
for open conditions is LIFO or FIFO, but not LC, a point we will
return to later in the paper.

Peot and Smith's second successful strategy is DUnf (Delay Unforced
Threats).  It makes use of the notion of forced flaws.  As we stated
earlier, a flaw is forced if there is at most one possible way to
repair it.  The DUnf strategy delays the repair of all unforced
threats:
\begin{center}
{\bf DUnf}\hspace*{.25in} \pref{n,s}{0}{LIFO} {\bf / }
\pref{n,s}{1}{LIFO}  {\bf / } \spref{o}{LIFO}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO}
\end{center}
We can define DUnf-LC and DUnf-FIFO in a manner analogous to that used
for DSep-LC and DSep-FIFO:
\begin{center}
{\bf DUnf-LC}\hspace*{.25in} \pref{n,s}{0}{LIFO} {\bf / }
\pref{n,s}{1}{LIFO} {\bf /} \spref{o}{LC}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO}\\
{\bf DUnf-FIFO}\hspace*{.25in} \pref{n,s}{0}{LIFO} {\bf / }
\pref{n,s}{1}{LIFO} {\bf /} \spref{o}{FIFO}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO}
\end{center}

Peot and Smith proved that the DUnf strategy would never generate a
larger search space than either of the remaining two strategies that
they examined.  They also proved that that DSep and
DUnf are incomparable: there exist planning problems for which DSep
generates a smaller search space than DUnf, and other problems for
which the reverse is true.

Peot and Smith support their theoretical results on DSep and DUnf with
experiments showing that, at least for the domains they examined,
these strategies can result in significant decrease in search-space
size.  The decrease in search is correlated with the difficulty of the
problem, and consequently, as the problems get more difficult, these
strategies reduce search time as well as space.  That is, on large
enough problems, they ``pay for'' their own overhead.

In follow-on work, Peot and Smith \citeyear{SmithPeot94a} describe a
strategy called DMin, which generates smaller search spaces than both
DSep and DUnf.  DMin combines a process of pruning dead-end nodes with
the process of flaw selection.  It gives preference to forced threats.
If there are no forced threats, it checks to see whether {\em all} the
remaining nonseparable threats could be repaired simultaneously.  If
so, it leaves them as threats, and selects an open condition to
repair; if there are no open conditions, then presumably it selects a
remaining unforced threat to repair.  On the other hand, if it is
impossible to repair all the unforced, nonseparable threats, then the
node is a dead end, and can be pruned from the search space.  Note
that some dead-end nodes can be recognized immediately, even without
doing the complete consistency checking of DMin.  This is because an
unrepairable flaw cannot subsequently become repairable, hence, any
node containing a flaw with repair cost of zero is a dead end.
Consequently, all flaw selection strategies should give highest
priority to such flaws \cite{JosPol96,dj-diss}.


\subsection{Least-Cost Flaw Repair}
\label{lcfr}

Peot and Smith's work provided the foundation for our subsequent
exploration of the least-cost flaw repair (LCFR) strategy
\cite{JosPol94}. We hypothesized that the power of the DUnf strategy
might come not from its relative ordering of threats and open conditions,
but instead from the fact that DUnf has the effect of imposing a
partial preference for least-cost flaw selection.  DUnf will always
prefer a forced threat, which, by definition has a repair cost of at
most one; thus, in cases in which there is a forced threat, DUnf will
make a low-cost selection.  What about cases in which there are no
forced threats?  Then DUnf will have to select among open conditions,
assuming there are any.  If our hypothesis is correct, a version of
DUnf that makes {\em this} selection using a least-cost strategy
(i.e., DUnf-LC) ought to perform better than a version that uses one
of the other strategies (i.e., bare DUnf or DUnf-FIFO).  In fact, if
it is the selection of low-cost repairs that is causing the
search-space reduction, then the idea of treating threat resolution
differently from open condition establishment ought to be abandoned.
Instead, a strategy that always selects the flaw with minimal repair
cost, regardless of whether it is a threat or an open condition, ought
to show the best performance.  This is the Least-Cost Flaw Repair
(LCFR) strategy:\footnote{The LCFR strategy is similar to the
branch-1/branch-n search heuristics included in the O-Plan system
\cite{CurrieTate91}.  The contribution of our original work on this topic was
to isolate this strategy and examine it in detail.}
\begin{center}
{\bf LCFR}\hspace*{.25in} \spref{o,n,s}{LC}
\end{center}

There are strong similarities between LCFR and certain heuristics that
have been proposed and studied in the literature on constraint
satisfaction problems (CSPs).  This is perhaps not surprising, given
that flaw selection in POCL planning corresponds in some fairly strong
ways to variable selection in constraint programming.  Flaws in a POCL
planner represent decisions that are yet to be made, and that must be
made before the plan will be complete; unbound variables play a
similar role in constraint satisfaction problems (CSPs).\footnote{When
planning problems are cast as CSPs in the planner Descartes
\cite{JosPol96,dj-diss}, this correspondence is even more direct.}
Although there exist a number of heuristics for selecting a variable
to branch on in solving a CSP \cite{Kumar92}, one well-known heuristic
that is often quite effective is the {\em fail first principle}, which
picks the variable that is the ``most constrained'' when selecting a
variable to branch on.  A simple and common implementation of the fail
first principle selects the variable with the smallest domain
\cite{Tsang93}.

The intuition behind the fail first principle is that one should prune
dead-end regions of the search as early as possible.  The unbound
variables that are most tightly constrained are likely to be points at
which the current partial solution is most ``brittle'' in some sense,
and by branching on those variables we hope to find a contradiction
(if one exists) quickly.  Similarly, LCFR can be thought of as
selecting the ``most constrained'' flaws, resulting in better pruning.

A similar heuristic has also been adopted in recent work on
controlling search in hierarchical task network (HTN) planning, in the
Dynamic Variable Commitment Strategy (DVCS).  DVCS, like LCFR, is
based on a minimal-branching heuristic.  Experimental analyses
demonstrate that DVCS generally produces a well-focused search
\cite{Tsuneto96}.

Our own initial experimental results, presented in Joslin and Pollack
\citeyear{JosPol94}, similarly supported the
hypothesis that a uniform least-cost flaw repair strategy could be
highly effective in reducing the size of the search space in POCL
planning.  In those experiments, we compared LCFR against four other
strategies: UCPOP, DUnf, and DUnf-LC, as defined above, and a new
strategy, UCPOP-LC which we previously called LCOS \cite{JosPol94}:
\begin{center}
{\bf UCPOP-LC}\hspace*{.25in} \spref{n,s}{LIFO}   {\bf /  } \spref{o}{LC}
\end{center}
We included UCPOP-LC to help verify that search-space reduction
results from a preference for flaws with minimal repair costs.  If this
is true, then UCPOP-LC ought to generate a smaller search space then
DUnf, even though it does not delay any threats.  Our results were as
expected.  UCPOP and DUnf, which do not do least-cost selection of open
conditions, generated the largest search spaces; UCPOP-LC generated
significantly smaller spaces; and DUnf-LC and LCFR generated the
smallest spaces.

At the same time, we observed that LCFR incurred an unwieldy overhead,
often taking longer to solve a problem than UCPOP, despite the fact
that it was searching far fewer nodes.  In part this was due a
particularly inefficient implementation of LCFR that we were using,
but in part it resulted from the fact that computing repair costs is
bound to take more time than simply popping a stack (as in a LIFO
strategy), or finding a flaw of a particular type (as in a strategy
that prefers threats).  We therefore explored approximation
strategies, which reduce the overhead of flaw selection by accepting
some inaccuracy in the repair cost calculation.  For example, we
developed the ``Quick LCFR'' (or QLCFR) strategy, which calculates the
repair cost of any flaw only once, when that flaw is first
encountered.  In any successor node in which the flaw remains
unresolved, QLCFR assumes that its repair cost has not changed.  Our
experiments with QLCFR showed it to be a promising means of making a
least-cost approach sufficiently fast to pay for its own overhead.
Additional approximation strategies were studied by Srinivasan and
Howe \citeyear{SriHow95}, who experimented with three variations of LCFR,
along with a fourth, novel strategy that moves some of the control
burden to the user.


\subsection{Threat Delays Revisited}

Recently, Gerevini and Schubert \citeyear{GerSchu96} have revived the idea
that a flaw selection strategy should treat open conditions and
threats differently, and have suggested that LIFO should be used as
the tie-breaking strategy for deciding among open conditions.  They
combine these ideas in their ZLIFO strategy:
\begin{center}
{\bf ZLIFO}\hspace*{.25in} \spref{n}{LIFO}   {\bf /  } \pref{o}{0}{LIFO}   {\bf /  }
\pref{o}{1}{New}   {\bf /  } \pref{o}{2-$\infty$}{LIFO}   {\bf /  } \spref{s}{LIFO}
\end{center}
The ZLIFO strategy gives highest priority to nonseparable threats, and
then to forced open conditions.  If there are neither nonseparable
threats nor forced open conditions, ZLIFO will select an open
condition using LIFO\@.  It defers all separable threats to the end of
the planning process.  The name ZLIFO is intended to summarize the
overall strategy.  The ``Z'' stands for ``zero-commitment'',
indicating that preference is given to forced open conditions: in
repairing these, the planner is not making any commitment beyond what
{\em must} be made if the node is ultimately to be refined into a
complete plan.  The ``LIFO'' indicates the strategy used for selecting
among unforced open conditions.

For open conditions with a repair cost of exactly one, the ZLIFO
strategy uses a tie-breaking strategy here called ``New''.  It prefers
the repair of an open condition that can only be established by
introducing a new action over the repair of an open condition that can
only be established by using an element of the start state.  Gerevini
and Schubert state that this preference ``gave improvements in the
context of Russell's tire changing domain \ldots without significant
deterioration of performance in other domains'' \citeyear[p.
104]{GerSchu96}.  However the difference was apparently not dramatic,
and Gerevini believes this to be an implementation detail, though is
open to the possibility that further study might show this preference
to be significant \cite{Gerevini-mail}.

Gerevini and Schubert make three primary claims about ZLIFO:
\begin{enumerate}
\item A POCL planner using ZLIFO will tend to generate a smaller
search space than one using a pure LIFO strategy.
\item The reduction in search space using ZLIFO, relative to LIFO, is
correlated with the complexity of the planning problem (where complexity is
measured by the number of nodes generated by the pure LIFO strategy).
\item ZLIFO performs comparably with LCFR on relatively easy problems,
and generates a smaller search space on harder problems.
\end{enumerate}

The first two claims are consistent with what we found in the earlier
LCFR studies.  While a LIFO strategy pays no attention to repair
costs, ZLIFO does, at least indirectly, both in its initial preference
for nonseparable threats, which have a repair cost of no more than
two, and in its secondary preference for forced opens.

The third claim is harder to square with our earlier LCFR study, in
which the LIFO-based strategies, such as UCPOP and DUnf, generated much
larger search spaces than the least-cost based strategies. 
What explains ZLIFO's performance?  Gerevini and Schubert answer this
question as follows:
\begin{quotation}
Based on experience with search processes
in AI in general, [a LIFO] strategy has much to recommend it, as a
simple default.  In the first place, its overhead cost is low compared
to strategies that use heuristic evaluation or lookahead to prioritize
goals.  As well, it will tend to maintain focus on the achievement of
a particular higher level goal by regression \ldots rather than
attempting to achieve multiple goals in a breadth-first fashion.  [p. 103]
\end{quotation}
Their point about overhead is an important one.  ZLIFO is a relatively
inexpensive control strategy, and a competing strategy that does a
better job of pruning the search space may end up paying excessive
overhead.  But it is the second point that addresses the question we
are asking here, namely, how ZLIFO could produce {\em smaller} search
spaces.  Gerevini and Schubert go on to say that:
\begin{quotation}
[m]aintaining focus on a single goal should be advantageous at least
when some of the goals to be achieved are independent.  For instance,
suppose that two goals G1 and G2 can both be achieved in various ways,
but choosing a particular method of achieving G1 does not rule out any
of the methods of achieving G2.  Then if we maintain focus on G1
until it is solved, before attempting G2, the total cost of solving
both goals will just be the sum of the costs of solving them
independently.  But if we switch back and forth, and solutions of both
goals involve searches that encounter many dead ends, the combined
cost can be much larger.  This is because we will tend to search any
unsolvable subtree of the G1 search tree repeatedly, in combination
with various alternatives in the G2 search tree \ldots. [p. 103]
\end{quotation}
This is certainly a plausible explanation.   A key remaining question, of
course, is the extent to which this explanation carries over to the
many planning problems that involve interacting goals.

\section{Experimental Comparison of Flaw Selection Strategies}
\label{exper}

As discussed in the previous section, several different proposals
have been made in the literature about how best to reduce the size of
the search space during POCL planning.  These include:
\begin{itemize}
\item giving preference to threats over open conditions;
\item giving preference only to certain kinds of threats (either separable or
forced threats), and delaying other threats until after all open
conditions have been resolved;
\item giving preference to flaws that have minimal repair cost;
\item giving preference to the most recently introduced flaws.
\end{itemize}
Moreover, different strategies have combined these preference schemes in
different ways, and apparently conflicting claims have been made
about the effects of these preferences on search-space size.

To resolve these conflicts, we performed experimental
comparisons of POCL planners using a variety of flaw selection
strategies.  We gave particular attention to the comparison of LCFR
and ZLIFO, because of the their apparently conflicting claims.  LCFR
generates its search space treating all flaws uniformly, using a
least-cost approach to choose among them.  ZLIFO distinguishes between
flaw types (non-separable threats, open conditions, and separable
threats), and uses a modified LIFO approach to select among the flaws in each
class.  The original LCFR studies would have led us to predict that
ZLIFO would generate larger search spaces than did LCFR, but Gerevini
and Schubert found just the opposite to be true.  We aimed, then, to
explain this discrepancy.

Our principal focus was on search-space size, for two reasons.  First,
the puzzle raised by LCFR and ZLIFO is one of space, not time.  As we
mentioned earlier, it is easy to see why ZLIFO would be faster than
LCFR, even on a per node basis.  A least-cost strategy must compute
repair costs, while ZLIFO need only pop a stack containing the right
type of flaws.  The puzzle for us was not why ZLIFO was faster, but
why it generated smaller search spaces.  Second, we believe that
understanding the effect of search control strategies on search-space
size can lead to development of approximation techniques that produce
speed-up as well; the QLCFR strategy \cite{JosPol94} and Srinivasan
and Howe's strategies
\citeyear{SriHow95} are examples of this.

However, a secondary goal was to analyze the time requirements of the
strategies we compared, and we therefore collected timing data for all
our experiments.  As we discuss in Section \ref{time}, the strategy
that tends to generate the smallest search space achieves enough of a
reduction to pay for its own overhead, by and large.


\subsection{Experimental Design}

To conduct our comparison, we implemented a set of flaw selection
strategies in UCPOP v.4.\footnote{Note that the experiments in both
our earlier LCFR paper \cite{JosPol94} and Gerevini and Schubert's
\citeyear{GerSchu96} ZLIFO paper were run using an earlier version
(v.2) of UCPOP\@.  As a result, the number of nodes produced in our
experiments sometimes differs from what is reported in these other two
papers.  This appears to be largely due to the fact that UCPOP v.4
puts the elements of a new set of open conditions onto the flaw list
in the reverse order of the way in which UCPOP v.2 does
\cite{Gerevini-mail}.  As discussed below in Sections
\ref{lz}--\ref{domaind}, we studied the influence of this ordering
change by also collecting data using a modified version of UCPOP v.4
in which we reversed the order of conditions entered in the open list.
While the resulting numbers are similar to those previously published,
they are not identical, leading us to conclude that
there are additional subtle differences between v.2 and v.4.
However, because {\em all} the experiments on which we report here
were run using the same version of UCPOP, we believe this to be a fair
comparison of the strategies.} Table
\ref{the-strats} lists the strategies that we implemented.  Except for
LCFR-DSep and DUnf-Gen, which are discussed later, all the implemented
strategies were described in Section \ref{lit}.


\begin{table}
\begin{tabular}{|l|l|}
\hline
UCPOP & \spref{n,s}{LIFO} {\bf / } \spref{o}{LIFO} \\
\hline
UCPOP-LC & \spref{n,s}{LIFO}   {\bf /  } \spref{o}{LC}\\
\hline
DSep & \spref{n}{LIFO} {\bf / } \spref{o}{LIFO} {\bf / }
\spref{s}{LIFO} \\
\hline
DSep-LC & \spref{n}{LIFO} {\bf / } \spref{o}{LC} {\bf /} \spref{s}{LIFO} \\
\hline
DUnf & \pref{n,s}{0}{LIFO} {\bf / } \pref{n,s}{1}{LIFO}  {\bf / }
\spref{o}{LIFO}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO} \\
\hline
DUnf-LC & \pref{n,s}{0}{LIFO} {\bf / } \pref{n,s}{1}{LIFO} {\bf /}
\spref{o}{LC}   {\bf /  } \pref{n,s}{2-$\infty$}{LIFO} \\
\hline
DUnf-Gen &  \pref  {n,s,o}{0}{LIFO} {\bf / } \pref{n,s,o}{1}{LIFO}
{\bf / } \pref{n,s,o}{2-$\infty$}{LIFO}\\
\hline
LCFR & \spref{o,n,s}{LC} \\
\hline
LCFR-DSep & \spref{n,o}{LC} {\bf /} \spref{s} {LC} \\
\hline
ZLIFO & \spref{n}{LIFO}   {\bf /  } \pref{o}{0}{LIFO}   {\bf /  } \pref{o}{1}{New}   {\bf /  } \pref{o}{2-$\infty$}{LIFO}   {\bf /  } \spref{s}{LIFO} \\
\hline
\end{tabular}
\caption{Implemented Flaw Selection Strategies}
\label{the-strats}
\end{table}

We tested all the strategies on three problem sets, also used in our
earlier work
\cite{JosPol94} and in Gerevini and Schubert's \citeyear{GerSchu96}:
\begin{enumerate}
\item {\em The Basic Problems},  33 problems taken from the test suite
distributed with the UCPOP system.  These include problems from a
variety of domains, including the blocks world, the Monkeys and
Bananas problem, Pednault's  \citeyear{Pednault88}
briefcase-and-office problem, Russell's \citeyear{Russell92} tire changing world,
etc.  
\item {\em The Trains Problems}, three problems taken from the TRAINS
transportation domain \cite{Allenetal95}.
\item {\em The Tileworld Problems}, seven problems taken from the
Tileworld domain \cite{AAAI90}.
\end{enumerate}

We ran each strategy on each problem twice.  The first time, we
imposed a node limit, of 10,000 nodes for the basic problems, and of
100,000 nodes for the Trains and Tileworld problems.  The second time,
we imposed a time limit, of 100 seconds for the basic problems, and of
1000 seconds for the Trains and Tileworld problems.  

Gerevini and Schubert experimented with several different node
selection strategies for the Trains and Tileworld domains, so to
facilitate comparison we also used the same node selection strategies
as they did.  For the basic problems, we used $S+OC$.

In reporting our results, we make use not only of raw counts of nodes
generated and computation time in seconds taken, but we also compute
a measure of how badly a strategy performed on a given problem or set
of problems.  We call this measure \%-overrun, and compute it as
follows.  Let $m$ be the minimum node count on a given problem for {\em
any} of the strategies we tested, and let $c$ be the node count for a
particular strategy $S$.  Then 
\begin{center} 
\%-overrun$(S) =[(c-m)/m]*100$ 
\end{center} 
Thus, for example, if the best strategy on
a given problem generated 100 nodes, then a strategy that generated
200 nodes would have a 100
\%-overrun on that problem.  The strategy that does best on a given
problem will have a \%-overrun of 0 on that problem.  In Section
\ref{time}, we make use of similarly computed \%-overruns for
computation time.  

If a strategy hit the node limit, we set $c$ to the relevant node
limit (10,000 or 100,000) to compute its node-count
\%-overrun.\footnote{Because of the way in which UCPOP completes its
basic iteration, it sometimes will go somewhat beyond the specified
node limit before terminating the run.  In such cases, we used the node
limit value, rather than the actual number of nodes generated, in our
computation of \%-overrun.} Similarly, if a strategy hit the time
limit, we used the relevant time limit (100 or 1000) to compute the
computation-time
\%-overrun. 

Online Appendix A provides the raw data---node counts and
computation-time taken---for all the experiments we conducted; it also
includes computed \%-overruns.

In conducting experiments such as these, one has to set either a node-
or time limit cutoff for each strategy/problem pair.  However, there
is always a danger that these cutoffs unfairly bias the data, if the
limits are set in such a way that certain strategies that fail would
instead have succeeded were the limits increased slightly.  We have
carefully analyzed our data to help eliminate the possibility of such a
bias; details are given in Appendix A.



\subsection{The Value of Least-Cost Selection}
\label{lc-value}

Having described our overall experimental design, we now turn to the
analysis of the results.  To begin, we sought to re-establish the
claims we originally made in our earlier work.  Specifically, we wanted
first to reconfirm, using a larger data set, that least-cost flaw
selection is an effective technique for reducing the size of the
search space generated by a POCL planner.  We therefore ran an
experiment in which we compared the the node counts for the five
strategies we had earlier studied---LCFR, DUnf, DUnf-LC, UCPOP, and
UCPOP-LC---plus one new one, DUnf-Gen, explained below.

The results of this experiment are shown in Figures \ref{table1} and
\ref{graph1}.  The former is a log-log scatter plot, showing the
performance of each of the six strategies on the 33 problems in the
basic set.
The problems were sorted by the minimal number of nodes generated on
them by any of the six strategies.
Thus, the left-hand side of
the graph includes the problems that at least one of the six strategies
found to be relatively easy, while the right-hand side has the
problems that were hard for all six strategies.
We omitted problems that none of the six strategies were
able to solve.  The actual number of nodes generated by each strategy
is plotted on the Y-axis, against the minimal number of nodes for that
problem, on the X-axis. LCFR's performance is highlighted with a line
connecting its data points.
This graph shows that, in general, LCFR generates 
small search spaces on this problem set, relative to the other
strategies in this class.  There were only six problems for
which LCFR was not within 10\% of the minimum.  Three of these are in
the Get-Paid/Uget-Paid class of problems---including two of the
``hardest'' problems (UGet-Paid3 and UGet-Paid4).  We discuss this
class of problems more in Section \ref{domaind}.

An alternative view of the data is given in Figure \ref{graph1}, which
shows the aggregate performance of the six strategies, i.e., 
the average of their node-count \%-overrun on the basic problems.  As
can be seen, LCFR has the smallest average \%-overrun.

Figures \ref{table3} and
\ref{graph3} present similar views of the data for the Tileworld
domain, while Figure \ref{table2} gives the data for the Trains problems.
On the Trains domain, these six strategies were only able to solve the
easiest problem (Trains1), so we simply show the actual node counts in
Figure \ref{table2}.   We have omitted two data points,
because they were so extreme that their inclusion on the graph made it
impossible to see the differences among the other strategies:  
LCFR and DUnf-Gen with $S+OC+UC$ node selection took 28,218, and
35,483 nodes, respectively, to solve the problem.

For the Tileworld and Trains problems, we observed the same sorts of
interactions between node and flaw selection strategies as were seen
by Gerevini and Schubert.  Specifically, LCFR performs relatively
poorly with $S+OC$ on the Tileworld problems, and it performs very
poorly with $S+OC+UC$ on the Trains problems.
However, when paired with the other node-selection
strategies, LCFR produces the smallest search spaces of any strategies
in this class.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph1.eps}}
\caption{Basic Problems:  Node Counts for Strategies without
Forced-Flaw Delay}
\label{table1}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph1.eps}}
\caption{Basic Problems:  Aggregate Performance for Strategies without
Forced-Flaw Delay}
\label{graph1}
\end{figure}




\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph3.eps}}
\caption{Tileworld Problems:  Node Counts for Strategies without
Forced-Flaw Delay}
\label{table3}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph3.eps}}
\caption{Tileworld Problems:  Aggregate Performance for Strategies without
Forced-Flaw Delay}
\label{graph3}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{newgraph2.eps}}
\caption{Trains 1:  Node Counts for Strategies without
Forced-Flaw Delay}
\label{table2}
\end{figure}


In sum, LCFR does tend to produce smaller search spaces than the other
strategies in this class.   But a question remains.  LCFR uses a
least-cost strategy, and a side effect of this is that it will prefer
forced flaws, since forced flaws are low-cost flaws.  It is therefore
conceivable that LCFR's performance is mostly or even fully due to its
preference for forced flaws, and not (or not greatly) influenced by
its use of a least-cost strategy for unforced flaws.  This same
hypothesis could explain why DUnf-LC consistently outperforms DUnf,
and why UCPOP-LC consistently outperforms UCPOP\@.

It was to address this issue that we included DUnf-Gen in our
experiment.  DUnf-Gen is a simple strategy that prefers forced flaws
of any kind, and otherwise uses a LIFO regime.  We would expect
DUnf-Gen and LCFR to perform similarly, since they frequently make the
same decision.  Specifically, they will both select the same flaw in
any node in which there is a forced flaw; they will differ when there
are only unforced flaws, with DUnf-Gen selecting a most recently
introduced flaw and LCFR selecting a least-cost flaw.

In practice, DUnf-Gen's performance closely mimicked that of LCFR's.
On the basic problem set it did only marginally worse than LCFR\@.  In
fact, it does marginally {\em better} when we reverse the order in
which the planner adds the preconditions of each new step to the open
list (see Section \ref{valsep}).  LCFR does somewhat better than
DUnf-Gen on both the Trains and Tileworld problems, and this is true
regardless of the order in which the preconditions were added to the
open list, but the extent to which it does better varies.

Thus, the data is inconclusive about the value of using a least-cost
strategy for unforced flaws.  LCFR clearly benefits from selecting
forced flaws early (as a side effect of preferring least-cost flaws),
but it {\em may} not matter whether it continues to use a least-cost
strategy for the unforced flaws.  If indeed it is generally sufficient
to use a least-cost strategy only for forced flaws, then ZLIFO's
performance is somewhat less puzzling, since ZLIFO also prefers forced
flaws.  However the puzzle is not completely resolved.  After all,
DUnf-Gen, like ZLIFO, prefers forced flaws and and then makes
LIFO-based decisions about unforced flaws, and while its performance
is not clearly inferior to LCFR's, neither is it clearly superior.
Even if the use of LIFO for unforced flaws does not obviously increase
the search-space, neither does it appear to decrease it.


\subsection{Comparing LCFR and ZLIFO}
\label{lz}

We next turn to a direct comparison of LCFR and ZLIFO\@.  Gerevini
and Schubert compared these strategies on only a few problems.  To get
a more complete picture of the performance of both LCFR and ZLIFO, we
ran them both on all the problems from our three problem sets.  

The data for the basic problem set is shown in Figure \ref{table4}.
We have sorted the problems by the difference between the node counts
produced by LCFR and ZLIFO\@. Thus, problems near the left-hand side
of the graph are those for which LCFR generated a smaller search
space, while problems near the right-hand side are the ones on which
ZLIFO had a space advantage.  We omit problems which neither strategy
could solve.

As can be seen, on some problems (notably R-Test2, Move-Boxes, and
Monkey-Test2), LCFR generates a much smaller search space than ZLIFO,
while on other problems (notably Get-Paid4, Hanoi, Uget-Paid4, and
Uget-Paid3), ZLIFO generates a much smaller search space.  These are
problems on which LCFR also did worse than the
strategies mentioned above in Section \ref{lc-value}.

As we noted earlier, one of the major changes between UCPOP v.2 and
v.4 is that v.4 puts the elements of a new set of open conditions onto
the flaw list in the reverse order from that of v.2.
This ordering may make a difference, particularly for LIFO-based
strategies.  Indeed, other researchers have suggested that one reason
a LIFO-based strategy may perform well is because it can exploit the
decisions made by the system designers in writing the domain
operators, since it is in some sense natural to list the most
constraining preconditions of an operator first \cite{WillHanks96}.
We therefore also collected data for a modified version of UCPOP, in
which the preconditions for each step are entered onto the open
condition in the reverse of the order in which they would normally be
entered.  We discuss the results of this modification in more detail
in the next two sections, but for now, we simply present the node
counts for LCFR and ZLIFO with the reversed precondition insertion, in
Figure \ref{table5}.  As can be seen, there are a few problems on
which reversing the precondition ordering has a significant effect
(notably FIXB and MonkeyTest2), but by and large LCFR and ZLIFO showed
the same relative performance.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph4.eps}}
\caption{Basic Problems:  Node Counts for LCFR and ZLIFO}
\label{table4}
\end{figure}



\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph5.eps}}
\caption{Basic Problems:  Node Counts for LCFR and ZLIFO with
Reversed Precondition Insertion}
\label{table5}
\end{figure}

For the problems in the basic set, it is difficult to discern an
obvious pattern of performance.  In contrast to what Gerevini and
Schubert suggest, there does not seem to be a clear correlation
between the difficulty of the problem, measured in terms of nodes
generated, and the relative performance of LCFR and ZLIFO\@.  (In
fact, it is a little difficult to determine which strategy's
node-count should serve as the measure of difficulty.)  On the other
hand, it is true that in the aggregate, ZLIFO generates smaller search
spaces than LCFR on the basic problems.  With the default precondition
ordering, ZLIFO obtains an average \%-overrun of 212.62, while LCFR
obtains 647.57.  With reverse ordering, ZLIFO's average \%-overrun is
244.24, while LCFR's is 914.87.  The fact that LCFR's relative
performance is worse when the preconditions are entered in the reverse
direction results primarily from its failure on MonkeyTest2 in the
reverse direction.

The Trains data is scant. 
Neither LCFR nor ZLIFO can solve the hardest problem,
Trains3, regardless of whether the preconditions are entered in the
default or the reverse order.  (In fact, none of the strategies we studied were able to
solve Trains3.)
But, at least when the preconditions are entered in the default order, ZLIFO can solve
Trains2, and LCFR cannot. With reverse precondition insertion, neither
strategy can solve Trains2.
The data are shown in Figure \ref{table7a}.  Note that LCFR's
performance is essentially the same for both node-selection strategies shown.

Finally, the Tileworld data, for the default order of precondition
insertion, is shown in Figure \ref{table8a}.  Here is the only place
in which LCFR clearly generates smaller search spaces than ZLIFO.  We
have not also plotted the data for reverse precondition insertion,
because most of the strategies are not affected by this change.  There
is however, one very notable exception: with reversed insertion, ZLIFO
(with $S+OC+.1UC+F$) does much better---indeed, it does as well as
LCFR\@.  We return to the influence of precondition ordering on the
Tileworld problems in
Section \ref{domaind}.

For now, however, it is enough to observe that our experiments show
that ZLIFO does tend to generate smaller search spaces than LCFR\@.
It does so on the basic problem set, regardless of the order of
precondition insertion, it does so on Trains for one ordering (and
does no worse than LCFR on the other ordering), and it does as well as
LCFR for the Tileworld problems when the preconditions are inserted in
the reverse order.  The only exception is the Tileworld problem set
when the preconditions are inserted in default order: there LCFR does
better.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph6.eps}}
\caption{Trains Problems:  Node Counts for LCFR and ZLIFO}
\label{table7a}
\end{figure}


\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph7.eps}}
\caption{Tileworld Problems:  Node Counts for LCFR and ZLIFO}
\label{table8a}
\end{figure}



\subsection{The Value of Separable-Threat Delay}
\label{valsep}

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 \ref{lc-value} 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 {\em 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 {\em dsep} switch, which when turned on will automatically
delay the repair of all separable threats.  As defined earlier in Table
\ref{the-strats}, the definition of LCFR-DSep is:
\begin{center}
{\bf LCFR-DSep}\hspace*{.25in} \spref{n,o}{LC} {\bf /} \spref{s} {LC} 
\end{center}
Our hypothesis was that if ZLIFO's reduction in search-space size were
largely due to its incorporating a DSep approach, then LCFR-DSep ought
to be ``the best of both worlds'', combining the advantages of LCFR's
least-cost approach with the advantages of a DSep approach.

On the basic problems, LCFR-DSep proved to have the smallest average node-count
\%-overrun of on the basic problems of {\em 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 \ref{graph5} 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.


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph5.eps}}
\caption{Basic Problems:  Aggregate Performance for all Strategies}
\label{graph5}
\end{figure}

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph8.eps}}
\caption{Basic Problems:  Node Counts for LCFR, ZLIFO, and DSep Strategies}
\label{table9}
\end{figure}

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph9.eps}}
\caption{Basic Problems:  Node Counts for all Strategies}
\label{table9a}
\end{figure}

For more detailed comparison, we plot node counts on the basic
problems for LCFR, ZLIFO, and the Separable-Threat Delay strategies in
Figure
\ref{table9}.  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 {\em 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 \ref{table9a}, 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.

\subsection{The Need for Domain Information}
\label{domaind}

The Tileworld and Trains domains problems challenge overly simple
conclusions we might draw from the basic problem sets.  We consider
each set of problems in turn.

\subsubsection{The Tileworld Problems}

The Tileworld domain involves a grid with tiles and holes, and the
goal is to fill each hole with a tile.  This goal can be achieved with
a {\bf fill} operator, which has two preconditions: the agent must be
at the hole, and it must be holding a tile.  In our encoding, an agent
can hold up to four tiles at a time.  The {\bf go} operator is used to
achieve the (sub)goal of being at a hole, while the {\bf pickup}
operator is used to achieve the (sub)goal of holding a tile.  In the
normal way, {\bf go} has a precondition of being at some location,
namely whatever location the agent will move from.  {\bf Pickup} has a
precondition of being at the location of some tile.  The problems in
the Tileworld problem set differ from one another in the number of
holes that the agent must fill: each problem adds another hole.

Figures \ref{graph6} gives the log-log plot for the various strategies
on the Tileworld problems, when the preconditions were entered in the
default order.  Note that LCFR ($S+OC+UC$) is the strategy
highlighted.  Three other strategies were almost indistinguishable
from LCFR ($S+OC+UC$), namely, LCFR ($S+OC+.1UC+F$), DUnf-Gen
($S+OC+UC$) and DUnf-Gen($S+OC+.1UC+F$).  All the other strategies
performed worse.  This can more easily be seen in Figure \ref{graph8},
which gives the aggregate performance for the leading strategies:
those that were able to solve all seven Tileworld problems.  In fact,
these leading
strategies were able to solve the seven Tileworld problems
without generating more than 1800 nodes for any problem.  In contrast,
the remaining strategies failed on at least one, and up to four, of
the seven problems, given the limit of 100,000 nodes generated.

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph10.eps}}
\caption{Tileworld Problems: Node Counts for All Strategies}
\label{graph6}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph6.eps}}
\caption{Tileworld Problems:  Aggregate Performance for Leading 
Strategies}
\label{graph8}
\end{figure}


What was originally surprising to us is that on the Tileworld
problems, delaying separable threats actually seems to hurt
performance.  The strategies that did best were those like LCFR and
DUnf-Gen that do {\em not} delay separable threats.  LCFR-DSep, ZLIFO,
DSep-LC, and DSep all generated larger search spaces, in contrast to
what we would have predicted given the experiments on the basic
problem set.

To understand this result, we looked in detail at the planning trace
for these problems.  What that revealed is that for the Tileworld
domain, the early resolution of separable threats has an important
advantage: it imposes what turns out to be the correct temporal
ordering between the steps of going to up a tile (to pick it up), and
carrying it to a hole.  Virtually all the strategies create subplans
like the one shown in Figure \ref{tw-pp}.   The goals involve filling
holes, so the planners insert steps to go to and pick up a tile, and
to go to the hole.  At this point, there are two separable threats:
(1) the effect of going to the hole, $\neg at(X)$, threatens the link
between going to the tile and picking it up ($at(Z)$), and (2) the
effect of going to the tile, $\neg at(W)$, threatens the link between
going to the hole and filling it ($at(Y)$).  Both threats are
separable, because $X$ and $W$ will be unbound; the planner does not
yet know where it will be traveling from.  But there is only one valid
temporal ordering that will resolve these threats: going to the tile
must precede picking up the tile, which in turn must precede going to
the hole.  Once this temporal ordering is determined, further planning
goes smoothly.

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{twpp.eps}}
\caption{Typical Partial Plan for the Tileworld Domain}
\label{tw-pp}
\end{figure}

In contrast, if this ordering decision is not made, the planner can
often ``get lost'', attempting to find plans in which it goes
from some location to the hole and then from the hole to the tile.
There are many ways to attempt this, because there are many different
tiles to select, and many different locations to move among.  The
planner may try many of these alternatives before determining that
there is a fundamental inconsistency in these plans, and that they are
destined to fail.  The larger the number of holes to be filled, the worse
the situation becomes.

Sometimes the planner may make the right decision about temporal
ordering even if it has deferred separable threats.  When faced with
the partial plan in Figure \ref{tw-pp}, if the planner does not select
a threat, it will select from among several open conditions.  It can
attempt to establish the precondition of going to the hole ($at(X)$)
by reusing the effect of going to the tile ($at(Z)$), or it can do the
reverse, and attempt to establish the precondition of going to the
tile ($at(W)$) by reusing the effect of going to the hole ($at(X)$).
Of course, the first solution is the right one, and includes the
critical temporal ordering constraint, while the second will
eventually fail.

The order in which the open conditions are selected will determine
which of these two choices the planner makes.  When preconditions are
entered in the default order, planners that delay separable threats
end up making the latter, problematic choice.  In contrast, when the
preconditions are entered in the reverse order, the planners make what
turns out to be the correct choice.  Thus, for the experiments in
which we reversed precondition insertion, we see a different pattern
of performance, as shown in Figures
\ref{table11}--\ref{graph9}.\footnote{To preserve readability, in
Figure \ref{graph9},
we have used ``(1)''
to denote $S+OC$, ``(2)'' for $S+OC+UC$, and ``(3)'' for
$S+OC+UC+.1F$.}

\begin{figure}
\epsfxsize=385pt
\centerline{\epsffile{newgraph11.eps}}
\caption{Tileworld Problems:  Node Counts with Reversed Precondition
Insertion}
\label{table11}
\end{figure}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph9.eps}}
\caption{Tileworld Problems:  Aggregate Performance for all Strategies
with Reversed Precondition Insertion}
\label{graph9}
\end{figure}


When the preconditions are entered in the reverse order, a larger
number of strategies perform well, solving all the problems.  In
particular, with $S+OC+.1UC+F$ node-selection, the performance of
LCFR, DUnf-Gen, ZLIFO, and LCFR-DSep is virtually indistinguishable.
It is important to note that the leading strategies that do not delay
separable threats---LCFR and DUnf-Gen---are not affected much by the
reversal of precondition insertion for the Tileworld problems; in
fact, LCFR's performance is identical in both cases.  In contrast, the
strategies that use separable-threat delay---LCFR-DSep, ZLIFO, and
DSep-LC---all perform much better when we reverse precondition
insertion.  This is explained by our analysis above.

In sum, what is most important for the Tileworld domain is for the
planner to recognize, as early as possible, that there are certain
required temporal orderings between some of the steps in any successful
plan.  Every successful plan will involve going to a tile before going
to a hole, although there is flexibility in the order in which
multiple holes are visited, and in the interleaving of picking up
tiles and dropping them in holes.  For the strategies we studied,
there were two different methods that led to this temporal constraint
being added to the plan.  It was added when the planner selected a
separable threat to resolve, and it was added when it selected one
particular precondition to resolve before another.


\subsubsection{The Trains and Get-Paid Problems}

The Trains domain present a somewhat different variation on our
original conclusions.  The Trains domain involves a set of locations
and objects, and the goal is to transport various objects from
specific starting locations to specified destinations.  Gerevini and
Schubert studied three Trains problems.  All of our strategies failed
to successfully complete the hardest of these (Trains3) within either
the 100,000 node or the 1000 second limit.   Moreover, many of them
also failed on the second hardest (Trains2).
Caution must 
therefore be taken in interpreting the results, as there are a limited
number of data points.


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{newgraph12.eps}}
\caption{Trains Problems:  Node Counts}
\label{table12}
\end{figure}

Figure \ref{table12} gives the node counts for the Trains domain, with
preconditions inserted in the default order.  We
only show the strategies that were able to solve both Trains1 and Trains2.
These  results are
closer to what we would have predicted from the basic problem set than
were the results with the Tileworld.  In particular, LCFR-DSep does
very well, generating much smaller search spaces than LCFR\@.
However, it does slightly worse than ZLIFO\@.  Recall that we saw the
same pattern of performance on a subset of the basic problems,
specifically on the Get-Paid/Uget-Paid problems.  There, LCFR-DSep
again improved on LCFR, but did not generate as small search spaces as
ZLIFO\@.  It turns out that there are similar factors influencing both
sets of problems, and it is instructive to consider in some detail the
planning done by ZLIFO and LCFR-DSep for the Get-Paid/Uget-Paid
problems to understand what is occurring.

Like the Trains domain problems, the Get-Paid/Uget-Paid problems
involve moving particular objects to specified locations.  
In the Get-Paid/Uget-Paid domain there are three objects: a paycheck, a
dictionary, and a briefcase.  As generally formulated, in the initial
state all three are at home, and the paycheck is in the briefcase.
The goal is to deposit the paycheck at the bank, bring the dictionary
to work, and have the briefcase at home.  Both the dictionary and the
paycheck can be moved only in the briefcase.  For a human, the
solution to this problem is obvious.  The dictionary must be put into
the briefcase, and it must then be carried to work, where the
dictionary is taken out.  The briefcase must then be carried home.  In
addition, a stop must be made at the bank, either on the way to work
or on the way home, at which point the paycheck must be taken out of
the briefcase and deposited.

ZLIFO and LCFR-DSep take different paths in solving this problem.
ZLIFO begins by forming plans to get the paycheck to the bank and the
dictionary to work.  These goals are selected first because they are
forced: there is only one way to get the paycheck to the bank (carry
it there), and similarly only one way to get the dictionary to the office
(carry it there).  In contrast, there are two possible ways to
get the briefcase home: either by leaving it there (i.e., reusing the
initial state) or by carrying it there from somewhere else (i.e.,
adding a new step).  The LIFO mechanism then proceeds to complete the
plans for achieving the goals of getting the paycheck to the bank and
the dictionary to work, before beginning to work on the remaining
goal, of getting the briefcase home.  At this point, that goal is easy
to solve.   All that is needed is to plan a route home from wherever the
briefcase is at the end of these two errands.

LCFR-DSep, like ZLIFO, begins by selecting the forced goals of getting
the dictionary to the office and getting the paycheck to the bank.
However, instead of next completing the plans for these goals,
LCFR-DSep continues to greedily select least-cost flaws, and thus
begins to work on achieving the goal of getting the briefcase home.
Unfortunately, at this point it is not clear where the briefcase needs
to be moved home {\em from}, and hence LCFR-DSep begins to engage in a
lengthy process of ``guessing'' where the briefcase will be at the end
of the other tasks, before it has planned for those
tasks.\footnote{The difficulty that LCFR-DSep encounters by greedily
picking low-cost flaws might be reduced by doing a lookahead of
several planning steps, to determine a more accurate repair cost.
This is the approach taken in the branch-n mechanism in O-Plan
\cite{CurrieTate91}.  Significant overhead can be involved 
in such a strategy, however.}

The key decision for the Get-Paid/Uget-Paid domain---and, as it turns
out, for the Trains domain---is related to, but subtly different from
the key decision in the Tileworld domain.  For Get-Paid/Uget-Paid and
Trains, the key insight for the planner is again that there is an
important temporal ordering between goals.  The goal of getting the
briefcase home is going to have to be achieved after the goal of
taking the dictionary to work.  However, recognition of this
constraint is not affected by separable-threat delay, as it was for
the Tileworld.  Instead, what happens in these domains is that a
higher-cost flaw interacts with a lower-cost one, causing the latter
to become fully constrained.

It is tempting to think that here finally is a case in which a
LIFO-based strategy is advantageous.  After all, for this example, by
completely determining what you will do to achieve one goal, you make
it much easier to know how to solve the another goal.  But the use of
ZLIFO (or an alternative LIFO-based strategy) does not guarantee that
the interactions between high- and lower-cost flaws will be exploited.
In particular if the interactions are among two or more unforced
flaws, then the order of the goals in the agenda can lead ZLIFO to
make an inefficient choice.  Thus, when we modified the problem so
that the briefcase was at work in the initial state, ZLIFO and
LCFR-DSep both solved the problem very quickly (178 nodes for ZLIFO
and 157 for LCFR-DSep).  Note that this modification removes the
problematic interaction between a low-cost and a high-cost flaw.

Finally, note that the effectiveness of the LIFO strategies is again
heavily dependent on the the order in which preconditions are entered
onto the open list.  Figure \ref{table13} gives the node counts for
the Trains domain with reverse precondition insertion.  We once again 
plot only the strategies that can solve both Trains 1 and 
Trains2.  In this case, there
are only two such strategies:
LCFR-DSep and DSep-LC.
The strategies that rely on
LIFO for open-condition selection, ZLIFO, DSep, DUnf-Gen, and UCPOP,
all do significantly worse than they did when the preconditions were
in the correct order.  To the extent that LIFO helps in such domains,
it appears to be because of its ability to exploit the 
decisions made by the system designers in writing the domain
operators, as suggested by Williamson and Hanks
\citeyear{WillHanks96}. 

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{newgraph13.eps}}
\caption{Trains Problems:  Node Counts with Reversed Precondition
Insertion}
\label{table13}
\end{figure}


\subsection{Computation Time}
\label{time}

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 \ref{graph12} and \ref{graph13} 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.

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph12.eps}}
\caption{Basic Problems: Aggregate Computation Time Performance for Leading Strategies}
\label{graph12}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph13.eps}}
\caption{Basic Problems:  Aggregate Computation Time Performance}
\label{graph13}
\end{figure}

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 \ref{graph14}--\ref{graph17} provide the timing data for the
Trains and Tileworld domains.\footnote{We have omitted the strategies
that did very poorly, performing worse {\em
both} on the node- and time-limit experiments than did any of the
strategies graphed. Note that we ran the reverse-order
experiments only with a node limit.} 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.\footnote{In interpreting the Trains timing data, it
is important to note that some of the strategies shown---notably UCPOP,
UCPOP-LC, and Dunf, failed to solve Trains2 within either the node or
the time limit.}

\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph14.eps}}
\caption{Tileworld Problems:  Aggregate Computation Time Performance
for Leading Strategies}
\label{graph14}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph15.eps}}
\caption{Tileworld Problems:  Aggregate Computation Time Performance
for Leading Strategies with Reversed Precondition Insertion}
\label{graph15}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph16.eps}}
\caption{Trains Problems:  Aggregate Computation Time Performance for
Leading Strategies}
\label{graph16}
\end{figure}


\begin{figure}
\epsfxsize=330pt
\centerline{\epsffile{graph17.eps}}
\caption{Trains Problems:  Aggregate Computation Time Performance for
Leading Strategies with Reversed Precondition Insertion}
\label{graph17}
\end{figure}


\section{Conclusion}

In this paper, we have synthesized much of the previous work on flaw
selection for partial-order causal link planning, showing how earlier
studies relate to one another, and have developed a
concise notation for describing alternative flaw selection strategies.

We also presented the results of a series of experiments aimed at
clarifying the effects of alternative search-control preferences on
search-space size.  In particular, we aimed at explaining the
comparative performance of the LCFR and ZLIFO strategies.  We showed
that neither of these flaw selection strategies consistently generates
smaller search spaces, but that by combining LCFR's least-cost
approach with the delay of separable threats that is included in the
ZLIFO strategy, we obtain a strategy---LCFR-DSep---whose space
performance was nearly always as good as the better of LCFR or ZLIFO
on a given problem.  We therefore concluded that much of ZLIFO's
advantage relative to LCFR is due to its delay of separable threats
rather than to its use of a LIFO strategy.  Although we were unable to
resolve the question of whether least-cost selection is required for
unforced, as well as forced flaws, we found no evidence that a LIFO
strategy for unforced flaws was better.  On the other hand,
separable-threat delay is clearly advantageous.  An open question is
exactly why it is so advantageous.  We have conducted preliminary
experiments that suggest that much of the search-space reduction that
results from delaying separable threats can also be achieved by making
separation systematic, something that UCPOP v.4 does not do.  

We also considered the question of computation time, and showed that
often LCFR-DSep only requires computation time comparable to that of
ZLIFO\@.  LCFR-DSep can therefore be seen as paying for its own
computational overhead by its search-space reduction.  Moreover, Peot
and Smith's DSep-LC provides a good approximation of LCFR-DSep:
although it produces somewhat larger search spaces, it does so more
quickly.

These conclusions, however, are tempered by the fact that for certain
clusters of problems, our combined strategy, LCFR-DSep, does not
generate minimal search spaces.  As we saw, for the Tileworld
problems, what is most important is to recognize the need for a
particular temporal ordering among plan steps, and this recognition
can be obtained by resolving separable threats early.  For the Trains
and Get-Paid/Uget-Paid domains, what matters most is recognizing that a
particular effect can in fact only be achieved in one way, and this is
only recognized when a particular flaw is selected---a flaw which
happens generally not to be the least cost flaw available.  The lesson
to be learned from these sets of problems is that although we now
understand the reasons that LCFR and ZLIFO perform the way they do,
and how to combine the best features of both to create good default
strategies for POCL planning, it is clear that domain-dependent
characteristics such as those we identified in the Trains and
Tileworld domains must still be taken into account in settling on a
flaw selection strategy for any domain.


\section*{Acknowledgments}

Martha Pollack's work on this project has been supported by the Air
Force Office of Scientific Research (F49620-96-1-0403) and an NSF
Young Investigator's Award (IRI-9258392).  David Joslin has been
supported by Rome Labs (RL)ARPA (F30602-95-1-0023) and an NSF CISE
Postdoctoral Research award (CDA-9625755).  Massimo Paolucci has been
supported by the Office of Naval Research, Cognitive and Neural
Sciences Division (N00014-91-J-1694).

We are very grateful to Alfonso Gerevini for providing us with the
code he used in his earlier study, and allowing us to use it in our
experiments.  We would also like to thank Arthur Nunes and Yazmine
DeLeon, who assisted us in carrying out experiments done in the
preliminary stages of this work.  Finally, we thank Alfonso Gerevini,
Len Schubert, Michael Wellman, and the anonymous reviewers for their
helpful comments on this work.


\section*{Appendix A:  Ruling Out Ceiling Effects}
\label{ceiling}

For the data collected using a node limit, we examined all the
problems in which at least one of the strategies hit the node
limit.
Table \ref{table14} gives the {\em second worst} node count for
all such problems.  It shows that, for all the basic problems in which at
least one strategy failed, and at least one other succeeded, the 
second-worst strategy generally created fewer than 7000 nodes.

Similarly, for the Trains
and Tileworld problems, in all such cases except TW3, the second-worst
strategy took fewer than 50,000 nodes (and in TW3 it took 89,790).
Recall that the node limit for the basic problems was 10,000 nodes,
while for the Trains and Tileworld problems it was 100,000 nodes.  It
is thus clear that the strategies that hit the node limit are doing
substantially worse than the strategies that succeed.  Even if they
were to succeed by increasing the node limit slightly, their
comparative performance would still be poor.  

Thus, by using the node limits we imposed, we are not making any
strategies look worse than they actually are.  On the other hand, in
computing \%-overrun, we may be making some strategies look better
than they actually are, because we use a value of 10,000 (or 100,000)
nodes generated when a strategy hits the limit, and the actual number
of nodes it might take, if run to completion, could be significantly
higher.  This is why, in our analyses, we considered both the absolute
performance of strategies on individual problems, and their aggregate
performance, as measured by average \%-overrun.

\begin{figure}
\epsfxsize=280pt
\centerline{\epsffile{table14.eps}}
\caption{Second-Worst Node Counts on Problems with Failing Strategies}
\label{table14}
\end{figure}

We also compared the experiments that were run with a time limit and
those that were run with a node limit.  For the basic problem set, the
time limit of 100 seconds was high enough that, in most cases,
strategies could compute significantly more nodes than they could with
the node cutoff.  Nonetheless, the results were almost identical.  In
nearly all cases, if a strategy failed with the node cutoff, it also
failed with the time limit cutoff.  There were only four
exceptions to this: \begin{enumerate} 
\item Hanoi:  With the 10,000 nodes limit, DSep fails, while with the
100 second time limit, it succeeds, taking 46,946 nodes.
\item Uget-Paid3: With the
10,000 node limit, UCPOP-LC fails, while with the 100 second time
limit, it succeeds, taking 37,951 nodes.  \item Uget-Paid4: With the
10,000 node limit, UCPOP-LC fails, while with 100 second time limit,
it succeeds, taking 23,885 nodes.  \item Fixit: With the 10,000 nodes
limit, DSep-LC, UCPOP-LC, and ZLIFO fail, while with the 100 second
time limit, they succeed in 12,732, 13,510, and 20,301 nodes
respectively.  All the other strategies fail to solve this problem
under either limit.  \end{enumerate}

There was a similarly strong correspondence between the results we
obtained on the Trains and Tileworld problems using a node limit and a
time limit.  In a few cases, a strategy that was able to succeed
within the 100,000 node limit was {\em not} able to succeed within the
1,000 second time limit.   The nature of these problems is that the
computation time per node can be very great.  Specifically,
\begin{enumerate} 

\item On TW3, DUnf succeeded in 56,296 nodes when
run with a node limit, but failed with the 1,000 second time limit.
\item On TW4, LCFR-DSep (with an S+OC node-selection strategy)
succeeded in 69,843 nodes, but failed on the time limit.  \item On
TW5, LCFR-DSep (with an S+OC+UC node-selection strategy) succeeded in
49,024, but failed on the limit.  \item On TW6, LCFR (with an S+OC
node-selection strategy) succeeded in 4,506 nodes, but failed with the
time limit.  \end{enumerate} In only one case did a strategy fail
under the node limit but succeed within the time limit:
\begin{enumerate} \item On
TW3, DSep (with an S+OC node-selection strategy) failed with a 100,000
node limit, but succeeded with 134,951 nodes using a 100 second time
limit.  Note that this is significantly worse than the second worst
strategy, which solved this problem generating 89,790 nodes.  
\end{enumerate}

Given this close correspondence between the experiments with node and
time limits, we collected only node-limit data for the experiments in
which we reversed the precondition insertion.

\newpage

\bibliography{complete}
\bibliographystyle{theapa}  




\end{document}


