Commitment Strategies in Planning: A Comparative Analysis

1 Introduction

Since the introduction of non-linear planning over a decade ago (Sacerdoti, 1977), the superiority of non­ linear planning over linear planning has been tacitly ac­ knowledged by the planning community. However, there has been little analysis supporting this intuition. In this paper, we focus on one aspect of non-linear planning: the use of partially ordered plans rather than totally ordered plans. The idea has been that a partially ordered plan allows a planner to avoid premature commitment to an incorrect operator ordering, and thus improve efficiency. We analyze the costs and benefits of using partially or­ dered and totally ordered plans to implement different commitment strategies for operator ordering.

Why should we be concerned about an issue that is over a decade old? Since modern planners are not very different from early planners in their basic approach, the issue is still with us. In this paper, we address the is­ sue by first considering a simple total-order planner, and from this planner we construct a partial-order planner which can have an exponentially smaller search space. Next, we show that a second, independent source of power is available to a partial-order planner, namely, the ability to make more informed planning decisions. The relationship between our two planners demonstrates the potential utility of a least commitment strategy. We also show that a partial-order planner based on Chapman's {1987) Tweak can be less efficient than our total-order planner, and we examine why this can happen.

2 Background

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 plan­ ner is defined similarly. We introduce these definitions because the terms "linear" and "non-linear" are over­ loaded. For example, some authors have used the term "non-linearity" when focusing on the issue of goal or­ dering. That is, some "linear" planners, when solv­ ing a conjunctive goal, require that all subgoals of one conjunct be achieved before subgoals of the oth­ ers; hence, planners that can arbitrarily interleave sub­ goals are often called "non-linear". This version of the linear/non-linear distinction is different than the partial­ order/total-order distinction investigated here. The for­ mer distinction impacts planner completeness, whereas the total-order/partial-order distinction is orthogonal to this issue (Drummond & Currie, 1989).

We claim that the only significant difference between partial-order and total-order planners is planning effi­ ciency. It might be argued that partial-order planning is preferable because a partially ordered plan can be more flexibly executed. However, this 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. The polynomial time complexity of this post-processing is negligible compared to the search time for plan gen­ eration (Veloso et al., 1990). Hence, we believe that execution flexibility is, at best, a weak justification for the supposed superiority of partial-order planning.

In order to analyze the relative efficiency of partial­ order and total-order planning, we begin by considering a total-order planner and a partial-order planner that can be directly compared. By elucidating the key differ­ ences between these planning algorithms, we reveal some important principles that are of general relevance.

3 Terminology

A plan consists of an ordered set of steps, where each step is a unique operator instance. Plans can be totally ordered, in which case every step is ordered with respect to every other step; or partially ordered, in which case steps can be unordered with respect to each other. We assume that a library of operators is available, where each operator has preconditions, deleted conditions, and added conditions; each deleted condition must be a pre­ condition. Each condition must be a non-negated propo­ sitional literal. Later, we consider how our results can be extended to more expressive languages.

A linearization of a partially ordered plan is a total order over the plan's steps consistent with the existing partial order. In a totally ordered plan, a precondition of a plan step is true if it is added by an earlier step and not deleted by any intervening step. In a partially ordered plan, a step's precondition is possibly true if there exists a linearization in which it is true, and a step's precondition is necessarily true if it is true in all linearizations. A step's precondition is necessarily false if it is not possibly true.

A planning problem is defined by a start state and goal state pair, where a state is a set of propositions. For con­ venience, we represent a problem as a two-step initial plan, where the first step adds the start state propo­ sitions and the preconditions of the final step are the goal state propositions. The planning process starts with this initial plan and searches through a space of possi­ ble plans. A successful search terminates with a solution plan, i.e., a plan in which all steps' preconditions are nec­ essarily true. The search space can be characterized as a tree, where each node corresponds to a plan and each arc corresponds to a plan transformation. Each trans­ formation incrementally extends (i .e., refines) a plan by adding additional steps or orderings. Thus, each leaf in the search tree corresponds either to a solution plan or a dead-end, and each intermediate node corresponds to an unfinished plan which can be further extended.

4 A Tale of Two Planners

In this section we define two simple planning algorithms. The first algorithm, shown in figure 1, is TO, a total­ order planner motivated by Warren (1974), Tate (1974), and Waldinger (1975). TO accepts an unfinished plan, P, and a goal set, G, containing the preconditions of steps in P which are currently false. If the algorithm terminates successfully then it returns a totally-ordered solution plan. Note, there are two backtracking points in this procedure: operator and ordering selection. As used in step 4, the last deleter of a precondition c for a step Oneed is a step Odel before Oneed which deletes c, such that there is no other deleter of c between Ode! and Oneed· The first plan step is considered the last deleter if it does not add c and no other step before Oneed deletes c.

Our purpose here is to characterize the search space of the TO planning algorithm, and the pseudo-code we give does this by defining a depth-first procedure for enu­ merating possible plans. All the algorithms described in this paper can also be implemented as breadth-first procedures in the obvious way, and in that case, all are provably complete (Minton et al., 1991).

The second planner is UA, a partial-order planner, shown in figure 2. UA is similar to TO in that it uses the same procedures for goal selection and operator se­ lection, and unlike TO in that its solution plans are par­ tially ordered. Step 4 of UA orders steps based on "inter­ actions". Two steps in a plan are said to interact if they TO(P,G)

1. Termination: H G is empty, report success and stop.
2. Goal selection: Let c be a goalinG, and let Oneed be the plan step for which c is a precondition.
3. Operator selection: Let Oo.dd be an <;>perator in the library that adds c. H there is no such o .. dd, then ter­ minate and report failure. Backtrack point: all such operators must be considered for completeness.
4. Ordering selection: Let Odel be the last deleter of c. Insert O .. dd somewhere between Ode1 and Oneed, call the resulting plan P'. Backtrack point: all such positions must be considered for completeness.
5. Update goal set: Let G' be the set of preconditions in P' that are not true.
6. Recursive invocation: TO(P', G').

Figure 1: The TO Planning Algorithm

are unordered with respect to each other and there exists a precondition c of one step that is added or deleted by the other . 1 The significant difference between UA and TO lies in step 4: TO orders the new step with respect to all others, whereas UA adds only those orderings that are required to eliminate interactions. It is in this sense that UA is less committed than TO.

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 P,.a and that TO is given Pto, one of its linearizations. P,.a and Pto have the same set of goals since, by definition, each goal in P,.a is necessarily false and if a precondition is necessarily false, it is false in every linearization.

Consider the relationship between the way that UA extends P,.a and TO extends Pto· 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, Oneed is the same for both. Similarly, both algorithms consider the same library op­ erators to achieve this goal. Since Pto is a linearization of P,. .. , and Oneed is the same in both plans, both algo­ rithms find the same last deleter as well. 2 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, so for any plan produced by TO, UA produces a corresponding plan that is less-ordered or equivalent. The following sections exploit this tight cor­ respondence between the search spaces of UA and TO. In the next section we compare the entire search spaces of UA and TO, and later we compare the number of nodes actually visited under different search strategies.

1 Note, a step that deletes c interacts with one that adds or deletes c according to this definition because a step's deleted conditions are required to be a subset of its preconditions.

2 There is a unique last deleter in an unambiguous plan since two steps which delete the same condition interact , and thus, must be ordered.

UA(P,G)

1. Termination: If G is empty, report success and stop.
2. Goal selection: Let c be a goalinG, and let Oneed be the plan step for which c is a precondition.
3. Operator selection: Let Oudd be an operator in the library that adds c. If there is no such Oudd, then ter­ minate and report failure. Backtrack point: all such operators must be considered for completeness.
4. Ordering selection: Let Odel be the last deleter of c. Order Oudd after Odel and before Oneed· Repeat until there are no interactions:
5. o Select a step 0;,., that interacts with Oudd·
6. o Order 0;,.1 either before or after Oudd· Backtrack point: both orderings must be considered for completeness.

Let P' be the resulting plan.

1. Update goal set: Let G' be the set of preconditions in P' that are necessarily false.
2. Recursive invocation: UA(P', G').

Figure 2: The UA Planning Algorithm

5 Search Space Comparison

Recall that a search space can be characterized as a tree. We denote the search space of TO by tree, 0 , and similarly the search space of UA by treeua· We show that for any given problem, tree10 has at least as many nodes as treeua· This is done by proving the existence of a function £ which maps nodes in treeua to sets of nodes in tree10 that satisfies the following two conditions.

1. For every node u in treeua, there exists a non-empty set {t1, ... , tm} of nodes in treeto such that C(u) = {t1,. · ·, tm}·
2. £ maps distinct nodes in treeua to disjoint sets of nodes in tree10; that is, if u1, u2 E treeua and u1 =I u2, then £(u1) n £(u2) = {}.

Let's examine why the existence of an £ with these two properties is sufficient to prove that the size of UA's search tree is no greater than that of TO. Figure 3 pro­ vides a guide for the following discussion. Intuitively, we can use £ to count nodes in the two search trees. For each node counted in treeua, we use £ to count a non-empty set of nodes in tree10 · The first property of £ means that every time we count a node in treeua, we count at least one node in tree10 ; this implies that I treeua I $ I:uetreeu I C(u) I· Of course, we must further show that each node counted in treeto is counted only once; this is guaranteed by the second property of £,which implies that I:uetreeu I C(u) j ~ I ~reeco I· Thus, the conjunction of the two propert1es 1mphes that I treeua I $ I treeto I·

We can define a function £ that has these two prop­ erties as follows. Let u be a node in treeua, let t be a node in tree10, and let parent be a function from a node to its parent node. Then t E C(u) if and only if the plan at t is a linearization of the plan at u and either both u and t are root nodes of their respective search trees, or par~nt(t) E C(parent(u)). Intuitively,£ maps a node u in treeua to all linearizations which share com­ mon derivation ancestry. This is illustrated in figure 3, where for each node in treeua a dashed line is drawn to the corresponding set of nodes in treeto·

We can show that £ satisfies both of the properties by induction on the depth of the search trees. Detailed proofs are in the appendix. To prove the first property, we show that for every plan contained in treeua, all lin­ earizations of that plan are contained in treeco· This can be proved by examining the tight correspondence between the search trees of UA and TO. To prove the second property, we show that £ maps nodes u1 and u2 at the same depth in treeua to disjoint sets of nodes in tree10: if u1 and u2 do not have the same parent, then the property holds; if they have the same parent, then the plans at u1 and u2 are distinct (by the definition of UA), in which case their linearizations are disjoint.

How much smaller is treeua than tree,0 ? The map­ ping described above provides an answer. For each node u in treeua there are I £(u) I distinct nodes in TO, where I C(u) I is the number of linearizations of the plan con­ tained at node u. The exact number depends on how unordered the plan at node u is. A totally unordered plan has a factorial number oflinearizations and a totally ordered plan has only a single linearization. Thus, the only time that the size of treeua equals the size of treeto is when every plan in treeua is totally ordered; other­ wise, treeua is strictly smaller than tree,0 , and possibly exponentially smaller.

6 Time Cost Comparison

While the size of UA's search tree is possibly exponen­ tially smaller than that of TO, it does not follow that UA is necessarily more efficient. Efficiency is determined by two factors: the time cost per node during search (dis­ cussed in this section) and the size of the subtree actually explored to find a plan (discussed below).

In this section we show that while UA can indeed take more time per node, the extra time is relatively small and grows only polynomially with the size of the plan. In our analysis, the size of the plan is simply the number of steps in the plan. 3 In comparing the relative efficiency of UA and TO, we first consider the number of times that each algorithm step is executed per node visited and then consider the time complexity of each step.

For both UA and TO, steps 1 and 2 are each executed once per node, and the number of executions of step 3 per node is bounded by a constant (the number of operators in the library). Analyzing the number of times step 4

3 We disregard operator size and the number of conditions in any given "state", since we assume these are bounded by a constant for a given domain. An analysis that includes these factors does not affect our conclusion.

is executed might seem more complicated, since it may be executed many times at an internal node and is not executed at a leaf node. However, notice that a new node is generated each time step 4 is executed. Consequently, step 4 is executed once per node. Step 5 is also executed once per node since it always follows step 4. Thus, both algorithms execute steps 1, 2, 4, and 5 once per node, and step 3 is executed 0(1) times per node.

In examining the costs for each step, we first note that for both algorithms, steps 1, 2, and 3 can be accom­ plished in 0(1) time. The cost of step 4, the ordering step, is different for TO and UA. In TO, step 4 is accom­ plished by inserting the new operator, Oadd, somewhere between Odel and Oneed· If the possible insertion points are considered starting at Oneed and working towards Odel, then step 4 takes constant time, since each inser­ tion constitutes one execution of the step. On the other hand, step 4 in UA involves carrying out interaction de­ tection and elimination. This step can be accomplished in 0( e) time, where e is the number of edges in the graph required to represent the partially ordered plan (Minton et al., 1991). If n is the number of steps in the plan, then in the worst case, there may be O(n 2 ) edges in the graph, and in the best case, O(n) edges. To carry out step 5 may require examining the entire plan, and thus, for UA, takes O(e) time and for TO, O(n) time.

To summarize, UA pays the penalty of having a more complex ordering procedure (step 4), as well as the penalty for having a more expressive plan language (a partial order as compared to total order) which is re­ flected in the extra cost of step 5. Overall, UA requires O(e) time per node, whereas TO only requires O(n) time.

7 Overall Efficiency Comparison

The previous sections compared TO and UA in terms of relative search space size and relative time cost per node. The extra processing time required by UA for each node would appear to be justified since its search space may contain exponentially fewer nodes. To complete our analysis, we must consider the number of nodes actually visited by each algorithm under a given search strategy.

Consider a breadth-first search technique that explores the entire search tree up to the depth of the smallest solution plan. By the search tree correspondence estab­ lished earlier, both algorithms find the first solution at the same depth. Thus, TO explores all linearizations of the plans explored by UA. We can formalize the overall efficiency comparison as follows. For a node u in treeua, we denote the number of steps in the plan at u by nu, and the number of edges by eu. Then for each node u that UA generates, UA incurs time cost O(eu)i whereas, TO incurs time cost O(nu) · I.C(u) I, where I.C(u) I is the number of linearizations of the plan at node u. There­ fore, the ratio of the total time costs of TO and UA is as follows, where bf(treeua) denotes the subtree considered by UA under breadth-first search.

The cost comparison is not so clear-cut for depth-first search, since TO does not necessarily explore all lineariza­ tions of the plans explored by UA. A node in a search tree is said to succeed if it is on a path to a solution, oth­ erwise, it is said to faiL When a node in UA's search tree fails, all corresponding nodes for TO also faiL If a UA node succeeds, then some subset of the corresponding TO nodes succeed. If, under a depth-first strategy, UA and TO generate corresponding plans in the same order, then (i) for every failed node u that UA generates, TO generates all nodes in .C(u) and (ii} for every UA node u that succeeds, TO generates at least one node in .C(u). However, in actuality, UA and TO need not generate cor­ responding plans in the same order. In this case, while the search spaces correspond, there is no guarantee that the planners will explore corresponding subtrees. N ev­ ertheless, the relative size of the subtree explored by TO under depth-first search can be ezpected to be propor­ tional to the average size of I .C I, since the relative size of TO's full search space is proportional to this value.

This intuition is supported by empirical experimen­ tation with depth-limited versions of UA and TO. In a blocksworld domain where all steps interact, UA tends to explore the same number of nodes as TO under depth­ first search. On another version of the blocksworld, where the probability of two randomly selected steps in­ teracting is approximately 0.5, UA tends to explore many fewer nodes. For example, on a representative problem, with a solution depth (and depth-bound) of eight, TO ex­ plored 8.0 times as many nodes as UA. This ratio tends to increase with solution depth; for a problem with so­ lution depth of nine, TO explored 15.4 times as many nodes. Although UA required more time per node, in terms of total search time, UA ran 4.6 times faster than TO on the first problem and 9.0 times faster than TO on the second problem. The results under breadth-first search were also as expected: when all steps interact, UA and TO search exactly the same number of nodes, and when relatively few steps interact, UA explores many fewer nodes than TO. For example, in our low-interaction version of the blocksworld, on a problem where the first solution is found at depth seven, TO explored 4.8 times as many nodes as UA, and UA ran 2.8 times faster. We caution that this is a small-scale study, intended only to illustrate our theoretical results.

The performance of TO can be improved with the ad­ dition of dependency-directed backtracking. Although space does not permit analysis of this search strategy, we note that by using dependency-directed backtrack­ ing, TO will behave almost identically to UA. Specifically, when TO backtracks to a node, a dependency analysis can indicate whether or not the failure below was inde­ pendent of the ordering decision at that node. Of course, this dependency analysis increases the cost per node.

8 Heuristic Advantages

It is often claimed that partial-order planners are more efficient due to their ability to make more informed or­ dering decisions. So far, we have shown that a partial­ order planner can be more efficient simply because its search tree is smaller, independent of its ability to make more informed decisions. We now show that a partial­ order planner does in fact have a "heuristic advantage" as well.

In the UA planning algorithm, step 4 arbitrarily or­ ders interacting steps. Similarly, step 4 of TO arbitrarily chooses an insertion point for the new step. It is easy to see, however, that some orderings should be tried be­ fore others in a heuristic search. This is illustrated by figure 4, which compares UA and TO on a particular prob­ lem. 'The key in the figure describes the relevant condi­ tions of the library operators, where preconditions are indicated to the left of an operator and added condi­ tions are indicated to the right (there are no deletes). For brevity, the start step and final step are not shown. Consider the node in treeu4 containing the plan with unordered steps 0 1 and 0 2 · When UA introduces 0 3 to achieve precondition p of 0 1 , step 4 of UA will order 0 3 with respect to 0 2 , since these steps interact. However, it makes more sense to order 02 before 0 3 , since 0 2 achieves precondition q of 0 3 · This illustrates a simple planning heuristic: "prefer the orderings that yield the fewest false preconditions". This strategy is not guaran­ teed to produce the optimal search or plan, but tends to be effective and is commonly used.

Notice, however, that TO cannot exploit this heuristic as effectively as UA because it must prematurely commit to an ordering on 0 1 and 0 2 · Due to this inability to postpone an ordering decision, TO must choose arbitrar­ ily between the plans 0 1 - 0 2 and 0 2 - 0 1 , before the impact of this decision can be evaluated.

In the general case, UA is more informed than TO by any heuristic h that satisfies the following property: for any UA node u and corresponding TO node t, h(u) !: h(t); that is, a partially ordered plan must be rated at least as high as any of its linearizations. (Note that for unambiguous plans the heuristic function in our example satisfies this property.) When we say that UA is more informed than TO, we mean that under h, some child of u is rated at least as high as every child oft. This is true since every child of t is a linearization of some child of

MT(P,G)

1. Termination: H G is empty, report success a.nd stop.
2. Goal selection: Let c be a. goal in G, a.nd let Oneed be the plan step for which cis a. precondition.
3. Operator selection: Let Oadd be either a. plan step possibly before Oneed that adds c or an operator in the library that adds c. H there is no such Oadd, then ter­ minate and report failure. Backtrack point: all such operators must be considered for completeness.
4. Ordering selection: Order O,.,u before Oneed· Repeat until there a.re no steps possibly between Oadd a.nd Oneed which delete c:

Let Ode1 be such a. step; choose one of the following ways to make c true for Oneed

• o Order Ode1 before Oa<l<l·
• o Order Ode1 after Oneed·
• o Choose a. step O~c,.; 11 ht that adds c that is possibly between Ode1 and Oneed; order it after Ode1 a.nd
• before Oneed· Backtrack point: all alternatives must be
• considered for completeness.

Let P' be the resulting plan.

1. Update goal set: Let G' be the set of preconditions in P' that are not necessarily true.
2. Recursive invocation: MT(P',G').

Figure 5: A Propositional Planner based on the MTC

u, and therefore no child oft can be rated higher than a child of u. Furthermore, there may be a child of u such that none of its linearizations is a child oft, and therefore this child of u can be rated higher than every child of t. Assuming that his a good heuristic, this means that UA can make a better choice than TO.

9 A Less Committed Planner

We have shown that UA, a partial-order planner, has cer­ tain computational advantages over a total-order plan­ ner, TO, due to its ability to delay commitments. How­ ever, there are planners that are less committed than UA. In fact, there is a continuum of commitment strate­ gies that we might consider. At the extreme liberal end of the spectrum is the strategy of maintaining a totally unordered set of steps during search, until there exists a linearization that is a solution plan.

Compared to many well-known planners, UA is con­ servative since it requires each plan to be unambiguous. This is not required by NOAH (Sacerdoti, 1977), NonLin (Tate, 1977), and Tweak (Chapman, 1987), for exam­ ple. How do these less-committed planners compare to UA and TO? One might expect a less-committed planner to have the same advantages over UA that UA has over TO. However, this is not necessarily true. For exam­ ple, we show in this section that Tweak's search tree is larger than TO's in some circumstances. 4 See figure 5 for a propositional planner, MT, based on Chapman's (1987) Modal Truth Criterion, the formal statement that char­ acterizes Tweak's search space.

The proof that UA's search tree is no larger than TO's search tree rested on the two properties of £ elaborated in section 5. By investigating the relationship between MT and TO, we found that the second of these proper­ ties does not hold for MT, and its failure illustrates how MT can explore more nodes than TO (and consequently UA) on certain problems. The second property guaran­ tees that UA does not generate "overlapping" plans. The example in figure 6 shows that MT fails to satisfy this property because it can generate plans that share com­ mon linearizations, leading to considerable redundancy in the search. The figure shows three steps, 0 1, 0 2, and 03, where each 0; has precondition p;, and added condi­ tions g;, Pll P2 1 and P3· The final step has preconditions g1, g2, and g3, but the start and final steps are not shown in the figure. The node at the top of the figure contains a plan constructed by MT where goals g1, g2 , and g3 have been achieved, but p11 P2, and p3 remain to be achieved. Subsequently, in solving the precondition p1, MT gener­ ates plans which share the linearization 0 3 --+ 0 2 --+ 0 1 (among others). In comparison, both TO and UA only generate the plan 03 --+ 02 --+ 0 1 once. In fact, it is simple to show that, under breadth-first search, MT gen­ erates many more nodes than TO on this example, due to redundancy (and also more than UA, by transitivity).

4 We use Tweak for this comparison because, like UA a.nd TO, it is a. formal construct rather than a. realistic planner, and therefore more easily analyzed.

This example shows that although one planner may be less committed than another, it is not necessarily more efficient. In general, a partially ordered plan can repre­ sent a large set of linearizations, but of course, there can be many more partial orders over a set of steps than there are linearizations. A general lesson from this is that a search space should be defined so as to minimize redun­ dancy whenever possible. In particular, partially ordered plans with linearization overlap should be avoided.

10 Concluding Remarks

By focusing our analysis on the single issue of operator ordering commitment, we were able to carry out a rig­ orous comparative analysis of two planners. In contrast, most previous work has focused on the definition of a sin­ gle planner, and comparative analyses have been rare. 5

6 Soderland and Weld {1991) have very recently, a.nd inde­ pendently, carried out a. comparative analysis of two planners corroborating some of the results reported in Section 5. '

We have shown that the search space of a partial-order planner, UA, is never larger than the search space of a total-order planner, TO. Indeed for certain problems, UA's search space is exponentially smaller than TO's. Since UA pays only a small polynomial time increment per node over TO, it is generally more efficient. We have also demonstrated that UA can be more informed than TO under a certain class of heuristic evaluation func­ tions. Lastly, we have shown that partial-order planners do not necessarily have smaller search spaces; in particu­ lar, we demonstrated that a Tweak-like planner can have a larger search space than TO on some problems.

How general are these results? While our analysis has considered only two specific planners, the tradeoffs that we have examined are of general relevance. We believe these tradeoffs are manifested in other styles of planner, including temporal-projection planners {Drum­ mond, 1989) and STRIPS-like planners such as Prodigy (Minton et al., 1989). We conjecture that one can define a partial-order version of Prodigy, for instance, which corresponds to the original in the same way that UA cor­ responds to TO. The key difficulty in analyzing possible correspondences between such planners is establishing a mapping between the planners' search trees.

What about more expressive operator languages? We have defined TO and UA to use propositional operators, but many problems demand operators with variables, conditional effects, or conditional preconditions. UA and TO can be extended to use such operators so that the search space correspondence still holds. In such cases the relative advantages of UA over TO will be preserved as long as the time cost of detecting possible interactions remains relatively small. For example, if library opera­ tors have variables, but are fully instantiated during the operator selection step, then our analysis holds without modification. The work required to demonstrate step in­ teraction tends to increase with the expressiveness of the operator language used (Dean & Boddy, 1988; Hertzberg & Horz, 1989); nevertheless, we believe the cost of de­ tecting interactions can often be kept low by using a conservative definition of step interaction.

The general lesson from this work is that partial-order plc;m?in~ can be ?etter than tota~-or.der planning, but th1s 1sn t necessanly so. When destgnmg a partial-order planner, one must understand the effect of plan rep­ resentation on the planner's search space, the cost in­ curred per node, and sources of possible redundancy in the search space.

Acknowledgements: The TORPOR group thanks Mark Bod?y for helping start this project, and Andy Philips, for 1mplementing and helping design the algorithms. Thanks also to our various reviewers.

A Proof of Correspondence £

Definition: A plan is a pair < (}, -<>, where (} is a set of steps, and -< is the "before" relation on(}, i.e.~ -< is a strict partial order on 9. Notationally, 0 1 -< 0 2 if and only if (011 02) E-<.

Defi.nition: A plan P' is a 1-step extension of a plan P w1th respect to a planning algorithm, if P' can be produced from P in one invocation of the algorithm.

Property 1: For every node u in treeua, there exists a non-empty set {t1, . . . , tm} of nodes in treet0 such that .C ( U) = { t 1, ··· , tm}.

Proof: It suffices to show that if a plan P is contained in a node u at depth din treeua, then each linearization of P is contained in some node t at depth d in treet 0 , such that t E .C(u).

Base case: The statement trivially holds for depth 0.

Induction step: Under the hypothesis that the statement holds for depth n, we now prove, by contradiction, that the statement holds for depth n + 1. Suppose that there exists a node u with plan Pu =< 0, -<u> at depth n + 1 in treeua such that Pt =< 0, -<t> is a linearization of Pu and there is no node t containing Pt at depth n + 1 in treeto such that t E .C(u). Let P~ =< 0', -<~>be at node u', the parent of u; i.e., Pu is a 1-step extension of P~ with respect to UA. By the definition of UA, 0 = 0' U { Oadd}, where Oadd added some c that is a precondition of some plan step Oneed that is necessarily false in P~. Hence, Pf =< 0', -<~> is a linearization of P~, where -<~= {(Oi, Oj) I (Oi, Oj) E-<t and Oi, Oi "f; Oadd}; that is, Pf is the result of removing Oadd from Pt. Thus, by the induction hypothesis, there exists a node t' at depth n in treeto that contains Pf, such that t' E .C( u').

For the supposition to hold, it must be the case that Pt is not a 1-step extension of Pf with respect to TO. Since c is necessarily false in P~, it is false in Pf, one of its linearizations. Likewise, since cis necessarily true in Pu, it is also true in Pt. Let Odel be the last deleter of c in Pf. Then, since P£ is a linearization of P~, Odel must be a last deleter of c in P~. Therefore, in Pu (by definition of UA), and hence in Pt (by definition oflinearization), Odel is ordered before Oadd, which is ordered before Oneed· Hence, Pt is a 1-step extension of P£ with respect to TO, which contradicts the supposition. Therefore, the statement holds for nodes at depth n + 1. Q.E.D.

Property 2: .C maps distinct nodes in treeua to disjoint sets of nodes in treetoi that is, if u1, u2 E treeua and u1 # u2, then .C(u1) n.C(u2) = {}.

Proof: By the definition of .C, if t1, t2 E .C(u), then t1 and t 2 are at the same tree depth d in treetoi further­ more, u is also at depth din treeua· Hence, it suffices to prove that if nodes u1 and u2 are at depth d in treeua and u1 # u2, then .C(u1) n .C(u2) = {}.

Base case: The statement vacuously holds for depth 0. Induction step: Under the hypothesis that the statement holds for depth n, we prove, by contradiction, that the statement holds for nodes at depth n + 1. Suppose that there exist two distinct nodes, u1 and u2, at depth n + 1 in treeua such that t E .C(u1) n .C(u2). Then (by defini­ tion of .C), parent(t) E .C(parent(u1)) and parent(t) E .C(parent(u2)). Since parent(u1) # parent(u2) contra­ dicts the induction hypothesis, suppose that u1 and u2 have the same parent uo. Let < 01, -<1> be the plan at Ut, and let < 02, -<2> be the plan at u2. These two plans are distinct 1-step extensions, with respect to UA, of the same (parent) plan. There are two cases to con­ sider: either {i) 01 # 02 or {ii) 01 = 02 and -<1#-<2· In the first case, since the two plans do not contain the same set of plan steps, they have disjoint linearizations, and hence, .C(ut) n .C(u2) = {}, which contradicts the supposition. In the second case, 01 = 02 ; hence, both plans resulted from adding plan step Oadd to the parent plan. Since -<1#-<2, there exists a plan step Oint that interacts with Oadd such that in one plan Oint is ordered before 0 add and in the other plan 0 add is ordered before Oint· Thus, in either case, the linearizations of the two plans are disjoint, and hence, .C(u1) n .C(u2) ={},which contradicts the supposition. Therefore, the statement holds for nodes at depth n + 1. Q.E.D.