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 (1975) 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 (Minton, Bresina & Drummond, 1991a; Barrett & Weld, 1994; Kambhampati, 1994c). 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 (Minton et al.,1991a; 1992) 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 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 necessarily hold for all partial-order planners, but depend critically on the construction of the planning space.