Challenges in Bridging Plan Synthesis Paradigms

1. Introduction

Most traditional approaches to plan generation, developed over the last twenty years, work by searching in the space of partial plans, extending a plan incrementally until it be­ comes a solution, and backtracking when a plan can no longer be fruitfully refined. More recently, several ap­ proaches have been developed that relate plan synthesis to constraint satisfaction. These include Graphplan [Blum & Furst, 1995], SATPLAN [Kautz & Selman, 1996], COPS [Ginsberg, 1996], Descartes [Joslin & Pollack, 1996] and UCPOP-D [Kambhampati & Yang, 1996]. Graphplan and SATPLAN approaches, in particular, have demonstrated impressive scale-up potential in practice.

At present, there exists a huge gulf between these n~w breed of algorithms and the traditional refinement planmng approaches. An important challenge for the plannin~ co~­ munity is to bridge these strands of research to see If their strengths can be complemented. To this end, I present a generalization of the refinement planning framework devel­ oped in our previous work [Kambhampati, Knoblock & Yang, 1995; Kambhampati & Srivastava, 1996] that covers most of the currently known approaches.

According to my general framework, partial plans are shorthand notations for sets of action sequences (called the candidate set of the plan). Plan synthesis involves a "split and prune" search [Pearl, 1980]. The pruning is carried out by applying refinement operations to a given set of partial plans (called a planset). Pruning attempt to incrementally get rid of non-solutions from the candidate set. The splitting part involves pushing the component partial plans of a plan­ set into different branches of the search tree. Its main aim is sets of action sequences are represented and manipulated in terms of partial plans which can be seen as a collection of constraints. The action sequences denoted by a partial plan, i.e., those that are consistent with its constraints, are called its candidates. For technical reasons that will become clear later, we find it convenient to think in terms of sets of (instead of single) partial plans. A set of partial plans is called a planset with its constituent partial plans referred to as the components. The candidate set of a planset is de­ fined as the union of the candidate sets of its components.

* This research is SUIJported in part by the NSF NYI award IRI9457634, the ARPI Initiative grant F30602-95-C-0247 and the ARPA AASERT grant DAAH04-96-1-0231. I would like to thank Bart Selman, Laurie Ihrig, Amol Mali and the anonymous review­ ers for critical comments on a previous draft.

A refinement (pruning) operation narrows the candidate set of a planset by adding constraints to its component plans. If no solutions are eliminated in this process, we will eventually progress towards the set of all solutions. Termi­ nation can occur as soon as we can pick up a solution using some bounded time operation -- called the solution extrac­ tion function. To make these ideas precise, we shall now look at the syntax and semantics of partial plans and refire­ ment operations.

2.1 Partial Plan Representation: Syntax

A partial plan can be seen as any set of constraints that together delineate which action sequences belong to the plan's candidate set and which do not. One commonly used representation models partial plans as a set of steps, order­ ing constraints between the steps, and auxiliary constraints (we shall discuss alternative representations, such as that proposed by Ginsberg [1996], later). The ordering con­ straints may require steps to precede each other or be con­ tiguous. The auxiliary constraints demand the preservation of a condition over a time interval between two steps (called IPCs) or the truth of a condition at a time point (called point truth constraints). An example plan in this representation from the one-way rocket domain (involving transportation of two packages from earth to moon using a single one-way rocket) is shown in Figure 1.

2.2 Partial Plan Representation: Semantics

The semantics of the partial plans are given in terms of candidate sets. A candidate can be seen as a model of the partial plan constraints. An action sequence belongs to the candidate set of a partial plan if it contains the actions corre­ sponding to all the steps of the partial plan, in an order con­ sistent with the ordering constraints on the plan, and it also satisfies all preservation constraints. For the example plan shown in Figure 1, the action sequences shown on the left in Figure 2 are candidates, while those on the right are non­ candidates.

Notice that the candidates may contain more actions than are present in the partial plan. Because of this, a plan's can­ didate set can be potentially infinite. We define the notion of "minimal candidates" to let us restrict our attention to a finite subset of the possibly infinite candidate set. Specifi­ cally, minimal candidates are candidates that only contain the actions listed in the partial plan (thus their length is equal to the number of steps in the plan other than 0 and oo). The top candidate on the left of Figure 2 is a minimal candidate while the bottom one is not. There is a one-to-one correspondence between the minimal candidates and the syntactic notion of safe linearizations of a plan, where a safe linearization is a permutation of plan steps that satisfies the auxiliary preservation constraints. For example, the mini­ mal candidate on the top left of Figure 2 corresponds to the safe linearization 0-1-3-2-4-oo (as can be verified by trans­ lating the step names in the latter to corresponding actions).

2.3 Refinement Strategies

A refinement strategy R maps a planset P to another planset pR such that the candidate set of pR is a subset of the cand i­ date set of P. R is said to be complete if pR contains all the solutions of P. It is said to be progressive if the candidate set of pR is a strict subset of the candidate set of P. R is said to be strongly progressive if the length of the minimal can­ didates increases after the refinement. The degree of pro­ gressiveness is measured in terms of the reduction in the candidate set size. It is said to be systematic if no action sequence falls in the candidate set of more than one compo­ nent of pR,

Completeness ensures that we don't lose solutions by the application of refinements. Progressiveness ensures that refinement narrows the candidate set (i .e., has pruning power). Strongly progressive refinement strategies simul­ taneously shrink the candidate set of the plan, and increase the length of its minimal candidates. This provides an in­ cremental way of exploring the (potentially infinite) candi­ date set of a planset for solutions: Examine the minimal candidates (corresponding to safe linearizations) of the planset after each refinement to see if any of them corre­ spond to solutions. Systematicity ensures that we never con­ sider the same candidate more than once, if we were to ex­ plore the components of the plan set separately.

Refinements are best seen as canned inference procedures that compute the consequences of the meta-theory of plan­ ning, and the domain theory (in the form of actions), in the specific context of the current partial plan constraints. Tm­ ditional planners use four types of refinement strategies -­ forward state space, backward state space, plan space and task-reduction [Kambhampati, 1997]. Figure 3 shows a for­ ward state space refinement of a partial plan in the one-way rocket domain. It takes the null planset, corresponding to all action sequences and maps it to a planset containing 3 components. In this case, given the theory of planning, which says that solutions must have actions that are execu­ table in their respective states, and the current planset con­ straint that the state of the world before the first step is the initial state, the forward state space refinement infers that the only actions that can come as the second step in the so­ lution are Load(A), Load(B) and Fly().

This particular refinement is complete since no solution to the rocket problem can start with any other action for the given initial state. It is progressive since it eliminated the action sequences not beginning with Load(A), Load(B) or Fly() from consideration. Finally, it is systematic since no action sequence will belong to the candidate set of more than one component (the candidates of the three components will differ in the first action).

2A Plan Synthesis

We are now in a position to present the general refinement planning template, which we do in Figure 4. If the current planset has an extractable solution-which is checked by inspecting its minimal candidates to see if any of them is a solution- we terminate. If not, we select a refinement strategy R and apply it to the current planset to get a new planset. This is the pruning step. The third step is the split­ ting step, and involves pushing the components of the re­ fined planset into different branches. The splitting is con­ trolled by the parameter k. If k equals 1, no splitting is done. If k equals the number of components of the refined planset, full splitting is done. Intermediate values of k correspond to intermediate levels of splitting. After the splitting step, one of the search branches is selected non-deterministically, and pruning and splitting is applied to it recursively.

As long as the selected refinement strategy R is complete, the algorithm will never lose a solution. As long as the refinements are strongly progressive, for solvable problems, the algorithm will eventually reach a planset one of whose minimal candidates will be a solution.

The solution extraction process involves searching through the possibly exponential number of minimal candi­ dates of a planset for a solution. As k increases, individual plansets have fewer components, and consequently the cost of solution extraction reduces.

The algorithm template in Figure 4 covers both traditional and newer plan synthesis approaches (see [Kambhampati, 1997] for a more elaborate discussion). Traditional refine­ ment planners, such as UCPOP, Prodigy, SNLP, etc. corre­ spond to complete splitting (i.e., k equals the number of components of the planset) differing mainly in the type of refinements they employ. The newer approaches such as Graphplan, COPS, Descartes and UCPOP-D can be seen as handling plansets without splitting. The first two do not do any splitting, while the last two do controlled splitting. Fi­ nally, SATPLAN approaches can be understood as posing the solution extraction as a SAT problem.

3. Disjunctive planning

We saw that traditional planners do refinement planning with full splitting, differing mainly in terms of the specific refinement strategies they use. Unfortunately, these planners tend to generate huge search spaces and have in practice shown disappointing scale-up potential. Viewing the newer approaches such as Graphplan and SA TPLAN as instances of our framework suggests that a promising general solu­ tion involves handling plansets without splitting. This idea, referred to as disjunctive planning, raises three immediate issues: How do we (a) represent, (b) refine and (c) extract solutions from large plansets? I will discuss the first two issues in this section. The most promising approach for so­ lution extraction at present seems to be to pose it as a CSP/SAT problem. I will discuss this further in Section 4, in the context of SATPLAN.

3.1 Disjunctive Representations

First off, keeping plansets together may lead to very un­ wieldy data structures. The way to get around this is to "internalize" the disjunction in the plansets so that we can represent them more compactly. The general idea of dis­ junctive representations is to allow disjunctive step, order­ ing, and auxiliary constraints into a plan. Figure 5 and Figure 6 show two examples the idea. The three plans on the left in Figure 5 can be combined into a single disjunctive step, with disjunctive contiguity constraints. Similarly, the two plans in Figure 6 can be combined by using a single disjunctive step constraint, a disjunctive precedence con­ straint, a disjunctive interval preservation constraint and a disjunctive point truth constraint.

Candidate set semantics for disjunctive plans follow natu­ rally from the fact that the presence of the disjunctive con­ straint c 1 V c 2 in a partial plan constrains its candidates to be consistent with either c 1 or c 2 · So, solution extraction on disjunctive plans can still be posed as the problem of searching through minimal candidates for a solution.

3.2 Refining Disjunctive Plans

In refining the disjunctive plans, we face a tradeoff between the pruning power of the refinement and its cost. The maxi­ mal pruning power is obtained by externalizing the disjunc­ tion, applying the traditional refinements to each of the re­ sulting non-disjunctive partial plans, and combining them back into a disjunctive plan. For example, to refine the plans on the left in Figures 5 and 6, we simply go back to the plans on the right, refine them, and combine the results into a new disjunctive plan. This approach is however infeasible in practice since it makes the refinement stage exponentially hard. We need to generalize the traditional refinement strategies so that they can appl~ directly .t? th~ disju~ctive plans. I will now attempt to outhne the cnticalissues m doing this. . . .

Since refinement strategies essentially denve the conse­ quences of planning and domain theory i~ the cont~~t of ~he current plan constraints, it is clear th.at I~ternal diSJUnctiOn in the partial plan may lead to the denvatwn of weaker con­ sequences (thus reducing their prunin~ po~er) . . For exam­ ple, for the disjunctive plan on the n~ht m Figure 5, w_e don't know which of the three steps will actually occur m the eventual solution. Consequently, we don't exactly know what the state of the world will be after the disjunctive step. This means that the forward state space refinement will not be able to infer exactly which actions can appear in the sec­ ond step of the solution. Similarly, for the disjunctive pl~n in Figure 6, we don't know whether steps 1 or 2 or both will be present in the eventual solution. Thus a plan space re­ finement won't know whether it should introduce steps relevant to At(A,E) precondition, those relevant to At(B,E) precondition, or both. . .

All is not lost however, as the refinements can still mfer a superset of the relevant actions. For example, for the plan in Figure 5, although we do not know the exact state after the first (disjunctive) step, we know that it can only be a subset of the union of conditions in the effects of the three steps. Knowing that only Load(A), Load(B) or Fly(R) can be the first steps in the plan tells us that the state after the first step can only contain the conditions In(A), In(B) and At(R,M). We can thus generalize forward state space refinement to add only those actions whose preconditions are subsumed by the union of propositions comprising the effects of the three steps. Similarly, plan-space refinement can be gener­ alized to introduce actions to achieve all parts of a disjunc­ tive precondition.

These "naive" generalizations of the standard refinements are still complete, but have far less pruning power than the standard refinements operating on non-disjunctive plansets. In the case of the generalized forward state space refine­ ment, even if the preconditions of an action are in the un­ ion of effects of the preceding disjunctive step, there may be no real way for that action to actually be take place. For example, in Figure 5, although the preconditions of "unload at moon" action may seem satisfied, it is actually never go­ ing occur as the second step in any solution because Load() and Fly() cannot be done at the same tin:te. In fact, this naiv.e generalization may allow an expo~enttal numbe.r . of addi­ tional actions that will not be considered by traditiOnal for­ ward state space refinement operating on non-disjunctive plans [Kambhampati & Lambrecht, 1997] .

Although the loss of progressiveness in refining a dis­ junctive plan cannot be completely avoided, it can be re­ duced to a significant extent by extending the types of con­ sequences inferred by the refinements. Traditional refine­ ment strategies concentrate exclusively on inferring the identities of new actions that must be part of any eventual solution. We can widen the focus in the context of disjunc­ tive plans. For example, in Figure 5, using the domain and planning theory, we can recognize that actions Load(A) and Fly(R) cannot both occur in the first step (since their pre­ conditions and effects are interacting). Propagating this in­ formation tells us that the second state may either have In(A) or At(R,M), but not both. Here the interaction be­ tween the steps 1 and 3 propagates to make the conditions In(A) and At(R,M) "mutually exclusive" in the next dis­ junctive state. Thus any action which needs both In(A) and At(R,M) can be ignored at the next level. The particular strategy described here is similar to the one employed by Blum and Furst's [1995] Graphplan algorithm, and has bee~ shown to be a major source of its efficiency [Kambhampati & Lambrecht, 1997]. Similar techniques need to be developed for plan-space refinements. .

To summarize, disjunctive plans can be refined dire?tlY and efficiently, at the expense of some of the progresst.ve­ ness (pruning power) of the refinement. The loss of prumng power can be countered by widening the ~cope . of t~e re­ finements to infer more than just the potential actiOns m the solution.

4. Relating SATPLAN to disjunctive planning

The SATPLAN approach involves generating a SAT en­ coding, all models of which will correspond to k-length so­ lutions to the problem (for some fixed integer k). Model­ finding is done by efficient SAT solvers [Selman et. al., 1992; Crawford & Auton, 1996; Bayardo & Schrag, 1997]. Kautz et. al. propose to start with some arbitrary value of k, and increase it if they do not find solutions of that .length. They have considered a variety of ways. of generati~~ the encodings, corresponding loosely to different traditiOnal planning algorithms.

In the context of the general refinement planning frame­ work, we can offer a rational basis for the generation of the various encodings. Specifically, the natural plac.e ~here SAT solvers can be used in refinement planmng IS m the "solution extraction phase". As illustrated in Figure 7, after doing k "complete" and "strongly progressive" refinements on a null plan, we get a planset whose minimal ca~di?ates contain all k-length solutions to the problem. So, ptckmg a solution boils down to searching through the minimal can­ didates-- which can be cast as a SAT problem. This account naturally relates the character of the encodings to the type of refinements used in coming with the k'h-level planset and how the plansets themselves are represented.

Ia there a minimal candidate of P, that Ia a solution to the problem? ( ctm be encodfld as 11 SAT pipblem If R,, R,, .... , R, are all complete and progressive Then Minimal candidates of P, will contain all k-length solutions Shape of the encoding depends on - Refinements " - Representations for plansets - Disjunctive/non-disjunctive

Figure 7. Relating refined plan at k-th level to SATPLAN encodings.

Kautz et./ al. concentrate primarily on direct translation of planning problems to SAT encodings, sidelining. refi~eme~t planning [Kautz et. al., 1996] (the only exceptiOn IS their Graphplan based encoding; see below) .. I believe that s1:1ch an approach confounds two orthogonal Issues: (1) Reachmg a disjunctive plan whose minimal candidates contain all the solutions and (2) Posing the solution extraction as a SAT problem. . . .

It is best to separate these Issues and see the mam contri­ butions of SA TPLAN as pertaining to the second one. The issues guiding the first are by and large specific to planning, and are best addressed in terms of refining disjunctive plans. The issues guiding the second are ~~neral heuri~tics ~­ garding the effective ways of compthng a combmatonal search problem into a SAT instance, and are only loosely tied to planning. The main concern here is to end up with a SAT instance that is "small" (e.g., in terms of number of variables). The techniques used to achieve this involve syn­ tactic optimizations such as converting n-ary predicates into binary predicates, or compiling out dependent variables.

Separating planset construction and its compilation into a SAT instance allows SATPLAN techniques to exploit, rather than re-invent, (disjunctive) refinement planning. It also removes the arbitrariness involved in "guessing" the length of the solution as a pre-requisite for corning up with a SAT encoding, since solution extraction is interleaved with refinements. It may also be possible to develop heuristics that attempt to predict whether it is worth doing solution extraction on the current plan (as for example, Graphplan does).

In addition, I speculate that basing encodings on kth level plansets may also lead to SAT instances that are "smaller" on the whole. Specifically, the pruning done by disjunctive refinements can also lead to a planset with fewer number of minimal candidates than can be achieved by direct encod­ ings. This can in turn lead to a tighter SAT encoding. My speculation is supported to some extent by the results re­ ported in [Kautz and Selman, 1996] which show that SAT encodings based on k-length planninggraphs generated by Graphplan, can be solved more efficient!~ than the "linear" encodings generated by direct translation.

5. Challenge Problems

The framework of relations that we have outlined in this paper gives rise to several open issues that are worth inves­ tigating. I pose them below as challenge problems to the researchers in the planning community:

5.1 Disjunctive refinements

In Section 3, I argued that the success of Graphplan can be interpreted in terms of the idea of disjunctive planning. The only implemented and widely tested disjunctive planner is Graphplan, and it is based on forward state space refine­ ments. Given the known disadvantages of forward state­ space refinements vis a vis the other goal directed refine­ ments, it seems likely that disjunctive planners based on these other refinements may scale-up even better. This leads to the first challenge:

Challenge 1. Develop disjunctive planners based on ( l.a) backward state space, (J.b) plan-space and (I .e) task re­ duction refinements, either working independently or in combination.

Section 3 explicates some of the critical issues involved in implementing disjunctive planners, but a lot remains to be done. An easy first step in this direction would be to have a version of Graphplan algorithm that uses backward state space refinements (which can in principle out-perform Graphplan by being goal-directed). A more interesting step is to develop a disjunctive planner based on plan-space re­ finement, and see if the advantages of plan-space refinement over state-space ones in the traditional planners carry over to disjunctive planners. Given the dominance of task reduc­ tion refinements in practical planners, it is also imperative to develop disjunctive planners based on task reduction re­ finement. Finally, since interleaving refinements is known to have advantages in traditional planners [Kambhampati & Srivastava, 1996], it would be worth considering disjunctive planners that interleave refinements. The key in all these cases will be to handle the tradeoff betwe('(n cost of the re­ finement and the loss of pruning power by generalizing the corresponding refinements to make them infer more than just action constraints. The discussion in Section 3 may suggest some ideas in this regard. Progress on the first challenge can put us at a good vantage point to answer a more global one:

1 Kautz and Selman interpret the superior performance of graph­ plan encodings over linear encodings to the fact that the former allow action parallelism. However, as shown in [Kambhampati & Lambrecht, f997], the real contribution of graphplan is not sup­ porting parallel actions, but rather allowing forward state space refinements over disjunctive plans.

Challenge 2. Characterize tradeoffs offered by different refinements in supporting disjunctive planning.

The most interesting issues to be resolved here include whether and how the tradeoffs between the various refine­ ments change when we shift from traditional refinement planners to disjunctive planners (c.f. [Barrett & Weld, 1994]): Would plan-space and task-reduction refinements maintain their advantages over in disjunctive planning algo­ rithms too, or would they be less effective (presumably be­ cause they do not support effective refinement and con­ straint propagation)? The answer may depend on how ef­ fectively the corresponding refinements can be generalized to disjunctive plans.

5.2 Issues in SAT compilation

Given that SAT compilation seems to be the most promising way of doing solution extraction on disjunctive plans, re­ velopment of effective disjunctive planners will require at­ tention to the SAT compilation issues. The problem­ independent tradeoffs in SAT compilation are the subject of a challenge paper by Selman et. al. [ 1997], and will not be discussed here. Our interest here is to understand the spe­ cific compilation tradeoffs directly related to planning:

Challenge 3. Characterize the tradeoffs offered by SAT­ encodings based on disjunctive plans derived by different types of refinements (alone or working in an interleaved combination).

The issues to be resolved here include understanding (1) how easy would it be to solve the SAT encodings resulting from different refinements and (2) how to effectively exploit the shared structure of the SAT encodings corresponding to successive levels of disjunctive plans. The first issue is es­ pecially interesting in light of the current experience that SNLP encodings, despite being more compact, are harder to solve [Selman et. al., 1997]. The second issue is motivated by the fact that solution extraction is interleaved with in­ cremental refinement operations, and thus the disjunctive plans at successive levels share a significant amount of sub­ structure. Indeed, one of the sources of efficiency for Graphplan algorithm is the way the backward search phase on successive planning-graphs can use the information computed in the previous levels (e.g. memoizing).

It would also be interesting to understand why SAT com­ pilation is so effective in the first place. Kautz and Selman's [1996] original arguments seemed to imply that the effec­ tiveness has a lot to do with stochastic search methods used in solving SAT problems. This implication been called into question by the recent results of Bayardo and Schrag [ 1997], which show that systematic approaches can do just as well. So, a pertinent question is: Is the compilation into SAT jus­ tified purely by modularity concerns (in that different plan­ ning algorithms do not have to worry about specialized so­ lution extraction procedures), or is there any inherent advantage to SAT representation? A partial attempt at resolv­ ing this issue would be to enrich the backward search (solution extraction) phase of the Graphplan algorithm with the CSP techniques such as dependency directed back­ tracldng, to see if it could rival the SAT performance.

5.3 The utility of controlled splitting

In terms of our general refinement planning template, tradi­ tional planners split each of their component plans into a different search branch, while Graphplan and SA TPLAN can be thought of in terms of not splitting the plansets at all. Research in constraint satisfaction and operations research shows that pruning and splitting can have synergistic inter­ actions. In fact, the best CSP search strategies combine low-level constraint propagation (pruning) techniques, such as forward checking, with splitting [Bayardo & Schrag, 1997]. This raises the possibility that best disjunctive plan­ ners may also do controlled splitting of plan sets (rather than no splitting at all) to facilitate refinements with more prun­ ing power. Controlled splitting may also be helpful in sce­ narios where planning and execution need to be interleaved of necessity. Although some initial exploration has been done in this direction by Descartes and UCPOP-D planners, a more systematic analysis of tradeoffs is still needed. This leads to the next challenge:

Challenge 4. Develop and explore the tradeoffs offered by planners that split some of the disjunction into the search space, while keeping the rest together in disjunctive format.

One immediate question is exactly how many branches should a planset be split into? Since the extent of propaga­ tion depends on the amount of shared sub-structure between the disjoined planset components, one way of controlling splitting may be to keep plans with shared sub-structure together. Of particular theoretical interest would be exhib­ iting domains and problems where full disjunction is counter-productive. A first step in this direction would in­ volve experimenting with versions of Graphplan algorithm that maintain multiple planning-graphs at each level [Kambhampati & Lambrecht, 1997].

SA Exploring alternative Representations

We have noted in Section 2.2 lhat there is nothing sacro­ sanct about the particular representation for partial plans that is used by most existing planners. Alternative repre­ sentations may either be dictated by necessity (for example, the time-map based plan representations used in planners like HSTS [Muscettola, 1993] to support the use of expres­ sive resource constraints in planning), or as more flexible ways of representing and handling sets of action sequences (for example, the representation used in COPS [Ginsberg, 1996]). The general framework and ideas described in this paper are independent of the specific representations used for partial plans. For example, Ginsberg's COPS planner can be seen as an instance of the disjunctive planning ap­ proach, that uses a very different partial plan representation (albeit with the same candidate set semantics). The approach shares the ideas of direct refinement of disjunctive plans and solution extraction by enumerating minimal candidates. Representations can however have a significant impact on the ldnds of refinements that can be supported. Ginsberg describes a type of refinement on his plan representation that has the ability compute both upper and lower approxi­ mations on the set of solutions. This leads us to an interest­ ing, but somewhat open-ended challenge.

Challenge 5. Develop and investigate the utility of alterna­ tive plan representations on the efficiency of plan genera­ tion.

While development of new representations is an open­ ended task, a first feasible step in this direction would be to do a direct empirical comparison of currently available al­ ternative representations, such as those used in COPS or HSTS. It would also be interesting to undertake each of the previous challenges in the context of the alternative repre­ sentations.

6. Conclusion

In this paper, I presented a generalized view of refinement planning that bridges several hither-to distinct strands of planning research. I have outlined how the insights from this unification can help both traditional and SAT-based plan­ ners. Finally, I have proposed as a challenge to the commu­ nity, a set of research problems, tackling which can lead to a significantly improved understanding of the issues involved in efficient plan synthesis.

To support research into these challenge problems, I in­ tend to maintain a web site that will act as a clearing house for information on our evolving understanding. Its URL will be http://rakaposhi.eas.asu.edu/challenge.html . This site will contain references to other relevant literature, pointers to benchmark problems and test-domains, as well as more fleshed out versions of the challenges and their up­ to-date status.