Generalizing GraphPlan by Formulating Planning as a CSP

1 Introduction

A powerful technique for solving planning problems, first used in [Kautz and Selman, 1996], is to impose a fixed bound on plan length. This converts the problem to one that lies in NP. The resulting problem can then be solved by encod­ ing it in any of a number of alternative NP-co_mplete for­ malisms, e.g., SAT [Kautz and Selman, 1996], mteger pro­ gramming [Vossen et a/., 2001 ], or constraint satisfaction problems (CSPs) [van Beek and Chen, 1999; Do a~d Kamb­ hampati, 2001 ], and then using the powerful algonthms that have been designed to solve these general problems ..

In this paper we examine the approach of encodmg _plan­ ning problems as CSPs more closely. We use a very Simple encoding to translate the planning problem into a _ CS~. The advantage of using CSPs in general, and our encodmg 1~ ~ar­ ticular is that it preserves much of the structure of the ongmal planni~g problem, and thus various t~ansformations that uti­ lize this specific structure can be applied to create a new CSP that is easier to solve.

The utility of exploiting planning specific structure has been convincingly demonstrated by the BLACKBox [Kautz

Fahiem Bacchus

Dept. Of Computer Science University of Toronto Toronto, Ontario Canada, MSS 3G4 tbacchus@cs. toronto.edu

and Selman, 1998] and GP-CSP [Do and Kambhampati, 2001] planners. These systems encode a transformed repre­ sentation of the planning problem called the planning graph to SAT and CSP respectively. The planning graph is a plan­ ning specific construction, due to [Blum and ~~rst, 1997], that computes and represents some important additiOnal struc~ral information about the planning problem. Thus by encodmg the planning graph rather than the original planning problem, BLACKBox and GP-CSP are able to capture more of the structure of the planning problem in their encoding, which results in a significant improvement in performance.

In our approach we bypass the construction of a planning graph. Instead, we study techniques that can equally well exploit the structure of the planning problem and at the same time work directly on the CSP encoding. We demonstrate that it is possible to develop transformations that uncover all of the additional structure obtained from planning graphs.

The advantage of our approach is that it works directly on a much richer and more robust representation. Consequently we obtain at least three important advances over the planning graph construction: ( 1) Our approach allows us to general­ ize planning graphs. In particular, we can enhance our ap­ proach to extract other kinds of structure to allow us to solve the planning problem more efficiently. (2) We can more e~s­ ily extend our approach to more complex types of p!annmg problems, e.g., those involving resource usage. (3) Smce the final result is a CSP we can automatically utilize CSP solu­ tion techniques which can be more powerful than st~ndard GRAPHPLAN searching methods. In the paper we will pro­ vide evidence for all of these points.

First, we present our CSP encoding of a planning problem. Then we present a set of transformation~ that can be use? to eliminate variables and add new constramts to the encodmg, and show that these transformations subsume and generalize planning graphs. Then we present empirical evi~ence to ~al­ idate the effectiveness of our approach to solvmg planmng problems. To demonstrate that our appro~ch can be more ea~­ ily lifted to more complex types ofp~annmg, we sh~w how It can be easily extended to plarming With resources. Fmally we close with some conclusions and a description of future work.

2 Generating the BASE-CSP

To encode a planning problem as a CSP we impose a bound k on the "size" of the plan. In this paper we will measure plan size by the number of GraphPlan-concurrent steps (GP­ steps) in the plan. It will become apparent in the sequel what GP-steps means.

In k GP-steps each proposition or action can change at most k times. So to encode a k GP-step plan in a CSP we can utilize k + 1 sets of propositional variables Pt , and k sets of action variables Aj, where s ranges from 0 to k for propositions and 0 to k - 1 for actions, and i and j range over the number of distinct propositions and action instances in the planning problem respectively. Each of these variables will be boolean. Intuitively, Pt means that proposition Pi is true at GraphPlan step s, and A j means that action instance Ai was executed at GraphPlan step s ( ·Pt and ·Aj denote the opposite).

Clearly by setting each of these variables we can capture any k GP-step plan and its effects. However, many illegal plans and nonsensical outcomes are also captured. We need constraints to ensure that any solution to the CSP (i.e. , any setting of the variables that satisfies all of the constrains) is a legal plan. There are various possible sets of constraints that can serve our purpose. Here we present one particular set:

1. Unary initial state and goal constraints. The fropositional variables from step zero, PP, and from step k, Pi are required to have values compatible with the initial and goal states of the planning problem.
2. Precondition constraints. An action Aj cannot be true unless its precondition is satisfied. This gives the constraint Aj --> Pre(A1 ) 8 , where Pre(A1 ) 8 is A1 's precondition rela­ tive to GP-step s.
3. Successor state constraints. Implicit in classical planning representations is the frame assumption: predicates not men­ tioned in the action's description are unaffected by the action. We can capture the effects of actions, including the implicit non-effects in a number of different ways. Here we use Re­ iter's formulation of successor state axioms [Reiter, 200!]. In particular, for each propositional variable Pt at GP-step s (s > 0) we have a constraint between it and the same propo­ sition at GP-step s-1. The constraint says that Pt is true if and only if some action made it true, or it was previously true and no action made it false. Thus the successor state axiom constraints take the form:

where Create(~) and Delete(P;) are the set of actions that create and delete P;. It is easy to automatically generate a set of successor state constraints from a set of STRIPS action de­ scriptions. Additionally, by using successor state constraints that mention additional propositions from step s -1, it is easy to encode ADL [Pednault, 1989] operators as a set of succes­ sor state axioms. 1

1 Note that the successor state constraints do not encode the action preconditions. These are encoded as separate constraints. Thus, the only complication with ADL actions has to do with con­ ditional effects. If P; is a conditional effect of action Ai , subject to the condition ¢>, the successor state constraint will have a disjunct "Aj- 1 1\ ¢>· - 1 " . That is, P/ will be true if Ai was executed and condition ¢> held at the previous step.

1. GP-Concurrency Constraints. The above successor state axiom allows the unintended model in which we have two actions at the same step, one creating a proposition and one deleting it. To avoid such unintended solutions we must re­ strict concurrent actions in some way. The most natural way is a serial constraint, which says that only one action variable can be true at any step. 2 Another type of constraint is one that imposes GraphPlan concurrency. Basically it asserts that two actions cannot be simultaneously true if they interfere with each other. In this work we have chosen to use the GraphPlan (GP) concurrency constraints.
2. Non-Null Steps Constraints. We impose the constraint that for every step s at least one action variable should be true. This blocks null steps in the plan, in contrast [Blum and Furst, 1997] and [Do and Kambhampati, 2001] both allow null plan steps.

We will refer to this set of variables and constraints as the BASE-CSP. Any solution to the BASE-CSP will contain a setting of the action variables that comprises a valid GP­ concurrent plan. If the BASE-CSP has no solution then no k GP-step plan exists for the problem.

3 Reduction of the BASE-CSP

Given a BASE-CSP representing a k-step planning problem we can use various transformations to modify it, generating a new CSP that is empirically easier to solve, and that is equiv­ alent to the BASE-CSP in the sense that any solution to the new CSP can easily be extended to a solution to the origi­ nal BASE-CSP. These transformations include inferring new constraints that can be added to the CSP and eliminating var­ ious single valued variables. Our transformations are related to the well known techniques of enforcing local consistency on a CSP prior to solving it [Freuder, 1985], however they are based on taking advantage of the specific logical form ofthe above set of constraints.

3.1 Adding GraphPian Mutex Constraints

A well known technique for making CSPs easier to solve is to add redundant constraints, e.g., [Getoor et al., 1997], which are constraints that make explicit additional relations between the variables. Redundant constraints that are useful to add are usually determined by examining the structure of the partic­ ular CSP. This is precisely what is done in planning graphs, where insights into the manner in which actions and propo­ sitions interact, are used to generate a new set of binary con­ straints called mutexes.

New binary constraints can be added to a CSP by enforcing 2-j consistency [Freuder, 1985]. A CSP is 2-j consistent if for every valid assignment to a pair of variables, there is a set of values for every j additional variables such that the 2+j assignments satisfy all of the constraints over these variables. Making a CSP 2-j consistent can be very expensive as it in­ volves testing all sets of 2+j variables, and each test in the worst case takes time exponential in j. In planning problems there can be thousands of variables, so it would be impossible to make the entire BASE-CSP 2-j consistent even for small j. The contribution of GRAPHPLAN is that it demonstrated a technique that quickly achieves a very effective partial form of 2-j consistency over a limited collection of 2+j variables.

2 Serial actions can be used to represent true concurrency by adding timestamps to the states [Bacchus and Ady, 200 I; Pirri and Reiter, 2000].

We can use the CSP representation to directly compute the binary mutex constraints generated by planning graphs. In this manner we lift the mutex computation to a more general framework where it can be more easily generalized.

Mutexes in GraphPlan are generated by three simple rules: (1) Base Action Mutexes. Actions in the same GP-step with interfering effects and preconditions are mutex. (2) Addi­ tional Action Mutexes. Two actions in the same GP-step are mutex ifthere is a pair of propositions, one from each action's preconditions, that are mutex at this GP-step. (3) Proposi­ tional Mutexes. Two propositions, P;" and PJ, at the same GP-step, are mutex if every action that achieves P;" is mutex with every action that achieves PJ . We can create all of these binary constraints by testing for very similar conditions in the CSP encoded planning problem:

Base Action Mutexes. These mutexes are already present in the BASE-CSP; they are the GP-concurrency constraints.

Additional Action Mutexes. The GRAPHPLAN condition for detecting additional action mutexes only handles actions with conjunctive preconditions, e.g., STRIPS actions. Thus if we have a pair of preconditions P;" for Ai and PJ for Aj, the corresponding precondition constraints Ai -+ P;" and Aj -+ PJ, and a mutex constraint ·P;" V ·PJ, a simple 2-2 consistency test with these variables and constraints al­ lows us to derive the new mutex constraint ·Ai V ·Aj. In fact, we can short-circuit this test by using the presence of the mutex constraint between P;" and PJ to immediately mark all actions with precondition P/ as bemg mutex with all actions with precondition PJ. Furthermore, if an action Ak contains both P;" and PJ in Its precondition we obtain the constraint ·Ak V ·Ak, i.e. , we obtain a unary constraint that forces Ak to be false. As we will describe below, single valued variables can be used to further reduce the CSP. A similar approach can be followed with more general types of preconditions using more general local consistency tests, e.g. , with ADL actions where the GRAPHPLAN test is no longer valid.

Propositional Mutexes. For propositional mutexes we have one added complication, which is that our encoding, un­ like planning graphs, does not utilize no-ops. Nevertheless, a general condition for when two propositions P/ and PJ are mutex can be given by examining the three cases.

1. ,pis- I A ·PF 1 holds. In this case for P;" and PJ both to be true in the next state they must both be created by an action. In particular, neither proposition can remain true by inertia. For a mutex between P;" and PJ to hold we must have for every action A:-I creating P/ that As- ! 1\ (As-! As-!) Th · ' i V Aj ECr eat e(Pj ) i -+ ' j · at IS, either the action is not possible, or it must be mutex with
2. all actions that create PJ. 3 A similar condition must be satisfied by the actions creating P;".
3. · P/ - 1 APJ- 1 (or analogously P/- 1 A ·PJ- 1 ) holds. In this case for both P;" and PJ to hold P;" must be created by an action. For the mutex to hold we must have for every action A: - I creating P{ that · Af - 1 V (Af- 1 -+ ·PJ ). That is, either the action is not possible or it must delete PJ (else PJ can be true by inertia).
4. P/- 1 A PJ- 1 holds. In this case we must have for every action A s-! that · As-l v(As-l -+ -,p/ - 1 )v(As-l-+ -,p; -I ). That is, either the action is not possible, or it must delete at least one of Pi or Pj. Note that this condition relies on the fact that at least one action must be executed at every step (the non-null steps constraint).

As in planning graphs, We can use the constraints added at step i to test for new mutex constraints at step i+ 1. The following result can then be easily proved (we omit the proof for reasons of brevity).

Proposition 1 If the planning graph construction has de­ tected a mutex constraint between two variables Vis and Vjs (action or propositional variables), then after transforming the BASE-CSP to add the above mutex constraints we will have that either (a) both variables in the CSP will have be­ come single valued with not both being true or (b) there will be a binary constraint in the CSP between these variables that prohibits them from both being true.

That is, the transformed CSP will capture all of the planning graph mutexes. Furthermore, it might contain more mutexes than those inferred by the planning graph. In the simplest case this can arise from the last case presented above where every action deletes one of Pi or Pj . This can create a new mutex in the middle of the plan. In planning graphs, on the other hand, once Pi and Pj appear in the graph without a mutex between them, they can never become mutex again (due to the presence of no-ops and the possibility of null steps in the plan).

3.2 Symbolic Reduction of Single Valued Variables

In any CSP P, if P has a variable V with only a single value a in its domain, we can reduce P by making the as­ signment V +-- a, to produce a new CSP P' that does not contain the variable V . P' has the property that for any so­ lution S of P', S U {V +-- a} is a solution to the original P. To reduce P, we replace every constraint mentioning V, e.g., C(V, V~, ... , Vk) by a new constraint C'(V1 , ... , Vk ) such that C' (VI +-- X! ' . .. ' vk +-- Xk ) is true of a tuple of assignments (x1 , . . . , x k) if and only if C(V +-- a, V1 +­ X! , .. . , Vk +-- Xk) is true.

Our translation from a planning problem produces a BASE­ CSP in which every constraint C is represented symboli­ cally by a logical formula. We can simplify this logical for­ mula directly by replacing the single valued variable V by its value, and then performing standard logical reductions, e.g. , FALSE 1\ a ~ FALSE, FALSE V a~ a, etc. This yields a new logical formula that represents the reduced constraint C'.

3 Note that if AI- 1 deletes Pf then it will be mutex with all ac­ tions creating P/ via the GP-concurrency constraints.

In the case of the BASE-CSP we also know the form of its different constraints. This allows us to precompute many types of constraint reductions, so we can realize many types of single valued variable reductions more efficiently.

The reduction of a single valued variable, or the applica­ tion of some of the other transformations described below, might generate new single valued variables that can in turn be reduced. It can also interact with the generation of mutex constraints, allowing new mutexes to be detected. For exam­ ple, say that we have determined that a propositional variable PJ must be false. If PJ appears in any conjunctive precon­ ditions, e.g., Aj -.. P~, we will also immediately infer -,AS, i.e., that Aj has also become single valued (false). With Aj false it can no longer be a candidate for producing some other proposition P/+ 1 , and we could possibly infer a new mutex involving P;"+l since one of the ways of making it true is now blocked. With mutexes, single valued variable reduction subsumes reachability analysis of planning graphs.

Proposition 2 The variables that remain in the CSP after single valued variables have been reduced, are a subset of the variables appearing in the planning graph.

4 Beyond GRAPHPLAN

Besides subsuming, and slightly generalizing, the planning graph inferences, further transformations can be utilized on the CSP. These transformations either add more constraints to the CSP or cause further variables to become single valued. In either case, like the planning graph inferences, they are used to make the CSP easier to solve. These additional con­ straints can also feed into the standard GraphPlan reductions described above, and thus generate even further mutexes.

4.1 Additional Binary Constraints

Graphplan mutexes only prohibit the single pair of values for two variables (TRUE, TRUE). Our representation treats negated propositions and actions in an entirely symmetric fashion. This means that the analysis for mutexes given above will allow us to compute mutexes between any two values. For example,when applied toP/ and ...,pJ, P/ being mutex with ...,pJ means that P/ is "mutin" with PJ; i.e., these vari­ ables must both be true or both be false. Such binary con­ straints can be detected and added to the BASE-CSP.

4.2 Single Valued Variable Reduction beyond GRAPHPLAN Reachability

As demonstrated above, single valued variable reduction is as powerful as the reachability analysis inherent in the planning graph construction. However, in the CSP encoding it is more powerful, obtaining, for example, the following additional re­ ductions:

1. Propositions that are never modified by any action, are propagated without change in the planning graph. Since these propositions have no creators nor deletors, their successor state axiom reduces all of them to being equiv­ alent to their status in the initial state, i.e., they will all

become single valued. Thus they can be reduced from the CSP prior to searching for a solution.

1. If all possible actions at step s create proposition P;"+ 1 then P;"+l is forced to be true. Similarly if it is deleted by all possible actions then it is forced to be false. P/+ 1 can then be reduced from the CSP. This particular reduc­ tion is not possible in planning graphs due to the pres­ ence of no-ops.
2. Variables that are forced to be true further reduce all variables that are mutex with them to be false. This does not help reduce a planning graph since in planning graphs mutexes are monotonically decreasing and, other than the initial state variables, variables are never forced to be true. 4 But in the CSP encoding the previous rules for forcing a variable to be true, and for creating a new mutex when it did not exist at the previous step, enable additional single valued variable reductions.

4.3 Sequence Constraints

There are some additional constraints that can be imposed on plans to rule out obvious inefficiencies. For example, it never makes sense in the plan to immediately follow an action by its inverse (e.g., a load followed by an unload). Adding this constraint allows eliminating different invalid combinations of actions by making mutex any inverse pairs of actions at consecutive time steps.

Blocking the immediate sequencing of inverse actions also allows us to infer additional sequence constraints. Say that actions Ai and Aj are inverses of each other, and that A; is the only action that produces Pk while Aj is the only action that deletes it. Then another constraint that can be inferred from the mutex between Af and A~+ 1 is that when Pk first becomes true, it must remain true fur at least one more time step:

There is also a similar constraint for when Pk first becomes false.

Our system automatically detects action pairs that are in­ verses of each other as well as any predicates over which a sequence constraint can be imposed.

5 CsP-PLAN: Implementation

Based on the transformations explained before, we have de­ veloped a planner called CsP-PLAN that will find a solution to a planning problem. CSP-PLAN builds the BASE-CSP in­ crementally up to step s (beginning with s = 1 ), and then sends it to a CSP Solver for its solution. If the solver reports no solution to it, then the BASE-CSP is constructed for s+ 1. This cycle can continue until some termination condition has been reached or a plan has been found. It is important to notice CSP-PLAN solves these problems incrementally, thus ensuring that it finds a GP-step optimal plan.

The CSP solver used by CsP-PLAN is EFC [Katsirelos and Bacchus, 2001] which allows the use of different techniques to solve a CSP problem, including: the ability to create and use tailored heuristics for dynamic variable ordering (DVO), the use of different state of the art CSP algorithms and a novel method to record nogoods. CSP-PLAN uses these methods as follows to efficiently solve general planning problems:

4 This means that the variable that is mutex with the true variable never appears in the planning graph until the mutex no longer holds.

DVO: CsP-PLAN uses a dynamic variable ordering heuristic called BSEARCH, specially tailored for planning problems. This heuristic instantiates first the variables that propagate the most changes in the domain.

Search Algorithm: The CSP algorithm uses a version of GAC propagation [Bacchus, 2000] during backtracking along with nogood recording. In addition, for each constraint with an arity higher than 2, special purpose propagators were de­ veloped to increase the efficiency ofGAC. It can be noted that although no good recording is a generic CSP technique, in the form implemented it is strictly more general than the mem­ oization of bad goal agendas described in [Blum and Furst, 1997].

6 Experimental Results

To test the performance ofCSP-PLAN, we used STRIPS prob­ lems from IPC2 and IPC3 (International Planning Competi­ tion 2000/2002). All experiments run on a Xeon 2.40GHz machine with 400MB of RAM. Times are in CPU seconds.

6.1 Effect of CSP techniques on CsP-PLAN

Table 1 shows the effect of a few different CSP algorithms on the performance of CSP-PLAN on some representative problems (using a standard CSP variable ordering heuris­ tic dom+deg). 5 We can see that GACCBJ and GACvsCBJ 6 perform over 2 times faster than plain GAC. GACCBJ and GACvsCBJ have comparable results on these problems, but we found that GACvsCBJ performed better on more com­ plex problems, e.g., for Gripper-04, GACvsCBJ finds a plan in 877 sees while GACCBJ required 1,133 sees. The table also shows that nogood recording yields another factor of almost 2 improvement over GACvsCBJ. Hence, we choose GACvsCBJ+RecordNoGood as our default CSP search algo­ rithm.

6.2 Effect of planning specific techniques

Some of the CSP simplification techniques explained in this article use planning related information, e.g, planning specific DVO heuristics, the addition of redundant constraints, the re­ moval of single valued variables, etc. The addition of redun­ dant binary constraints, particularly mutexes, and the detec­ tion and removal of single valued variables has a clear and dramatic effect on the efficiency of CSP-PLAN, even for sim­ ple problems. For example, on bw-large-12, the BASE-CSP has 1,289 variables and 10,426 constraints, but only 657 vari­ ables and 2,847 constraints after single valued variables are removed. Similarly, without the inferred mutex constraints and the removal of single valued variables, CSP-PLAN re­ quired 154.3 sec. to solve the problem. Adding the mutex constraints reduced this time down to 0.33 sec, and removing single valued variables brought the time down even further to 0.04 sees. The effect of some of the other planning specific techniques is described below.

5 0ther CSP algorithms were experimented with, but they did not provide adequate performance.

6 GACvsCBJ is described in [Bacchus, 2000].

DVO heuristic: The order in which variables are instanti­ ated during search greatly affects the solution times for a CSP. Table 2 shows the difference in performance between the standard CSP heuristic dom+deg, and our BSEARCH heuristic which was designed specifically to take advantage of the planning based structure of the CSPs that CsP-PLAN is solving. These representative problems show that BSEARCH performs much better than dom+deg.

Redundant Constraints: Table 3 shows the performance of CSP-PLAN when mutexes between inverse actions and se­ quence constraints are added to the BASE-CSP. On these problems we see that there is a slight improvement in CsP­ PLAN when mutexes between inverse actions are present. In­ terestingly, adding sequence constraints did not help. Minor improvements on some problems were negated by significant degradation on others.

6.3 Comparison with similar approaches

The results in Table 4 show how CSP-PLAN (using the same setting for all problems? compares with GRAPHPLAN [Blum and Furst, 1997], GP-CSP [Do and Kambhampati, 2001], BLACKBOX [Kautz and Selman, 1998] and IPP 4.1 [Koehler et a/., 1997]. These planners have in common the construc­ tion of a planning graph. The planning graph is either then compiled into a CSP (GP-CSP) or a SAT formula (BLACK­ Box), or searched directly for a solution (GRAPHPLAN and IPP 4.1). CsP-PLAN, on the other hand, bypasses the plan­ ning graph construction and directly exploits the CSP encod­ ing of the problem as explained above.

7 A number of planning domains could be solved faster with dif­ ferent settings; e.g., the heuristics sometimes performed differently

It can be seen that CsP-PLAN yields significantly better performance in almost all cases over the standard planning graph planners GRAPHPLAN and GP-CSP. This provides evidence of the effectiveness of the additional constraints and reductions computed by CsP-PLAN. The results against BLACKBox are mixed. This version of BLACKBox utilizes the highly engineered Zchaff [Moskewicz et a!., 2001] SAT solver. Zchaffutilizes very different heuristics and techniques for learning nogoods (clauses) than CSP-PLAN and is more efficient that our current CSP code on larger problems. Nev­ ertheless, there is considerable scope for making our Csr­ PLAN implementation more efficient, and our heuristics are at this stage very simple. Even so, our approach demonstrates its usefulness on problems like gripper.

Similarly against IPP our results are mixed. A key com­ ponent of IPP is a method for solving planning problems by dividing them into a set of smaller problems using a goal agenda [Koehler, 1998b]. This technique is particularly effec­ tive on domains like BlocksWorld, Depots and Gripper, and it can easily be recast in terms of CSPs. Hence, CsP-PLAN could be extended to utilize this technique. On other domains like logistics CsP-PLAN is more effective. This is due partic­ ularly to the presence of mutexes between inverse actions in these domains that can be effectively used by CSP-PLAN.

on different domains.

7 Extensions: Planning with Resources

A major advantage of encoding planning problems as CSPs is that we can easily extend the encoding to represent more complex planning problems. For example, planning prob­ lems with resources can simply be represented as CSPs with numeric variables. To demonstrate the flexibility of our ap­ proach we implemented an extension of CsP-PLAN to deal with such planning problems. Previous approaches based on planning graphs (e.g., [Koehler, 1998a]) have had to develop from scratch methods for dealing with the resources variables in the planning graph, like interval arithmetic and bounds propagation. These techniques are already well known in the CSP field.

To handle planning with resources we introduced the fol­ lowing into Csr-PLAN: (1) Mathematical operation con­ straints, e.g., x = z + y; (2) comparison constraints, e.g., x > y; (3) precondition constraints containing comparisons, e.g., fuel( truck) > 0; (4) successor state constraints to define how the numeric variables could change between states, e.g., if no action affecting it is true, its value cannot change; (5) and finally, additional concurrency constraints to block ac­ tions from simultaneously altering a numeric variable. These new constraints were very easy to add to the BASE-CSP, and the reduction transformations described above were used al­ most unchanged to simplify the BASE-CSP.

We compared CSP-PLAN with MIPS [Edelkamp, 2002] 8 to evaluate its performance on resource planning problems. MIPS combines two paradigms, model checking and heuris­ tic search, to find totally ordered plans that are then made concurrent using a post-processing procedure. This combi­ nation of paradigms introduces additional complexity to the algorithm, in contrast with the uniform paradigm used in our approach. MIPS tries to minimize the number of steps in the final plan, using an optimization parameter that ranges from 1 to 10. Table 5 shows this how parameter affects the qual­ ity of the final plans in MIPS. Increasing the parameter causes MIPS to spend more time trying to find plans with fewer steps. However, this search is not always successful. In fact MIPS can spend more time and generate worse results. CSP-PLAN, on the other hand, is an optimal planner always finding the shortest plan in terms of number of GP-steps. This is a sightly different optimization criteria from that used by MIPS. How­ ever, even under MIPS's optimization criteria CSP-PLAN's plans are much better than those found by MIPS. 9

Table 6 compares both planners (MIPS running with its op­ timization flag set to 5). The results in this table show that CSP-PLAN has a performance comparable to MIPS, and in most cases, the quality of the plans (number of steps) is con­ siderably better. However, CSP-PLAN does not scale as well as MIPS, e.g., it takes much longer than MIPS on Driver­ LoglO. But is not surprising since CSP-PLAN is an optimal planner while MIPS is not. Achieving optimality quickly be­ comes very difficult. It is also important to note that our pro­ totype implementation uses very simple techniques to prop­ agate numeric variables. These techniques are far from the current state of the art in CSPs. Nonetheless, we see that we still obtain results competitive with the competition version of MIPS.

8 MIPS competed in IPC3. No planning graph based planner was

8 Conclusions

Our implementation of CSP-PLAN has demonstrated that the structure of planning problems can be exploited directly in a CSP encoding. By lifting the planning problem to a CSP we obtain a richer and more robust representation for which many sophisticated and effective solution techniques have been developed. In particular, we are able to capture and gen­ eralize the important inferences generated by planning graphs directly in the CSP representation. This provides excellent performance for CSP-PLAN in comparison with similar tech­ niques. Additionally, by showing how easily we can extend our representation to planning with resources, we have pro­ vided evidence for the benefits oflifting the problem to a CSP encoding.

This work naturally leads to a number of future research topics. For example, the fastest current planners are based on local search. Nevertheless, the heuristics used in these planners utilize notions from the planning graph construction. It seems feasible that instead of planning graphs, CSP tech­ niques could be utilized directly to compute better heuristics. This could be particularly beneficial for computing more in­ formative admissible heuristics. Better heuristics and addi­ tional transformations could also be explored. In particular, there is still much scope for improving the performance of this approach. Finally, the approach is well suited to resource usage optimization using branch and bound techniques dur­ ing the search, and this could be further investigated.

extended to deal with resources in this competition.

9 Note that neither planner is actually trying to optimize resource usage, just the size of the plan.