Journal of Artificial Intelligence Research 2 (1994) 227-262
ReSubmitted 10/94; published 12/94
(c) 1993 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.
Total-Order and Partial-Order Planning: <BR>A Comparative
Analysis
Next: Introduction
Total-Order and Partial-Order Planning:
A Comparative Analysis
Steven Minton (minton@ptolemy.arc.nasa.gov)
John Bresina (bresina@ptolemy.arc.nasa.gov)
Mark Drummond (med@ptolemy.arc.nasa.gov)
Recom Technologies
NASA Ames Research Center, Mail Stop: 269-2
Moffett Field, CA 94035 USA
Abstract:
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.
Table of Contents:
The PostScript version of this paper is
available.
Return to the
JAIR home page.