In this section we define two simple planning algorithms. The first algorithm, shown in Figure 1, is TO, a total-order planner motivated by Waldinger's regression planner (Waldinger,1975), Interplan (Tate,1974), and Warplan (Warren, 1974). Our purpose here is to characterize the search space of the TO planning algorithm, and the pseudo-code in Figure 1 accomplishes this by defining a nondeterministic procedure that enumerates possible plans. (If the plans are enumerated by a breadth-first search, then the algorithms presented in this section are provably complete, as shown in Appendix A.)
Figure 1: The TO planning algorithm
Figure 2: How TO extends a plan: Adding 
to plan 
generates three alternatives.
TO accepts an unfinished plan, P, and a goal set, G, containing preconditions which are currently not true. If the algorithm terminates successfully then it returns a totally ordered solution plan. Note that there are two choice points in this procedure: operator selection and ordering selection. The procedure does not need to consider alternative goal choices. For our purposes, the function select-goal can be any deterministic function that selects a member of G.
As used in Step 4, the last deleter of a precondition c for a
step 
is defined as follows. Step 
is the last
deleter of c if deletes c, is before
, and there is no other deleter of c between and
. In the case that no step before deletes c,
the first step is considered to be the last deleter.
Figure 2 illustrates TO's plan extension process.
This example assumes that steps A and B do not add or delete
c. There are three possible insertion points for in plan P,
each yielding an alternative extension.
The second planner is UA, a partial-order planner, shown in Figure 3. UA is similar to TO in that it uses the same procedures for goal selection and operator selection; however, the procedure for ordering selection is different. Step 4 of UA inserts orderings, but only ``interacting'' steps are ordered. Specifically, we say that two steps interact if they are unordered with respect to each other and either:
Figure 4 illustrates UA's plan extension process. As
in Figure 2, we assume that steps A and B do not
add or delete c; however, step A and interact with
respect to some other condition. This interaction yields two
alternative plan extensions: one in which is ordered before
A and one in which is ordered after A.
Figure 3: The UA planning algorithm
Figure 4: How UA extends a plan: Adding to plan P
generates two alternatives. The example assumes
that
interacts with step A.
Since UA orders all steps which interact, the plans that are
generated have a special property: each precondition in a plan is
either necessarily true or necessarily false. We call
such plans unambiguous. This property yields a tight
correspondence between the two planners' search spaces. Suppose UA is given the unambiguous plan U and TO is given the plan
T, where T is a linearization of U. Let us consider the
relationship between the way that UA extends U and TO
extends T. Note that the two planners will have the same set of
goals since, by definition, each goal in U is a precondition that is
necessarily false, and a precondition is necessarily false if and only
if it is false in every linearization. Since the two plans have the
same set of goals and since both planners use the same goal selection
method, both algorithms pick the same goal; therefore, is
the same for both. Similarly, both algorithms consider the same
library operators to achieve this goal. Since T is a linearization
of U, and is the same in both plans, both algorithms find
the same last deleter as well.
When TO adds a step to a plan, it orders the new step with respect to
all existing steps. When UA adds a step to a plan, it orders
the new step only with respect to interacting steps. UA
considers all possible combinations of orderings which eliminate
interactions; hence, for any plan produced by TO, UA
produces a corresponding plan that is less-ordered or equivalent.
The following sections exploit this tight correspondence between the search spaces of UA and TO. In the next section we analyze the relative sizes of the two planners' search spaces, and later we compare the number of plans actually generated under different search strategies.