Plan Modification versus Plan Generation: A Complexity-Theoretic Perspective

1 Introduction

Plan generation in complex domains is normally a re­ source and time consuming process. One way to improve the efficiency of planning systems is to avoid the repeti­ tion of planning effort whenever possible. For instance, in situations when the goal specification is changed dur­ ing plan execution or when execution time failures hap­ pen, it seems more reasonable to modify the existing plan than to plan from scratch again. In the extreme, one might go as far as basing the entire planning process on plan modification, a method that could be called plan­ ning from second principles.

Instead of generating a plan from scratch, that method tries to exploit knowledge stored in previously gener­ ated plans. The current problem instance is used to find a plan in a plan library that-perhaps after some modifications-can be used to solve the problem instance at hand. Current approaches try to integrate meth­ ods from analogical or case-based reasoning to achieve a higher efficiency [Hammond, 1990; Veloso, 1992], int~ grate domain-dependent heuristics or investigate reuse m the general context of deductive planning [Koehler, 1992; Bauer et al., 1993].

·This work was supported by the German Ministry for Re­ search and Technology (BMFT) under contracts ITW 8!Hll 8 and ITW 9000 8 as part of the WIP project and the PHI project.

Some experiments give evidence that planning based on second principles might indeed be more efficient than planning from scratch [Kambhampati and Hendler, 1992; Veloso, 1992; Hanks and Weld, 1992]. However, it is by no means clear to what extent these results general­ ize. In fact, it is not obvious that modifying an existing plan is computationally as easy as generating one from scratch, in particular, if we adopt the principle of con­ servatism [Kambhampati and Hendler, 1992], that is to try to recycle "as much of the old solution as possible" [Veloso, 1992, p. 133] or to "produce a plan ... by mini­ mally modifying [the original plan]" [Kambhampati and Hendler, 1992, p. 196].

Considering, for instance, the revision of logical the­ ories most revision schemata turn out to be computa­ tion~lly harder than deduction [Nebel, 1991; Eiter and Gottlob, 1992].A similar result holds for abduction [Eiter and Gottlob, 1993], which may be viewed as "modifying the assumptions in a proof." Hence, it seems worthwhile to have a closer look at the computational nature of the process of modifying a plan in order to find out why and under which circumstances plan modification and reuse promises to be more efficient than planning from scratch.

The computational complexity of different forms of planning has been recently analyzed by a number of authors [Chapman, 1987; Backstrom and Klein, 1991; Bylander, 1991; Chenoweth, 1991; Gupta and Nau, 1991; Bylander, 1992; Erol et al., 1992] . However, the compu­ tational complexity of plan modification · has not been investigated yet . We will analyze this problem in the formal framework of propositional STRIPS planning as defined by Bylander [1991; 1992]. As Bylander [1991] notes, this model of planning is "impoverished com­ pared to working planners" and is only intended to be a "tool for theoretical analysis." However, since we are mainly interested in comparing plan generation with plan modification from a complexity-theoretic perspective, this framework is appropriate for our purposes.

As it turns out, modifying a plan is not easier than planning from scratch. On the positive side, we show that modification does not add any complexity to plan­ ning if we consider the general case. However, there exist special cases when modifying a plan conservatively, i.e., by using as much of the old plan as possible, can be harder than creating one from scratch , as we will show. This means that plan modification is not uniformly as easy as plan generation. Further, we show that these results also hold if we assume that the old and the new planning situation are similar.

Putting these results into perspective and relating them to practical approaches reveals that these ap­ proaches do not address the plan modification problem at all, although some authors claim otherwise.

2 Propositional STRIPS Planning

Like Bylander (1991], we define an instance of proposi­ tional planning as a tuple II= (P,O,I,9), where:

• P is a finite set of ground atomic formulae, the con­ ditions,
• 0 is a finite set of operators, where each operator o E 0 has the form o+, o- => o+, o_, where
• o+ ~ P are the positive precondition~;,
• o- ~ P are the negative pr·econditions,
• o+ ~ P are the positive post conditions (add list), and
• o_ ~ P are the negative postconditions (delete list).
• I ~ P is the initial state, and
• 9 = (9+, 9-) is the goal specification with 9+ ~ P the positive goals and 9- ~ P the negative goals.

P is the set of relevant conditions . A state is a subset S ~ P with the intended meaning that p E P is true in state S if p E S, false otherwise. 0 is the set of operators that can change states. I is the initial state, and 9 is the goal state specification, with the intended meaning that all conditions p E 9+ must be true and all conditions p E 9- must be false. A plan A is a finite sequence (o1 , ... , on) of plan steps o; E 0 . An operator may occur more than once in a plan. A plan A solves an instance II of the planning . problem iff the result of the application of A to I leads to a state S that satisfies the goal specification 9, where the result of applying A = (o1 , . .. , on) to a state S is defined by the following function:

In other words, if the precondition of an operator is sat­ isfied by a state, the positive postconditions are added and the negative postconditions are deleted . Otherwise, the state becomes undefined, denoted by l. (j. P . 1

1 This is a slight deviation from Bylander's [1991] defini­ tion that does not affect the complexity of planning. This deviation is necessary, however, to allow for a meaningful definition of the plan modification problem.

As usual, we consider decision problems in order to analyze the computational complexity of planning. 2 PLANSAT is defined to be the decision problem of deter­ mining whether an instance II = (P, 0, I, 9) of propo­ sitional STRIPS planning has a solution, i.e., whether there exists a plan A such that Result(I, A) satisfies the goal specification. PLANMIN (Bylander, 1993) is defined to be the problem of determining whether there exists a solution of length nor less, i.e., it is the decision problem corresponding to the search problem of generating plans with minimal length.

Based on this framework, Bylander [1991; 1992; 1993] analyzed the computational complexity of the general propositional planning problem and a number of gen­ eralizations and restricted problems. In its most gen­ eral form, both PLANSAT and PLANMIN are PSPACE­ complete. Severe restrictions on the form of the opera­ tors are necessary to guarantee polynomial time or even NP-completeness.

3 Plan Modification in a Propositional Framework

Kambhampati and Hendler [1992) define the plan modi­ fication problem as follows (adapted to our framework of propositional STRIPS planning):

Given an instance of the planning problem II' = (P, 0, I', 9') and a plan A that solves the instance II = (P, 0, I, 9), produce a plan A' that solves II' by minimally modifying A.

We will call this problem MODGEN.

By "minimal modification of a plan" Kambhampati and Hendler [1992] mean to "salvage as much of the old plan as possible'' Of course, the part of the old plan that has been salvaged should be executable, i.e., the preconditions of all operators should be satisfied. In or­ der to guarantee this, we require that all operators are executable (see the definition of the function Result).

Turning the above specified search problem into a de­ cision problem leads to what we will call the MODSAT problem:

An instance of the MODSAT problem is given by II' = (P, 0, I', 9'), a plan A that solves II= (P,O,I,Q), and an integer k ~ IAI. The question is whether there exists a plan A' that solves II' and contains a subplan of A of at least length k?

In order to fully specify MODSAT, we have to define the meaning of the phrase "A' contains a subplan of A of length k." For this purpose, we define the notion of a plan skeleton, a sequence of operators and "wildcards," denoted by "*·" The length of a plan skeleton is the num­ ber of operators, i.e., we ignore the wildcards. A plan skeleton can be derived from a plan according to a mod­ ification strategy M by deleting and rearranging plan steps and adding wildcards. A plan skeleton can be ex­ tended to a plan by replacing each wildcard by a possibly empty sequence of operators . Now we say that plan !::i' contains a subplan of !::i of length k accor·ding to a mod­ ification strategy M iff a skeleton r of length k can be derived from !::i according toM and r can be extended to !::i' . In general, we will consider only polynomial-time modification strategies , i.e., strategies such that verify­ ing that the skeleton r can be derived from the plan !::i is a polynomial-time problem. In the following , we will consider two different plan modification strategies that satisfy this constraint .

2 We assume that the reader is familiar with the basic notions of complexity theory as presented, for instance, in [Garey and Johnson, 1979) .

The first alternative we consider is to allow for dele­ tions in the original plan and additions before and after the original plan . Supposing the plan

the following plan skeleton could be derived from /::i, for instance:

where r has length i + n - j + 1. The corresponding modification problem will be called MODDEL.

Another alternative is to allow for deletion of plan steps in the old plan and additions before, after , and in the middle of the old plan . Assuming the same plan !::i as above, the following skeleton plan of length i + n- j + 1 could be derived:

The corresponding modification problem is called MOD­ DELINS.

Finally, it should be noted that although the frame­ work we have defined above deals only with linear plans, it can be easily modified to apply to nonlinear planning, as well . In particular , all hardness results will apply di­ rectly to nonlinear planning since linear plans are simply a special case of nonlinear ones.

4 The Complexity of Plan Modification

One almost immediate consequence of the definitions above is that plan modification cannot be easier than plan generat ion. This even holds for all restrictions of the PLANSAT problem. If PLANSATp is a restricted planning problem, then MODSATp shall denote the cor­ responding modification problem with the same restric­ tions.

Proposition 1 PLANSAT P tr·ansforms polynomially to MODSATp for all restrict ions p. 3

However , plan modification is also not harder than plan generation in the general case.

Proposition 2 MODSAT is PSPACE-comp/dt:.

This proposition could be taken as evidence that plan modification is not harder than plan generation . How­ ever, it should be noted that the proposition is only about the general problem. So, it may be the case that there exist special cases such that plan modification is harder than generation. Such a case will not be found among the PSPACE- and NP-complete planning prob­ lems, however.

3 Full proofs of propositions and theorems can he found in the full paper [Nebel and Koehler , 1992] .

Theorem 3 If PLANSATp is a restricted planning problem that is PSPACE-complete or NP-complete , then MODSATp is PSPACE-comp/ete or NP-complete prob­ lem, respectively.

Proof. PSPACE-hardness and NP-hardness, respec­ tively, are obvious because of Proposition 1. Member­ ship follows in case of PSPACE by Proposition 2. In case of NP, we initially guess (1) n (0 ~ n ~ l!:il + 2) possi­ bly empty plans l:::i; such that l!:i;l ~ l!:il, (2) 2n states S1 , . . . , S2n, and (3) n polynomially bounded proofs that there exists plans from each state s2i to state s2i+l for 1 ~ i ~ n- 1. Since PLANSATp is in NP, such proofs exist (in most cases, these proofs will be plans) . Then we verify in polynomial time (1) that S1 =I and S2n satis­ fies the goal specification 9, (2) that Result(S2;_1 , l:::i;) = S2;, (3) that the plan existence proofs are correct, and (4) that (!:il,*,/::i2,*,-·- ·l:::in-l,*,l:::in) is a skeleton of length k that can be derived from !::i . This is obviously a nondeterministic algorithm that runs in polynomial time. ·

The converse of the above theorem does not hold, however. There exist cases when plan generation is a polynomial time problem while plan modification is NP­ complete.

Theorem 4 There exists a polynomial-time PLANSATp problem such that the corresponding MODDELp and MODDELINSp problems are NP-complete.

Proof. The planning problem PLANSATi defined by restricting operators to have only positive preconditions and only one postcondition can be solved in polynomial time [Bylander , 1991 , Theorem 7] . Let PLANSATi'P 0 ' 1 be the planning problem defined by restricting oper­ ators to have (1) only one postcondition p, (2) the negated condition p as a precondition, and (3) any number of additional positive preconditions. From the specification of the algorithm Bylander [1991] gives for PLANSATt , it is evident that PLANSATt·po·t can also be solved in polynomial time. We will show that the corresponding modification problems MODDELi'po·t and MODDELINSi ·post are NP-complete.

For the hardness part we use a reduction from SAT, the problem of satisfying a boolean formula in conjunctive normal form. Let V = { v1 , ... , Vm} be the set of boolean variables and let C = { c1, ... , en} be the set of clauses. Now we construct a MODDELi·po·t problem that can be satisfied iff there exists a satisfying truth assignment for the SAT problem.

The set of conditions P contains the following ground atoms:

T; , 1 ~ i ~ m, v; = true has been selected

F;, 1 ~ i ~ m, v; = false has been selected

S;, 1 ~ i ~ m, the truth value for v; has been selected

E;, 0 ~ i ~ m, enable evaluation

Cj , 1~n~n, c; evaluates to true.

Further, we assume the following set of operators 0 :

Assume the following initial and goal state:

The instance IT = (P, 0 , I , 9) is, for example, solved by the following plan ~:

Now consider the instance II'= (P ,O,I',9') such that

It is obvious that the SAT formula is satisfiable if, and only if, the plan ~ can be modified by deleting at most m operators and adding some operators before and after the original plan ~ in order to achieve a new plan ~' that solves II'.

Membership in NP follows since PLANSAT{·post is in NP. Using the same algorithm as described in the proof of Theorem 3 leads to a nondeterministic polynomial-time algorithm for MODDEL{ 'post and MODDELINS{ ·rost . ·

5 Modifying Plans When the Situations are Similar

The results above could be considered as being not rel­ evant for plan modification in real applications because we made no assumption about the similarity between old and new planning situation . The efficiency gains ex­ pected from plan reuse, on the other hand , are based on the assumption that the new situation is sufficiently close to the old one-which supposedly permits an easy adaptation of the old plan to the new situation. Besides the fact that this looks like a good heuristic guidance, there is the question whether small differences between the old and the new situation lead to a provable effi­ ciency gain in terms of computational complexity. So it might be perhaps the case that modification is easier than planning if the goal specifications differ only on a constant or logarithmic number of atoms . Although this seems to be possible, there is the conflicting intuition that small changes in the planning situations could lead to drastic (and hard to compute) changes in the plans.

As it turns out, restricting the number of differing atoms does not lead to a different picture than the one presented in the previous section. First of all, Theo­ rem 4 still holds for the restricted versions of the mod­ ification problems MODDEL and MODDELINS, where we require the old and new initial states to be identical and the old and new goal specification to differ only on one atom. We call these restricted versions of the mod­ ification problems MODDELlG and MODDELINSlG, respectively.

Theorem 5 There exists a polynomial-time PLANSAT P problem such that the corresponding MODDELlGp and MODDELINSlGp problems are NP-complete.

Proof. The transformation used in the proof of Theo­ rem 4 is modified as follows. A new atom B is added, which is assumed to be false in the initial state I and not mentioned in the old goal specification 9. The new goal specification 9' is:

Although this theorem confirms the intuition that small changes in the goal specification can lead to drastic changes in the plan, it does not rule out the possibility that there are some hard planning problems such that the corresponding modification problems are easy if the goal specification is only changed marginally. In order to rule out this possibility, we would need something similar to Proposition 1. Since there appears to be no general way to reduce PLANSATp problems to MODSATlGp problems, we will settle for something slightly less gen­ eral. We will show that generating a plan by modifying a plan for a similar goal specification is at least as hard as the corresponding PLANSAT problem. Hence, in­ stead of the decision problem MODSATlG, we consider the search problem MODGENlG. Further , in order to allow for a "fair" comparison between PLANSAT and MODGENlG, we measure the resource restrictions of MODGENlG in terms of the size of the planning prob­ lem instance-and ignore the size of the old problem. 4 Under these assumptions, it is possible to specify a 'lUr­ ing reduction from PLANSATp to MODGENlGp.

Theorem 6 If PLAN SAT p is a restricted planning problem that is PSPACE-hard or NP-hard, then the cor­ responding MODGENlGp problem is PSPACE-hard or NP-/wrd, respectively.

Proof. Using an algorithm for MODGENlGp, we can generate a plan by modifying it iteratively, starting with the empty plan and empty goal specification and contin­ uing by adding step by step one goal atom. Since the size of the goal specification is linearly bounded by the prob­ lem instance, we would need only linearly many calls. Supposing that the theorem does not hold would imply that generating a plan under restrictions p is easier than PLANSATp, which is impossible by definition. ·

4 This is necessary to rule out such pathological situations as the one where modifying an exponentially long plan ap­ pears to be polynomial while generating it is exponential.

It should be noted that we did not rely on any particu­ lar property of the MODGEN1Gp algorithm. In particu­ lar, we did not make the assumption that the algorithm has to recycle a maximal reusable plan skeleton. Fur­ thermore, the above theorems apply, of course, also to the modification problems that are restricted to have an one-atom-difference between the initial states.

6 Discussion

Of course, there arises the question of how the above results relate to practical plan modification systems. Kambhampati and Hendler [1992] investigate plan reuse and modification in the framework of the hierarchical planner and modification system PRIAR, which is based on NONLIN [Tate, 1977]. They use a large number of blocks-world examples in order to evaluate the relative efficiency gains provided by plan modification compared with planning from scratch. The average savings of run­ time when plans were reused is given by the authors as 79%.

Hanks and Weld [1992] performed experiments on reusing blocks world plans with their system SPA. This plan generation and modification system is based on a lifted version of McAllester's and Rosenblitt's [1991] sys­ tematic nonlinear planning algorithm. In case of the SPA system, the savings turned out to be less drastic than in the PRIAR system. In fact, in the SPA system plan modification can be more expensive than plan genera­ tion in terms of runtime if the reuse candidate is not close enough [Hanks and Weld, 1992, p. 103], a situa­ tion that did not happen with similar input data in the PRIAR system.

While the relative savings appear to be different for the two approaches , in both cases there is a positive ef­ fect which increases when the difference between the new and the old situations decreases. Although this seems to run counter to our complexity results (in particular Theorem 6), these empirical findings do not contradict our results because the experiments were clearly not de­ signed to explore worst-case situations, which complex­ ity analysis is about. An interesting avenue of research would be to characterize the form of planning problems that can exploit plan-reuse techniques to improve the efficiency of the planning process.

What seems to be less easily explainable is, however, the discrepancy between the hope that reusing maximal subplans increases the efficiency of plan reuse and our findings. Our results imply that conservative plan mod­ ification introduces some combinatorics into the plan­ ning and reuse process . In particular, as a Corollary. of Proposition 2 it follows that is not possible to determme efficiently (i.e. , in polynomial time) a maximal reusable plan skeleton befor·e plan generation starts to extend the skeleton.

Corollary 7 It is PSPACE-hard to compute a maximal plan skeleton for MODSAT instances.

In other words, plan generation and plan modification cannot be separated. For this reason, the planning pro­ cess becomes actually more involved when recycling as much of the old plan as possible. Instead of searching for an arbitrary solution, a plan that contains a maximal subplan of the old plan has to be sought.

Kambhampati and Hendler [1992] mention conser­ vatism, i.e., to "salvage as much of the old plan as pos­ sible," as an "important desideratum" for a .plan mod­ ification capability, in order to "ensure effictency." At a first glance, this seems to be indeed reasonable since it promises to minimize the additional planning effort. As we have seen however, finding the maximal reusable plan skeleton is' already as difficult as planning an~ is sometimes even more difficult than the correspondmg planning problem (Theorem 4). Hence, "conservatism" seems to run counter to increasing planning efficiency.

Having a closer look at the PRIAR framework re­ veals that plan skeletons are derived in polynomial time [Kambhampati and Hendler, 1992, p . 197] by a process called "annotation verification." Hence, by Corollary 7, this process cannot by any means derive maximal appli­ cable plan skeletons. Further, the authors do not give any arguments that they approximate such skeletons. In fact , the skeletons derived by PRIAR are not even guar­ anteed to be applicable. So, PRIAR does not seem to ad­ dress the problem of "minimally modifying plans," con­ trary to what the authors claim.

In fact, maximal reuse of an old plan only seems to make sense in a replanning context if costs are charged for not executing already planned steps. So, it seems to be the case that the two motivations for plan modification, namely, replanning and reuse may not be as similar as one might think. While in plan reuse the efficaency ?f the planning process is the most important factor, m replanning the minimal disturbance of the old plan may be more important, leading to a more involved planning process . 5 .

Plan modification in the PRIAR framework-and m other plan-reuse systems-seems not to be a computa­ tional problem that has to be addressed, but rather a solution, a heuristic technique. The "plan skeleton" that is reused is not the maximal applicable one, but the one that the particular planning algorithm perhaps can ex­ ploit in generating a solution. In other words, the old plan is used as an "entry point" into the search space of possible plans, as made explicit by Hanks and Weld [1992].

7 Conclusion

Improving the efficiency of planning systems by adding capabilities to modify existing plans has received some research interest recently. In analyzing the computa­ tional complexity of this problem, we showed that it is as hard as planning and sometimes modification i.s even harder than planning from scmtch. We showed also that. these results hold under the restriction that. the mod­ ification process has to account for only one changed atom in the goal specification. In particular, we showed that deriving the maximal reusable subplan is not easier than planning. Hence, we cannot hope for minimizing planning effort by first identifying the maximal applica­ ble subplan which is then (minimally) extended by plan generation.

5 Kambhampa.ti makes the same distinction in a later pa· per (Kambhampa.ti, 1992]. Based on arguments concerning the search process of a planner, he also argues that guaran­ teeing that every step that could be reused is reused could be computationally expensive-a conjecture confirmed by The­ orem 4.

Relating these results to existing plan reuse and mod­ ification systems, it turns out that these do not address the modification problem at all, although some authors claim otherwise. In fact, in plan-reuse systems, plan modification is not attacked as a problem but consid­ ered as a heuristic technique. This means that instead of "using as much of the old plan as possible" these sys­ tems recycle "as much of the old plan as the particular planning algorithm will perhaps be able to use in solving the new problem instance." In fact, adopting the prin­ ciple of conservatism in plan modification only seems to make sense in a replanning context where one wants to minimize the perturbation of the original plan .

Acknowledgements

We would like to thank Christer Backstrom, Tom Bylan­ der, Subbarao Kambhampati , and the anonymous refer­ ees, who provided helpful comments on an earlier ver­ sion of this paper. In particular, Tom's remarks and questions heavily inft uenced the paper.