Total-order and partial-order planning: A comparative analysis

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 speci c planners that can be directly compared. We show that there are some subtle assumptions that underly the wide-spread intuitions regarding the supposed e ciency 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 e cient planners. 1