Complexity Results for SAS+ Planning

1 Introduction

We have previously reported a. number of tractable planning problems using the SAS+ and SAS for­ malisms. We started by identifyin~ the SAS-PUBS prob­ lem [Backstrom and Klein, 1991bj and prove this prob­ lem to be tractable. Then we applied a bottom-up strategy, generalizing the results by removing restric­ tions, which resulted in the more expressive, but still tractable, SAS-PUS [Backstrom and Klein, 1991a] and SAS+ -PUS [Backstrom, 1992a, 1992b] problems. The overall goal of this research has been to identify suc­ cessively more and more expressive, tractable planning problems, with the hope of ultimately finding problems which are relevant to practical applications, especially in sequential control. 1

We found the tractable problems mentioned above by studying a test problem in sequential control and identifying a number of inherent restrictions (denoted

·This research was supported by the Swedish National Board for the Engineering Sciences (TFR) under grant Dnr. 92-143 and by the German Ministry for Research and Technology (BMFT) under grant ITW 8901 8.

1 Sequential control is a subdisciplin of automatic control and includes many planning-like problems.

Bernhard Nebel

German Research Center for Artificial Intelligence (DFKI)

Stuhlsatzenhausweg 3

D-6600 Saarbnicken 11, Germany

email: nebel@dfki. uni-sb.de

P, U, B and S) on that problem. We have proven [Backstrom, 1992a, 1992b] that the SAS+ formalism is expressively equivalent to 'standard' variants of proposi­ tional STRIPS and ground TWEAK. Yet, it was essen­ tial to use the SAS+ formalism since the P, U, B and S restrictions cannot be naturally expressed in any of the other formalisms [Backstrom, 1992a Backstrom and Nebel, 1992] and it is unlikely that we would have man­ aged to isolate them if using a standard formalism.

Having started from one tractable problem and gen­ eralized twice to new tractable problems it is interest­ ing to ask how much further we can generalize and stay tractable by simply removing restrictions. This paper answers that question by providing an exhaustive map over the complexities for finding both optimal and non­ optimal plans for all possible combinations of the P, U, B and S restrictions. It turns out that the SAS+ -PUS problem is the maximally expressive tractable problem if we insist on finding optimal ( ie. minimal length) plans. Whichever of the three restrictions on this problem we drop, the resulting problem is intractable. On the other hand, if we do not require the solutions to be minimal, then we can generalize somewhat further. We prove that if we remove the P restriction, resulting in the SAS+ -US problem, we can still plan in polynomial time, although we are no longer guaranteed to find optimal plans.

2 The SAS+ Formalism

This section briefly recasts the main differences between the SAS+ formalism and the STRIPS formalism and also gives a somewhat simplified account of the formal defi­ nition. Due to the page limit we have to refer the reader to previous publications [Backstrom and Klein, 1991a, 1991b, Backstrom, 1992a, 1992b] for background, moti­ vation and examples.

2.1 World Modelling

There are basically two important differences between the SAS+ formalism and the propositional STRIPS for­ malism. The first one is that the SAS+ formalism uses partial, multi-valued state variables instead of proposi­ tional atoms. The second difference is that the oper­ ators also have a prevail-condition in addition to the usual pre- and post-conditions. This makes it possi­ ble to distinguish easily between those parts of the (traditional STRIPS) pre-condition that is changed by the operator and the part that remains unchanged. 2 That is, the (SAS+) pre-condition of an operator specifies those state variables which must have a certain defined value in order to execute the operator and that will also be changed to some other value by the operator. The prevail-condition, on the other hand, specifies those state variables that must have a certain value but will remain unchanged after executing the operator.

Definition 2.1 A SAS+-structure ci> = (M,S, 1-i) is defined by:

• a set M = { i1, . . . , im} of state variable indices;
• a spaceS= Si 1 X ·.. X Sim of total states, where for each j EM,
• Sj is a domain of mutually exclusive values for the jth state variable and
• Sf = Si u { u} is the extended domain for the j th state variable, where u denotes the un­ defined value,

and the space S+ = Si~ X . .· X Stm of partial states is implicitly defined;

• a set 1i of operators {action types), each h E 1i being of the form h = (b, e, f) E S+ X s+ X s+ where b, e and f, denote the pre-, post- and prevail­ condition respectively of h , and where the set 1i is subject to the following restrictions:
• for all h E 1i and for all i EM, if b(h)[i] ::j; u, then b(h)[i] ::j; e(h)[i] ::j; u
• for all hE 1i and i EM, either e(h)[i] = u or f(h)[i] = u.

The first of the two restrictions on 1i expresses that all state variables having a defined value in the pre­ condition of some operator to have a defined but dif­ ferent value in the post-condition. That is, an operator cannot change a state variable from a defined value to the undefined value and it must either change a variable or not define it at all in the pre- and post-conditions; Vari­ ables that are defined but not changed should go into the prevail-condition. The second restriction expresses that the post-condition and the prevail-condition of an operator must not define the same state variables since an operator cannot both change a state variable and re­ quire it to be constant. Neither of these is a restriction in practice.

We write s[i] to denote the value of the ith state vari­ able in a state s. We also write s ~ t if the state s is subsumed (or satisfied) by state t, ie.,

2.2 Plans

To simplify matters we only define linear plans and do not distinguish between operators and their instantia­ tions (actions).

2 This distinction could be implicitly derived from the or­ dinary STRIPS pre- and post-conditions but we find it both formally and conceptually clearer to make it explicit . Fur­ thermore, the distinction is important if we a.lso consider parallel execution of operators [Backstrom and Klein, 1991b, 1991a, Backstrom, 1992a].

Definition 2.2 A plan over a SAst -structure ci> = (M,S,1i) is a sequence of operators {h1, .. . ,hn) s.t . hk E 1i for 1 ~ k ~ n.

Given two plans a _ {h1, ... , hm) and iJ {hL ... ,h~) we define (a ;{J) = {hl , ... ,hm,hi, ... ,h~) . The result of executing a plan is defined recursively as follows, using the update function (fl.

Definition 2.3 Given two states s, t E s+, we define for all i EM,

The function result gives the state resulting from execut­ ing a plan and is defined recursively as:

An operator h is admissible wrt . a state s iff b(h) ~ s and f(h) ~ s . A plan a= {h1, ... , hn) is admissible wrt. a state s iff h1 is admissible wrt. s and for 1 < k ~ n, hk is admissible wrt . result( s, (h1, ... , hk-l) ). In addition, the empty plan () is admissible wrt . any state.

Definition 2.4 An instance of the SAS+ planning problem is a tuple II = {cl> , s0 , s*) s.t . ci> is a SAst­ structure and so, s* E s+ denote the initial state and goal state respectively. A plan a over ci> solves II iff

1. a is admissible wrt. so and

More specifically we distinguish four different problems. The SAS+plan existence problem is: given an in­ stance II, decide whether there exists some plan a over ci> s.t. a solves II. The SAS+plan search problem is: given an instance II, find a plan a over ci> that solves II , or answer that there is no such plan. The corresponding bounded plan existence {search) problem takes an ex­ tra parameter K and asks only for plans of length K or shorter.

3 Restrictions

We have previously identified four restrictions on the SAS+ planning problem that together result in tractabil­ ity. An instance of the SAS+ problem is post-unique (P) iff no two distinct operators can change the same state variable to the same value and it is unary (U) iff each operator changes exactly one state variable. The instance is binary (B) iff all state variable domains are two-valued. Finally, the instance is single-valued (S) iff any two operators that both require the same state vari­ able to have some specific value during their respective occurrences must require the same defined value. For example, single-valuedness prevents us from having two operators such that one requires a certain room to be lit during its occurrence while the other requires the same room to be dark during its occurrence.

Definition 3.1 A SAst structure 4> = (M,S, 7i) is

• binary iff lSi I= 2 for all i EM,
• post-unique iff for all h, h' E 1i, if e(h)[i] e(h')[l1 =/; u for some i EM, then h = h';
• unary iff for all hE 1i, there is exactly one i E M s.t. e(h)[i] =/; u;
• single-valued iff there exists some state s s. t. f(h)!;::; s for all hE 1i. In particular, we define the global prevail-condition f?t for 1i as the minimal such s (wrt. the number of defined values).

All these restrictions were identified by studying a test example in automatic control, thus complementing the usual problems from the AI world. For a somewhat more elaborate discussion of the restrictions, see Backstrom and Klein [1991a] or Backstrom [1992a].

We name subproblems of the SAS+ problem satisfy­ ing combinations of the above restrictions by appending the letters denoting these restrictions. For example, the SAS+ -PUS problem is the SAS+ problem restricted to instances that are post-unique, unary and single-valued while the SAS+ -B problem is only restricted to binary state variables.

Since we have previously studied also the slightly more restricted SAS formalism and it could, thus, be interest­ ing to view also SAS problems as restricted versions of the corresponding SAS+ problems. It turns out, how­ ever, that all complexity results presented in this paper hold regardless of whether we consider SAS+ -structures or SAS-structures. The complexity figures depend only on the restrictions in Definition 3.1.

4 Existence of Optimal Plans

We already know [Backstrom, 1992a, 1992b] that we can find optimal (in the sense of minimal length) plans for the SAS+ -PUS problem in polynomial time.

Theorem 4.1 Bounded SAs+ -PUS plan existence and plan search is solvable in polynomial time.

Since this problem is a generalization of the previously studied, tractable SAS-PUBS [Backstrom and Klein, 1991b] and SAS-PUS [Backstrom and Klein, 1991a] plan­ ning problems, it is interesting to ask whether we can generalize even further, staying tractable. Unfortu­ nately, it turns out that we cannot remove any of the three restrictions {P, U and S) and still find optimal plans tractably, as we will see in this section. The complex­ ity results for bounded plan existence are summarized in Figure 1 for all possible combinations of the restrictions in Definition 3.1.

The following theorems together establish that the SAS+ -PUS problems is the maximal tractable problem wrt. the P, U and S restrictions. Due to space limi­ tations we will sometimes omit proofs or provide only proof sketches, but the full proofs of all theorems appear in Backstrom and Nebel [1993].

We first note that all problems which are both unary and single-valued have polynomially-sized mini­ mal plans.

Theorem 4.2 All solvable instances of the SAs+ -US problem have minimal solutions which are of polynomi· ally bounded length.

Proof: Appears in Backstrom and Nebel [1993]. It is also an immediate consequence of Theorem 6.1 in this paper. D

We can now prove the NP-hardness results.

Theorem 4.3 Bounded plan existence is NP-complete in the strong sense for SAst- UBS and SAs+- US.

Proof: We prove NP-hardness of SAS+-UBS plan ex­ istence by reduction from minimum cover [Garey and Johnson, 1979, page 222] which is defined as follows. Let X= {xlJ . . . ,xm} be a set, let C = {Cl, .. . ,Cn} be a set of subsets of X and let K be an integer. Does there exist a cover for X, ie., a subcollection C' C C s.t. Uc.EC' C~c =X and IC'I:::; K. -

Define one binary state variable, x~c, for each x~c EX and one, cr, for each Cr E C. Further define an operator hr for each cr s.t. hr sets c, and also define an operator hr 1c for each Cr and each XJc E Cr s.t. hr 1c can set Zt iff cr is set . Let all state variables be reset' initially and require all XJc to be set in the goal state. It is obvious that X has a cover C' s.t. IC'I ~ K iff there is a plan of size lXI + K or less solving II.

Both problems are in NP since the minimal solutions are always of polynomial length (Theorem 4.2) and can, thus, be verified in polynomial time. 0

Theorem 4.4 Bounded plan existence is NP-hard in the strong sense for SAs+ -PUB.

Proof sketch: NP-hardness in the stron~ sense fol­ lows by a reduction from the clique problem lGarey and Johnson, 1979, p. 194]. Assuming a graph G = (V, E), the underlying idea of the proof is to define a SAS+­ PUB instance as follows. For each vertex Vi E V we use five state variables Ai, Bi, Ci, Di and Vi and eight t + b+ + - d+ d- + d - t opera ors ai , i , ci , ci , i , i , vi an vi s . . operators denoted + {-) set {reset) their corresponding state variables. The prevail-conditions are chosen s.t. at can be executed only if C; is set and D; is reset, while bt can be executed only if C; is reset and D; is set. We let all state variables be reset initially and require all variables but V; to be set in the goal state. Obviously, anJ plan must include either of the operator se~uences (c; ,at,c;,dt,bt,ct} and (dt,bt ,d;,ct,a[,d; ). We further add prevail-conditions s.t. c; be executable only if V; is set and di is executable only if Vj is set for all Vj not incident to v; in G. It can be proven that G has a clique of size k iff the above SAS+-PUB instance has a plan of length 8jVj- 2k or less. 0

Theorem 4.5 Bounded plan existence is NP-hard in the strong sense for SAs+ -PBS.

Proof sketch: SAS+ -PUB plan existence can be re­ duced to SAS+ -PBS plan existence as follows . For each state variable x add a new state variable x' and redefine the operators s.t . x' is set when xis reset , reset when xis set and undefined when x is undefined. This is possible since the new instance need not be unary. Furthermore, we can now test whether x is reset by instead testing whether x' is set, so the operators can be redefined to be single-valued. 0

If we further drop post-uniqueness, then the last two problems become PSPACE-complete.

Theorem 4.6 Both bounded and unbounded SAs+ plan existence is PSPACE-complete.

Proof: Immediate from the formalism equivalence re­ sult [Backstrom, 1992a, Corollary 5.18] and PSPACE­ completeness for propositional STRIPS [Bylander, 1991, Theorem 1] . 0

We also sharpen the PSPACE-completeness results presented by Bylander [1991] and Erol et a/. [1992].

Theorem 4. 7 Both bounded and unbounded SAs+- UB and SAs+ -BS plan existence is PSPACE-complete.

5 Finding Optimal Plans

We are ultimately interested in finding a solution, not only finding out whether one exists. Hence, it is in­ teresting to also analyse the complexity of the bounded plan search problem. Obviously, a search problem can never be easier than its corresponding existence prob­ lem, so the results in the previous section provide lower bounds for the bounded plan search problems. Further­ more, if we can solve the bounded plan existence prob­ lem, then we can also solve the bounded plan search problem by using prefix search [Balcazar et a/., 1988, Garey and Johnson, 1979, pp. 116- 117]. It is impor­ tant to note, however, that this method does not provide a polynomial reduction of the bounded search problem to the bounded existence problem. The reason for this is that some of the problems we consider do not have polynomially bounded minimal solutions, as we will see below. Hence, the prefix search method provides only a pseudo-polynomial reduction, ie., the reduction is poly­ nomially bounded in K, but not necessarily in the size of the representation of K.

Theorem 5.1 The SAs+ -PUB and SAs+ -PBS plan­ ning problems have instances with exponentially sized minimal solutions.

Proof sketch: Given m > 0, define a SAS+ -PUB instance IT= ((M,S,1i),s0 ,s*) s.t . M = {1, ... ,m}; all S; = {0,1} ; 1i = {ht,h!, ... ,h;t",,h;;;}, where for 1 ~ k ~ m,

so = (0, . .. , 0) and s* = (0, . .. , 0, 1) . This instance has a unique minimal solution of length 2m -1 corresponding to a Hamilton path in the state space.

The above SAS+ -PUB instance can be encoded as a SAS+ -PBS instance, using the same technique as in the proof of Theorem 4.5, which, thus, has a unique minimal plan of length 2m - 1. 0

An immediate consequence of this theorem is that both bounded and unbounded SAS+ -PUB and SAS+­ PBS plan search is provably intractable since we might have to output a solution which is exponentially larger than the problem instance itself. Some care should be taken in interpreting these results, though. What we see here is the second cause for intractability as defined by Garey and Johnson [1979, pp. 11-12] and we should hardly regard instances with exponentially sized solu­ tions as realistic. However, even if we look only for solutions with a specified length the problems are still NP-hard in the length parameter 3 , which follows from the strong NP-hardness of SAS+ -PBS and SAS+ -PUB bounded plan existence. A further discussion on this topic appears in Backstrom [1992a, pp. 142-147].

Finally, the following result is immediate from Theo­ rem 4.

Theorem 5.2 Bounded plan search is NP-equivalent for SAs+- UBS and SAs+- US

6 Non-optimal Planning

While an algorithm for the bounded plan existence prob­ lem can be used to find plans, this is not the case for the unbounded existence problem. The reason is that we no longer have a measure of the distance to the goal. A polynomial-time algorithm used to prove that an exis­ tence problem is tractable can often be modified to also find a solution in polynomial time. This is not always the case, however. Hence, it seems that it is not of much use to know the complexity of the plan existence prob­ lem since we are ultimately interested in the complexity of finding a plan. Therefore, we focus only on the search problem in this section.

Figure 2 summarizes the complexity results for both the bounded and the unbounded plan search problems. The only difference is that the problems in the grey area are tractable for unbounded plan search but NP­ equivalent for bounded plan search.

3 That is, NP-hard in the value of the length parameter, not only in the size of its representation.

While the SAS+ -PUS problem was found to be the maximal tractable problem for optimal planning (wrt. the restrictions in Definition 3.1), this is no longer the case if we consider also non-optimal solutions. It turns out that we can find a solution in polynomial time even if we remove the P restriction, ie. if we have alternative ways of achieving an effect .

Theorem 6.1 Plan search is solvable in polynomial time for SAs+- US .

Proof sketch: The following algorithm, Plan, finds plans for the SAS+-US problem in polynomial time. 4

1 Plan(M,S,1i,so,s*) 2 N+-0 3 loop 4 (s, ~) +- AchievePrevaii(N) 5 (t, /3) +- AchieveGoal(s) _ 6 if t!;; s then return (a;/3) 7 elsif 3i E N(t[i]!b s[i]) then reject 8 elseN +- N U {i E Mjs[i] f. f'H[i]} 9 end loop

AchievePrevail returns a state s and a plan a from s0 to s s.t . s[i] = f'H[i] for as many i E M - N as possible and s[i] = s0 [i] otherwise. Unariness and single­ valuedness together guarantee that a unique such state exists, since achieving the global prevail-condition, f'H, for one state variable cannot make f'H unachievable for another state variable. An iterated greedy strategy is used to find s and a, which is not guaranteed to be minimal.

Using a similar strategy, AchieveGoal returns a state t and a plan i3 from t to s* s.t. t[i] = s[i] for as many i EM as possible and t[i] = s*[i] otherwise.

4 The algorithm is a descendant from an algorithm used by Bylander [1991, Theorem 7].

The first time around the loop in Plan the global prevail-condition is achieved for as many i E M as pO&­ sible in the state s, and t is the state 'closest' to s from which the goal can be achieved. If 8 = t, then 8 is a subgoal s.t. a is a plan from s0 to s and i3 is a plan from s to s*, and we are done. Otherwise, if s[i] f. t[i] for some i E M - N, then s*[i] could not .be achieved from s[i] so f'H[i] must not be a subgoal. Hence, i is put in N to guarantee that f'H [ i] is not achieved the next time around the loop. Furthermore, if there is some i E N s.t. s[i] f. t[i], then there cannot be any plan at all since s*[i] cannot be achieved from s0 [i] and not from f'H[i] (or f'H[i] itself could never be achieved) .

Plan terminates since N grows strictly. To see that Plan is correct, note that N is empty the first time around the loop, so if s*[i] could not be achieved from s[i] because such a plan would require some operator h s.t . f(h) !l s, then it could not be achieved at all. Fur­ thermore, any prevail-condition which is subsequently blocked by N must not be achieved since this would make some other part of the goal unachievable. 0

Theorem 5.1 imply provable intractability also for the unbounded SAS+ -PUB and SAS+ -PBS plan search problems. Hence, we can find plans in polynomial time exactly for those problems that have polynomially bounded minimal solutions. One should not try to draw any generalized conclusions from this observation, how­ ever.

7 Discussion and Conclusions

Recently a number of results have been published on the computational complexity of propositional STRIPS planning under various restrictions [Bylander, 1991, 1992a, Erol et a/., 1992]. In addition to this we have pre­ viously presented a number of tractable planning prob­ lems using the SAS+ formalism [Backstrom and Klein, 1991a, 1991b, Backstrom, 1992a, 1992b]. All of these results concerns the complexity of planning in various restricted versions of certain formalisms. One might also investigate the complexity of planning for specific · problems instead of specific formalisms. This has been done for some variants of the blocks-world problem by Gupta and Nau [1992]. Furthermore, the complexity of temporal projection and its relationship to planning has been investigated by Dean and Boddy [1988] and by ourselves [Backstrom and Nebel, 1992, Nebel and Backstrom, 1993].

Our previous publications on SAS+ planning have con­ centrated on finding tractable subproblems and trying to extend these while retaining tractability. This pa­ per complements these results by presenting a complet.e investigation of the complexity for each of the possible combinations of the previously considered restrictions. We already know [Backstrom, 1992a, 1992b] that the SAS+ formalism is expressively equivalent to a num­ ber of 'standard' propositional STRIPS formalisms, in­ cluding those analysed by Bylander [1991] and Erol et al. [1992] . One might wonder, then, why we have both­ ered doing such a complexity analysis for the SAS+ for­ malism. However, there are at least two important differences between our analysis and the previous ones.

Firstly, Bylander and Erol et al. have only stud­ ied local restrictions on operators. Unariness is such a local restriction, while post-uniqueness and single­ valuedness are global restrictions on the whole set of op­ erators. Korf [1987] has studied some computationally interesting global properties, like independent and seri­ alizable subgoals. Unfortunately, finding out whether a problem instance has serializable subgoals is PSPACE­ complete [Bylander, 1992b]. In contrast to this, all our restrictions can be tested in low-order polynomial time [Backstrom, 1992a, Theorem 4.8]. Furthermore, we have not derived our restrictions from the formalism per se but from studying a test example in the area of automatic control. Using the SAS+ formalism instead of the STRIPS formalism has facilitated in finding these restrictions, which are interesting from a computational point of view by resulting in tractability. One should also note that the equivalence result applies to the unre­ stricted versions of the formalisms and it is not guaran­ teed to hold under arbitrary restrictions. Furthermore, it is not always obvious how to translate a restriction for SAS+ into a restriction for STRIPS and vice versa.

The second difference is that the previous analyses of planning complexity have only considered the plan ex­ istence problem [Bylander, 1991], and sometimes also the bounded plan existence problem [Bylander, 1993, Erol et al., 1992]. In addition to this, we also analyse the complexity of actually finding a (possibly optimal) plan, which is what we are ultimately interested in. In many cases there is a strong relationship between a deci­ sion (solution existence) problem and its corresponding search problem (finding a solution) , but it is not always so.

The result of our analysis shows that we have reached the tractability borderline and we cannot continue to re­ move restrictions and still have tractability. This should not discourage us, however. It means that we have will have to start considering alternative restrictions or less restricted variants of the P, U, B and S restrictions. The proposed research methodology is further described in Backstrom [1992a] where also some suggestions for such alternative restrictions are given. Finally, it seems that one important reason for the disappointing complexity results is that most formalisms allow formulating un­ realistic problems, having exponentially sized minimal solutions.

Acknowledgements

Bart Selman and the anonymous reviewers have provided helpful comments on the paper.