Complexity Results for Planning

1 Introduction

If the relationship between intelligence and computation is taken seriously, then intelligence cannot be explained by intractable theories because no intelligent creature has the time to perform intractable computations. Nor can intractable theories provide any guarantees about the performance of engineered systems. Presumably, robots don't have the time to perform intractable com­ putations either.

Of course, heuristic theories are a valid approach if partial or approximate solutions are acceptable. How­ ever, my purpose is not to consider the relative merits of heuristic theories and tractable theories. Instead, I shall focus on formulating tractable planning problems.

Planning is the reasoning task of finding a sequence of operators that achieve a goal from a given initial state.

*This research has been supported in part by DARPA/ AFOSR contract F49620-89-C-0110 and AFOSR grant 89-

0250.

It is polynomial if each operator is restricted to positive preconditions and one postcondition. The blocks-world problem, slightly modified, is a sub­ class of this restricted planning problem.

It is polynomial if each operator has one precon­ dition and if the number of goals is bounded by a constant.

It is polynomial if each operator is restricted to no preconditions.

One additional box in the figure identifies a commonality between four of the problems. 2

The remainder of this paper is organized as follows. First, I describe previous results on the complexity of planning. Then, propositional planning is defined. Next, I demonstrate the complexity results and show how the blocks world is covered by one of the results . Finally, I discuss the impact of these results on the search for tractable planning.

2 Previous Results

The literature on planning is voluminous, and no at­ tempt to properly survey the planning literature is at­ tempted here. Instead, the reader is referred to Allen et al. (1990]and Hendler et al. (1990]. Despite the large lit­ erature, results on computational complexity are sparse. In turn, I discuss previous results from Dean and Boddy (1987], Korf [1987], and Chapman [1987].

Dean and Boddy [1987] analyze the complexity of tem­ poral projection-given a partial ordering of events and causal rules triggered by events, determine what condi­ tions must be true after each event . Their formalization of temporal projection shares many features with plan­ ning, e.g., their causal rules contain antecedent condi­ tions {preconditions) and added and deleted conditions (postconditions). In fact, the notation for propositional planning is mostly borrowed from Dean and Boddy. However, they only consider problems of prediction in which a partial ordering of events is given, whereas the equivalent planning problem would be to find some or­ dering of any set of events that achieves some set of conditions.

Korf {1987) considers how various global properties of planning problems {e.g., serializable subgoals, opera­ tor decomposability, abstraction) affect the complexity of using problem space search to fi-nd plans. In con­ trast, I focus exclusively on local properties of operators. However, except for Korf's own analysis of operator de­ composability [Korf, 1985], neither he nor I describe the relationship from these properties of planning problems to the properties of operators. Clearly, this is a "gap" that future work should address.

2 The following are other results not judged to be as in­ teresting, but are included here for completeness. Proposi­ tional planning is NP-complete if each operator is restricted to positive preconditions and negative postconditions, even if restricted to one positive precondition and two negative postconditions. It is polynomial in the previous cases if the number of goals is bounded by a constant. It is polynomial if each operator is restricted to positive preconditions and positive postconditions.

Perhaps the most important complexity results for planning are due to Chapman's analysis of his planner TWEAK [Chapman, 1987]. Because virtually all other planners are as expressive as TWEAK, his results have wide applicability. TWEAK's representation includes the following features. The preconditions and postconditions of an operator schema are finite sets of "propositions." A proposition is represented by a tuple of elements, which may be constants or variables, and can be negated. A postcondition of an operator can contain variables not specified by any precondition of the operator, which in effect allows creation of new constants.

Chapman proved that planning is undecidable and so clearly demonstrated the difficulty of planning in gen­ eral, but it is not obvious what features of TWEAK's representation are to blame for the complexity. What happens to the complexity, for example, if postcondi­ tions cannot introduce new variables? What happens if the size of states are bounded for any given instance of a planning problem? Are there any interesting restricted planning problems that are tractable? By considering a model of planning with considerably fewer features, the following analysis begins to address these questions.

3 Propositional Planning

An instance of propo&itional planning is specified by a tuple (P, 0, I, g), where:

P is a finite set of condition&;

0 is a finite set of operator&, where each operator has the form ("P. 7], a, c):

"() ~ P is a set of po&itive preconditions;

TJ ~ P is a set of negative preconditions;

a ~ P is a set of positive postconditions;

c ~ P is a set of negative postconditions; and

I ~ P is the initial state; and

That is, P is the set of conditions that are relevant . Any state can be specified by a subsetS ~ P, indicating that p E P is true in that state if and only if p E S. 0 is the set of the operators that can change one state to another . I specifies what conditions are true and false in the initial state, i.e., p E P is initially true if p E I and initially false otherwise. g specifies the goals, i.e., S ~ P is a goal state if and only if M ~ Sand S n N = 0.

The effect of a finite sequence of operators ( o1, o2, . . . , on) on a state S can be formalized as follows:

In essence, any operator can be applied to a state, but only has an effect if its preconditions are satisfied. If its preconditions are satisfied, its positive postconditions are added and its negative postconditions are deleted, cf. [Fikes and Nilsson, 1971] . An operator can appear multiple times in a sequence of operators.

A finite sequence of operators (o1,o2, ... , on) is a solution to an instance of propositional planning if Resu.lt(I, (o1, 02, ... , on)) is a goal state.

An instance of a propositional planning problem is sat­ isfiable if it has a solution. PLANSAT is defined as the decision problem of determining whether an instance of propositional planning is satisfiable. Below, the compu­ tational complexity of PLANSAT and restricted versions of PLANSAT are demonstrated.

To show how a planning instance can be modeled by propositional planning, consider the Sussman anomaly. In this blocks-world instance, there are three blocks A, B, and C. Initially Cis on A, A is on the table, and B is on the table. The goal is to have A on B, B on C, and C on the table. Only one block at a time can be moved. The conditions, initial state, and goals can be represented as follows:

The negative goals N exploit the fact that C is on the table if it is not on top of anything else.

The operator to unstack A can be represented as:

That is, A can be moved to the table if nothing is on A. As a result, A will not be on top of any other block.

The operator to stack A on B can be represented as:

That is, A can be stacked on B if nothing is on top of A or B. The result is that A will be on B and not on top of any other block.

Obviously, any blocks-world instance can be easily modeled as propositional planning. More generally, any TWEAK planning instance can be polynomially reduced to a propositional planning instance if the initial state is finite, if each variable in an operator schema is limited to a polynomial number of values, and if each opera­ tor schema is limited to a constant number of variables. An exponential number of values for a variable would lead to an exponential number of propositional planning conditions. A polynomial number of variables in an op­ erator schema would lead to an exponential number of propositional planning operators.

4 Complexity Results

This section describes and demonstrates our complexity results for propositional planning. Due to space limi­ tations, some of the proofs are overly abbreviated. As mentioned above, PLANSAT is the decision problem of determining whether an instance of propositional plan­ ning is satisfiable.

4.1 PSPACE-complete Propositional Planning Theorem 1 PLANSAT is PSPACE-complete.

Proof: PLANSAT is in NPSPACE because a sequence of operators can be nondeterministically chosen, and the size of a state is bounded by the number of conditions. That is, if there are n conditions and there is a solution, then the length of the smallest solution path must be less than 2n. Any solution of length 2n or larger must have "loops," i.e., there must be some state that it visits twice. Such loops can be removed, resulting in a solution of length less than 2n . Hence, no more than 2n nonde­ terministic choices are required. Because NPSPACE = PSPACE, PLANSAT is also in PSPACE.

Turing machines whose space is polynomially bounded can be polynomially reduced to PLANSAT. The PLANSAT conditions can be encoded (and roughly translated) as follows:

in;,., Symbol z is in tape position i.

at;,q The input tape head is at the ith position and the Turing machine is in state q.

do;,q,z Perform the transition at the ith position for state q on character z.

accept The Turing machine accepts the input.

. If qo is the initial state of the Turing machine, its input 1s z1z2 ... z,, and the space used by the Turing machine is bounded by n, then the the initial state and goals for propositional planning can be encoded as:

I is encoded so that that position 1 to position k contain the input and the remaining positions (position 0 and positions k + 1 ton- 1) contain a special symbol#.

. Suppose that the Turing machine is in state q, the mput tape is at the ith position, z is the character at the ith position, and the transition is to replace z with y, move to the right, and be in state q'. This can be encoded using three operators:

The first operator "packs" all the information about the current position into a single condition. The second op­ erator changes the symbol. The third operator moves to the next position and the new state. To handle boundary conditio~s, encode no operators for at_ L,q and at,., 9 ·

A Turmg machine accepts an input if it is in an ac­ cepting state and no transition can be made from the current symbol. For each s.uch case, an operator to add accept can be encoded.

Because there are a polynomial number of (i, q, z) combinations, there will be a polynomial number of con­ ditions and operators. Thus, any PSPACE Turing ma­ chine with its input can be polynomially reduced to a propositional planning instance. 0

Note that none of the above operators requires more than two positive preconditions and two postconditions. This leads to the following corollary.

Corollary 2 PLANSAT with operators restricted to two positive preconditions and two postconditions M PSPACE-complete.

~sing the same conditions as encoded above, the fol­ lowmg theorem can be demonstrated:

Theorem 3 P LANSA T with operators restricted to one postcondition (allowing any number of preconditions) is PSPACE-complete.

Proof: Let Do; = {dou, 11 ,w lu = i}. That is, Do; is the set of all do conditions whose first subscript is i. Then the Turing machine transition described above can be encoded using the following six operators:

In essence, two operators replace each operator in the previous reduction. The structure of the operators en­ sures that they must be performed in sequence. The key part is the first operator, whose negative preconditions include all do conditions whose first subscript is i- 1 or i + 1. This ensures that the do condition associated with the previous transition has been removed (see the sixth operator) before the next Turing machine transition be­ gins. This is why any number of preconditions may be necessary. 0

4.2 NP-complete and NP-hard Propositional Planning

Let PLANSAT+ be PLANSAT with operators restricted to positive postconditions.

Theorem 4 PLANSAT+ is NP-complete.

Proof: PLANSAT + operators can never negate a condi­ tion, so a previous state is always a subset of succeed­ ing states. Also, operators within an operator sequence that have no effect can always be removed. Hence, if a solution exists, the length of the smallest solution can be no longer than the number of conditions. Thus, PLANSAT+ is in NP because only a linear number of nondeterministic choices is required.

3SAT can be polynomially reduced to PLANSAT+. 3SAT is the problem of satisfying a formula in proposi­ tional calculus in conjunctive normal form, in which each clause has at most three factors.

Let F be a formula in propositional calculus in 3SAT form. Let U = { Ut, u2, .. . , tLm} be the variables used in F . Let n be the number of clauses in F . An equiva­ lent PLANSAT+ instance can be constructed using the following types of conditions.

T; u; = true is selected.

F; u; = false is selected.

C; The jth clause is satisfied.

The initial state and goals can be specified as:

That is, the goal is to satisfy each of the clauses. For each variable u;, two operators are needed:

That is, Ui = true can be selected only if Ui = false is not, and vice versa. In this fashion, only one of Ui = true and Ui =false can be selected.

For each case where a clause c; contains a variable Ui, the first operator below is needed; for a negated variable Ui, the second operator below is needed:

Clearly, every C; can be made true if and only if a satisfying assignment can be found. Thus PLANSAT+ is NP-hard. Since PLANSAT+ is also in NP, it follows that PLANSAT+ is NP-complete. o

Note that each operator above only requires one pre­ condition and one positive postcondition. This leads to the following corollary.

Corollary 5 PLANSAT+ with operators restricted to one precondition and one postcondition is NP-complete.

There is one additional intractability result .

Theorem 6 P LANSAT with operators restricted to one positive precondition and two postconditions is NP-hard.

Proof: This can be shown by reduction from 3SAT, sim­ ilar to that for Theorem 4. One additional type of con­ dition is needed:

ui The value of Ui is unknown.

The initial state is {Ut, ... , Um}·

Now all that is needed are different operators for se­ lecting an assignment.

Again, both Ui = true and Ui = false cannot be selected. The same operators for clauses as in the proof for The­ orem 4 can be used. 0

4.3 Polynomial Propositional Planning

Theorem 7 P LANSA T with operators restricted to pos­ itive preconditions and one postcondition is polynomial.

Proof Outline: The difficulty is that some negative goals might need to be temporarily true to make some posi­ tive goals true or some negative goals false. Fortunately, because of the restrictions on the operators, it can be shown that any plan can be transformed to another plan that first makes conditions true and then makes condi­ tions false. Thus, if there is a solution, there is a state S that meets the following conditions:

S can be reached from the initial state I via oper­ ators with positive postconditions;

the positive goals M are a subset of S; and

S \ .N, i.e., a state that satisfies the negative goals, can be reached from S via operators with negative postconditions.

Because each operator has only positive preconditions and affects only one condition, and because the positive goals are true of S, the only thing remaining is to make all the negative goals false, i.e., to achieve S \ .N. There is no reason to make other conditions false.

Let Turnon then be a subroutine that inputs a set of conditions X and returns the maximal state S ~ 1' \ X that can be reached from I . Let Turnoff be another subroutine that inputs a set of conditions S and returns the maximal state S' ~ S such that S\.N can be reached from S'. It can be shown that each subroutine is poly­ nomial, and that each maximal state is unique.

The following algorithm determines if a solution exists by iterating between Turnon and Turnoff:

end loop

It can be shown that every condition added to X is a condition that, if true, prevents the goal state from being reached. Since X grows monotonically, the algorithm is polynomial. 0

Theorem 8 P LANSA T with k goals and operators re­ stricted to one precondition is polynomial.

Proof: This is the algorithm. Construct all possible com­ binations of k conditions. Mark those combinations true of the initial state. For each marked combination, mark any combinations that can be reached from that combi­ nation via an operator. After all possible combinations are marked, if the combination of conditions correspond­ ing to the goal is marked then accept , otherwise reject.

This is why the algorithm works. Consider a solution plan and any one of the k goals. To reach this goal, there must be a "chain" of operators leading frol}l one condition in the initial state through one condition at a time until the goal is reached. Consider now the k chains of operators for the k goals. Consider also any state reached during the execution of the solution plan. This state will correspond to k nodes on the k chains . Any state that satisfies the k conditions corresponding to those nodes can reach the goal state. Since this is true for all states reached by the solution plan, it must be the case that only k conditions at a time need to be consid­ ered to determine what combinations of k conditions can be reached. 0

Note that if operators can have more than one precon­ dition, then a conjunctive goal problem can be converted into a single goal problem by adding operators that map the original set of goals onto a single "supergoal."

Theorem 9 P LANSA T with operators restricted to no preconditions is polynomial.

Proof: It is possible to work backwards from the goals. First look for operators that do not clobber any of the goals. Goals that are achieved by these operators can be removed from consideration. These operators can also be removed from consideration. Then look for operators that do not clobber the remaining goals, and remove from consideration these operators and the goals they achieve. This can be repeated until the remaining goals are true of the initial state (accept) or until no more appropriate operators can be found (reject). D

4.4 The Blocks World

Theorem 7 can be used to show that the blocks-world problem is tractable.

Theorem 10 The blocks-world problem can be solved using operators restricted to positive preconditions and one postcondition.

Proof: Note that stacking one block on another can be accomplished by first moving the former block on the table and then moving it on top of the latter block. Thus, solving any blocks-world instance only requires operators to move a block to the table and to move a block from the table.

Let {B1 , B2, ... , Bn} be the blocks in an instance of the blocks-world problem. The conditions can be en­ coded as follows:

If Bi is on the table, then all off i 1c will be true. If Bi has a clear top, then all off 1c i will 'be true. If Bi is on top of Bj, then all off i,lc except for off i,j will be true.

For each Bi and Bj, i # j, the operator to move Bi from on top of Bj to the table can be encoded as:

That is, if nothing is on Bi and nothing is on Bj ex­ cept possibly Bi, then when this operator is applied, the result is that Bi will not be on top of Bj.

For each Bi and Bj, i # j, the operator to move Bi from on the table to on top of Bj can be encoded as:

That is, if nothing is on Bi and Bj, and if Bi is not on top of any other block, then when this operator is applied, the result is that Bi will be on top of Bj.

Since there are only O(n 2 ) (i, j) combinations, only O(n 2 ) conditions and operators are needed to encode a blocks-world instance.

As required, all preconditions are positive and each operator has only one postcondition. Thus, Theorem 7, in a sense, explains why the blocks world is tractable. 3

3 The algorithm for Theorem 7 corresponds to the unimag­ inative, but robust, strategy of moving all the blocks to the table, which makes all the conditions positive, and then form­ ing the stacks from the table on up.

5 Remarks

Planning is intractable even if the size of states are bounded and operators have no variables. Merely allow­ ing two preconditions and two postconditions for opera­ tors gives rise to an extremely hard problem. However, operators must have preconditions, postconditions, and apparently many more "features" to implement any in­ teresting domain [Chapman, 1987; Hendler et al., 1990). While additional features might be good for making a planner more useful as a programming tool, generality has its downside-tractability cannot be guaranteed un­ less there are sufficient restrictions on the operators.

Some restricted propositional planning problems are tractable. Restricting operators to positive precondi­ tions and one postcondition explains the tractability of the blocks-world. Restricting operators to one precondi­ tion and limiting the number of goals is the only inter­ esting case where restricting the number of goals leads to tractability. Restricting operators to no preconditions shows that planning is tractable if preconditions can be ignored, e.g., if preconditions of operators can be easily satisfied without clobbering already achieved goals.

However, many, if not most, planning domains vio­ late these categories. Thus, these domains cannot be shown to be tractable based on restrictions on the local properties of operators. As mentioned in the section on previous research, Korf [1987]lists several global prop­ erties of planning problems that lead to efficient search for plans. Understanding how these properties are real­ ized as restrictions on the set of operators as a whole is a promising research approach.

Unfortunately, the prospects for a single domain­ independent planning algorithm are pessimistic. The three tractable problems above appear to require quite different algorithms, and many other tractable planning problems are yet to be discovered. This indicates that it will be more fruitful to adopt different algorithms for different types of planning problems.