On the Utility of Systematicity: Understanding Tradeoffs between Redundancy and Commitment in Partial-ordering Planning

1. Introduction

Although the idea of generating plans through partial-order (PO) planning 1 has been around for almost twenty years, it is only recently that the search space characteristics of PO planners have received particular attention. A big thrust in this work has been on reducing the redundancy in the search space of PO planners. This was largely motivated by the belief that redundancy reduction will lead to improvements in planning efflciency[9, 8]. One approach towards redundancy elimination, that turned out to be particularly influential (as evidenced by several closely related extensions [8, 13, 4, 12]), was that of McAllester's [8] . McAllester showed that it is possible to design a PO planner that is systematic in the strong sense that it never visits two equivalent plans or plans having overlapping linearizations (see Section 2.). Such systematic planners were claimed to be more efficient than planners that admit redundancy in their search space.

While search space redundancy is an important factor affecting the efficiency of a PO planner,another (perhaps) equally important one is the level of commitment in the planner. After all, avoiding premature commitment was one of the primary motivations for PO planning. There is often a tradeoff between the redundancy elimination and least commitment, in that often the redundancy is eliminated at the expense of increased commitment in the planner. For example, McAllester's planner achieves systematicity by keeping track of the causal structures of the plans generated during search, and ensuring that each branch of the search space commits to and protects mutually exclusive causal structures for the partial plans. We will see that such protection amounts to a strong form of premature commitment, which can increase the amount of backtracking as well as the solution systematic will wind up doinf less search than a corresponding planner that is not systematic.

· This research is supported in part by National Science Foundation under grant IRI-9210997.

1 Throughout this paper, we shall use the term PO planning rather than nonlinear planning ,as the former avoids confusion with linearity assumption.

Completeness and Systematicity for PO Planning: Partial-order planners search in the space of partially ordered (rather than totally ordered) sequence of operators. Partial orders serve as a compact representation for all the operator sequences (potential solutions) that are equivalent to some topological sort of the partial ordering. The primary motivation behind PO planning is efficiency -- by deferring orderings among operators, PO planners avoid premature commitment and the consequent unnecessary backtracking, thereby improving performance [13]. In other words, the main goal of partial-order planning is not to fmd least constrained partially ordered operator sequences, but rather to fmd the solutions (ground operator sequences) more efficiently. The completeness criterion for partial-order planning is thus that every potential solution must be produced as a topological sort of some partial ordering generated by the planner. A partial-order planner is said to be systematic if no potential solution (ground operator sequence) is represented by two or more partial orders generated in different search branches. In other words, the set of operator sequences represented by the topological sorts of partial orders appearing in different search branches will be disjoint (whether or not the partial ordering itself represents a complete and correct PO plan).

In ensuring systematicity of partial-order planners, one runs into two distinct forms of redundancy: (i) The same (or equivalent) partial order my appear in two different search branches and (ii) The set of operator sequences represented by the topological sorts of two distinct partial orders appearing in different branches may have non-empty intersection. The standard way of eliminating redundancy in a search, viz., keeping a CLOSED list, and checking for duplicates, turns out to be infeasible here both because of the excessive storage requirements, and because of the high cost of checking plan equivalence (which reduces to graph isomorphism for partially ordered plans). So, we are left with the option of building systematicity into the planning algorithm.

Search Space redundancy in TWEAK: Chapman's [1] modal truth criterion specifies a superset of plan refmement operations used by most partial-order planners using SlRIPS action representation. TWEAK, a planner achieved by inverting this truth criterion, turns out to have a lot of redundancy in its search space. In particular, the example (a) in Figure 2 (originally from [9]) shows that TWEAK admits both multiple paths to same partial order, as well as distinct partial orders with overlapping linearizations into the search space.

2A solution is said to be bloated (c.f. [7]) if it is possible to remove a single operator from that solution without affecting the correctness of the solution. Most planners guarantee completeness with respect only to un-bloated plans. Unfortunately, however, almost all planners, including SNLP, do produce some bloated solutions; although the extent of bloated plan generation varies from planner to planner. In [5], we argue that in comparing search spaces of different planners, one should take into account not just redundancy, but also the extent of bloated plans allowed by the planner.

Figure 2: Examples showing redundancy and looping in TWEAK search space. In all the examples, the operators are shown with preconditions on the right side, and effects on the left (with " +" sign for add list literals, and "-" sign for delete list literals). The Init and Goal lists specify the problem.

Further more, since TWEAK does not keep track of which goals it already achieved and which it is yet to achieve, it may achieve and clobber a goaVsubgoal arbitrarily many times within the same refmement branch. This causes unnecessary looping and generates many useless operator sequences. Example (b) in Figure 2 shows a scenario where TWEAK repeatedly achieves and clobbers the conditions Q and Rat action al. In fact, in this example, TWEAK would loop infmitely if the action a4 is not available.

Book-keeping through Causal Links: The looping behavior in the above example could have been avoided had TWEAK kept track of the reasons for introducing different steps into the partial plan in the flfst place. In particular, had it remembered that a2 is introduced to give Qat al, then while introducing a3, into the plan, it would have realized that there is no way the interaction between a2 and a1 can be resolved, and would thus have abandoned that path. This would have obviated the possibility of repeated establishment and undoing of the same goal (and hence the looping). 3

It is this realization that served as the flfst impetus for protection intervals/causal links in planning. Protection intervals were flfst introduced in Sussman's Hacker [15] as a book-keeping device for keeping track of the goals that have already been worked on, and thereby avoiding undoing them or working on them multiple times. They were flfst used in partial-order planning in Tate's Nonlin [16] . A protection interval. denoted as{"} .!. w, is best seen as a commitment by the planner that the condition p at step w, flfst established by the step " will henceforth be protected from being violated before w . Specifically, if there is a possibility of p being not true before w, the planner tries to see if the steps that are deleting p could be ordered to come either before " or after w.

Redudancy elimination through Exhaustive causal links: McAllester [8] was the flfst to point out that a natural extension of the commitment to a protection interval, {"} .!. w, viz., " will be the effective contributor (i.e., last step before w that provides p) of p for w in every topological sort of the current partially ordered plan -- can be used to eliminate redundancy in the planner's search space. Notice that with this extension, any step 11 that can possibly come between s and w and either delete or add p is going to threaten the commitment promised by the causal link {"} .!. w, and thus is considered a threat. Specifically, 11 is considered a -ve threat if it deletes p and a +Ve threat if it adds p. Causal links with these semantics are called exhaustive causal links (c.f. [4]). To make an exhaustive causal link {"} .!. w safe, every threat must either be promoted to come after w or be demoted to come before"· (Notice that white-knight declobbering [1] is inconsistent with the semantics of an exhaustive causal link).

Systematicity of SNLP: McAllester described a planner based on the idea of exhaustive causal links (which later became known as SNLP). In SNLP, planning process involves supporting every goal and every precondition of each step of the plan with causal links, and ensuring that those causal links are safe (i.e., all their threats are resolved). Link establishment and threat resolution are thus the two important operations in SNLP. A partial plan generated by SNLP is said to be safe if all the causal links of the plan are safe (i.e .. none of them have unresolved threats). It is said to be complete if it is safe, and all the goals, and all the preconditions of the steps of the plan are supported by causal links.

3 Planners using causal links do not eliminate looping; they merely reduce it. In particular, although no causal-link based planner will loop on Example (b) of Figure 2, there are other examples on which they will.

It can be shown that SNLP is systematic, if it folds threat resolution into link establishment, and thus searches only in the space of safe partial plans. 4 Specifically, no two incomplete or complete plans appearing in two different search branches will have an operator sequence common between them (i.e., they won't have overlapping topological sorts). Thus, the planner never considers the same potential solution (ground operator sequence) more than once.

The systematicity claim of SNLP. stated above, can be proved rigorously by adapting the proofs of Harvey et. al. [3] . Harvey shows that given any two complete plans in the search space of SNLP. the sets of operator sequences defined by the topological sorts of these plans will be disjoint. Harvey's proof only utilizes the safeness of plans, rather than their completeness. Thus, the proof also implies that no two safe plans will have overlapping sets of operator sequences. This, in turn implies that SNLP which folds threat resolution into link establishment, and thus searches in the space of safe partial orderings, will be systematic. 5

Other conflicting notions of Systematicity: There have been several conflicting interpretations of "systematicity" of partial­ order planning in the literature. Some researchers (c.f. [2]) have interpreted McAllester's systematicity claim to mean that even though the same operator sequence may appear in more than one branch, it will never have the same causal structure. This notion of causal structure systematicity is considerably weaker than the notion of systematicity which we defmed above, and which is guaranteed by SNLP. Systematicity is stated in terms of operator sequences rather than in terms of step names and causal structures. This is reasonable because step names and causal links are artifacts of the particular planning strategy, while systematicity should be defmed with respect to the space of potential solutions (Figure 1).

Another weaker notion of irredundancy, that we term solution­ systematicity has also been used by some researchers (c.f. [3]). A planner is solution-systematic as long as it never generates the same solution (i.e, operator sequence which is a correct plan for the problem) more than once. 6 It can be shown (c.f. [3]) that regardless of the order in which threat resolution and link-establishment is done (i.e., even if we don't fold the former into the latter), SNLP will have solution-systematicity. Solution systematicity does not in general imply systematicity. This point is illustrated by the example in Figure 3, which compares complete search space for a problem generated by systematic SNLP with that generated by a variant called SNLP' that postpones +ve threats. The latter clearly is un-systematic; the same potential solutions (operators sequences) are examined and refmed in multiple search branches. It is however solution-systematic since all the redundant search branches will be ultimately pruned when the planner attempts to resolve the +ve threats. In other words, a planner that is solution systematic may do arbitrary amount of redundant work in the branches that will ultimately get pruned. Furthermore, a planner that is solution-systematic may have a larger search space than a corresponding planner that is not solution-systematic. In the current example, a planner which completely ignores +ve threats (such as McNonlin to be described in the next section), and is thus not solution systematic, would stop before resolving the positive threats, and thus would generate a smaller search space than SNLP'. Thus, from the point of view of redundancy elimination, which was the primary reason for systen'laticity, solution-systematicity is of dubious utility . 7

4 Note that although the original SNLP algorithm described in McAllester does not fold threats resolution into link establishment, it does always resolve threats before considering new link establishments. Thus, a simple syntactic change will make it search in the space of safe plans and thus make it systematic.

5 Space limitations preclude a serious discussion of systematicity of lifted SNLP (i.e., SNLP that handles operator schemas and partially instantiated plans). In [S], we show that the usual practice of using separation as a resolution strategy side-by-side with promotion and demotion, is an overkill in terms of search space size. Since we need completeness only in the space of ground (rather than partially instantiated) operator sequences, we suggest that a better way would be to change the defmition of threats to preclude steps whose effects possibly (but not necessarily) codesignate with the condition being supported by a causal link. This obviatea separation as a resolution strategy, and gives a planning strategy with a provably smaller search space (c.f. [12]).

6More technically, given two nodes in different branches of the search space, any solution to the given problem will appear in at most one of the subtrees rooted at these nodes.

3. The Redundancy-Commitment Tradeoff

In the previous section, we saw that SNLP avoids redundancy in the search space through a strong form of commitment to causal links. 1WEAK, on the other hand, does not commit to causal links, and as a result introduces redundancy into its search space. We shall now focus on how this affects their performance in practice.

Clearly. worst case search space size will have a strong correlation with performance only when the planner is forced to explore a significant portion of its search space in solving the problem. Since the goal of planning typically is to fmd one, rather than all, solutions of a problem, unless the problem is unsolvable; or the solution density is low and the planner's initial choices lead it towards non-solution branches, systematicity may not necessarily lead to improvements in planning performance (c.f. [6]).

If systematicity may not always improve performance, the next question is: does it hurt performance? While redundancy in the search space is an important factor affecting the performance of a PO planner, another (perhaps equally) important factor is the level of commitment in the planner. Indeed, as mentioned earlier, the original impetus for PO planning was the realization that total ordering planners such as STRIPS [10] commit too soon to specific action orderings.

The use of protection intervals and causal links, while systematiz­ ing the search, also results in increased commitment to particular establishment structures. Increased commitment leads to higher backtracking as well as increased depth of the solution, which in turn adversely affect the performance. This is in contrast to 1WEAK, which avoids commitment to causal links, but at the expense of increased redundancy.

7 Note that the example only shows that arbitrary postponement of threat resolution does not preserve systematicity. In private correspondence, David McAllester observed that a planner having solution systernaticity can be converted into a systematic one by ensuring that the set of solutions in the subtree rooted at every intermediate node is non-empty. Searching in the space of safe plans provides sufficient, but not necessary, grounds to guarantee this condition. A way of relaxing safe search would be to postpone those threats that can always be resolved in the end (c.f. [14])

This leads us to the hypothesis that performance depends not solely on the level of redundancy or commitment in the planner. but rather on the tradeoff between them. This also suggests that neither SNLP which eliminates redundancy without worrying about commitment, nor 1WEAK which guarantees least commitment without worrying about redundancy, is guaranteed to be efficient all the time. In the next two sections, we will explore this tradeoff further by comparing a spectrum of solutions that fall in the middle of SNLP and 1WEAK. and strike a better balance in this tradeoff than either.

4. A Spectrum of solutions for the tradeoff between redundancy and commitment

Figure 4 shows other sound and complete PO planners that fall in the middle of these two extremes. In this section, we will characterize the dimensions along which these planners vary. with particular em­ phasis on the way they deal with redundancy-commitment tradeoff.

SNLP. McNonlin, MP and MP-1 · the four planners on the bottom left in Figure 4 use causal links to organize their search. They introduce causal links to support each open condition of the plan, and ensure that none of the causal links are threatened. All of them do threat resolution before link establishment. The planners differ only in their defmition and treatment of threatened causal links. We say that S ~ w is a generalized (multi-contributor) causal link of plan P if the step w and the set of steps S (called the contributor set) belong to P. such that all the steps in S are ordered to precede w and each of them is capable of giving the precondition p to w. Given a step 11 , and causal link S -!. w of the plan P such that 11 can possibly come between every step of S and w. 11 is called a negative threat for the causal link if 11 deletes p. 11 is called a positive threat for the causal link if 11 adds p. A causal link S ~ w of a plan P is said to be exhaustive (c.f. [4]), if for every ground linearization of P, some step ·' E Swill be the last step preceding w that gives p in that linearization. It is easy to see that a correct plan with exhaustive causal links. none of the causal links will have positive or negative threats. If every causal link of the plan has a singleton contributor set (i.e .· lSI = 1). then the plan is said to have single contributor causal structure.

Given this formulation of causal links, we can now describe the four causal link planners as four points along a spectrum. Two of them, SNLP and McNonlin, use the traditional single contributor causal links to guide planning. SNLP uses exhaustive causal links (and thus resolves +ve as well as -ve threats). In contrast, McNonlin 8 uses non-exhaustive causal links, and thus ignores +ve threats. In both planners. a threat 11 to a causal link {'} ~ w is resolved by ordering it to come either before' or after w .

The other two planners, MP and MP-1 · use multi-contributor causal links [4] to guide planning. MP maintains exhaustive causal links. In MP . a threat 11 to a link S ~ w is resolved by either promoting 11 to come after w or demoting 11 to come before some step ' E S (a choice point). In addition. if 11 is adding the condition p, we can also make the link safe by ordering 11 to come before w and merging 11 with S . MP-1 on the other hand maintains non-exhaustive causal links and thus ignores +ve threats. It however introduces an additional declobbering resolution operation for -ve threats: Suppose there is a negative threat 11 to a causal link S ~ w and there exists step ·' such that it follows 11 and adds p. In this case. the threat can be resolved by ordering ·' to come before w and merging ·' with S . The overall effect is that MP-1 is less eager than MP in accumulating new contributors to a causal link.

8 McNonlin is a considerable simplification of Tate's original implemen­ tation of NONLIN[l6], which was a hierarchical nonlinear planner.

Clearly, the four planners balance the tradeoff between redun­ dancy and commitment in different ways. In particular, SNLP and McNonlin reduce redundancy in the search space by increasing the commitment to specific contributors. while MP and MP-1 reduce commitment to individual contributors at the expense of increased redundancy. MP and SNLP maintain exhaustive causal structures which allow them to split the possible partial plans into sets of plans with mutually exclusive establishment structures, there by control­ ling the redundancy in the search space. (Specifically. although MP is not systematic, it can be shown to be causal structure systematic; Section 2.). However, exhaustiveness also increases effective solu­ tion depth, since unlike McNonlin and MP-1. MP and SNLP have to deal with positive as well as negative threats to the causal links.

UA. 1WEAK and NG1WEAK, the three planners on the bottom right in Figure 4, do not use causal links (or protection intervals) in their search. Thus, they completely eliminate the commitment to contributors. Of these three, 1WEAK closely follows the idea of inverting Chapman's MTC (with the minor difference that it doesn't use external white-knights for declobbering) . It is the only planner among the seven that backtracks on goal orderings. NG1WEAK reduces some of the redundancy in the 1WEAK search space by avoiding backtracking on goal ordering decisions (similar to the implementation described in [17]). UA [9], reduces the redundancy further by maintaining partial plans that are unambiguous in the sense that each prerequisite in the plan is either necessarily true or necessarily false. UA achieves this by ordering every newly introduced step with respect to all possibly interacting steps. This policy allows UA to eliminate plans with overlapping linearizations from its search space (unlike 1WEAK). However, like 1WEAK, UA still allows multiple paths to the same partial-order, as well as establishing and violating the same condition multiple times within the same search branch.

The seven planners described in the previous section thus represent a spectrum of solutions for the tradeoff between redundancy and commitment. Informally, in Figure 4. the search space redundancy increases from left to right, while the level of commitment decreases from left to right.

5. Empirical Analysis of the tradeoff between Redundancy and Commitment

To understand how the various solutions to the tradeoff between redundancy and commitment affect the planning efficiency. we implemented all seven planners described in the previous section on a common platform, and performed focused empirical studies. The broad objectives of the studies were to demonstrate that neither systematicity nor least-commitment alone are good predictors of plarming performance. and that performance can be better predicted by the way a planner balances the redundancy-commitment tradeoff. This section describes the study and analyzes the results.

5.1. Experimental Setup

Our test domains included classical toy-worlds such as blocks world, as well as the synthetic domains used in Weld et. al. 's work [13]. In this paper, we will concentrate on the results from Weld et. al.'s synthetic domains and our variants of them. as they provide for a more controlled testing of the tradeoffs. Weld et. al.'s original domains include ART-MD and ART-lD (also called D"' 5 1 , D 1 S 1 respectively), which are designed to contain easily serializable and laboriously serializable sub-goals respectively. The domains are defmedas:

ART-MD A; prec : l; add : G; del: {I;Ii < i}

ART-lD A; precond : l; add : G; del : Ii-I

To these. we also added our own variants: ART-MD-RD and ART-lD-RD, which introduce preconditions achieved and deleted by multiple operators. The variants are produced by making every even numbered action require an additional precondition he, delete that precondition and add an additional postcondition hf. 9 The odd numbered actions similarly require and delete hf and add he. The specification of ART-MD-RD is shown below. ART-lD-RD is produced similarly from ART-lD

A, prec : I,, he add : G;, hf del: {I;Jj < i} U {he} for even i A, prec : I;, hf add : G; , he del : {I;Jj < i} U {hf} for odd i

In each of the domains, we compared all seven planners, over solvable problems with 1 to 8 goals from the set { Gt · · · Gs}. Since the effect of commitment to contributors depends significantly upon the order in which the various goals and sub goals are addressed by the planner, we tested with two types of goal order strategies: strategy L which is a LIFO strategy where a goal and all its recursive sub goals are addressed before the next higher level goal is addressed; and strategy GbyG, which is a FIFO strategy where all the top level goals are addressed before their subgoals are considered by the planner (strategy L corresponds to a depth-first traversal of the goal-subgoal tree, while strategy GbyG corresponds to a breadth-first traversal). An A · search regime was used for all the planners (see [5]).

5.2. Experimental Results and Discussion

5.2.1. Comparison between the Causal Link Based Planners

We started by comparing the cpu time (in m.sec. on a SUN SP ARC-m. taken by the four causal link based planners for each of the goal ordering strategies in ART-MD and ART-lD respectively. We found that there is no appreciable difference in time taken by the planners for solving problems in these domains (plots omitted due to space limitations).

Next, we studied the performance of these planners in ART-MD­ RD. and ART-lD-RD domains. We started by comparing the sizes of the overall search spaces of all the planners. The leftmost plot in Figure 5 compares the total search space sizes of these four planners for one of the goal orderings. 10 It shows that they have varying amounts of redundancy in the search space, with SNLP having the smallest search space, and MP-1 having the largest. If the search space size were to be sole indicator of performance, we would expect SNLP to perform best, followed by McNonlin, MP and MP-1 .

The middle plot in Figure 5 compares the performance of the planners in ART-MD-RD domain which contain the easily achieved and deleted conditions hf and he (the performance proftles for ART-lD-RD were very similar, but are omitted here due to space limitations). The missing data points on a plot correspond to the problems that couldn't be solved before the time bound, which for us was the time it took for the lisp to run out of memory and fail. These empirical performance relations are surprisingly robust. In particular, we found that short of providing the correct order in which to attack goals, there is no other way to change the qualitative performance relations between SNLP and MP-1. Specifically, static threat delay strategies, such as those described in [12], while improving the overall performance of all planners slightly, leave the qualitative relations between the planners unchanged. Same is true of the heuristic of working only on the goals that are not necessarily true (a la TWEAK and UA).

Analysis: The behavior of the four causal link based planners in our experiments can be explained in terms of the tradeoff between redundancy and commitment that we discussed earlier. In particular, the near identical performance of the four planners in the original ART-MD and ART-lD domains can be explained by the fact that in these domains each precondition is ultimately provided by a single action in the plan, and there is no penalty for committing prematurely to that action as the contributor. Premature commitment does hurt performance In ART-x-RD domains, and we find that:

9 he and hf are supposed to be mnemonics for hcndempty and hcncifull conditions in the traditional blocks world domain [10], which are achieved or deleted by many of the actions in the domain.

10 The size of the overall search space is found by setting the termination condition for each planner to be uniformly false, thus forcing the planners to visit every node in the search space before giving up.

• MP and MP-1 perform better than SNLP and McNonlin in the case of the LIFO goal ordering strategy L (see plots in Figure 5) even though the latter two search in exponentially smaller search spaces (see plots in Figure 5), with SNLP in particular having the smallest search space, as guaranteed by its systematicity property.
• MP-1 and McNonlin perform better than SNLP and MP in the case of GbyG strategy, even though the former two don't use exhaustive causal links and thus have more redundancy.

Once again, this behavior can be explained in terms of the way each planner handles the tradeoff between redundancy and commit­ ment. Since both MP and MP-1 can change their commitment to establishment structures within the same branch, they may visit a potential solution more than once. They thus have larger search spaces compared to SNLP. Moreover, MP and SNLP, which main­ tain exhaustive causal structures, have smaller search spaces than MP-1 and McNonlin respectively.

However, the performance is not directly correlated with the search space size. In the LIFO ordering strategy L, SNLP and McNonlin are forced to commit to a specific contributor for the hf and he subgoals (preconditions) of a top level goal G;, before the other top level goals are expanded. Since both hf and he are easily added and deleted by many actions in the domains, such premature commitment has a high probability of being wrong. Since both SNLP and McNonlin protect causal links to eliminate redundancy, the only way they can get rid of a wrong causal link is to backtrack over it (i.e., go over to another branch of the. search space). Such backtracking turns out to be very costly in terms of performance. MP and MP-1 avoid problematic backtracking as they can deal with their initial wrong commitment by merging additional contributors into the contributor list as and when they become available.

Premature commitment turns out to be less of a problem when the FIFO ordering strategy GbyG is used, since in this case G; and I, are addressed before hf and he, and each action A, is capable of giving only one of the goals G;. Since only the initial state is capable of giving all !;, the orderings imposed to deal with the deletions of l ; 's by individual actions of the plans constrain the plan enough so that by the time hf and he are addressed, the only available contributor choice also happens to be the correct choice.

Although premature commitment is not a problem, SNLP and MP consider positive as well as negative threats for causal links and thus have higher solution depth. In particular, note that plans that are complete for MP-1 and McNonlin may still need to be reftned further to ensure exhaustiveness of their validation structure and thereby make them complete with respect to MP and SNLP. This explains the higher planning cost of SNLP and MP compared to McNonlin and MP-1 respectively.

Note however that ability to avoid premature commitment, and solution density are more predictive of performance than is the presence or absence of +ve threats. In particular, the middle plots in Figure 5 show that McNonlin performs worse than SNLP in the LIFO strategy (this effect was even more pronounced in the case of ART-lD-RD domain [5]). This can be explained by noting that the redundancy that McNonlin introduces into its search space by ignoring +ve threats, adversely affects the performance exactly when the planner's initial commitments all tum out to be wrong, forcing it to look at a significant portion of its search space.

5.2.2. Comparison between Causal Link based and Non-causal Link based Planners

Given that the reduced commitment to contributors provided by multi-contributor causal links allows them to strike a better balance between redundancy and commitment than is the case with single contributor causal links, a natural question arises as to whether planners that completely avoid causal links strike an even better balance. To answer this question, we compared the performance of all seven planners shown in Figure 4. The rightmost plot in Figure 5 shows the results of these comparisons in ART -MD-RD for the LIFO ordering (the plots for GbyG ordering are omitted due to space limitations; see [5]) .

As expected, both SNLP, which completely eliminates redun­ dancy at the expense of increased commitment, and 1WEAK which avoids all forms of commitment, fare badly in this domain. The former gets penalized for the overcommitment (especially in the LIFO goal ordering strategy), and the latter gets penalized for the excessive redundancy (high branching factor). For the LIFO goal ordering strategy, the planners using multi-contributor causal links, and those using no causal links (except 1WEAK), do better than the planners using single contributor causal links. including SNLP and 1WEAK. This can be explained by the fact that LIFO goal ordering heavily penalizes planners that commit too early to specific contributors and protect the commitments. The best performance for both goal orderings is shown by UA and MP-1 with NG1WEAK coming third. This also shows that the cost of maintaining causal links is not a factor affecting performance. The real issue is the level of commitment forced by them. Although UA, a causal-link-less planner performed as well as the best causal link planner, MP-1 in this domain, we believe that this may change as we go to more expressive action representations. In these latter situations, not maintaining causal links leads to an additional form of redundancy which can adversely affect performance: the planner may work on multiple secondary preconditions in aid of the same (sub )goal (c.f. [11]) We are currently testing this hypothesis [5].

6. Concluding Remarks

In this paper we provided a rational reconstruction of the motivations for systematicity, and argued that the performance of a PO planner is correlated more closely with the way it balances the tradeoff between redundancy and commitment, than on the systematicity of its search. We showed that there are a spectrum of solutions to this tradeoff, and identified the type of causal links used (single vs. multi­ contributor vs. none), and the level of commitment to the causal links (exhaustive vs. non-exhaustive) as the important dimensions of variation. We conducted focused empirical studies to understand how these different dimensions affect the performance of a planner. The main objective of the empirical study has been to establish the presence of tradeoffs. The studies characterize SNLP and 1WEAK as two extreme solutions to the redundancy-commitment tradeoff, and demonstrate that planners which strike a more judicious balance in this tradeoff can outperform both less committed, and more systematic planners. Although our empirical studies were mainly done in artificial domains, we believe that the hypotheses regarding tradeoffs between redundancy and commitment will also apply to other domains. Our future plans include a more analytical formulation of these tradeoffs [5].

Acknowledgements: Special thanks to Bulusu Gopi Kumar, Laurie Ihrig, Suresh Katukam and Eric Cohen of ASU planning seminar for helping me clarify my thinking. Thanks are also due to Mark Drum­ mond, Will Harvey, Richard Korf, Pat Langley, David McAllester, Steve Minton, Mark Peot, Dave Smith, Austin Tate and Dan Weld for many helpful discussions.