Planning can be characterized as search through a space of possible plans. A total-order planner searches through a space of totally ordered plans; a partial-order planner is defined analogously. We use these terms, rather than the terms ``linear'' and ``nonlinear'', because the latter are overloaded. For example, some authors have used the term ``nonlinear'' when focusing on the issue of goal ordering. That is, some ``linear'' planners, when solving a conjunctive goal, require that all subgoals of one conjunct be achieved before subgoals of the others; hence, planners that can arbitrarily interleave subgoals are often called ``nonlinear''. This version of the linear/nonlinear distinction is different than the partial-order/total-order distinction investigated here. The former distinction impacts planner completeness, whereas the total-order/partial-order distinction is orthogonal to this issue (Drummond & Currie, 1989; Minton et al., 1991a).
The total-order/partial-order distinction should also be kept separate from the distinction between ``world-based planners'' and ``plan-based planners''. The distinction is one of modeling: in a world-based planner, each search state corresponds to a state of the world and in a plan-based planner, each search state corresponds to a plan. While total-order planners are commonly associated with world-based planners, such as STRIPS, several well-known total-order planners have been plan-based, such as Waldinger's regression planner (Waldinger, 1975), Interplan (Tate, 1974) and Warplan (Warren, 1974). Similarly, partial-order planners are commonly plan-based, but it is possible to have a world-based partial-order planner (Godefroid & Kabanza, 1991). In this paper, we focus solely on the total-order/partial-order distinction in order to avoid complicating the analysis.
We claim that the only significant difference between partial-order
and total-order planners is planning efficiency. It might be argued
that partial-order planning is preferable because a partially ordered
plan can be more flexibly executed. However, execution flexibility
can also be achieved with a total-order planner and a post-processing
step that removes unnecessary orderings from the totally ordered
solution plan to yield a partial order
(Backstrom, 1993;
Regnier & Fade, 1991;
Veloso, Perez, & Carbonell, 1990).
The polynomial time
complexity of this post-processing is negligible compared to the
search time for plan generation.
Hence, we believe that execution
flexibility is, at best, a weak justification for the supposed
superiority of partial-order planning.
In the following sections, we analyze the relative efficiency of partial-order and total-order planning by considering a total-order planner and a partial-order planner that can be directly compared. Elucidating the key differences between these planning algorithms reveals some important principles that are of general relevance.