To Encode or Not to Encode - Linear Planning

1 Introduction

Rapid improvement in the performance of stochastic local search (SLS) methods for solving propositional satisfiabil­ ity (SAT) problems coupled with the naturalness with which many problems can be reduced to SAT problems has led to the popularity of an encode & solve approach to problem solving. In this three phase approach, the original problem is reduced into a sentence in propositional logic; a satisfying assignment for the sentence is searched for using state of the art SLS al­ gorithms; and a solution, if found, is converted back into a solution to the original problem. This method has become increasingly influential in the area of classical AI planning, where it is known as the planning as satisfiability approach (PAS) [Kautz and Selman, 1992].

But is it not more effective to apply SLS methods directly to the original problem space? In this paper we report on our investigation into this issue in the context of planning problems. We describe the LPSP planner (linear Elan-level ~tochastic planner) which uses SLS on the space of linear plans to solve planning problems. We chose to explore the space of linear plans because we found it easier t~ formu­ late and program heuristics, metrics, and moves m this space. LPSP has a number of operators for moving in this space that

Holger H. Hoos

Department of Computer Science University of British Columbia Vancouver, BC V6T 1Z4, Canada

hoos@cs.ubc.ca

enable it to discover plans in a small fraction of the number of steps required by SLS algorithms operating on the encoded planning problems. Some of its moves are reasonably nat­ ural when projected to the encoded problem. Others have no apparent equivalent, are motivated by the particular struc­ ture of planning problems, and are based on intuitions devel­ oped in classical work on partial-order planners (e.g., causal links, threats, producers, consumers, plan repair). Each move is considerably more expensive than moves made by, e.g., WALKS AT [Selman et at., 1994], yet the overall performance is better than that of SAT based algorithms operating on en­ coded planning problems that share the linearity assumption.

Our planner is not competitive with planners such as BLACKBOX [Kautz and Selman, 1998] in domains in which parallel plans are much shorter than linear plans, e.g., the lo­ gistics domain. 1 Because the search space size is exponen­ tial in the plan length, LPSP is in a considerable disadvantage in such cases. However, it performs better than SAT based planners when the use of concurrency leads to little or no decrease in plan length. More generally, it does better than the SAT based approaches when we use Medic's [Ernst et at., 1997] encodings in which the linearity assumption is en­ forced. We believe that this latter comparison is more valid when we come to examine the encoded vs. un-encoded for­ mulations. In fact, we believe that these observations will ap­ ply when we extend this work to parallel plan structures. In Section 5, we discuss evidence from current research support­ ing this view. Overall, our results seem to support the thesis that SLS methods applied to problem domains with sufficient structure can outperform the encode & solve approach.

2 The Planning as Satisfiability Approach

Given a planning problem and some natural number n, we can generate a propositional formula whose models correspond to n step solutions to the problem. There are a number of schemes for generating such a formula (see, e.g., [Ernst et at., 1997]), but the essential idea is that variables in this formula represent the value of the propositions describing the domain at different time points as well as the actions that are or are not applied at each time point. Hence, these variables contain information about the dynamics of the world throughout the execution of the plan. The formula contains constraints that these variables must satisfy if they describe the state of the world during the execution of a valid plan. From the value assigned to variables representing actions in any satisfying assignment we can easily infer a valid plan.

1 By plan-length we refer to the number of time-steps in the plan representation. Parallel plan representations, unlike linear represen­ tations, allow the assignment of more than one (non-interfering) ac­ tions to a single time point.

We can extend this idea into a planning algorithm as fol­ lows. Starting with some initial guess for n, we generate an appropriate formula. If it is satisfiable, we can get a plan by inspecting the satisfying assignment. Otherwise, we increase n and repeat.

As shown in [Kautz and Selman, 1996], this approach can be quite efficient thanks to the availability of fast SLS-based algorithms for SAT problems such as WALKSAT [Selman et al. , 1994]. WALKSAT starts by randomly picking a truth as­ signment. At each step, WALKS AT randomly chooses an un­ satisfied clause c and makes it satisfied by flipping the value of one of its variables v. If possible, vis chosen so that no cur­ rently satisfied clause becomes unsatisfied by this flip. Oth­ erwise, the variable is either chosen randomly or by selecting the flip that maximizes the number of satisfied truth assign­ ments - called the assignment's score.

3 The LPSP Planner

Search space The LPSP planner performs SLS on a space of fixed length linear plans. As in the PAS approach, LPSP is given this length as part of its input. Hence, the states of the search space consist of sequences of ground actions of length n, where n is an input parameter. Null actions (i.e., actions with no preconditions or effects) are allowed as part of the sequence. In principle, with the introduction of appropriate operators, it is a simple matter to let LPSP operate on plans of varying length, much like conventional planners. However, we have not experimented with this option, yet.

Scoring plans LPSP scores (or more accurately, penalizes) plans by a weighted sum of plan flaws. A flaw arises in a plan when an action a (the consumer) has a precondition p and the closest predecessor a' of a that influences the value of p (the cloberer) has ·p as an effect. Each flaw's weight is d, the distance between a' and a. (In some domains, a weight of d 2 or cfl, performs better.) Each plan is penalized by the sum of the weights of all its flaws. Naturally, a plan is valid iff it has no flaws and consequently has 0 penalty.

Example 1: Consider a blocks' world domain with four blocks and actions of the form MOVE(x , y, z) which takes block x from y and places it on z . Its preconditions are ON(x , y), CLEAR(x), and CLEAR(z). Its effects are ON(x, z), CLEAR(y), ·ON(x, z), ·CLEAR(z).

Suppose that initially c is on A, and that B and D are on the table, and we want to reach a goal state in which A is on B and B is on c. Consider the following three step plan: MOVE(C,A,D), MOVE(B,D,C), and MOVE(A,TABLE,B). This plan contains a single flaw: the ON(B,D) precondition of MOVE(B,D,C). The closest predecessor of this action influ­ encing ON(B,D) is the initial action, 2 which has ·ON(B,D) as an effect. In this cased= 2 and so the plan's penalty is 2.

Moving around the search space Since plan space is searched, we can use various operators for moving in this search space that do not have natural counterparts in the space of truth assignments. In particular, the use of special plan re­ ordering operators is crucial to LPSP's success. Without them, it usually does not find a solution.

2 We use the well known technique of inserting a (fixed) fictitious initial action that "sets-up" the initial state as its effects and a ficti ­ tious final action that has the goal as its precondition.

(1) Best-Replacement: This operator scores all plans that differ from the current plan by a single action, i.e., plans in which one of the current plan's steps was replaced. It returns the plan with the least penalty score among these. 3 In Example 1, we would consider plans in which one of the current steps was replaced by some ground action. In particular, when we replace the MOVE(B,D,C) step with MOVE(B,TABLE,C) we get a plan with no flaws.

(2) Flaw-Repair: This operator randomly chooses a flaw from the current plan flaws . It then scores all possible plans in which this flaw is repaired by replacing one plan step between the cloberer and the consumer. The new action must establish the precondition of the consumer destroyed by the cloberer. If none of these plans has a lower penalty score than the current plan, it examines plans in which the consumer is replaced by some other action.

Flaw-repair is motivated by a similar strategy employed by WALKS AT where a "flawed" (i.e., unsatisfied) clause is cho­ sen and repaired by changing the value of one of its variables.

Example 2: Consider actions that repair the flaw of the plan in Example 1, i.e., actions that have ON(B,D) as an ef­ fect. Such actions are of the form MOVE(B,?x,D) and the best scoring plan is obtained when we use MOVE(B,TABLE,D). The resulting plan will be: MOVE(B,TABLE,C), MOVE(B,D,C), and MOVE(A,TABLE,B). This plan has a single flaw: the CLEAR(A) precondition of the last action. The closest pre­ decessor of the last action affecting CLEAR(A) is the initial action, and so this plan's penalty is 3, which is higher than the penalty of the original plan. Consequently, we consider actions that replace the consumer, namely the second step, among them MOVE(B,TABLE,C), which gives us a solution.

(3) Reorder-]: We generate a directed graph whosever­ tices are the current plan steps. An edge exists from plan step a to step a' if a (the producer) has an effect that is a precon­ dition of a' (the consumer). First, we use this graph to throw out steps that are not useful (by replacing them with null ac­ tions). A step is useful if it has an effect that is part of the goal conjunct or an effect that is a precondition of a useful step. Adjacent plan steps, between which we have edges in both directions, are deleted as well. Now, we add additional edges to the graph that reflect a heuristic notion of threats: If a, a' are nodes in the graph between which there is no edge, and if a clobers some precondition of a' we say that a threat­ ens a' and we add an edge from a' to a.

Finally, we attempt to generate an ordering consistent with the graph, i.e., such that step a will precede step a' if there is a path from a to a'. Usually, this is not possible, and we heuristically order the edges as follows: One of the nodes with the minimal number of incoming edges is chosen as the first step. It is removed from the graph, and the next step is chosen from this revised graph in the same fashion .

Example 3: We have two stacks of blocks: A on B on c and D on E on F; our goal state is F on B on E and A on c on D; plan length is 7. Suppose that our cur­ rent plan is: (1) MOVE(A,B,TABLE), (2) MOVE(A,TABLE,C), (3) MOVE(E,F,TABLE), (4) MOVE(B,C,E), (5) MOVE(F,TAB­ LE,B), (6) MOVE(D,E,C), (7) MOVE(C,TABLE,D).

3 We break ties randomly.

The producer/consumer pairs appears in Figure 1 (left) and are denoted by solid edges. According to this graph, all nodes are useful. Next, we add edges reflecting threats, denoted by broken edges. Now, we start reordering the nodes. The only node without incoming arcs is (1), and it is assigned to the first plan step. Deleting it, we see four nodes with a single incoming edge (2),(3),(6),(7), among which we can choose arbitrarily. Suppose we chose (6). Removing it from the graph, we see that (3) has no incoming edges, and we choose it. Next comes ( 4) and then either (5) or (7). If we choose (7), we can next choose between (5) and (2). Hence, one possible resulting plan is: (1) MOVE(A,B,TABLE), (6) MOVE(D,E,C), (3) MOVE(E,F,TABLE), (4) MOVE(B,C,E), (7) MOVE(C,TAB­ LE,D), (5) MOVE(F,TABLE,B), (2) MOVE(A,TABLE,C).

Example 4: Here is a similar plan in which the correct plan steps are ordered incorrectly. (1) MOVE(A,B,TABLE), (2) MOVE(A,TABLE,C), (3) MOVE(E,F,TABLE), (4) MOVE(B, C, E), (5) MOVE(F, Table, B), (6) MOVE(D, E, TABLE), (7) MOVE(C, TABLE, D). The initial graph contains the solid edges in Figure 1 (right). All nodes are useful. When we add threat arcs we obtain the additional broken edges. Nodes (1) and (6) have no incoming edges. Either choice is correct. We choose (1). (6) is still the only node without incoming edges, and we choose it next. Node (3) comes next, followed by (4). Now we can choose between (5) and (7). Both choices are correct. If we choose (7) we can then choose (2) as well. Whichever choice we made, we would get a correct plan.

(4) Reorder-2: Reorder-2 attempts to partition the set of ac­ tions into disjoint ranks such that, roughly, each rank is pre­ ceded by a rank containing actions that supply its precondi­ tions. The actions within a rank are not needed by each other. After removing unneeded actions, we attempt to reorder ac­ tions within a rank based on whether they destroy each oth­ ers' effects. A more detailed description is deferred to the full version of this paper

(5) Reorder: Applies Reorder-! with probability 0.5 and otherwise applies Reorder-2.

Initialization We initialize the plan by performing sto/­ chastic bi-directional search. That is, if n is the plan size, we run a standard regression algorithm in which branches are chosen stochastically for n/2 steps. This determines the latter half of the plan. Then, we run stochastic forward search for n/2 steps, which generates the first half of the plan.

Reachability Analysis Before we start the planning pro­ cess, we perform a fast heuristic reachability analysis in order to prune the number of actions considered at each time step. First, we determine which actions are applicable at the initial state. Let E1 be the set of effects of all these actions. Clearly, actions that have a precondition outside E1 can be pruned as candidates for the second plan step. We continue, letting Ek be the effects of all actions that were not pruned as candidates for the k + 1 time step, etc.

The LPSP algorithm The algorithm is described below; upper-case names are constants.

Procedure LPSP(MAX_TRIES,MAX_STEPS): Perform reachability analysis; Repeat for MAX_ TRIES or until solution found: Initialize CurrenLPian; Repeat for MAX_STEPS or until solution found: If (Current Step MOD 5 = 0) Obtain New_Pian by applying Best-Replacement; Else Obtain New_Pian by applying Flaw-Repair; End If; If solution not found If (New_Pian's penalty score < (CurrenLPian's penalty score+ DOWN_ THRESH)) CurrenLPian := New_Pian; Else If AlmosLSolution holds Threshold :=GREEDY _IF _.ALMOST; Else Threshold :=GREEDY _IF _NOT _.ALMOST; End If; With probability Threshold: CurrenLPian := New_Pian; With probability (1-Threshold): If (AimosLSolutionor (New_Pian = CurrenLPian)) Apply Reorder; Else New_Pian := CurrenLPian; End If; End If; End If; End Repeat; End Repeat;

Notes: AlmosLSolution holds if New _plans's penalty score is lower than OPT _THRESHOLD, and we did not call Re­ order in the previous step. We keep a tabu list of pairs (whose length is set to 2 in our experiments) containing the last two actions added and their respective positions. We disallow new plans in which an action is inserted in a position for which the corresponding action-position pair appear in the tabu list.

State of the planner LPSP is implemented in C++. It does not have a domain parser, yet. Hence, for each planning prob­ lem we write a procedure that specifies the propositions that hold in the initial and goal state; and for each action schema we define a class whose parameters are the schema's parame­ ters and a list of the appropriate preconditions and effects. In addition, we supply a procedure that, given an action identi­ fier (which is simply some integer), returns an action object. These operations have negligible running times and we be­ lieve that the time required to parse a domain description into a more generic action representation will be inconsequential (and, most likely, smaller than the time required to encode the same problem into SAT).

4 Experimental Results

We empirically compared LPSP to the PAS approach on prob­ lem instances from three well-known planning domains: the blocks world and logistics domains [Kautz and Selman, 1996; Ernst et al., 1997] and the artificial D 1 S 1 domain [Barrett and Weld, 1994]. 4 For the PAS approach, the performance depends on three components: (i) the SAT-encoding of the planning instances, (ii) polynomial simplification algorithms which are applied to the SAT formula before general SAT solvers are invoked, and (iii) the SAT algorithm used to solve the simplified encoded problem instance. All three com­ ponents have a significant influence on the overall perfor­ mance; in particular, the solver performance heavily depends on the encoding and simplification algorithms used to cre­ ate the SAT instance. Considering that additionally the SAT algorithms have several parameters which have to be tuned to achieve optimal performance, the number of choices over which one would have to optimize in order to get the best possible performance for the PAS approach is too high to practically allow an exhaustive analysis. Therefore, for this comparative study, we chose the following approach:

• We used two linear SAT encodings which are known to be good from the literature; for the blocks world do­ main, this is the linear encoding with operator splitting described in [Kautz and Selman, 1996], for the logis­ tics and D1S1 we used the "erse" (explanatory frame axioms, regular operator splitting, sequential plans, full type elimination) encoding as described in [Ernst et al., 1997].
• We considered several simplification strategies, as pro­ vided by Jimmy Crawford's COMPACT simplifier; be­ sides "no simplification" [-] these were unit propagation and pure literal elimination [p] plus the unary [u] and binary [b] failed literal strategies which are based on ef­ ficiently computing unary and binary implicates. For the blocks world domain, we also considered the simplifier based on unit propagation and subsumption [ps] which is part of the SATPLAN system.
• We focussed on stochastic local search algorithms for SAT; in particular, we considered the four best-per­ forming WALKSAT variants described in [McAllester et al., 1997] which are among the fastest existing SAT solvers. To get an impression, how LPSP's performance compares to that of systematic SAT algorithms, we also used SATZ [Li and Anbulagan, 1997], one of the best deterministic SAT solvers.

For the stochastic solvers, we took great care to opti­ mize the parameters (especially the noise parameter which is known to significantly affect performance) so that the over­ all time required for finding a solution was minimized. This was done for each SAT instance independently, ensuring that for our comparison we got an approximately optimal per­ formance. Because for a given problem instance, the dif­ ferent types of local search steps in LPSP require a variable amount of time, and for the PAS approach, the simplifica­ tion and solving time have to be taken into account, we com­ pared CPU times as measured on a PC with a 400MHz Pen­ tium II pr()cessor and 256 MB RAM running under Linux (Red Hat 5.2). For both LPSP and the stochastic SAT solvers, our comparison is based on 100 tries, using MAX_STEPS settings high enough to guarantee that a solution was found in all tries. For LPSP, we left the value of many parame­ ters fixed throughout the experiments (e.g, tabu list length was 2 and DOWN_THRESH was 5) and varied the values of GREEDY _IF _.ALMOST, GREEDY _IF _NOT -ALMOST, and OP'LTHRESH.

4 The first two were chosen because of their use in the original SATPLAN paper, and the third because [Kautz and Selman, 1996] mentions that it seems difficult for SATPLAN.

The problem instances have the following characteristics:

• Blocks World: We used the instances described in [Kautz and Selman, 1996]; these are: bw_large. a (9 blocks, 6 steps minimal linear plan length), bw_large. b (11 blocks, 9 steps), bw_large. c (15 blocks, 14 step plan), and bw_large. d (19 blocks, 18 step plan).
• Logistics: We used three instances in which there were 8 packages and 3 cities but only a small num­ ber of packages change their location. The instances are log. new. a (6 steps minimal linear plan length), log. new. b (10 steps), and log. new. c (16 steps).
• D 1 S 1: We used domain sizes n = 15 and 30 and four in­ stances per domain size: dlsl-n. a (15/30 steps mini­ mal linear plan length), dlsl. b (12/23 steps), dlsl. c (8/16), and dlsl. d (14/28 steps).

In Table 1, we report our experimental results. For LPSP, we report the mean and median CPU times over 100 suc­ cessful tries (see above) as well as the variation coefficient (standard deviation I mean), which gives a scaling indepen­ dent impression of the variability of the observed run-times. For PAS/WALKSAT, we report the CPU times for simplify­ ing the formula and the mean CPU time required by WALK­ SAT for solving the resulting simplified problem instance av­ eraged over 100 successful tries. Furthermore, we report the variation coefficient for the time used by WALKSAT. 5 Note that here, we report only the best results we found for any simplification and WALKSAT combination, using approxi­ mately optimal noise parameter settings for WALKSAT. 6 For PASISATZ, as only deterministic algorithms are used, we re­ port the CPU times for simplification and SATZ.

As can be seen from Table 1, LPSP shows superior perfor­ mance compared to PAS/WALKS AT as well as PAS/SATZ on almost all problem instances. For the blocks world instances, LPSP is between 3 and 13 times faster than PASIWALKSAT. Interestingly, for PASIWALKSAT, the time required for sim­ plifying the formula dominates the overall performance. Since different from WALKSAT, the implementations of the simplification algorithms are not optimized for speed, one might expect a significant reduction in overall performance when using optimized simplifiers. However, for the larger in­ stances, LPSP shows superior performance even when (unre­ alistically) assuming that simplification would come for free. Furthermore, LPSP requires much less tweaking then WALK­ SAT,'for which various simplification strategies must be con­ sidered, various heuristics, and various parameter tuning per heuristic. In addition, our LPSP implementation is certainly not fully optimized.

5 0ur actual experimental methodology is based on measuring run-time distributions (RTDs) as outlined in [Hoos and Stiitzle, 1998]; because of the limited space the RTDs could not be reported here, but this data is available from the authors.

6 The best-performing WALKSAT variants were TABU for the Blocks World instances and Novelty for all others. The approx­ imately optimal noise settings varied between the instances and seemed to be strongly dependent on the simplification strategies ap­ plied before.

The more complex SAT-simplifications seem to be far more effective for the logistics domain than for the blocks world or D 1 S 1 problems. Here, the formulae obtained by simplifying with the "unary/binary failed clauses" options are almost trivial for WALKSAT. However, although they have polynomial worst-case complexity, these simplifica­ tions are quite expensive in practice. So here, again, for PAS/WALKSAT the overall performance is dominated by the time required for simplification. Comparing the overall performance, LPSP is between 15 and 80 times faster than PAS/WALKSAT. Even assuming that the implementation of the simplifier could be considerably more optimized than LPSP, it is hard to imagine that PAS/WALKSAT could reach LPSP's performance on this domain. It should be noted, how­ ever, that for the logistics domain, most problem instances have significantly shorter parallel plans which are much eas­ ier to find than sequential plans. But since LPSP is a lin­ ear planner, it would be unfair to compare its performance to PAS approaches which allow for parallel plans. Finally, even for D 1 S 1, a domain which has been noted to be diffi­ cult for SATPLAN using SLS for solving the SAT instances [Kautz and Selman, 1996], LPSP shows better performance than PAS/WALKSAT. The only exception is instance d1s13 0 . a, which is solved by simplification (unit propagation) alone. The reason for this is that the d1 s 1-n. a instances have a chaining structure of the goals and operators which is very regular, but, in our opinion, highly untypical for realistic planning problems. We also believe that LPSP's performance on this domain can be significantly improved by optimizing its parameter settings.

Regarding the results on PAS/SATZ, LPSP's performance is still considerably better on all instances except for instance d1 s 1-3 0 . a, which in principle is solved by simplification (unit propagation) alone. Nevertheless, for this particular in­ stance, SATZ is actually faster then the simplification algo­ rithm we use, probably because it is more efficiently imple­ mented. Interestingly, when compared to PAS/WALKSAT, PAS/SATZ shows a better performance for 7 of our 11 bench­ mark instances. For the biggest blocks world and logistics in­ stances, as well as for one of the d1s1-3 0 instances, SATZ did not find a solution in 60 seconds- which could possibly indicate that SATZ does not scale as well as SLS approaches (LPSP and PAS/WALKS AT). However, this issue needs to be further investigated, especially using newer, randomized sys­ tematic search algorithms [Gomes et al., 1998].

5 Discussion

The thesis that SLS-based algorithms operating on un­ encoded problems can fare better than those operating on en­ coded problems cannot be proved experimentally. The per­ formance of LPSP does, however, lend it greater credibility, especially when we compare the effort invested in it with that invested in work on SAT-based SLS algorithms in general and the PAS approach specifically.

In a longer version of this paper, we describe experiments which we conducted on two additional problem domains: Hamiltonian circuit and binary CSPs. The first domain has interesting, inherent structure, and we have been able to ob­ tain better results using an SLS-based algorithm applied to the graph description directly. The second problem domain is more general and closely resembles SAT problems. There, we found that SAT-based methods perform better than the SLS-based algorithms we experimented with. 7

Of course, one could argue that in the area of planning in general, SLS-based methods applied to encoded problems that do not enforce the linearity assumption have the upper hand. However, recent research is starting to show that the situation is a bit more complicated. [Serina and Gerevini, 1998] employ SLS methods to search Graphplan's planning graph. Their algorithm outperforms PAS based methods on some problems, and in particular, those in which concurrent plans are much shorter. Our algorithm seems to outperform PAS based approaches when concurrency is not an important factor (e.g., the blocks' world instances). The best SAT-based planner, BLACKBOX [Kautz and Selman, 1998], relies more on traditional plan representations than the original SATPLAN planner [Kautz and Selman, 1996]. BLACKBOX goes very far with the original planning problem before converting it into a propositional formula: It first generates a planning graph and encodes this graph together with the mutual exclu­ sion constraints it generated. More importantly, recent work [Giunchiglia et al., 1998] shows that better performance can be obtained if the variables describing state properties are treated as dependent variables (i.e., one chooses an assign­ ment for the action variables and this determines the value of the state variables). What this result mean is that it is better to search over the space of assignments to actions than over the whole space of truth assignments. The space of action assignments is very similar to LPSP's search space.

7 See also [Hoos, 1999].

Naturally, we have not heard the last word in SAT algo­ rithms, and recent work on exploiting variable dependences [Kautz et al., 1997] may allow us to utilize knowledge about problem structure in solving the encoded problems. Another promising direction in which little work has been carried out is the analysis of the encoded problems for useful features of search space structures (see also [Hoos, 1999]) or syntac­ tic properties. Such features may stem from deep properties of the encoded problem. To date, most SAT solvers do not attempt to utilize such information (although it could be ar­ gued that formula simplification routines do something of this sort). But perhaps there are algorithms that can operate much better than the standard methods on sentences with special properties. This is particularly interesting if such properties are shared by all problems from a particular domain. If this turns out to be the case, then, indeed, the encode & solve ap­ proach may be our best bet. 8

To use Chapman's terminology, LPSP is a somewhat "scruffy" planner. It would be nice to see a simpler, more principled and general planner based on SLS techniques. However, it is already much easier to optimize than the PAS based algorithms that have three distinct phases (translate, simplify, solve) each of which needs to be fine-tuned sepa­ rately. Moreover, it may be the case that good SLS algorithms must be a bit involved if they are to exploit domain structure.

LPSP's reordering operators are interesting in their own right and could possibly be integrated into plan reuse and plan repair algorithms. Plan reordering has been considered in the past (see [Backstrom, 1998] and references therein) but typ­ ically with the goal of optimizing the order of correct plans. The idea of repairing plans in general is not new either, and goes back at least to [Sussman, 1975]. The heuristic, rather than more systematic, approach LPSP takes stems from the need to balance the desire for a better, and more sophisticated order analysis (which is likely to be intractable), and the need to maintain a low cost for each step. Finally, we note that dif­ ferent types of domain specific knowledge can be used to fo­ cus the search process, e.g., by using general variables rather than binary variable to specify state information, by restrict­ ing the type of operators that should be considered in various situations, etc.

8 See [Brafman, 1999] for a recent attempt along this direction.

Acknowledgments

Craig Boutilier was instrumental in the development of earlier versions of LPSP. The first author is partially supported by the Paul Ivanier Center for Robotics Research and Production Management.