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, UA, is never larger than the search space of a total-order planner, TO. Indeed for certain problems, UA's search space is exponentially smaller than TO's. Since UA pays only a small polynomial time increment per node over 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, 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. UA and 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 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.