9.2 Less Committed Planners

  
Figure 15: A continuum of commitment strategies

We have shown that UA, a partial-order planner, can have certain computational advantages over a total-order planner, TO, since its ability to delay commitments allows for a more compact search space and potentially more intelligent ordering choices. However, there are many planners that are even less committed than UA. In fact, there is a continuum of commitment strategies that we might consider, as illustrated in Figure 15. Total-order planning lies at one end of the spectrum. At the other extreme is the strategy of maintaining a totally unordered set of steps during search until there exists a linearization of the steps that is a solution plan.

Compared to many well-known planners, UA is conservative since it requires each plan to be unambiguous. This is not required by NOAH (Sacerdoti, 1977), NonLin (Tate, 1977), nor Tweak (Chapman, 1987), for example. 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. As an example, in this section we introduce a Tweak-like planner, called MT, and show that its search space is larger than even TO's in some circumstances.

  
Figure 16: A Propositional Planner based on the Modal Truth Criterion

Figure 16 presents the MT procedure. MT is a propositional planner based on Chapman's Modal Truth Criterion (Chapman 1987), the formal statement that characterizes Tweak's search space. It is straightforward to see that MT is less committed than UA. The algorithms are quite similar; however, in Step 4, whereas UA orders all interacting steps, MT does not. Since MT does not immediately order all interacting operators, it may have to add additional orderings between previously introduced operators later in the planning process to produce correct plans.

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 property, the disjointness property, does not hold for MT, and its failure illustrates how MT can explore more plans than TO (and, consequently, than UA) on certain problems. The disjointness property guarantees that UA does not generate ``overlapping'' plans. The example in Figure 17 shows that MT fails to satisfy this property because it can generate plans that share common linearizations, leading to considerable redundancy in the search tree. The figure shows three steps, , , and , where each has precondition and added conditions , , , and . The final step has preconditions , , and , but the initial and final steps are not shown in the figure. At the top of the figure, in the plan constructed by MT, goals , , and have been achieved, but , , and remain to be achieved. Subsequently, in solving precondition , MT generates plans which share the linearization (among others). In comparison, both TO and UA only generate the plan once. In fact, it is simple to show that, under breadth-first search, MT explores many more plans than TO on this example (and also more than UA, by transitivity) due to the redundancy in its search space.

  
Figure 17: ``Overlapping'' plans.

This result may seem counterintuitive. However, note that the search space size for a partial-order planner is potentially much greater than that of a total-order planner since there are many more partial orders over a set of steps than there are total orders. (Thus, when designing a partial-order planner, it is often preferable to preclude overlapping linearizations in order to avoid redundancy, McAllester & Rosenblitt, 1991; Kambhampati, 1994c.)

Of course, one can also construct examples where MT does have a smaller search space than both UA and TO. Our example simply illustrates that although one planner may be less committed than another, its search space is not necessarily smaller. The commitment strategy used by a planner is simply one factor that influences overall performance. In particular, the effect of redundancy in a partial-order planner can overwhelm other considerations. In comparing two planners, one must carefully consider the mapping between their search spaces before concluding that ``less committed smaller search space''.