  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.
