\documentstyle[jair,twoside,11pt,theapa]{article}
\input epsf 
\input psfig



\jairheading{2}{1994}{227-262}{10/94}{12/94}
\ShortHeadings{Total-Order and Partial-Order Planning}
{Minton, Bresina, \& Drummond}
\firstpageno{227}
\begin{document}

\newcommand{\TO}{{\sc to}}
\newcommand{\UA}{{\sc ua}}
\newcommand{\UAC}{{\sc ua-c}}
\newcommand{\TOC}{{\sc to-c}}


\title{Total-Order and Partial-Order Planning: \\
A Comparative Analysis}
\author{\name Steven Minton \email minton@ptolemy.arc.nasa.gov \\
       \name John Bresina \email bresina@ptolemy.arc.nasa.gov \\
       \name Mark Drummond \email med@ptolemy.arc.nasa.gov \\
       \addr Recom Technologies \\
       \addr NASA Ames Research Center, Mail Stop: 269-2\\
       Moffett Field, CA  94035 USA}

\maketitle


\begin{abstract}
For many years, the intuitions underlying partial-order planning
were largely taken for granted. Only in the past few years has there
been renewed interest in the fundamental principles underlying this
paradigm.  In this paper, we present a rigorous comparative analysis
of partial-order and total-order planning by focusing on two
specific planners that can be directly compared. We show that there
are some subtle assumptions that underly the wide-spread intuitions
regarding the supposed efficiency of partial-order planning. For
instance, the superiority of partial-order planning can depend
critically upon the search strategy and the structure of the search
space.  Understanding the underlying assumptions is crucial for
constructing efficient planners.
\end{abstract}

\section{Introduction}


For many years, the superiority of partial-order planners over
total-order planners has been tacitly assumed by the planning
community.  Originally, partial-order planning was introduced by
Sacerdoti \citeyear{sacerdoti} as a way to improve planning efficiency by
avoiding ``premature commitments to a particular order for achieving
subgoals''. The utility of partial-order planning was demonstrated
anecdotally by showing how such a planner could efficiently solve
blocksworld examples, such as the well-known ``Sussman anomaly''.

Since partial-order planning intuitively seems like a good idea,
little attention has been devoted to analyzing its utility, at least
until recently \cite{ijcai91,barrett-weld-AIJ,rao-kr94}.
However, if one looks closely at the issues involved, a number of
questions arise.  For example, do the advantages of partial-order
planning hold regardless of the search strategy used?  Do the
advantages hold when the planning language is so expressive that
reasoning about partially ordered plans is intractable (e.g., if
the language allows conditional effects)?

Our work \shortcite{ijcai91,kr92} has shown that the situation is much more
interesting than might be expected. We have found that there are some
``unstated assumptions'' underlying the supposed efficiency of
partial-order planning. For instance, the superiority of partial-order
planning {\em can} depend critically upon the search strategy and
search heuristics employed.

This paper summarizes our observations regarding partial-order and
total-order planning. We begin by considering a simple total-order
planner and a closely related partial-order planner and establishing a
mapping between their search spaces. We then examine the relative
sizes of their search spaces, demonstrating that the partial-order
planner has a fundamental advantage because the size of its search
space is always less than or equal to that of the total-order planner.
However, this advantage does not necessarily translate into an
efficiency gain; this depends on the type of search strategy used.
For example, we describe a domain where our partial order planner is
more efficient than our total order planner when depth-first search is
used, but the efficiency gain is lost when an iterative sampling
strategy is used.

We also show that partial-order planners can have a second,
independent advantage when certain types of operator ordering
heuristics are employed. This ``heuristic advantage'' underlies
Sacerdoti's anecdotal examples explaining why least-commitment works.
However, in our blocksworld experiments, this second advantage is
relatively unimportant compared to the advantage derived from the
reduction in search space size.

Finally, we look at how our results extend to partial-order planners
in general.  We describe how the advantages of partial-order planning
can be preserved even if highly expressive languages are used. We also show
that the advantages do not {\em necessarily} hold for all
partial-order planners, but depend critically on the construction of
the planning space.

\section{Background}

Planning can be characterized as search through a space of possible
plans.  A {\em total-order planner} searches through a space of
totally ordered plans; a {\em partial-order planner} is defined
analogously.  We use these terms, rather than the terms ``linear'' and
``nonlinear'', because the latter are overloaded.  For example, some
authors have used the term ``nonlinear'' when focusing on the issue of
{\em goal ordering}.  That is, some ``linear'' planners, when solving
a conjunctive goal, require that all subgoals of one conjunct be
achieved before subgoals of the others; hence, planners that can
arbitrarily interleave subgoals are often called ``nonlinear''.  This
version of the linear/nonlinear distinction is different than the
partial-order/total-order distinction investigated here.  The former
distinction impacts planner completeness, whereas the
total-order/partial-order distinction is orthogonal to this issue
\cite{med-ijcai89,ijcai91}.

The total-order/partial-order distinction should also be kept separate
from the distinction between ``world-based planners'' and ``plan-based
planners''. The distinction is one of modeling: in a world-based
planner, each search state corresponds to a state of the world and in
a plan-based planner, each search state corresponds to a plan.  While
total-order planners are commonly associated with world-based
planners, such as {\sc Strips}, several well-known total-order
planners have been plan-based, such as Waldinger's regression planner
\cite{wally}, Interplan \cite{interplan} and Warplan
\cite{warplan}.  Similarly, partial-order planners are commonly
plan-based, but it is possible to have a world-based partial-order
planner \cite{godefroid}.  In this paper, we focus solely on the
total-order/partial-order distinction in order to avoid complicating
the analysis.

We claim that the only significant difference between partial-order
and total-order planners is planning efficiency.  It might be argued
that partial-order planning is preferable because a partially ordered
plan can be more flexibly executed.  However, execution flexibility
can also be achieved with a total-order planner and a post-processing
step that removes unnecessary orderings from the totally ordered
solution plan to yield a partial order
\cite{backstrom,veloso-90,Fade-Regnier}.  The polynomial time
complexity of this post-processing is negligible compared to the
search time for plan generation.\footnote{Backstrom \citeyear{backstrom}
  formalizes the problem of removing unnecessary orderings in order to
  produce a ``least-constrained'' plan. He shows that the problem is
  polynomial if one defines a least-constrained plan as a plan in
  which no orderings can be removed without impacting the correctness
  of the plan. Backstrom also shows that the problem of finding a plan
  with the fewest orderings over a given operator set is a much harder
  problem; it is NP-hard.} Hence, we believe that execution
flexibility is, at best, a weak justification for the supposed
superiority of partial-order planning.

In the following sections, we analyze the relative efficiency of
partial-order and total-order planning by considering a total-order
planner and a partial-order planner that can be directly compared.
Elucidating the key differences between these planning algorithms
reveals some important principles that are of general relevance.

\section{Terminology}
\label{terminology}

A plan consists of an ordered set of {\em steps}, where each step is a
unique operator instance.  Plans can be {\em totally ordered}, in
which case every step is ordered with respect to every other step, or
{\em partially ordered}, in which case steps can be unordered with
respect to each other.  We assume that a library of operators is
available, where each operator has preconditions, deleted conditions,
and added conditions.  All of these conditions must be nonnegated
propositions, and we adopt the common convention that each deleted
condition is a precondition.  Later in this paper we show how our
results can be extended to more expressive languages, but this simple
language is sufficient to establish the essence of our argument.

A {\em linearization} of a partially ordered plan is a total order
over the plan's steps that is consistent with the existing partial
order.  In a totally ordered plan, a precondition of a plan step is
{\em true} if it is added by an earlier step and not deleted by an
intervening step. In a partially ordered plan, a step's precondition
is {\em possibly true} if there exists a linearization in which it is
true, and a step's precondition is {\em necessarily true} if it is
true in {\em all} linearizations.  A step's precondition is {\em
necessarily false} if it is not possibly true.

A {\em state} consists of a set of propositions.  A {\em planning
problem} is defined by an {\em initial state} and a set of {\em
goals}, where each goal is a proposition.  For convenience, we
represent a problem as a two-step {\em initial plan}, where the
propositions that are true in the initial state are added by the first
step, and the goal propositions are the preconditions of the final
step.  The planning process starts with this initial plan and searches
through a space of possible plans.  A successful search terminates
with a {\em solution} plan, i.e., a plan in which all steps'
preconditions are necessarily true.  The search space can be
characterized as a tree, where each node corresponds to a plan and
each arc corresponds to a plan transformation.  Each transformation
incrementally extends (i.e., refines) a plan by adding
additional steps or orderings.  Thus, each leaf in the search tree
corresponds either to a solution plan or a dead-end, and each
intermediate node corresponds to an unfinished plan which can be
further extended.

\newpage
\section{A Tale of Two Planners}

\begin{figure}
%\rule{\textwidth}{0.1mm}
\begin{footnotesize}
TO$(P,G)$
\begin{enumerate}
\item {\bf Termination check:}
     If $G$ is empty, report success and return solution plan P.
\item {\bf Goal selection:} Let $c \; = \;$ select-goal($G$), and
     let $O_{need}$ be the plan step for which $c$ is a precondition.
\item {\bf Operator selection:}
     Let $O_{add}$ be an operator in the library that adds $c$. 
     If there is no such $O_{add}$, then terminate and report failure. 
     {\em Choice point: all such operators must be considered for
completeness.}
\item {\bf Ordering selection:}
     Let $O_{del}$ be the last deleter of $c$. 
     Insert $O_{add}$ somewhere between $O_{del}$ and $O_{need}$,
     call the resulting plan $P'$.
     {\em Choice point: all such positions must be considered for
completeness.}
\item {\bf Goal updating:}
     Let $G'$ be the set of preconditions in $P'$ that are not true.
\item {\bf Recursive invocation:} TO$(P',G')$.
\end{enumerate}
\caption{The {\sc to} planning algorithm}
\label{to-alg}
\end{footnotesize}
\end{figure}

\begin{figure}
\begin{center}
\
\setlength{\epsfxsize}{5.3in}
\epsfbox{to-illus.ps} 
\end{center}
\caption{How \TO\ extends a plan: Adding $O_{add}$ to plan $P$
generates three alternatives.  }
\label{to-example}
\end{figure}


In this section we define two simple planning algorithms.  
The first algorithm, shown in Figure~\ref{to-alg}, is {\sc to}, a total-order
planner motivated by Waldinger's regression planner \cite{wally},
Interplan \cite{interplan}, and Warplan \cite{wally}.
Our purpose here is to characterize the search space of the {\sc to}
planning algorithm, and the pseudo-code in Figure~\ref{to-alg}
accomplishes this by defining a nondeterministic procedure that
enumerates possible plans.  (If the plans are enumerated by a
breadth-first search, then the algorithms presented in this section
are provably complete, as shown in Appendix \ref{proofs-section}.)

{\sc to} accepts an unfinished plan, $P$, and a goal set, $G$,
containing preconditions which are currently not true.  If the
algorithm terminates successfully then it returns a totally ordered
solution plan.  Note that there are two choice points in this
procedure: operator selection and ordering selection.  The procedure
does not need to consider alternative goal choices.  For our purposes,
the function {\tt select-goal} can be any deterministic function that
selects a member of $G$.

As used in Step 4, the {\em last deleter} of a precondition $c$ for a
step $O_{need}$ is defined as follows. Step $O_{del}$ is the last
deleter of $c$ if $O_{del}$ deletes $c$, $O_{del}$ is before
$O_{need}$, and there is no other deleter of $c$ between $O_{del}$ and
$O_{need}$.  In the case that no step before $O_{need}$ deletes~$c$,
the first step is considered to be the last deleter.

Figure~\ref{to-example} illustrates \TO's plan extension process.
This example assumes that steps $A$ and $B$ do not add or delete 
$c$. There are three possible insertion points for $O_{add}$ in plan $P$,
each yielding an alternative extension.


\begin{figure}[p]
\begin{footnotesize}
UA$(P,G)$
\begin{enumerate}
\item {\bf Termination check:}
     If $G$ is empty, report success and return solution plan P.
\item {\bf Goal selection:} Let $c \; = \;$ select-goal($G$), and
     let $O_{need}$ be the plan step for which $c$ is a precondition.
\item {\bf Operator selection:}
     Let $O_{add}$ be an operator in the library that adds $c$. 
     If there is no such $O_{add}$, then terminate and report failure. 
     {\em Choice point: all such operators must be considered for
completeness.}
\item {\bf Ordering selection:}
     Let $O_{del}$ be the last deleter of $c$. 
     Order $O_{add}$ after $O_{del}$ and before $O_{need}$. 
     Repeat until there are no interactions: \\
    \hspace*{0.25in} $\circ$ Select a step $O_{int}$ that
interacts with $O_{add}$. \\ 
   \hspace*{0.25in} $\circ$ Order $O_{int}$ either 
before or after $O_{add}$.\\
 \hspace*{0.29in} {\em Choice point: both orderings must be 
considered for completeness}. \\
     Let $P'$ be the resulting plan.
\item {\bf Goal updating:}
     Let $G'$ be the set of preconditions in $P'$ that are necessarily false.
\item {\bf Recursive invocation:} UA$(P',G')$.
\end{enumerate}
\caption{The {\sc ua} planning algorithm}
\label{ua}
\end{footnotesize}
\end{figure}



\begin{figure}[p]
\begin{center}
\
\setlength{\epsfxsize}{5.3in}
\epsfbox{ua-illus.ps} 
\end{center}
\caption{How \UA\ extends a plan: Adding $O_{add}$ to plan $P$
generates two alternatives.  The example assumes 
that $O_{add}$
interacts with step $A$.}
\label{ua-example}
\end{figure}





The second planner is {\sc ua}, a partial-order planner, shown in
Figure~\ref{ua}.  {\sc ua} is similar to {\sc to} in that it uses the
same procedures for goal selection and operator selection; however,
the procedure for ordering selection is different.  Step 4 of {\sc ua}
inserts orderings, but only ``interacting'' steps are ordered.
Specifically, we say that two steps {\em interact} if they are
unordered with respect to each other and either:
\begin{itemize}
\item one step has a precondition that is added or deleted by the
  other step, or
\item one step adds a condition that is deleted by the other step.
\end{itemize}
The only significant difference between {\sc ua} and {\sc to} lies in
Step 4: {\sc to} orders the new step with respect to {\em all} others,
whereas {\sc ua} adds orderings only to eliminate interactions.  It is
in this sense that {\sc ua} is {\em less committed} than {\sc to}.

Figure~\ref{ua-example} illustrates \UA's plan extension process.  As
in Figure~\ref{to-example}, we assume that steps $A$ and $B$ do not
add or delete $c$; however, step $A$ and $O_{add}$ interact with
respect to some other condition.  This interaction yields two
alternative plan extensions: one in which $O_{add}$ is ordered before
$A$ and one in which $O_{add}$ is ordered after $A$.



Since {\sc ua} orders all steps which interact, the plans that are
generated have a special property: each precondition in a plan is
either {\em necessarily} true or {\em necessarily} false.  We call
such plans {\em unambiguous}.  This property yields a tight
correspondence between the two planners' search spaces.  Suppose {\sc
  ua} is given the unambiguous plan $U$ and {\sc to} is given the plan
$T$, where $T$ is a linearization of $U$.  Let us consider the
relationship between the way that {\sc ua} extends $U$ and {\sc to}
extends $T$.  Note that the two planners will have the same set of
goals since, by definition, each goal in $U$ is a precondition that is
necessarily false, and a precondition is necessarily false if and only
if it is false in every linearization.  Since the two plans have the
same set of goals and since both planners use the same goal selection
method, both algorithms pick the same goal; therefore, $O_{need}$ is
the same for both.  Similarly, both algorithms consider the same
library operators to achieve this goal. Since $T$ is a linearization
of $U$, and $O_{need}$ is the same in both plans, both algorithms find
the same last deleter as well.\footnote{There is a unique last deleter
  in $U$.  This follows from our requirement that for any operator in
  our language, the deleted conditions must be a subset of the
  preconditions.  If two unordered steps delete the same condition,
  then that condition must also be a precondition of both operators.
  Hence, the two steps interact and will be ordered by \UA.} When {\sc
  to} adds a step to a plan, it orders the new step with respect to
all existing steps.  When {\sc ua} adds a step to a plan, it orders
the new step {\em only} with respect to interacting steps.  {\sc ua}
considers all possible combinations of orderings which eliminate
interactions; hence, for any plan produced by {\sc to}, {\sc ua}
produces a corresponding plan that is less-ordered or equivalent.

The following sections exploit this tight correspondence between the
search spaces of {\sc ua} and {\sc to}.  In the next section we
analyze the relative sizes of the two planners' search spaces, and
later we compare the number of plans actually generated under
different search strategies.

\section{Search Space Comparison}
\label{space-section}

The search space for both {\sc to} and {\sc ua} can be characterized
as a tree of plans. The root node in the tree corresponds to the
top-level invocation of the algorithm, and the remaining nodes each
correspond to a recursive invocation of the algorithm.  Note that in
generating a plan, the algorithms make both operator and ordering
choices, and each different set of choices corresponds to a single
branch in the search tree.

We denote the search tree for {\sc to} by $tree_{_{TO}}$ and,
similarly, the search tree for {\sc ua} by $tree_{_{UA}}$. The number
of plans in a search tree is equal to the number of times the planning
procedure ({\sc ua} or {\sc to}) would be invoked in an exhaustive
exploration of the search space.  Note that every plan in
$tree_{_{UA}}$ and $tree_{_{TO}}$ is unique, since each step in a plan
is given a unique label. Thus, although two plans in the same tree
might both be instances of a particular operator sequence, such as $O1
\prec O2 \prec O3$, the plans are distinct because their steps have
different labels. (We have defined our plans this way to make our
proofs more concise.)

We can show that for any given problem, $tree_{_{TO}}$ is at least as large
as $tree_{_{UA}}$, that is, the number of plans in $tree_{_{TO}}$ is greater
than or equal to the number of plans in $tree_{_{UA}}$.  This is done by
proving the existence of a function $\cal L$ which maps plans in
$tree_{_{UA}}$ into sets of plans in $tree_{_{TO}}$ that satisfies the
following two conditions.

\begin{enumerate}
\item {\bf Totality Property}:
For 
every plan $U$ in $tree_{_{UA}}$, there exists a non-empty set $\{ T_1,
\ldots, T_m \}$ of plans in $tree_{_{TO}}$ such that ${\cal L} (U) = \{
T_1, \ldots, T_m\}$.

\item  {\bf Disjointness Property}:
${\cal L}$ maps distinct plans in $tree_{_{UA}}$ to disjoint sets of
plans in $tree_{_{TO}}$; that is, if $U_1, U_2 \in tree_{_{UA}}$ and $U_1
\neq U_2$, then ${\cal L} (U_1) \cap {\cal L} (U_2) = \{ \}$.
\end{enumerate}

Let us examine why the existence of an $\cal L$ with these two
properties is sufficient to prove that the size of {\sc ua}'s search
tree is no greater than that of {\sc to}.  Figure~\ref{proof-fig}
provides a guide for the following discussion.  Intuitively, we can
use $\cal L$ to count plans in the two search trees.  For each plan
counted in $tree_{_{UA}}$, we use $\cal L$ to count a non-empty set of
plans in $tree_{_{TO}}$.  The totality property means that every time
we count a plan in $tree_{_{UA}}$, we count at least one plan in
$tree_{_{TO}}$; this implies that $\mid tree_{_{UA}} \mid \; \; \leq
\; \; \sum_{U \in tree_{_{UA}}} \mid {\cal L} (U) \mid$.  Of course,
we must further show that each plan counted in $tree_{_{TO}}$ is
counted only once; this is guaranteed by the disjointness property,
which implies that $\sum_{U \in tree_{_{UA}}} \mid {\cal L} (U) \mid
\; \; \leq \; \; \mid tree_{_{TO}} \mid$.  Thus, the conjunction of
the two properties implies that $\mid tree_{_{UA}} \mid \; \; \leq \;
\; \mid tree_{_{TO}} \mid$.

We can define a function $\cal L$ that has these two properties as
follows.  Let $U$ be a plan in $tree_{_{UA}}$, let $T$ be a plan in
$tree_{_{TO}}$, and let $parent$ be a function from a plan to its
parent plan in the tree.  Then $T \in {\cal L} (U)$ if and only if
({\em i}) $T$ is a linearization of $U$ and ({\em ii}) either $U$ and
$T$ are both root nodes of their respective search trees or $parent(T)
\in {\cal L} (parent(U))$.  Intuitively, $\cal L$ maps a plan $U$ in
$tree_{_{UA}}$ to all linearizations which share common derivation
ancestry.\footnote{The reader may question why $\cal L$ maps $U$ to
  all its linearizations in $tree_{_{TO}}$ that
  share common derivation ancestry, as
  opposed to simply mapping $U$ to all its linearizations in $tree_{_{TO}}$. 
  The reason
  is that our planners are not systematic, in the sense that they may
  generate two or more plans with the same operator sequence. We can
  distinguish such plans by their derivational history. For example,
  suppose two instantiations of the same operator sequence $O1 \prec
  O2 \prec O3$ exist within a $tree_{_{TO}}$ but they correspond to
  different plans in $tree_{_{UA}}$. $\cal L$ relies on their
  different derivations to determine the appropriate correspondence.}
This is illustrated in Figure~\ref{proof-fig}, where for each plan in
$tree_{_{UA}}$ a dashed line is drawn to the corresponding set of
plans in $tree_{_{TO}}$.

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.012in}
\begin{picture}(341,144)(150,615)
% ** \thicklines
\thinlines
\put(410,730){\circle{10}}
\put(450,690){\circle{10}}
\put(390,650){\circle{10}}
\put(350,650){\circle{10}}
\put(370,690){\circle{10}}
\put(470,630){\circle{10}}
\put(430,630){\circle{10}}
\put(230,630){\circle{10}}
\put(170,650){\circle{10}}
\put(190,730){\circle{10}}
\put(190,690){\circle{10}}
\multiput(200,690)(8.00000,0.00000){18}{\line( 1, 0){  4.000}}
\put(340,690){\vector( 1, 0){0}}
\multiput(240,630)(8.20513,0.00000){20}{\line( 1, 0){  4.103}}
\put(400,630){\vector( 1, 0){0}}
\multiput(180,650)(8.00000,0.00000){18}{\line( 1, 0){  4.000}}
\put(320,650){\vector( 1, 0){0}}
\put(450,680){\vector( 1,-2){ 20}}
\put(190,720){\vector( 0,-1){ 25}}
\put(190,680){\vector( 1,-1){ 40}}
\put(410,720){\vector( 2,-1){ 40}}
\put(410,720){\vector(-2,-1){ 40}}
\multiput(200,730)(8.13953,0.00000){22}{\line( 1, 0){  4.070}}
\put(375,730){\vector( 1, 0){0}}
\put(450,680){\vector(-1,-2){ 20}}
\put(370,680){\vector( 1,-1){ 20}}
\put(370,680){\vector(-1,-1){ 20}}
\put(190,680){\vector(-1,-1){ 20}}
\put(485,625){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\}$}}}
\put(405,645){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\}$}}}
\put(465,685){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\}$}}}
\put(430,725){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\}$}}}
\put(410,625){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\{$}}}
\put(330,645){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\{$}}}
\put(350,685){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\{$}}}
\put(385,725){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\large $\{$}}}
\put(300,635){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]
        {\normalsize $\cal L$}}}
\put(255,660){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]
        {\normalsize $\cal L$}}}
\put(275,700){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]
        {\normalsize $\cal L$}}}
\put(295,740){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]
        {\normalsize $\cal L$}}}
\put(365,745){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]
        {\normalsize {\sc to} search tree}}}
\put(150,745){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]
        {\normalsize {\sc ua} search tree}}}
\end{picture}

\end{center}
\caption{How ${\cal L}$ maps from $tree_{_{UA}}$ to  $tree_{_{TO}}$}
\label{proof-fig}
\end{figure}

We can show that ${\cal L}$ satisfies the totality and disjointness
properties by induction on the depth of the search trees.  Detailed
proofs are in the appendix.  To prove the first property, we show that
for every plan contained in $tree_{_{UA}}$, all linearizations of that
plan are contained in $tree_{_{TO}}$.  To prove the second property, we
note that any two plans at different depths in $tree_{_{UA}}$ have
disjoint sets of linearizations, and then show by induction that any
two plans at the same depth in $tree_{_{UA}}$ also have this property.

How much smaller is $tree_{_{UA}}$ than $tree_{_{TO}}$? The mapping
described above provides an answer.  For each plan $U$ in
$tree_{_{UA}}$ there are $\mid {\cal L} (U) \mid$ distinct plans in
{\sc to}, where $\mid {\cal L} (U) \mid$ is the number of
linearizations of $U$.  The exact number depends on how unordered $U$
is.  A totally unordered plan has a factorial number of linearizations
and a totally ordered plan has only a single linearization.  Thus, the
only time that the size of $tree_{_{UA}}$ equals the size of
$tree_{_{TO}}$ is when every plan in $tree_{_{UA}}$ is totally
ordered; otherwise, $tree_{_{UA}}$ is strictly smaller than
$tree_{_{TO}}$ and possibly exponentially smaller.

\section{Time Cost Per Plan}
\label{time-cost}

While the size of {\sc ua}'s search tree is possibly exponentially
smaller than that of {\sc to}, it does not follow that {\sc ua} is
necessarily more efficient.  Efficiency is determined by two factors:
the time cost per plan in the search tree (discussed in this section)
and the size of the subtree explored during the search process
(discussed in the next section).

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|} \hline
Step & Executions Per Plan & TO Cost &  UA Cost \\ \hline\hline
1 & $1$ & $O(1)$  & $O(1)$ \\ \hline
2 & $1$ & $O(1)$ & $O(1)$ \\ \hline
3 & $<1$ & $O(1)$ & $O(1)$ \\ \hline
4 & $1$ & $O(1)$ & $O(e)$ \\ \hline
5 & $1$ & $O(n)$ & $O(e)$ \\ \hline
\end{tabular}  
\end{center}
\caption{Cost per plan comparisons}
\label{cost-table}
\end{table}

In this section we show that while {\sc ua} can indeed take more time
per plan, the extra time is relatively small and grows only
polynomially with the number of steps in the plan,\footnote{We assume
that the size of the operators (the number of preconditions and
effects) is bounded by a constant for a given domain.} which we denote
by $n$. In comparing the relative efficiency of {\sc ua} and {\sc
  to}, we first consider the number of times that each algorithm step
is executed per plan in the search tree and we then consider the time
complexity of each step.

As noted in the preceding sections, each node in the search tree
corresponds to a plan, and each invocation of the planning procedure
for both {\sc ua} and {\sc to} corresponds to an attempt to extend
that plan. Thus, for both {\sc ua} and {\sc to}, it is clear that the
termination check and goal selection (Steps 1 and 2) are each executed
once per plan.  Analyzing the number of times that the remaining steps
are executed might seem more complicated, since each of these steps is
executed many times at an internal node and not at all at a leaf.
However, the analysis is actually quite simple since we can amortize
the number of executions of each step over the number of plans
produced.  Notice that Step 6 is executed once for each plan that is
generated (i.e., once for each node other than the root node).
This gives us a bound on the number of times that Steps 3, 4, and 5
are executed.\footnote{Since Steps 3 and 4 are nondeterministic, we
  need to be clear about our terminology. We say that Step 3 is
  executed once each time a different operator is chosen, and Step 4
  is executed once for each different combination of orderings that is
  selected.} More specifically, for both algorithms, Step 3 is
executed fewer times than Step 6, and Steps 4 and 5 are executed
exactly the same number of times that Step 6 is executed, that is,
once for each plan that is generated.  Consequently, for both
algorithms, no step is executed more than once per plan, as summarized
in Table \ref{cost-table}. In other words, the number of times each
step is executed during the planning process is bounded by the size of
the search tree.

In examining the costs for each step, we first note that for both
algorithms, Step 1, the termination check, can be accomplished in
$O(1)$ time. Step 2, goal selection, can also be accomplished in
$O(1)$ time; for example, assuming the goals are stored in a list, the
{\tt select-goal} function can simply return the first member of the
list.  Each execution of Step 3, operator selection, also only
requires $O(1)$ time; if we assume the operators are indexed by their
effects, all that is required is to ``pop'' the list of relevant
operators on each execution.

Steps 4 and 5 are less expensive for \TO\ than for \UA. Step 4 of \TO\ 
is accomplished by inserting the new operator, $O_{add}$, somewhere
between $O_{del}$ and $O_{need}$. If the possible insertion points are
considered starting at $O_{need}$ and working towards $O_{del}$, then
each execution of Step 4 can be accomplished in constant time, since
each insertion constitutes one execution of the step.  In contrast,
Step 4 in {\sc ua} involves carrying out interaction detection and
elimination in order to produce a new plan $P'$.  This step can be
accomplished in $O(e)$ time, where $e$ is the number of edges in the
graph required to represent the partially ordered plan. (In the worst
case, there may be $O(n^2)$ edges in the plan, and in the best case,
$O(n)$ edges.)  The following is the description of \UA's ordering
step, from Figure~\ref{ua}, with some additional implementation
details:

%\rule{\textwidth}{0.1mm}
\begin{footnotesize}
\noindent
\begin{enumerate}
\item[4.] {\bf Ordering selection}:
Order $O_{add}$ after $O_{del}$ and before $O_{need}$.
Label all steps preceding $O_{add}$ and all steps
following $O_{add}$. 
Let $steps_{int}$ be the unlabeled steps that 
interact with $O_{add}$.
Let $O_{del}$ be the last deleter of $c$. 
Repeat until $steps_{int}$ is empty:
\begin{itemize}
\item Let $O_{int}$ = Pop($steps_{int}$)
\item  if $O_{int}$ is still unlabeled then either:
\begin{itemize}
\item order $O_{int}$ before $O_{add}$, and
      label $O_{int}$ and the unlabeled steps before $O_{int}$; or
\item order $O_{int}$ after $O_{add}$, and
      label $O_{int}$ and the unlabeled steps after $O_{int}$.
\end{itemize}
 {\em Choice point: both orderings must be 
considered for completeness}.
\end{itemize}
 Let $P'$ be the resulting plan. 
\end{enumerate}
\end{footnotesize}
The ordering process begins with a preprocessing stage.  First, all
steps preceding or following $O_{add}$ are labeled as such.  The
labeling process is implemented by a depth-first traversal of the plan
graph, starting with $O_{add}$ as the root, which first follows the
edges in one direction and then follows edges in the other direction.
This requires at most $O(e)$ time.  After the labeling process is
complete, only steps that are unordered with respect to $O_{add}$ are
unlabeled, and thus the interacting steps (which must be unordered
with respect to $O_{add}$) are identifiable in $O(n)$ time.  The last
deleter is identifiable in $O(e)$ time.


After the preprocessing stage, the procedure orders each interacting
step with respect to $O_{add}$, updating the labels after each
iteration.  Since each edge in the graph need be traversed no more
than once, the entire ordering process takes at most $O(e)$ time 
\shortcite<as described in>{details}.  To see this, note that
the process of labeling the steps before (or after) $O_{int}$ can stop
as soon as a labeled step is encountered.

Having shown that Step 4 of \TO\ has $O(1)$ complexity and Step 4 of
\UA\ has $O(e)$ complexity, we now consider Step 5 of both algorithms,
updating the goal set.  \TO\ accomplishes this by iterating through
the steps in the plan, from the head to the tail, which requires
$O(n)$ time. \UA\ accomplishes this in a similar manner, but it
requires $O(e)$ time to traverse the graph.  (Alternatively, \UA\ can
use the same procedure as \TO, provided an $O(e)$ topological sort
is first done to linearize the plan.)

To summarize our complexity analysis, the use of a partial order means
that \UA\ incurs greater cost for operator ordering (Step 4) and for
updating the goal set (Step 5).  Overall, \UA\ requires $O(e)$ time
per plan, while {\sc to} only requires $O(n)$ time per plan. Since a
totally ordered plan requires a representation of size $O(n)$, and a
partially ordered graph requires a representation of size $O(e)$,
designing procedures with lower costs would be possible only if the
entire plan graph did not need to be examined in the worst case.

\section{The Role of Search Strategies}
\label{search-space-compression}

The previous sections have compared {\sc to} and {\sc ua} in terms of
relative search space size and relative time cost per node.  The extra
processing time required by {\sc ua} for each node would appear to be
justified since its search space may contain exponentially fewer
nodes. However, to complete our analysis, we must consider the number
of nodes actually visited by each algorithm under a given search
strategy.

For breadth-first search, the analysis is straightforward.  After
completing the search to a particular depth, both planners will have
explored their entire trees up to that depth.\footnote{For
  perspicuity, we ignore the fact that the number of nodes explored by
  the two planners on the last level may differ if the planners stop
  when they reach the first solution.} Both \UA\ and \TO\ find a
solution at the same depth due to the correspondence between their
search trees.  Thus, the degree to which \UA\ will outperform \TO,
under breadth-first, depends solely on the ``expansion factor'' under
$\cal L$, i.e., on the number of linearizations of \UA's plans.

We can formalize this analysis as follows.  For a node $U$ in
$tree_{_{UA}}$, we denote the number of steps in the plan at $U$ by
$n_u$, and the number of edges in $U$ by $e_u$.  Then for each node
$U$ that {\sc ua} generates, {\sc ua} incurs time cost $O(e_u)$;
whereas, {\sc to} incurs time cost $O(n_u) \; \cdot \mid {\cal L} (U)
\mid $, where $\mid {\cal L} (U) \mid$ is the number of linearizations
of the plan at node $U$.  Therefore, the ratio of the total time costs
of {\sc to} and {\sc ua} is as follows, where $bf(tree_{_{UA}})$
denotes the subtree considered by {\sc ua} under breadth-first search.
\begin{displaymath}
\frac{\mbox{cost}(\mbox{{\sc to}}_{bf})}
{\mbox{cost}(\mbox{{\sc ua}}_{bf})} = \frac{ \sum_{u \in bf (tree_{_{UA}})}
O(n_u) \; \cdot \mid {\cal L} (U) \mid }
{ \sum_{u \in bf (tree_{_{UA}})} O(e_u) }
\end{displaymath}
                                                
The analysis of breadth-first search is so simple because this search
strategy preserves the correspondence between the two planners' search
spaces. In breadth-first search, the two planners are {\em
synchronized} after exhaustively exploring each level, so that {\sc
to} has explored (exactly) the linearizations of the plans explored by
{\sc ua}.  For any other search strategy which similarly preserves the
correspondence, such as iterative deepening, a similar analysis can be
carried out.

\begin{figure*}[t]
\begin{center}
\ 
\setlength{\epsfxsize}{3.0 in}
\epsfbox{Graph1.ps} \hspace*{2em}
\setlength{\epsfxsize}{3.0 in}
\epsfbox{Graph2.ps}
\hspace*{-0.2in}
\end{center}
%\vskip -0.1in
%\vspace*{-0.2in}
\caption{\UA\ and \TO\ Performance Comparison under Depth-First Search}
\label{graph1}
%\vspace*{-0.1in}
\end{figure*}

The cost comparison is not so clear-cut for depth-first search, since
the correspondence is not guaranteed to be preserved.  It is easy to
see that, under depth-first search, {\sc to} does not necessarily
explore all linearizations of the plans explored by {\sc ua}. This is
not simply because the planners nondeterministically choose which
child to expand.  There is a deeper reason: the correspondence ${\cal
  L}$ does not preserve the subtree structure of the search space. For
a plan $U$ in $tree_{_{UA}}$, the corresponding linearizations in
${\cal L}(U)$ may be spread throughout $tree_{_{TO}}$.  Therefore, it
is unlikely that corresponding plans will be considered in the same
order by depth-first search.  Nevertheless, even though the two
planners are not synchronized, we might expect that, on average, \UA\ 
will explore fewer nodes because the size of $tree_{_{UA}}$ is less
than or equal to the size of $tree_{_{TO}}$.

Empirically, we have observed that \UA\ does tend to outperform \TO\ 
under depth-first search, as illustrated by the experimental results
in Figure~\ref{graph1}.  The first graph compares the mean number of
{\em nodes} explored by \UA\ and \TO\ on 44 randomly generated
blocksworld problems; the second graph compares the mean planning {\em
  time} for \UA\ and \TO\ on the same problems and demonstrates that
the extra time cost per node for \UA\ is relatively insignificant.
The problems are partitioned into 4 sets of 11 problems each,
according to minimal solution ``length'' (i.e., the number of
steps in the plan). For each problem, both planners were given a
depth-limit equal to the length of the shortest
solution.\footnote{Since the depth-limit is equal to the length of the
shortest solution, an iterative deepening \cite{korf-ideep} approach
would yield similar results.  Additionally, we note that increasing
the depth-limit past the depth of the shortest solution does not
significantly change the outcome of these experiments.} Since the
planners make nondeterministic choices, 25 trials were conducted for
each problem. The source code and data required to reproduce these
experiments can be found in Online Appendix 1.

As we pointed out, one plausible explanation for the observed
dominance of \UA\ is that \TO's search tree is at least as large as
\UA's search tree. In fact, in the above experiments we often observed
that \TO's search tree was typically much larger. However, the full
story is more interesting. Search tree size alone is not sufficient to
explain \UA's dominance; in particular, the density and distribution
of solutions play an important role.

The solution density of a search tree is the proportion of nodes that
are solutions.\footnote{This definition of solution density is
  ill-defined for infinite trees, but we assume that a depth-bound is
  always provided, so only a finite subtree is explicitly enumerated.}
If the solution density for \TO's search tree is greater than that for
\UA's search tree, then \TO\ might outperform \UA\ under depth-first
search {\em even though} \TO's search tree is actually larger.  For
example, it might be the case that all \UA\ solution plans are
completely unordered and that the plans at the remaining leaves of
$tree_{_{UA}}$ -- the {\em failed plans} -- are totally ordered.  In
this case, each \UA\ solution plan corresponds to an exponential
number of \TO\ solution plans, and each \UA\ failed plan corresponds
to a single \TO\ failed plan.  The converse is also possible: the
solution density of \UA's search tree might be greater than that of
\TO's search tree, thus favoring \UA\ over \TO\ under depth-first
search.  For example, there might be a single totally ordered solution
plan in \UA's search tree and a large number of highly unordered
failed plans.  Since each of these failed \UA\ plans would correspond
to a large number of \TO\ failed plans, the solution density for \TO\ 
would be considerably lower.

For our blocksworld problems, we found that the solution densities of
the two planners' trees does not differ greatly, at least not in such
a way that would explain our performance results.  We saw no tendency
for $tree_{_{UA}}$ to have a higher solution density than
$tree_{_{TO}}$.  For example, for the 11 problems with solutions at
depth six, the average solution density\footnote{In our experiments, a
  nondeterministic goal selection procedure was used with our
  planners, which meant that the solution density could vary from run
  to run.  We compared the average solution density over 25 trials for
  each problem to obtain our results.} for \TO\ exceeded that of \UA\ 
on 7 out of the 12 problems.  This is not particularly surprising
since we see no {\em a priori} reason to suppose that the solution
densities of the two planners should differ greatly.


\begin{figure}
\begin{center}
\
\setlength{\epsfxsize}{5.3 in}
\epsfbox{tree-uni2.ps} 
\end{center}
\caption{Uniform solution distribution, with solution density 0.25}
\label{dfs-fig1}
\end{figure}

Since solution density is insufficient to explain \UA's dominance on
our blocksworld experiments when using depth-first search, we need to
look elsewhere for an explanation. We hypothesize that the {\em
  distribution} of solutions provides an explanation.  We note that if
the solution plans are distributed perfectly uniformly (i.e., at
even intervals) among the leaves of the search tree, and if the
solution densities are similar, then both planners can be expected to
search a similar number of leaves, as illustrated by the schematic
search tree in Figure~\ref{dfs-fig1}.  Consequently, we can explain
the observed dominance of \UA\ over \TO\ by hypothesizing that
solutions are {\em not} uniformly distributed; that is, solutions tend
to cluster.  To see this, suppose that $tree_{_{UA}}$ is smaller than
$tree_{_{TO}}$ but the two trees have the same solution density. If
the solutions are clustered, as in Figure~\ref{dfs-fig2}, then
depth-first search can be expected to produce solutions more quickly
for $tree_{_{UA}}$ than for $tree_{_{TO}}$.\footnote{Even if the
  solutions are distributed randomly amongst the leaves of the trees
  with uniform probability (as opposed to being distributed
  ``perfectly uniformly''), there will be some clusters of nodes.
  Therefore, \TO\ will have a small disadvantage. To see this, let us
  suppose that each leaf of both $tree_{_{UA}}$ and $tree_{_{TO}}$ is
  a solution with equal probability $p$.  That is, if $tree_{_{UA}}$
  has $N_{_{UA}}$ leaves, of which $k_{_{UA}}$ are solutions, and
  $tree_{_{TO}}$ has $N_{_{TO}}$ leaves, of which $k_{_{TO}}$ are
  solutions, then $p=k_{_{UA}}/N_{_{UA}} = k_{_{TO}}/N_{_{TO}}$.  In
  general, if $k$ out of $N$ nodes are solutions, the expected number
  of nodes that must be tested to find a solution is $.5 N/k$ when
  $k=1$ and approaches $N/k$ as $k$ (and $N$) approaches $\infty$.
  (This is simply the expected number of samples for a binomial
  distribution.)  Therefore, since $k_{_{TO}} \geq k_{_{UA}}$, the
  expected number of leaves explored by \TO\ is greater than or equal
  to the expected number of leaves explored by \UA, by at most a
  factor of 2.} The hypothesis that solutions tend to be clustered
seems reasonable since it is easy to construct problems where a
``wrong decision'' near the top of the search tree can lead to an
entire subtree that is devoid of solutions.

\begin{figure}
\begin{center}
\
\setlength{\epsfxsize}{5.3 in}
\epsfbox{tree-nonuni2.ps} 
\end{center}
\caption{Non-uniform solution distribution, with solution density 0.25}
\label{dfs-fig2}
\end{figure}


One way to test our hypothesis is to compare
\UA\ and \TO\ using a randomized search strategy, a type of Monte Carlo
algorithm, that we refer to as ``iterative 
sampling'' \cite<{\em cf.}>{kr92,langley,chen-thesis,crawford-baker}.  
The iterative sampling strategy explores randomly chosen paths in the
search tree until a solution is found.  A path is selected by
traversing the tree from the root to a leaf, choosing randomly at each
branch point.  If the leaf is a solution then search terminates; if
not, the search process returns to the root and selects another path.
The same path may be examined more than once since no memory is
maintained between iterations.

In contrast to depth-first search, iterative sampling is relatively
insensitive to the distribution of solutions. Therefore, the advantage
of \UA\ over \TO\ should disappear if our hypothesis is correct.  In
our experiments, we did find that when \UA\ and \TO\ both use
iterative sampling, they expand approximately the same number of nodes
on our set of blocksworld problems.\footnote{The iterative sampling
strategy was depth-limited in exactly the same way that our
depth-first strategy was.  We note, however, that the performance of
iterative sampling is relatively insensitive to the actual
depth-limit used.} (For both planners, performance with iterative
sampling was worse than with depth-first search.) The fact that there
is no difference between \UA\ and \TO\ under iterative sampling, but
that there {\em is} a difference under depth-first search, suggests
that solutions are indeed non-uniformly distributed. Furthermore, this
result shows that \UA\ is not necessarily superior to \TO; the search
strategy that is employed makes a dramatic difference.

Although our blocksworld domain may be atypical, we conjecture that
our results are of general relevance. Specifically, for
distribution-sensitive search strategies like depth-first search, one
can expect that \UA\ will tend to outperform \TO. For
distribution-insensitive strategies, such as iterative sampling,
non-uniform distributions will have no effect.  We note that while
iterative sampling is a rather simplistic strategy, there are more
sophisticated search strategies, such as iterative
broadening \cite{ginsberg}, that are also relatively distribution
insensitive.  We further explore such strategies in
Section~\ref{exp-res}.

\section{The Role of Heuristics}

In the preceding sections, we have shown that a partial-order planner
can be more efficient simply because its search tree is smaller. With
some search strategies, such as breadth-first search, this size
differential obviously translates into an efficiency gain. With other
strategies, such as depth-first search, the size differential
translates into an efficiency gain, provided we make additional
assumptions about the solution density and distribution.

However, it is often claimed that partial-order planners are more
efficient due to their ability to make {\em more informed} ordering
decisions, a rather different argument.  For instance, Sacerdoti
\citeyear{sacerdoti} argues that this is the reason that {\sc noah}
performs well on problems such as the blocksworld's ``Sussman
anomaly''. By delaying the decision of whether to stack A on B before
or after stacking B on C, {\sc noah} can eventually detect that a
conflict will occur if it stacks A on B first, and a critic called
{\sc ``resolve-conflicts''} can then order the steps intelligently.

In this section, we show that this argument can be formally described
in terms of our two planners. We demonstrate that \UA\ does in fact
have a potential advantage over \TO\ in that it can exploit certain
types of heuristics more readily than \TO.  This advantage is
independent of the fact that \UA\ has a smaller search space. Whether
or not this advantage is significant in practice is another question,
of course.  We also describe some experiments where we evaluate the
effect of a commonly-used heuristic on our blocksworld problems.

\subsection{Making More Informed Decisions}

\begin{figure}
\begin{center}
\
\setlength{\epsfxsize}{5.5 in}
\epsfbox{heuristic-fig3.ps} 
\end{center}
\caption{Comparison of {\sc ua} and {\sc to} on an example.}
\label{ex-comparison}
\end{figure}

First, let us identify how it is that \UA\ can make better use of
certain heuristics than \TO.  In the {\sc ua} planning algorithm, step
4 arbitrarily orders interacting plan steps.  Similarly, Step 4 of
{\sc to} arbitrarily chooses an insertion point for the new step. It
is easy to see, however, that some orderings should be tried before
others in a heuristic search.  This is illustrated by
Figure~\ref{ex-comparison}, which compares {\sc ua} and {\sc to} on a
particular problem.  The key in the figure describes the relevant
conditions of the library operators, where preconditions are indicated
to the left of an operator and added conditions are indicated to the
right (there are no deletes in this example).  For brevity, the
initial step and final step of the plans are not shown.  Consider the
plan in $tree_{_{UA}}$ with unordered steps $O_1$ and $O_2$.  When
{\sc ua} introduces $O_3$ to achieve precondition $p$ of $O_1$, Step 4
of {\sc ua} will order $O_3$ with respect to $O_2$, since these steps
interact.  However, it makes more sense to order $O_2$ before $O_3$,
since $O_2$ achieves precondition $q$ of $O_3$.  This illustrates a
simple planning heuristic that we refer to as the {\em min-goals}
heuristic: ``prefer the orderings that yield the fewest false
preconditions''.  This heuristic is not guaranteed to produce the
optimal search or the optimal plan, but it is commonly used. It is the
basis of the ``resolve conflicts'' critic that Sacerdoti employed in
his blocksworld examples.

Notice, however, that {\sc to} cannot exploit this heuristic as
effectively as {\sc ua} because it prematurely orders
$O_1$ with respect to $O_2$.  Due to this inability to postpone an
ordering decision, {\sc to} must choose arbitrarily between the plans
$O_1 \prec O_2$ and $O_2 \prec O_1$, before the impact of
this decision can be evaluated.

In the general case, suppose $h$ is a heuristic that can be applied to
both partially ordered plans and totally ordered plans. Furthermore,
assume $h$ is a ``useful'' heuristic;  i.e., if $h$ rates one
plan more highly than another, a planner that explores the more highly
rated plan first will perform better on average.  Then, {\sc ua} will
have a potential advantage over {\sc to} provided that $h$ satisfies
the following property: for any {\sc ua} plan $U$ and corresponding
{\sc to} plan $T$, $h(U) \geq h(T)$; that is, a partially ordered plan
must be rated at least as high as any of its linearizations.  (Note
that for unambiguous plans, the min-goals heuristic satisfies this
property since it gives identical ratings to a partially ordered plan
and its linearizations.)

{\sc ua} has an advantage over {\sc to} because if {\sc ua} is
expanding plan $U$ and {\sc to} is expanding a corresponding plan
$T$, then $h$ will rate some child of $U$ at least as high as the most
highly rated child of $T$.  This is true since every child of $T$ is a
linearization of some child of $U$, and therefore no child of $T$ can
be rated higher than a child of $U$.  Furthermore, there may be a
child of $U$ such that none of its linearizations is a child of $T$,
and therefore this child of $U$ can be rated higher than every child
of $T$.  Since we assumed that $h$ is a useful heuristic, this means
that {\sc ua} is likely to make a better choice than {\sc to}.

\subsection{Illustrative Experimental Results}
\label{exp-res}

The previous section showed that \UA\ has a potential advantage over
\TO\ because it can better exploit certain ordering heuristics.  We
now examine the practical effects of incorporating one such heuristic
into \UA\ and \TO.

First, we note that ordering heuristics only make sense for some
search strategies.  In particular, for breadth-first search,
heuristics do {\em not} improve the efficiency of the search in a
meaningful way (except possibly at the last level).  Indeed, we need
not consider any search strategy in which \TO\ and \UA\ are
``synchronized'', as defined earlier, since ordering heuristics do not
significantly affect the relative performance of \UA\ and \TO\ under
such strategies. Thus, we begin by considering a standard search
strategy that is not synchronized: depth-first search.

\begin{figure}
\begin{center}
\ 
\setlength{\epsfxsize}{3.0 in}
\epsfbox{Graph3.ps}
\hspace*{-0.2in}
\end{center}
\caption{Depth first search with and without min-goals}
\label{graph3}
\end{figure}

We use the min-goals heuristic as the basis for our experimental
investigation, since it is commonly employed, but presumably we could
choose any heuristic that meets the criterion set forth in the
previous section.  Figure~\ref{graph3} shows the impact of min-goals
on the behavior of \UA\ and \TO\ under depth-first search. Although
the heuristic biases the order in which the two planners' search
spaces are explored \cite<{\em cf.}>{rosenbloom-bias}, it appears
that its effect is largely independent of the
partial-order/total-order distinction, since both planners are
improved by a similar percentage.  For example, under depth-first
search on the problems with solutions at depth six, \UA\ improved 88\%
and \TO\ improved 87\%. Thus, there is no obvious evidence for any
extra advantage for \UA, as one might have expected from our analysis
in the previous section. On the other hand, this does not contradict
our theory, it simply means that the potential heuristic advantage was
not significant enough to show up.  In other domains, the advantage
might manifest itself more significantly.  After all, it is certainly
possible to design problems in which the advantage is significant, as
our example in Figure~\ref{ex-comparison} illustrates.  Our results
simply illustrate that in our blocksworld domain, making intelligent
ordering decisions produces a negligible advantage for \UA, in
contrast to the significant effect due to search space compression
(discussed previously).\footnote{In Section~\ref{less-committed}, we
  discuss planners that are ``less-committed'' than \UA.  For such
  planners, the advantage due to heuristics might be more pronounced
  since they ``delay'' their decisions even longer than \UA.}

While the min-goals heuristic did not seem to help \UA\ more than \TO,
the results are nevertheless interesting, since the heuristic had a
very significant effect on the performance of {\em both} planners, so
much so that \TO\ {\em with} min-goals outperforms \UA\ {\em without}
min-goals.  While the effectiveness of min-goals is domain dependent,
we find it interesting that in these experiments, the use of min-goals
makes more difference than the use of partial orders.  After all, the
blocksworld originally helped motivate the development of
partial-order planning and most subsequent planning systems have
employed partial orders.  While not deeply surprising, this result
does help reinforce what we already know: more attention should be
paid to specific planning heuristics such as min-goals.

\begin{figure}
\begin{center}
\ 
\setlength{\epsfxsize}{3.0 in}
\epsfbox{Graph4.ps}
\hspace*{-0.2in}
\end{center}
\caption{Iterative sampling \& iterative broadening, both with min-goals}
\label{graph4}
\end{figure}

In our analysis of search space compression in
Section~\ref{search-space-compression}, we described a ``distribution
insensitive'' search strategy called iterative sampling and showed
that under iterative sampling \UA\ and \TO\ perform similarly,
although their performance is worse than it is under depth-first
search. If we combine min-goals with iterative sampling, we find that
this produces a much more powerful strategy, but one in which \TO\ and
\UA\ still perform about equally.  For simplicity, our implementation
of iterative sampling uses min-goals as a pruning heuristic; at each
choice point, it explores only those plan extensions with the fewest
goals.  This strategy is powerful, although
incomplete.\footnote{Instead of exploring {\em only} those plan
  extensions with the fewest goals at each choice point, an
  alternative strategy is to assign each extension a probability that
  is inversely correlated with the number of goals, and pick
  accordingly. Given a depth bound, this strategy has the advantage of
  being {\em asymptotically complete}. We used the simpler strategy
  here for pedagogical reasons.} Because of this incompleteness, we
note there was one problem we removed from our sample set because
iterative sampling with min-goals would never terminate on this
problem.  With this caveat in mind, we turn to the results in
Figure~\ref{graph4}, which when compared against Figure~\ref{graph3},
show that the performance of both \UA\ and \TO\ with iterative
sampling was, in general, significantly better than their performance
under depth-first search.  (Note that the graphs in Figures
\ref{graph3} and \ref{graph4} have very different scales.) Our results
clearly illustrate the utility of the planning bias 
introduced by min-goals in our blocksworld
domain, since on 43 of our 44 problems, a solution exists in the very
small subspace preferred by min-goals.

These experiments do not show any advantage for \UA\ as compared with
\TO\ under the heuristic, which is consistent with our conclusions
above.  However, this could equally well be because min-goals was so
powerful, leading to solutions so quickly, that smaller influences
were obscured.

The dramatic success of combining min-goals with iterative sampling
led us to consider another search strategy, iterative broadening,
which combines the best aspects of depth-first search and iterative
sampling.  This more sophisticated search strategy initially behaves
like iterative sampling, but evolves into depth-first search as the
breadth-cutoff increases \cite{langley}.  Assuming that the solution
is within the specified depth bound, iterative broadening is complete.
In its early stages iterative broadening is distribution-insensitive;
in its later stages it behaves like depth-first search and, thus,
becomes increasingly sensitive to solution distribution.  As one would
expect from our iterative sampling experiments, with iterative
broadening, solutions were found very early on, as shown in
Figure~\ref{graph4}.  Thus, it is not surprising that \UA\ and \TO\ 
performed similarly under iterative broadening.

We should point out that the results presented in this subsection are
only illustrative, since they deal with only a single domain and with
a single heuristic. Nevertheless, our experiments do illustrate how
the various properties we have identified in this paper can interact.

\section{Extending our Results}

Having established our basic results concerning the efficiency of \UA\ 
and \TO\ under various circumstances, we now consider how these
results extend to other types of planners.

\subsection{More Expressive Languages}

In the preceding sections, we showed that the primary advantage that
\UA\ has over \TO\ is that {\sc ua}'s search tree may be exponentially
smaller than \TO's search tree, and we also showed that \UA\ only pays
a small (polynomial) extra cost per node for this advantage.  Thus far
we have assumed a very restricted planning language in which the
operators are propositional; however, most practical problems demand
operators with variables, conditional effects, or conditional
preconditions. With a more expressive planning language, will the time
cost per node be significantly greater for \UA\ than for \TO?  One
might think so, since the work required to identify interacting steps
can increase with the expressiveness of the operator language used
\cite{dean-boddy,hertzberg}.  If the cost of detecting step
interaction is high enough, the savings that \UA\ enjoys due to its
reduced search space will be outweighed by the additional expense
incurred at each node.


Consider the case for simple breadth-first search. Earlier we showed
that the ratio of the total time costs of {\sc to} and {\sc ua} is as
follows, where the subtree considered by \UA\ under breadth-first search
is denoted by $bf(tree_{_{UA}})$, the number of steps in plan a $U$ is
denoted by $n_u$, and the number of edges in $U$ is denoted by $e_u$:

\begin{displaymath}
\frac{\mbox{cost}(\mbox{TO}_{bf})}
{\mbox{cost}(\mbox{UA}_{bf})} = \frac{ \sum_{U \in bf (tree_{_{UA}})}
O(n_u) \; \cdot \mid {\cal L} (U) \mid } { \sum_{U \in bf (tree_{_{UA}})}
O(e_u) }
\end{displaymath}

This cost comparison is specific to the simple propositional operator
language used so far, but the basic idea is more general.  \UA\ will
generally outperform \TO\ whenever its cost per node is less than the
product of the cost per node for \TO\ and the number of \TO\ nodes
that correspond under $\cal L$.  Thus, \UA\ could incur an exponential
cost per node and still outperform \TO\ in some cases.  This can
happen, for example, if the exponential number of linearizations of a
\UA\ partial order is greater than the exponential cost per node for
\UA.  In general, however, we would like to avoid the case where \UA\ 
pays an exponential cost per node and, instead, consider an approach
that can guarantee that the cost per node for \UA\ remains polynomial
(as long as the cost per node for \TO\ also remains polynomial).

The cost per node for \UA\ is dominated by the cost of updating the
goal set (Step 5) and the cost of selecting the orderings (Step 4).
Updating the goal set remains polynomial as long as a plan is
unambiguous. Since each precondition in an unambiguous plan is either
{\em necessarily} true or {\em necessarily} false, we can determine
the truth value of a given precondition by examining its truth value
in an arbitrary linearization of the plan.  Thus, we can simply
linearize the plan and then use the same procedure \TO\ uses for
calculating the goal set.  As a result, it is only the cost of
maintaining the unambiguous property (i.e., Step 4) that is
impacted by more expressive languages.  One approach for efficiently
maintaining this property relies on a ``conservative'' ordering
strategy in which operators are ordered if they even {\em possibly}
interact.

As an illustration of this approach, consider a simple propositional
language with conditional effects, such as ``if {\em p} and {\em q},
then add {\em r}''.  Hence, an operator can add (or delete)
propositions depending on the state in which it is applied.  We refer
to conditions such as ``{\em p}'' in our example as {\em dependency
conditions}.  (Note that, like preconditions, dependency conditions
are simple propositions.)  Chapman \citeyear{chapman} showed that with
this type of language it is NP-hard to decide whether a precondition
is true in a partially ordered plan. However, as we pointed out above,
for the special case of {\em unambiguous} plans, this decision can be
accomplished in polynomial time.

Formally, the language is specified as follows.  An operator $O$, as
before, has a list of preconditions, pre($O$), a list of
(unconditional) adds, adds($O$), a list of (unconditional) deletes,
dels($O$).  In addition, it has a list of conditional adds,
cadds($O$), and a list of conditional deletes, cdels($O$); both
containing pairs $\langle D_e,\, e\rangle$, where $D_e$ is a
conjunctive set of dependency conditions and $e$ is the conditional
effect (either an added or a deleted condition).  Analogous with the
constraint that every delete must be a precondition, every conditional
delete must be a member of its dependency conditions; that is, for
every $\langle D_e,\, e\rangle \in$ cdels($O$), $e \in D_e$.

Figure~\ref{uac} shows a version of the \UA\ algorithm, called \UAC,
which is appropriate for this language.  The primary difference
between the \UA\ and \UAC\ algorithms is that in both Steps 3 and 4b
an operator may be {\em specialized} with respect to a set of
dependency conditions.  The function specialize($O$, $D$ ) accepts a
plan step, $O$, and a set of dependency conditions, $D$; it returns a
new step $O'$ that is just like $O$, but with certain conditional
effects made unconditional.  The effects that are selected for this
transformation are exactly those whose dependency conditions are a
subset of $D$.  Thus, the act of specializing a plan step is the act
of committing to expanding its causal role in a plan.\footnote{For
  simplicity, the modifications used to create \UAC\ are not very
  sophisticated.  As a result, \UAC's space may be larger than it
  needs to be in some circumstances, since it aggressively commits to
  specializations.  A more sophisticated set of modifications is
  possible; however, the subtlies involved in efficiently planning
  with dependency conditions \cite{pednault,collins-pryor,weld-ucpop}
  are largely irrelevant to our discussion.} Once a step is
specialized, \UAC\ has made a commitment to use it for a given set of
effects.  Of course, a step can be further specialized in a later
search node, but specializations are never retracted.

More precisely, the definition of $O' = \mbox{specialize}(O, D)$,
where $O$ is a step, $D$ is a conjunctive set of dependency conditions
in $O$, and $\backslash$ is the set difference operator, is as
follows.

\begin{itemize}
\item $\mbox{pre}(O') \: = \: \mbox{pre}(O) \; \cup \; D$.
\item $\mbox{adds}(O') \: = \: \mbox{adds}(O) \;\cup \; \{e \; | \;
  \langle D_e,\, e\rangle \, \in \, \mbox{cadds}(O) \: \wedge \: D_e
  \subset D\}$. 
\item $\mbox{dels}(O') \: = \: \mbox{dels}(O) \; \cup \; \{e \; | \;
  \langle D_e,\,e\rangle \, \in \, \mbox{cdels}(O) \: \wedge \: D_e \subset
  D\}$. 
\item $\mbox{cadds}(O') \: = \: \{\langle D_{e'},\,e \rangle \; | \;
  \langle D_e,\, e\rangle \, \in \, \mbox{cadds}(O) \: \wedge \: D_e
  \not\subset D \: \wedge \: D_{e'} \,  = \, D_e \backslash D \}$. 
\item $\mbox{cdels}(O') \: = \: \{\langle D_{e'},\,e \rangle \; | \;
  \langle D_e,\, e\rangle \, \in \, \mbox{cdels}(O) \: \wedge \: D_e
  \not\subset D \: \wedge \: D_{e'} \, = \, D_e \backslash D \}$. 
\end{itemize}

The definition of step interaction is generalized for \UAC\ as
follows.  We say that two steps in a plan {\em interact} if they are
unordered with respect to each other and the following disjunction
holds:
\begin{itemize}
\item one step has a precondition {\em or dependency condition}
 that is added or deleted by the other step, or
\item one step adds a condition that is deleted by the other step.
\end{itemize}
The difference between this definition of step interaction and the one
given earlier is indicated by an italic font.  This modified
definition allows us to detect interacting operators with a simple
inexpensive test, as did our original definition.  For example, two
steps that are unordered interact if one step conditionally adds {\em
  r} and the other has precondition {\em r}. Note that the first step
need not actually add {\em r} in the plan, so ordering the two
operators might be unnecessary.  In general, our definition of
interaction is a sufficient criterion for guaranteeing that the
resulting plans are unambiguous, but it is not a necessary criterion.

\begin{figure}
\begin{footnotesize}
UA-C$(P,G)$
\begin{itemize}
\item[1\ ] {\bf Termination check:}
     If $G$ is empty, report success and return solution plan P.
\item[2\ ] {\bf Goal selection:}
     Let $c\; = \;$ select-goal($G$), and let $O_{need}$ be the plan
     step for which $c$ is a precondition.
\item[3\ ] {\bf Operator selection:} Let $O_{add}$ be an operator
   schema in the library that {\em possibly} adds $c$; that is,
   either $c \in \mbox{adds}(O)$, or there exists an $\langle D_c,\,
   c\rangle \in \mbox{cadds}(O)$.  In the former case, insert step
   $O_{add}$ and in the latter case, insert step
   $\mbox{specialize}(O_{add},D_c)$.  If there is no such
   $O_{add}$, then terminate and report failure.  {\em Choice point:
     all ways in which $c$ can be added must be considered for
     completeness.}
\item[4a] {\bf Ordering selection:}
  Let $O_{del}$ be the (unconditional) last deleter of $c$. 
  Order $O_{add}$ after $O_{del}$ and before $O_{need}$. \\
  Repeat until there are no interactions: \\
    \hspace*{0.25in} $\circ$ Select a step $O_{int}$ that
interacts with $O_{add}$. \\ 
   \hspace*{0.25in} $\circ$ Order $O_{int}$ either 
before or after $O_{add}$.\\
 \hspace*{0.38in} {\em Choice point: both orderings must be 
considered for completeness}. \\
     Let $P'$ be the resulting plan.
\item[4b] {\bf Operator role selection:} 
  While there exists a step $O_{cadd}$ with unmarked conditional add
  $\langle D_c, \, c \rangle$ and a step $O_{use}$ with precondition
  $c$, such that $O_{use}$ is after $O_{cadd}$ and there is no 
  (unconditional) deleter of $c$ in between $O_{use}$ and
  $O_{cadd}$. \\ 
  \hspace*{0.25in} $\circ$ Either mark $\langle D_c, \, c \rangle$,
  or replace $O_{cadd}$ with $\mbox{specialize}(O_{cadd},D_c)$. \\
  \hspace*{0.38in}   {\em Choice point: Both options must be
    considered for completeness.} 
\item[5\ ] {\bf Goal updating:}
  Let $G'$ be the set of preconditions in $P'$ that are necessarily
  false.
\item[6\ ] {\bf Recursive invocation:} UA-C$(P',G')$.
\end{itemize}
\caption{The \UA-C\ planning algorithm}
\label{uac}
\end{footnotesize}
\end{figure}

Figure~\ref{uac-ex} shows a schematic example illustrating how \UAC\ 
extends a plan. The preconditions of each operator are shown on the
left of each operator, and the unconditional adds on the right. (We
only show the preconditions and effects necessary to illustrate the
specialization process; no deletes are used in the example.)
Conditional adds are shown underneath each operator. For instance, the
first operator in the plan at the top of the page has precondition
{\em p}. This operator adds {\em q} and conditionally adds {\em u}
if {\em t} is true. The figure illustrates two of the plans produced
as a result of adding a new conditional operator to the plan. In one
plan, the conditional effects $[u \rightarrow s]$ and $[t \rightarrow
u]$ are selected in the specialization process, and in the other plan
they are not.

\begin{figure}
\begin{center}
\ 
\setlength{\epsfxsize}{4.2 in}
\epsfbox{cond4.ps}
\end{center}
\caption{An example illustrating the \UAC\ algorithm}
\label{uac-ex}
\end{figure}

The new step, Step 4b, requires only polynomial time per plan
generated, and the time cost of the other steps are the same as for
\UA.  Hence, as with our original \UA\ algorithm, the cost per node
for the \UAC\ algorithm is polynomial.

\TO\ can also handle this language given the corresponding
modifications (changing Step 3 and adding Step 4b), and the time cost
per plan also remains polynomial.\footnote{In fact, Step 4b be
  implemented so that the time cost is $O(e)$, using the graph
  traversal techniques described in Section~\ref{time-cost}. As a
  result the \UAC\ implementation and the corresponding \TOC\ 
  implementation have the same time cost per node for this new
  language as they did for the original language, $O(e)$ and $O(n)$,
  respectively.} Moreover, the same relationship holds between the two
planners' search spaces -- $tree_{_{UA}}$ is never larger than
$tree_{_{TO}}$ and can be exponentially smaller.  This example
illustrates that the theoretical advantages that \UA\ has over \TO\ 
can be preserved for a more expressive language.  As we pointed out,
our definition of interaction is a sufficient criterion for
guaranteeing that the resulting plans are unambiguous, but it is not a
necessary criterion.  Nevertheless, this conservative approach allows
interactions to be detected via a simple inexpensive syntactic test.
Essentially, we have kept the cost per node for \UAC\ low by
restricting the search space it considers, as shown in
Figure~\ref{spaces}. \UAC\ only considers unambiguous plans that can
be generated via its ``conservative'' ordering strategy. \UAC\ is
still a partial-order planner, and it is complete, but it does not
consider all partially ordered plans or even all unambiguous
partially ordered plans.

\begin{figure}
\begin{center}
\
\setlength{\epsfxsize}{3in}
\epsfbox{circles3.ps} 
\end{center}
\caption{Hierarchy of Plan Spaces}
\label{spaces}
\end{figure}

The same ``trick'' can be used for other languages as well, provided
that we can devise a simple test to detect interacting operators.  For
example, in previous work \cite{details} we showed how this can be
done for a language where operators can have variables in their
preconditions and effects. In the general case, for a given \UA\ plan
and a corresponding \TO\ plan, Steps 1,2, and 3 of the \UA\ algorithm
cost the same as the corresponding steps of the \TO\ algorithm.  As
long as the plans considered by \UA\ are unambiguous, Step 5 of the
\UA\ algorithm can be accomplished with an arbitrary linearization of
the plan, in which case it costs at most $O(e)$ more than Step 5 of
the \TO\ algorithm.  Thus, the only possibility for additional cost is
in Step 4. In general, if we can devise a ``local'' criterion for
interaction such that the resulting plan is guaranteed to be
unambiguous, then the ordering selection step can be accomplished in
polynomial time.  By ``local'', we mean a criterion that only
considers operator pairs to determine interactions; i.e., it
must not examine the rest of the plan.

Although the theoretical advantages that \UA\ has over \TO\ can be
preserved for more expressive languages, there is a cost. The
unambiguous plans that are considered may have more orderings than
necessary, and the addition of unnecessary orderings can increase the
size of \UA's search tree.  The magnitude of this increase depends on
the specific language, domain, and problem being considered.
Nevertheless, we can guarantee that {\sc ua}'s search tree is never
larger than \TO's.

The general lesson here is that the cost of plan extension is not
solely dependent on the expressiveness of the operator language, it
also depends on the nature of the plans that the planner considers.
So, although the extension of partially ordered plans is NP-hard for
languages with conditional effects, if the space of plans is
restricted (e.g., only unambiguous plans are considered) then
this worst-case situation is avoided.

\begin{figure}[b]
\begin{center}
\
\setlength{\epsfxsize}{3.0in}
\epsfbox{continuum.ps} 
\end{center}
\vspace*{-.15in}
\caption{A continuum of commitment strategies}
\label{continuum}
\end{figure}

\subsection{Less Committed Planners}
\label{less-committed}

We have shown that {\sc ua}, a partial-order planner, can have certain
computational advantages over a total-order planner, {\sc to}, since
its ability to delay commitments allows for a more compact search
space and potentially more intelligent ordering choices.  However,
there are many planners that are even less committed than {\sc ua}.
In fact, there is a continuum of commitment strategies that we might
consider, as illustrated in Figure~\ref{continuum}. Total-order
planning lies at one end of the spectrum. At the other extreme is the
strategy of maintaining a {\em totally unordered} set of steps during
search until there exists a linearization of the steps that is a
solution plan.

\begin{figure}
\begin{footnotesize}
MT$(P,G)$
\begin{enumerate}
\item {\bf Termination check:}
     If $G$ is empty, report success and stop.
\item {\bf Goal selection:}
  Let $c\; = \;$ select-goal($G$), and let $O_{need}$ be the plan
  step for which $c$ is a precondition.
\item {\bf Operator selection:}
     Let $O_{add}$ be either a plan step possibly before $O_{need}$
that adds $c$ or an operator in the library that adds $c$.  If there
is no such $O_{add}$, then terminate and report failure.  \\
{\em Choice point: all such operators must be considered for
completeness.}
\item {\bf Ordering selection:}
     Order $O_{add}$ before $O_{need}$.  Repeat until there are no
steps possibly between $O_{add}$        and $O_{need}$ which delete
$c$:\\ \hspace*{0.125in} Let $O_{del}$ be such a step; choose one of
the following ways to make $c$ true for $O_{need}$ \\
\hspace*{0.25in} $\circ$ Order $O_{del}$ after $O_{need}$. \\
\hspace*{0.25in} $\circ$ Choose a step $O_{knight}$ (possibly $O_{add}$) that adds $c$ that
is possibly between $O_{del}$ and $O_{need}$; \\ 
\hspace*{0.4in} 
order it after $O_{del}$
and before $O_{need}$. \\
\hspace*{0.4in} {\em Choice point: both alternatives must be
considered for completeness.} \\
     Let $P'$ be the resulting plan.
\item {\bf Goal updating:}
     Let $G'$ be the set of preconditions in $P'$ that are not
necessarily true.
\item {\bf Recursive invocation:} MT$(P',G')$.
\end{enumerate}
\caption{A Propositional Planner based on the Modal Truth Criterion}
\label{mt}
\end{footnotesize}
\end{figure}


Compared to many well-known planners, {\sc ua} is conservative since
it requires each plan to be unambiguous.  This is not required by {\sc
  noah} \cite{noah}, NonLin \cite{tate-ijcai77}, nor
Tweak \cite{chapman}, for example.  How do these less-committed
planners compare to {\sc ua} and {\sc to}?  One might expect a
less-committed planner to have the same advantages over {\sc ua} that
{\sc ua} has over {\sc to}.  However, this is not necessarily true.
As an example, in this section we introduce a Tweak-like planner,
called {\sc mt}, and show that its search space is larger than even
{\sc to}'s in some circumstances.\footnote{We use Tweak for this
  comparison because, like \UA\ and \TO, it is a formal construct
  rather than a realistic planner, and therefore more easily
  analyzed.}


\begin{figure}[t]
\begin{center}
\
\setlength{\epsfxsize}{3.5in}
\epsfbox{overlap-fig.ps} 
\end{center}
\vspace*{-.15in}
\caption{``Overlapping'' plans.}
\label{overlap}
\vspace*{-.1in}
\end{figure}

Figure~\ref{mt} presents the {\sc mt} procedure. {\sc mt} is a
propositional planner based on Chapman's Modal Truth Criterion
\cite{chapman}, the formal statement that characterizes Tweak's search
space.  It is straightforward to see that {\sc mt} is less committed
than \UA. The algorithms are quite similar; however, in Step 4,
whereas \UA\ orders all interacting steps, {\sc mt} does not. Since
{\sc mt} does not immediately order all interacting operators, it may
have to add additional orderings between previously introduced
operators later in the planning process to produce correct plans.


The proof that {\sc ua}'s search tree is no larger than {\sc to}'s
search tree rested on the two properties of $\cal L$ elaborated in
Section~\ref{space-section}.  By investigating the relationship
between {\sc mt} and {\sc to}, we found that the second property, the
disjointness property, does not hold for {\sc mt}, and its failure
illustrates how {\sc mt} can explore more plans than {\sc to} (and,
consequently, than {\sc ua}) on certain problems.  The disjointness
property guarantees that {\sc ua} does not generate ``overlapping''
plans.  The example in Figure~\ref{overlap} shows that {\sc mt} fails
to satisfy this property because it can generate plans that share
common linearizations, leading to considerable redundancy in the
search tree.  The figure shows three steps, $O_1$, $O_2$, and $O_3$,
where each $O_i$ has precondition $p_i$ and added conditions $g_i$,
$p_1$, $p_2$, and $p_3$.  The final step has preconditions $g_1$,
$g_2$, and $g_3$, but the initial and final steps are not shown in the
figure.  At the top of the figure, in the plan constructed by {\sc
  mt}, goals $g_1$, $g_2$, and $g_3$ have been achieved, but $p_1$,
$p_2$, and $p_3$ remain to be achieved.  Subsequently, in solving
precondition $p_1$, {\sc mt} generates plans which share the
linearization $O_3 \prec O_2 \prec O_1$ (among others).  In
comparison, both {\sc to} and {\sc ua} only generate the plan $O_3
\prec O_2 \prec O_1$ once. In fact, it is simple to show that, under
breadth-first search, {\sc mt} explores many more plans than {\sc to}
on this example (and also more than {\sc ua}, by transitivity) due to
the redundancy in its search space.

This result may seem counterintuitive. However, note that the search
space size for a partial-order planner is potentially much greater
than that of a total-order planner since there are many more partial
orders over a set of steps than there are total orders.  (Thus, when
designing a partial-order planner, one may preclude
overlapping linearizations in order to avoid redundancy, as discussed 
by McAllester \& Rosenblitt, 1991 and Kambhampati, 1994c.)


Of course, one can also construct examples where {\sc mt} does have a
smaller search space than both {\sc ua} and {\sc to}.  Our example
simply illustrates that although one planner may be less committed
than another, its search space is not {\em necessarily smaller}.  The
commitment strategy used by a planner is simply one factor that
influences overall performance.  In particular, the effect of
redundancy in a partial-order planner can overwhelm other
considerations. In comparing two planners, one must carefully consider
the mapping between their search spaces before concluding that ``less
committed $\Rightarrow$ smaller search space''.

\section{Related Work}

For many years, the intuitions underlying partial-order planning
were largely taken for granted. Only in the past few years has there 
been renewed interest in the fundamental principles underlying
these issues. 

\shortciteA{barrett-and-co} and 
Barrett and Weld \citeyear{barrett-weld-AIJ} 
describe an interesting and novel
analysis of partial-order planning that complements our own work. They
compare a partial-order planner with two total-order planners derived
from it, one that searches in the space of plans, and the other that
searches in the space of world states.  Their study focuses on how the
goal structure of the problem affects the efficiency of partial-order
planning. Specifically, they examine how partial-order and total-order
planning compare for problems with independent, serializable, and
non-serializable goals, when using a resource-bounded depth-first
search.  They refine Korf's work on serializable goals
\cite{korf-planning}, introducing a distinction between {trivially
  serializable} subgoals, where the subgoals can be solved in any
order without violating a previously solved subgoal, and {laboriously
  serializable} subgoals, where the subgoals are serializable, but at
least $1/n$ of the orderings can cause a previously solved subgoal to
be violated. Their study describes conditions under which a
partial-order planner may have an advantage. For instance, they show
that in a domain where the goals are trivially serializable for their
partial-order planner and laboriously serializable for their
total-order planners, their partial-order planner performs
significantly better.

Our study provides an interesting contrast to Barret and Weld's work,
since we investigate the relative efficiencies of partial-order and
total-order planning algorithms independent of any particular domain
structure.  Instead, we focus on the underlying properties of the
search space and how the search strategy affects the efficiency of our
planners.  Nevertheless, we believe there are interesting
relationships between the forms of serializability that they
investigate, and the ideas of solution density and clustering that we
have discussed here.  To illustrate this, consider an artificial
domain that Barret and Weld refer to as $D^1S^1$, where, in each
problem, the goals are a subset of $\{G_1,G_2,\ldots G_{15}\}$, the
initial conditions are $\{I_1,I_2,\ldots I_{15}\}$, and each operator
$O_{i \in \{1,2,\ldots,15\}}$ has precondition $I_i$, adds $G_i$, and
deletes $I_{i-1}$.  It follows that if a solution in $D^1S^1$ contains
operators $O_i$ and $O_j$ where $i < j$, then $O_i$ must precede
$O_j$.  In this domain, the goals are trivially serializable for their
partial-order planner and laboriously serializable for their
total-order planners; thus, the partial-order planner performs best.
But note also that in this artificial domain, there is exactly one
solution per problem and it is totally ordered.  Therefore, it is
immediately clear that, if we give \UA\ and \TO\ problems from this
domain, then \UA's search tree will generally be much smaller than
\TO's search tree.  Since there is only single solution for both
planners, the solution density for \UA\ will clearly be greater than
that for \TO.  Thus, the properties we discussed in this paper should
provide a basis for analyzing how differences in subgoal
serializibility manifest their effect on the search. This subject,
however, is not as simple as it might seem and deserves further study.


In other related work, Kambhampati has written several papers
\cite{rao-aips94,rao-multi-contrib-aij,rao-kr94} that analyze the
design space of partial-order planners, including the {\sc ua} planner
presented here.  Kambhampati compares {\sc ua}, Tweak, {\sc snlp}
\cite{snlp}, {\sc ucpop} \cite{weld-ucpop}, and several other planners
along a variety of dimensions.  He presents a generalized schema for
partial order planning algorithms \cite{rao-kr94} and shows that the
commitment strategy used in {\sc ua} can be viewed as a way to
increase the tractability of the plan extension (or refinement)
process.  Kambhampati also carries out an empirical comparison of the
various planning algorithms on a particular problem \cite{rao-aips94},
showing how the differences in commitment strategies affects the
efficiency of the planning process.  He distinguishes two separate
components of the branching factor, $b_t$ and $b_e$, the former
resulting from the commitment strategy for operator ordering (or in
his terms, the ``tractability refinements'') and the latter resulting
from the choice of operator (``establishment refinements'').
Kambhampati's experiments demonstrate that while ``eager'' commitment
strategies tend to increase $b_t$, sometimes they also decrease
$b_e$, because the number of possible establishers is reduced when
plans are more ordered.  This is, of course, closely related to the
issues investigated in this paper.

In addition, Kambhampati and Chen \citeyear{rao-and-chen} have compared
the relative utility of {\em reusing} partially ordered and totally
ordered plans in ``learning planners''. They showed that the reuse of
partially ordered plans, rather than totally ordered plans, result in
``storage compaction'' because they can represent a large number of
different orderings.  Moreover, partial-order planners have an
advantage because they can exploit such plans more effectively than
total-order planners. In many respects, these advantages are
fundamentally similar to the advantages that \UA\ derives from its
potentially smaller search space.

\section{Conclusions}

By focusing our analysis on a single issue, namely, operator ordering
commitment, we have been able to carry out a rigorous comparative
analysis of two planners.  We have shown that the search space of a
partial-order planner, {\sc ua}, is {\em never} larger than the search
space of a total-order planner, {\sc to}.  Indeed for certain
problems, {\sc ua}'s search space is exponentially smaller than {\sc
to}'s.  Since {\sc ua} pays only a small polynomial time increment per
node over {\sc to}, it is generally more efficient.

We then showed that \UA's search space advantage may not necessarily
translate into an efficiency gain, depending in subtle ways on the
search strategy and heuristics that are employed by the planner. For
example, our experiments suggest that distribution-sensitive search
strategies, such as depth-first search, can benefit more from partial
orders than can search strategies that are distribution-insensitive.

We also examined a variety of extensions to our planners, in order to
demonstrate the generality of these results.  We argued that the
potential benefits of partial-order planning may be retained even with
highly expressive planning languages. However, we showed that
partial-order planners do not necessarily have smaller search spaces,
since some ``less-committed'' strategies may create redundancies in
the search space. In particular, we demonstrated that a Tweak-like
planner, {\sc mt}, can have a larger search space than our total-order
planner on some problems.

How general are these results?  Although our analysis has considered
only two specific planners, we have examined some important tradeoffs
that are of general relevance. The analysis clearly illustrates how
the planning language, the search strategy, and the heuristics that
are used can affect the relative advantages of the two planning
styles.

The results in this paper should be considered as an investigation of
the possible benefits of partial-order planning. {\sc ua} and {\sc to}
have been constructed in order for us to analyze the
total-order/partial-order distinction in isolation. In reality, the
comparative behavior of two planners is rarely as clear (as witnessed
by our discussion of {\sc mt}).  While the general points we make are
applicable to other planners, if we chose two arbitrary planners, we
would not expect one planner to so clearly dominate the other.

Our observations regarding the interplay between plan representation
and search strategy raise new concerns for comparative analyses of
planners.  Historically, it has been assumed that representing plans
as partial orders is categorically ``better'' than representing plans
as total orders.  The results presented in this paper begin to tell a
more accurate story, one that is both more interesting and more
complex than we initially expected.


\appendix
\section{Proofs}
\label{proofs-section}
\subsection{Definitions}

This section defines the terminology and notation used in our proofs.
The notion of plan equivalence is introduced here because each plan
step is, by definition, a uniquely labeled operator instance, as noted
in Section \ref{terminology} and Section \ref{space-section}.  Thus, no two
plans have the same set of steps.  Although this formalism simplifies
our analysis, it requires us to define plan equivalence explicitly.

\begin{itemize}

\item A {\em plan} is a pair $\langle \theta, \prec\rangle$, where
  $\theta$ is a set of steps, and $\prec$ is the ``before'' relation
  on $\theta$, i.e., $\prec$ is a {\em strict partial order} on
  $\theta$.  Notationally, $O_1 \prec O_2$ if and only if $(O_1 , O_2)
  \in \prec$.

\item For a given problem, we define the search tree $tree_{_{TO}}$ as
  the complete tree of plans that is generated by the {\sc to}
  algorithm on that problem.  $tree_{_{UA}}$ is the corresponding
  search tree generated by {\sc ua} on the same problem.

\item Two plans, $P_1 \; = \; \langle \theta_{1}, \prec_{1}\rangle$
  and $P_2 \; = \; \langle \theta_{2}, \prec_{2}\rangle$ are said to
  be {\em equivalent}, denoted $P_1 \simeq P_2$, if there exists a
  bijective function $f$ from $\theta_{1}$ to $\theta_{2}$ such that:
\begin{itemize}

\item for all $O \in \theta_{1}$, $O$ and $f(O)$ are instances of the
  same operator, and

\item for all $O',O'' \in \theta_{1}$, $O' \prec O''$ if and only if
  $f(O') \prec f(O'')$.
\end{itemize}


\item A plan $P_2$ is a {\em 1-step} {\sc to}{\em -extension} (or {\em
    1-step} {\sc ua}{\em -extension}) of a plan $P_1$ if $P_2$ is
  equivalent to some plan produced from $P_1$ in one invocation of
  {\sc to} (or {\sc ua}).

\item A plan $P$ is a {\sc to}{\em -extension} (or {\sc ua}{\em
    -extension}) if either:
\begin{itemize}
\item $P$ is the initial plan, or

\item $P$ is a 1-step {\sc to}-extension (or 1-step {\sc
    ua}-extension) of a {\sc to}-extension (or {\sc ua}-extension).
\end{itemize}
It immediately follows from this definition that if $P$ is a member of
$tree_{_{TO}}$ (or $tree_{_{UA}}$), then $P$ is a {\sc to}-extension
(or {\sc ua}-extension). In addition, if $P$ is a {\sc to}-extension
(or {\sc ua}-extension), then some plan that is equivalent to $P$ is a
member of $tree_{_{TO}}$ (or $tree_{_{UA}}$).

\item $P_1$ is a {\em linearization of} $P_2 \; = \; \langle
  \theta,\prec_2\rangle$ if there exists a strict total order
  $\prec_1$ such that $\prec_2 \; \subseteq \; \prec_1$ and $P_1 \simeq
  \langle \theta, \prec_1\rangle$.

\item Given a search tree, let $parent$ be a function from a plan to
  its parent plan in the tree.  Note that $P_1$ is the parent of
  $P_2$, denoted $P_1 \; = \; parent(P_2)$, only if $P_2$ is a 1-step
  extension of $P_1$.

\item Given $U \in tree_{_{UA}}$ and $T \in tree_{_{TO}}$, $T \in
  {\cal L} (U)$ if and only if plan $T$ is a linearization of plan $U$
  and either both $U$ and $T$ are root nodes of their respective
  search trees, or $parent(T) \in {\cal L} (parent(U))$.

\item The {\em length} of the plan is the number of steps in the plan
  excluding the first and last steps. Thus, the initial plan has
  length 0.  A plan $P$ with $n$ steps has length $n-2$.

\item $P_1$ is a {\em subplan of} $P_2 \; = \; \langle
  \theta_2,\prec_2\rangle$ if $P_1 \simeq \langle \theta_1,
  \prec_1\rangle$, where
\begin{itemize}
\item $\theta_1 \; \subseteq \; \theta_2$ and

\item $\prec_1$ is $\prec_2$ restricted to $\theta_1$, i.e.,
  $\prec_{1} \; = \: \prec_{2} \cap \: \theta_1 \! \! \times \!
  \theta_1$.
\end{itemize}

\item $P_1$ is a {\em strict} subplan of $P_2$, if $P_1$ is a subplan
  of $P_2$ and the length of $P_1$ is less than the length of $P_2$.

\item A solution plan $P$ is a {\em compact solution} if no strict
  subplan of $P$ is a solution.

\end{itemize}

\subsection{Extension Lemmas}

\smallskip

\noindent {\bf TO-Extension Lemma}: Consider totally ordered plans
$T_0 \; = \; \langle \theta_0, \prec_0\rangle$ and \mbox{$T_1 \; = \;
\langle \theta_1, \prec_1\rangle$}, such that $\theta_1 \; = \;
\theta_0 \cup \{ O_{add} \}$ and $\prec_0 \; \subset \; \prec_1$. Let
$G$ be the set of false preconditions in $T_0$.  Then $T_1$ is a
1-step {\sc to}-extension of $T_0$ if:
\begin{itemize}
\item $c \; = \;$ {\tt select-goal}$(G)$, where $c$ is the precondition of 
some step $O_{need}$ in $T_0$, and
\item $O_{add}$ adds $c$, and
\item $(O_{add}, O_{need}) \in \prec_1$, and
\item $(O_{del}, O_{add}) \in \prec_1$, where $O_{del}$
is the last deleter of $c$ in $T_1$.
\end{itemize}

\smallskip
\noindent
{\bf Proof Sketch:} This lemma follows from the definition of {\sc
  to}. Given plan $T_0$, with false precondition $c$, once {\sc to}
selects $c$ as the goal, {\sc to} will consider all operators that
achieve $c$, and for each operator {\sc to} considers all positions
before $c$ and after the last deleter of $c$.

\bigskip
\noindent {\bf UA-Extension Lemma}: Consider a plan $U_0 \; = \; \langle
\theta_0, \prec_0\rangle$ produced by {\sc ua} and plan $U_1 \; = \; \langle
\theta_1, \prec_1\rangle$, such that $\theta_1 \; = \; \theta_0 \cup \{
O_{add} \}$ and $\prec_0 \; \subset \; \prec_1$.  Let $G$ be the set
of false preconditions of the steps in $U_0$.  Then $U_1$ is a 1-step
{\sc ua}-extension of $U_0$ if:
\begin{itemize}
\item $c \; = \;$ {\tt select-goal}$(G)$, where $c$ is the precondition of
  some step $O_{need}$ in $U_0$, and
\item $O_{add}$ adds $c$, and
\item $\prec_{1}$ is a minimal set of consistent orderings such that
\begin{itemize}
\item $\prec_0 \; \subseteq \; \prec_1$, and
\item $(O_{add}, O_{need}) \in \prec_1$, and
\item $(O_{del}, O_{add}) \in \prec_1$, where $O_{del}$ is the last
  deleter of $c$ in $U_1$, and
\item no step in $U_1$ interacts with $O_{add}$
\end{itemize}
\end{itemize}

\smallskip
\noindent
{\bf Proof Sketch:} This lemma follows from the definition of {\sc
  ua}. Given plan $U_0$, with false precondition $c$, {\sc ua}
considers all operators that achieve $c$, and for each such operator
{\sc ua} then inserts it in the plan such that it is before $c$ and
after the last deleter. {\sc ua} then considers all consistent
combinations of orderings between the new operator and the operators
with which it interacts.  No other orderings are added to the plan.

\subsection{Proof of Search Space Correspondence $\cal L$}

\noindent {\bf Mapping Lemma:} Let $U_0 \; = \; \langle \theta_0,
\prec_{u0}\rangle$ be an unambiguous plan and let $U_1 \; = \; \langle
\theta_1, \prec_{u1}\rangle$ be a 1-step {\sc ua}-extension of $U_0$.
If $T_1 \; = \; \langle \theta_1, \prec_{t1}\rangle$ is a
linearization of $U_1$, then there exists a plan $T_0$ such that $T_0$
is a linearization of $U_0$ and $T_1$ is a 1-step {\sc to}-extension
of $T_0$.

\smallskip
\noindent {\bf Proof:} Since $U_1$ is a 1-step {\sc ua}-extension of
$U_0$, there is a step $O_{add}$ such that $\theta_1 \; = \; \theta_0
\cup \{ O_{add}\}$.  Let $T_0$ be the subplan produced by removing
$O_{add}$ from $T_1$; that is, $T_0 \; = \; \langle \theta_0,
\prec_{t0}\rangle$, where $\prec_{t0} \, = \: \prec_{t1} \cap \,
\theta_0 \! \! \times \!  \theta_0$.  Since $\prec_{u0} \, = \:
\prec_{u1} \! \cap \, \theta_0 \! \! \times \!  \theta_0 \; \subseteq
\: \prec_{t1} \! \cap \, \theta_0 \! \! \times \! \theta_0\; = \; \,
\prec_{t0}$, it follows that $T_0$ is a linearization of $U_0$.

Using the TO-Extension lemma, we can show that $T_1$ is a 1-step {\sc
  to}-extension of $T_0$.  First, $T_0$ is a linearization of $U_0$,
so the two plans have the same set of goals. Therefore, if {\sc ua}
selects some goal $c$ in expanding $U_0$, {\sc to} selects $c$ in
extending $T_0$. Second, it must be the case that $O_{add}$ adds $c$
since $O_{add}$ is the step {\sc ua} inserted into $U_0$ to make $c$
true. Third, $O_{add}$ is before $O_{need}$ in $T_1$, since $O_{add}$
is before $O_{need}$ in $U_1$ (by definition of {\sc ua}) and since
$T_1$ is a linearization of $U_1$.  Fourth, $O_{add}$ is after the
last deleter of $c$, $O_{del}$, in $T_1$, since $O_{add}$ is after
$O_{del}$ in $U_1$ (by definition of {\sc ua}) and since $T_1$ is a
linearization of $U_1$.  Therefore, the conditions of the TO-Extension
lemma hold and, thus, $T_1$ is a 1-step {\sc to}-extension of $T_0$.
{\em Q.E.D.}

\bigskip
\noindent
{\bf Totality Property} For every plan $U$ in $tree_{_{UA}}$, there
exists a non-empty set $\{ T_1, \ldots, T_m \}$ of plans in
$tree_{_{TO}}$ such that ${\cal L} (U) \; = \; \{ T_1, \ldots, T_m\}$.

\smallskip
\noindent 
{\bf Proof:} It suffices to show that if plan $U_1$ is a {\sc
  ua}-extension and plan $T_1$ is a linearization of $U_1$, then $T_1$
is a {\sc to}-extension. The proof is by induction on plan length.

\noindent
{\em Base case}: The statement trivially holds for plans of length 0.

\noindent
{\em Induction step}: Under the hypothesis that the statement holds
for plans of length $n$, we now prove that the statement holds for
plans of length $n+1$.  Suppose that $U_1$ is a {\sc ua}-extension of
length $n+1$ and $T_1$ is a linearization of $U_1$.  Let $U_0$ be a
plan such that $U_1$ is a 1-step {\sc ua}-extension of $U_0$.  By the
Mapping lemma, there exists a plan $T_0$ such that $T_0$ is a
linearization of $U_0$ and $T_1$ is a 1-step {\sc to}-extension of
$T_0$.  By the induction hypothesis, $T_0$ is a {\sc to}-extension.
Therefore, by definition, $T_1$ is also a {\sc to}-extension.  {\em
  Q.E.D.}

\bigskip
\noindent
{\bf Disjointness Property:} ${\cal L}$ maps distinct plans in
$tree_{_{UA}}$ to disjoint sets of plans in $tree_{_{TO}}$; that is,
if $U_1, U_2 \in tree_{_{UA}}$ and $U_1 \neq U_2$, then ${\cal L}
(U_1) \cap {\cal L} (U_2) \; = \; \{ \}$.

\smallskip
\noindent
{\bf Proof:} By the definition of $\cal L$, if $T_1, T_2 \in {\cal L}
(U)$, then $T_1$ and $T_2$ are at the same tree depth $d$ in
$tree_{_{TO}}$; furthermore, $U$ is also at depth $d$ in
$tree_{_{UA}}$.  Hence, it suffices to prove that if plans $U_1$ and
$U_2$ are at depth $d$ in $tree_{_{UA}}$ and $U_1 \neq U_2$, then
${\cal L} (U_1) \cap {\cal L} (U_2) \; = \; \{ \}$.

\noindent
{\em Base case}:  The statement vacuously holds for depth 0.

\noindent {\em Induction step}: Under the hypothesis that the
statement holds for plans at depth $n$, we prove, by contradiction,
that the statement holds for plans at depth $n+1$.  Suppose that there
exist two distinct plans, $U_1 \; = \; \langle \theta_1,
\prec_1\rangle$ and $U_2 \; = \; \langle \theta_2, \prec_2\rangle$, at
depth $n+1$ in $tree_{_{UA}}$ such that $T \in {\cal L} (U_1) \cap
{\cal L} (U_2)$.  Then (by definition of $\cal L$), $parent(T) \in
{\cal L} (parent(U_1))$ and $parent(T) \in {\cal L} (parent(U_2))$.
Since $parent(U_1) \neq parent(U_2)$ contradicts the induction
hypothesis, suppose that $U_1$ and $U_2$ have the same parent $U_0$.
Then, by the definition of {\sc ua} either {\em (i)} $\theta_1 \neq
\theta_2$ or {\em (ii)} $\theta_1 \; = \; \theta_2$ and $\prec_1 \neq
\prec_2$.  In the first case, since the two plans do not contain the
same set of plan steps, they have disjoint linearizations and, hence,
${\cal L} (U_1) \cap {\cal L} (U_2) \; = \; \{ \}$, which contradicts
the supposition.  In the second case, $\theta_1 \; = \; \theta_2$;
hence, both plans resulted from adding plan step $O_{add}$ to the
parent plan.  Since $\prec_1 \neq \prec_2$, there exists a plan step
$O_{int}$ that interacts with $O_{add}$ such that in one plan
$O_{int}$ is ordered before $O_{add}$ and in the other plan $O_{add}$
is ordered before $O_{int}$.  Thus, in either case, the linearizations
of the two plans are disjoint and, hence, ${\cal L} (U_1) \cap {\cal
  L} (U_2) \; = \; \{ \}$, which contradicts the supposition.
Therefore, the statement holds for plans at depth $n+1$.  {\em Q.E.D.}

\subsection{Completeness Proof for TO}

We now prove that {\sc to} is complete under a breadth first search
control strategy.  To do so, it suffices to prove that if there exists
a solution to a problem, then there exists a {\sc to}-extension that
is a compact solution. Before doing so, we prove the following lemma.

\bigskip
\noindent
{\bf Subplan Lemma:} Let totally ordered plan $T_0$ be a strict
subplan of a compact solution $T_s$.  Then there exists a plan $T_1$
such that $T_1$ is a subplan of $T_s$ and $T_1$ is a 1-step {\sc
to}-extension of $T_0$.

\smallskip
\noindent {\bf Proof:} Since $T_0$ is a strict subplan of $T_s$ and
$T_s$ is a compact solution, the set of false preconditions in $T_0$,
$G$, must not be empty.  Let $c \; = \;$ {\tt select-goal}$(G)$, let
$O_{need}$ be the step in $T_0$ with precondition $c$, and let
$O_{add}$ be the step in $T_s$ that achieves $c$.  Consider the
totally ordered plan $T_1 \; = \; \langle \theta_0 \cup \{ O_{add} \},
\prec_1\rangle$, where $\prec_1 \; \subset \; \prec_s$.  Clearly,
$T_1$ is a subplan of $T_s$.  Furthermore, by the TO-Extension Lemma,
$T_1$ is a 1-step extension of $T_0$ by {\sc to}.  To see this, note
that $O_{add}$ is ordered before $O_{need}$ in $T_1$ since it is
ordered before $O_{need}$ in $T_s$.  Similarly, $O_{add}$ is ordered
after the last deleter of $c$ in $T_0$ since any deleter of $c$ in
$T_0$ is a deleter of $c$ in $T_s$, and $O_{add}$ is ordered after the
deleters of $c$ in $T_s$.  Thus, the conditions of the TO-Extension
Lemma hold.  {\em Q.E.D.}

\bigskip
\noindent
{\sc TO} {\bf Completeness Theorem:} If plan $T_s$ is a totally
ordered compact solution, then $T_s$ is a {\sc to}-extension.

\smallskip
\noindent
{\bf Proof:} Let $n$ be the length of $T_s$.  We show that for all $k
\leq n$, there exists a subplan of $T_s$ with length $k$ that is a
{\sc to}-extension. This is sufficient to prove our result since any
subplan of exactly length $n$ is equivalent to $T_s$. The proof is by
induction on $k$.

\noindent {\em Base case}: If $k\; = \;0$ the statement holds since
the initial plan, which has length 0, is a subplan of any solution
plan.

\noindent {\em Induction step}: We assume that the statement holds for
$k$ and show that if $k < n$ the statement holds for $k+1$. By the
induction hypothesis, there exists a plan $T_0$ of length $k$ that is
a strict subplan of $T_s$.  By the Subplan Lemma, there exists a plan
$T_1$ that is both a subplan of $T_s$ and a 1-step {\sc to}-extension
of $T_0$.  Thus, there exists a subplan of $T_s$ of length $k+1$.
{\em Q.E.D.}

\subsection{Completeness Proof for UA}

We now prove that {\sc ua} is complete under a breadth-first search
strategy. The result follows from the search space correspondence
defined by ${\cal L}$ and the fact that {\sc to} is complete. In
particular, we show below that for any {\sc to}-extension $T$, there
exists a {\sc ua}-extension $U$ such that $T$ is a linearization of
$U$.  Since {\sc ua} produces only unambiguous plans, it must be the
case that if $T$ is a solution, $U$ is also a solution.  From this, it
follows immediately that {\sc ua} is complete.

\bigskip
\noindent {\bf Inverse Mapping Lemma:} Let $T_0 \; = \; \langle
\theta_0,\prec_{t0}\rangle$ be a totally ordered plan.  Let $T_1 \; = \;
\langle \theta_1,\prec_{t1}\rangle$ be a 1-step {\sc to}-extension of
$T_0$.  Let $U_0 \; = \; \langle \theta_0,\prec_{u0}\rangle$ be a plan
produced by {\sc ua} such that $T_0$ is a linearization of $U_0$.
Then there exists a plan $U_1$ such that $T_1$ is a linearization of
$U_1$ and $U_1$ is a 1-step {\sc ua}-extension of $U_0$.

\smallskip
\noindent {\bf Proof:} By the definition of {\sc to}, $\theta_1 \; =
\; \theta_0 \cup \{ O_{add}\}$, where $O_{add}$ added some $c$ that is
a false precondition of some plan step $O_{need}$ in $U_0$. Consider
$U_1\; = \; \langle \theta_1,\prec_{u1}\rangle$, where $\prec_{u1}$ is
a minimal subset of $\prec_{t1}$ such that:
\begin{itemize}
\item $\prec_{u0} \; \subseteq \; \prec_{u1}$, and
\item $(O_{add}, O_{need}) \in \prec_{u1}$, and
\item $(O_{del}, O_{add}) \in \prec_{u1}$, where $O_{del}$
is the last deleter of $c$ in $U_1$, and
\item no step in $U_1$ interacts with $O_{add}$
\end{itemize}
Since $\prec_{u1} \; \subseteq \; \prec_{t1}$, $T_1$ is a
linearization of $U_1$.  In addition, $U_1$ is an extension of $U_0$
since it meets the three conditions of the UA-Extension Lemma, as
follows. First, since $c$ must have been the goal selected by {\sc to}
in extending $T_0$, $c$ must likewise be selected by {\sc ua} in
extending $U_0$.  Second, $O_{add}$ adds $c$ since $O_{add}$ achieves
$c$ in $T_0$.  Finally, by construction, $\prec_{u1}$ satisfies the
third condition of the UA-Extension Lemma. {\em Q.E.D.}

\bigskip
\noindent
{\bf UA Completeness Theorem:} Let $T_s$ be a totally ordered compact
solution.  Then there exists a {\sc ua}-extension $U_s$ such that
$T_s$ is a linearization of $U_s$.

\smallskip
\noindent
{\bf Proof:} Since {\sc to} is complete, it suffices to show that if
$T_1$ is a {\sc to}-extension, then there exists a {\sc ua}-extension
$U_1$ such that $T_1$ is a linearization of $U_1$. The proof is by
induction on plan length.

\noindent
{\em Base case}: The statement trivially holds for plans of length 0.

\noindent
{\em Induction step}: Under the hypothesis that the statement holds
for plans of length $n$, we now prove that the statement holds for
plans of length $n+1$.  Assume $T_1$ is a {\sc to}-extension of length
$n+1$, and let $T_0$ be a plan such that $T_1$ is a 1-step {\sc
  to}-extension of $T_0$. By the induction hypothesis, there exists a
{\sc ua}-extension $U_0$ of length $n$ such that $T_0$ is a
linearization of $U_0$.  By the Inverse Mapping Lemma, there exists a
plan $U_1$ that is both a linearization of $T_1$ and a 1-step {\sc
  ua}-extension of $U_0$. Since $U_1$ is a 1-step {\sc ua}-extension
of $U_0$, it has length $n+1$.  {\em Q.E.D.}

\newpage
\acks{Most of the work present in this paper was originally described in two
conference papers \cite{ijcai91,kr92}.  We thank Andy Philips for his
many contributions to this project.  He wrote the code for the
planners and helped conduct the experiments.}



\bibliography{torpor}
\bibliographystyle{theapa}

\end{document}

