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.
Barret et al.
(1991) and
Barrett and Weld (1994)
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
(Korf, 1987), 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 
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 
, where, in each
problem, the goals are a subset of 
, the
initial conditions are 
, and each operator
has precondition 
, adds 
, and
deletes 
. It follows that if a solution in contains
operators 
and 
where 
, then must precede
. 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
(Kambhampati, 1994a,
1994b,
1994c) that analyze the
design space of partial-order planners, including the UA planner
presented here. Kambhampati compares UA, Tweak, SNLP
(McAllester &
Rosenblitt, 1991), UCPOP
(Penberthy & Weld, 1992), and several other planners
along a variety of dimensions. He presents a generalized schema for
partial order planning algorithms (Kambhampati, 1994c) and shows that the
commitment strategy used in 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 (Kambhampati, 1994a),
showing how the differences in commitment strategies affects the
efficiency of the planning process. He distinguishes two separate
components of the branching factor, 
and 
, 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 , sometimes they also decrease
, 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 (1993) have compared the relative utility of 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.