Parallel Non-Binary Planning in Polynomial Time

1 Introduction

A large proportion of earlier papers about planning fo­ cus either on implementation of planners, or on repre­ sentation problems, using logic or otherwise, and do not address computational issues at all.

Among earlier work on planning complexity, Chap­ man [1987] has designed an algorithm, called TWEAK, which captures the essentials of constraint-posting non­ linear planners. TWEAK is proven correct, but does not always terminate. Chapman has proven that the class of problems TWEAK is designed for is undecidable. Dean and Boddy [1988] have investigated some classes of tem­ poral projection problems with propositional state vari­ ables. They report that practically all but some trivial classes are NP. It should be noted, however, that they assume a non-deterministic domain where events actu­ ally occur only if their pre-conditions are fulfilled. Korf [1987] presents some complexity results for traditional search based planning. He shows how the complexity can be reduced for problems where subgoals are serializable or independent, and he also shows how macro-operators and abstract actions can reduce complexity under cer­ tain assumptions.

The majority of papers on temporal logics discuss rep­ resentation of problems, and results about complexity and computability are almost non-existent. An imple­ mentation of a restricted version of one temporal logic, ETL, is reported by Hansson [1990]. His decision proce­ dure solves temporal projection in exponential time, but is not guaranteed to terminate for planning. Recent work by van Beek [1990] presents some complexity results for some temporal ordering problems in a point algebra and

Inger Klein

Dept. of Electrical Engineering, Linkoping University S-581 83 Linkoping, Sweden email: inger@isy.liu.se

a simplified interval algebra. These results are relevant, but not immediately applicable, to planning.

Chapman [1987] says: 'The restrictions on action rep­ resentation make TWEAK almost useless as a real-world planner.' He also says: 'Any Turing machine with its in­ put can be encoded in the TWEAK representation.' It seems that any useful class of planning problems is nec­ essarily undecidable. However, we think that a planner that is capable of encoding a Turing machine has much more power than needed fm: most problems. It seems that TWEAK is too limited in some aspects, but overly expressive in other aspects. We think that finding classes of problems that balance such aspects against each other, so that they are decidable or even tractable, is an im­ portant and interesting research challenge. On the other hand, we should probably not have much hope of finding one single general planner with such properties. The re­ search task is rather to find different classes of problems which are strong in different aspects, so as to be tuned to different kinds of application problems.

We have focussed our research on problems where the action representation is even more restricted than in TWEAK, but where we can prove interesting theoretical properties. Our intended applications are in the area of sequential control, a subfield of control theory, where a restricted problem representation is often sufficient, but where the size of the problems make tractability an im­ portant issue (see section 6) .

In previous papers [Backstrom and Klein, 1990a, Backstrom and Klein, 1990b] we have presented a polynomial-time, 0( m 3 ) in the number of state vari­ ables, planning algorithm for a limited class of planning problems, the SAS-PUBS class. Compared to previous work on complexity of algorithms for knowledge-based or logic-based planning, our algorithm achieves compu­ tational tractability, but at the expense of only applying to a significantly more limited class of problems. Our general research strategy is to start with a restricted but tractable class of planning problems and to then grad­ ually extend this class while establishing its properties after each such step. This is a very usual strategy in most disciplines of science, but is, unfortunately, not very common in AI. A similar strategy has been pur­ sued by Brachman and Levesque [1984] who have stud­ ied the relationship between generality and tractability in knowledge representation languages.

The SAS-PUBS class constitutes the first step along the strategy just outlined, but this class is probably too simple to be of other than theoretical interest. However, even with very moderate extensions one would proba­ bly obtain problem classes that occur frequently in prac­ tice. This paper presents the SAS-PUS class, which is an extension of the SAS-PUBS class and which brings us closer to reality. We prove this class also to be tractable by presenting a sound and complete polynomial time planning algorithm for it. Furthermore, the algorithm only orders those actions that must necessarily be ex­ ecuted in sequence and allows for parallel execution of unordered actions.

2 Ontology of Worlds, Actions and Plans

This section defines our planning ontology with the main concepts being: world states, actions, and plans. Al­ though presented in a slightly different way, the ontology is essentially as described by Sandewall and ROnnquist [1986]. For further explanation and intuition regarding action structures, the reader is referred to Sandewall and ROnnquists paper.

2.1 World Description

We assume that the world can be modelled by a finite number of features, or state variables, where each feature can take on values from some finite discrete domain, or the value undefined, u. For technical reasons, the con­ tradictory value, k, is added. The combination of the values of all features is a partial state, and if no values are undefined the state is also a total state. If it is clear from the context, or if it does not matter whether a state is total or not, we simply call it a state. The order !;;;, reflecting information content, is defined on the feature values s.t. the undefined and contradictory values con­ tain less and more information, respectively, than all the other values. These other values contain equal amount of information and are mutually incomparable.

Definition 2.1

1. M is a finite set of feature indices.
2. Si, where i EM, is the domain for the i:th feature. Si must be finite. st = Si u { u, k} where i E M is the i:th extended domain. S = niEM Si is the total state space and s+ = flieM St is the partial state space.
3. 8[t1 for 8 E s+ and i EM denotes the value of the i:th feature of 8. The function dim : s+ --+ 2M is defined s.t. for 8 E s+, dim(8) is the set of all feature indices i s.t. 8[i] :/:- u. If i E dim(8) then i is said to be defined for 8. A state 8 E s+ is said to be consistent if 8[i] :/:- k for all i EM.
4. !;;; is a reflexive partial order on st defined as Vx x' E s-J-(x c x' +-+X= u v X= x' v x' = k) ' . - (St, !;;;) forms a flat lattice for each i.
5. !;;; is a reflexive partial order over s+ defined as ¥8,8 1 E s+(s !;;; s' +-+ViE M(s[a1 !;;; 8'[·1)) so (S+, !;;;) forms a lattice.

0

The lattice operations U, join, and n, meet, are defined as usual on the lattices (St, !;;;) and (s+, !;;;).

2.2 Action Types and Actions

Plans are constituted by actions, the atomic objects that will have some effect on the world when the plan is exe­ cuted. Each action in a plan is a unique occurrence, or instantiation, of an action type, the latter being the spec­ ification of how the action 'behaves'. Two actions are of the same type iff they behave in exactly the same way. The 'behaviour' of an action type is defined by three partial state valued functions, the pre-, the post-, and the prevail-condition. Given an action, the conditions of its type are interpreted as follows: the pre-condition states what must hold at the beginning of the action, the post-condition states what will hold at the end of the action, and the prevail-condition states what must hold during the action. One could think of the pre- and post-conditions as defining non-sharable resources and the prevail-condition as defining sharable resources, us­ ing operating systems terminology.

Every action type is subject to the following con­ straints: all conditions must be consistent, the pre- and post-conditions must define exactly the same features, the pre- and post-condition must not specify the same value for any of their defined features, and a feature de­ fined in the pre-condition must not be defined in the prevail-condition. We also demand that two distinct ac­ tion types must differ in at least one condition.

In order to distinguish actions of the same type we attach a unique label to each action. We also let an action 'inherit' the conditions from its associated action type.

Definition 2.2

1. 1t is a set of action types.
2. b, e, f : 1t --+ s+ are functions givmg the pre-, post- and prevail-condition, respectively, of an ac­ tion type.
3. £ is an infinite set of action labels.
4. A set A C £ x 1t is a set of actions iff no two distinct elementsin A have identical labels. 0

2.3 Plans

An ordered set of actions is a plan from one total state to another total state iff, when starting in the first state, we end up in the second state after executing the actions of the plan in the specified order. The plan is linear if the set is totally ordered, and it is non-linear if it is partially ordered. In a non-linear plan, the order be­ tween two actions does not have to be specified if these actions can be executed in arbitrary order. The per­ sistence handling essentially uses the STRIPS assump­ tion [Fikes and Nilsson, 1971], and, since the formal­ ism is very restricted, the frame problem [Hayes, 1981, Brown, 1987] is also avoided. The definition of plans is based on the relation 1--+ which defines how ordered sets of actions can transform one state into another.

Definition 2.3 The relation 1--+~ S x 2(.Cx'H) x 2(.Cx'H) 2 x S is defined s.t. if s, s' E S, "IV is a set of actions, a E \), and u is a total order on \) then 1--+ is defined as:

1. s~s
2. s ~ s' iff b(a) U /(a) !; s, e(a) U /(a) !; s' and s[a1 = s'[a1 for all i V. dim(b(a) U /(a))
3. s ~ s' where I'~ I~ 2 iff a1, ... , an are the actions in \) in the order u and there are states s1, ... , sn E S I d {a·},CiJ r 1 s.t. s =so, s = Sn an SJ:-1 1--+ SA: tOr $ k$ n. 0

Definition 2.4 A tuple ('I, p) is a linear plan from s0 to s* iff \) is a set of actions and p is a total order on \) s.t. s0 ~ s* . Similarly, a tuple {'I, p) where p is a partial order on \) is a non-linear plan from s0 to s* iff ('I, u) is a linear plan for any total order u on \) s.t. p~u. o

A plan for a specific problem is minima/ iff there is no other plan solving the same problem using fewer actions.

Definition 2.5 A plan ('I, p) from s0 to s* is minima/iff there is no other plan (4, u) from so to s* s.t. 141 < I'~ I· 0

We say that two actions are independent, meaning they can be executed in parallel, iff any feature changed by one of the actions is undefined in all conditions of the other action and whenever both actions define the same feature in their prevail-conditions, they define the same value for this feature. We further say that a plan is a parallel plan if all its unordered actions are independent, and it is maximally parallel if no pair of independent actions is ordered.

Definition 2.6 Two actions a and a' are independent iff, for all i E M, all of the following conditions hold:

1. b(a)[a11 u implies b(a')[a1 U f(a')[a1 = u
2. b(a')[q I u implies b(a)(a1 U /(a)[a1 = u
3. /(a)[i] !; /(a')[a1 or /(a')[a1 !; /(a)[i]

0

Definition 2. 7 A non-linear plan ('I, p) from s0 to s* is a parallel plan iff all pairs of actions a, a' E \) s.t. neither apa' nor a' pa are independent. 0

Definition 2.8 A parallel plan ('I, p) is maximally par­ allel iff ('I, u) is not parallel for any u C p. 0

3 Classes of Planning Problems

The class of planning problems according to our ontology so far is called the SAS, Simplified Action Structures, class.

We also want to talk about more restricted classes, so we define some useful properties that can be ascribed to problem classes. We say that a domain is binary if it has exactly two elements, ISil = 2. The set of action types is unary if all action types change exactly one feature, post-unique if no two different action types can change a certain feature to the same value, and single-valued if no two action types have defined but different values of their prevail-conditions for the same feature.

The rest of this paper concentrates on the SAS-PUS class (PUS meaning post-unique, unary, and single­ valued). The implications of these restriction are dis­ cussed in section 6. The SAS-PUS class is an extension of the previously presented SAS-PUBS cl~, which also requires the domains to be binary.

Definition 3.1 A planning problem is in the SAS-PUS class iff it is SAS and 1l is unary, post-unique and single­ valued. 0

4 SAS-PUS Planning

This section presents an algorithm for finding minimal plans for the SAS-PUS class and also states some the­ oretical results about the algorithm and the SAS-PUS class. The proofs are omitted because of the page limit, but they can be found in our report [Backstrom and Klein, 1991].

The definitions of most functions and procedures used in the algorithm should be obvious, but the following three might need some explanation.

FindActionPost{A,i,x) Searches the set A of actions for a member a s.t. e(a)(a1 = z[a1 and which is returned if it exists. If such an a does not exist, the value nil is returned.

FindAndRemove(A,i,x) Like FindActionPost but also removes a from A.

Order( a, a', r) Adds ara' to the relation r.

Algorithm 4.1

Input: M, a set of feature indices, A, a set containing two actions of each type in 1£, and s0 and s*, the initial and final states respectively.

Output: D, a set of actions, and r a relation on D.

1 Procedure Plan( s0 , s* :state; M :set of) 2 feature indices; A :set of actions); 3 var i : feature index; a, a' : action; 4 D, P, T: set of actions; L :list of actions; 5 r : relation on D; 6 7 ProcedureBui/dChain(sp, ST :state;) 8 i :featureindex; A: set of actions; D, T: in out 9 set of actions; r : in out relation); 10 vars : state; a, a' : action; L : list of actions; 11 begin{BuildChain} 12 L := nil; a' := nil; s := ST; 13 while s[i] I sp[i] do 14 a :=FindAndRemove(A, i, s); 15 if a= nil then fail 16 else 17 Insert( a, D); Insert( a, T); Concat(a, L); 18 if a' I nil then Order( a, a', r) 19 a' :=a; s := b{a); 20 return£; 21 end; {Build Chain} 22 23 begin{Plan} 24 D := 0; T := 0; r := 0; 25 fori EM do

26 L :=BuildChain(s0 ,s*,i,.A,D,T,r); 27 P :=Copy(D); 28 whileT-:/; 0do 29 a :=RemoveAnAction(T); 30 fori EM do 31 if /(a)[a1 ~ s0 [a1 then 32 a' :=FindActionPost(D, i, f(a)); 33 if a'-:/; nil then Order( a', a, r) 34 else 35 L :=BuildChain(s0 ,/(a),i,.A,D,T,r); 36 Order(Last(L), a, r); 37 if f(a)[i] ~ s*[a1 then 38 a' :=FindActionPre(D, i, f(a)); 39 if a' -:/;nil then Order( a, a', r) 40 else 41 L :=BuildChain(!(a), 801 i, .A, D, T, r); 42 Order(a,First(L), r); 43 a' :=FindActionPre(P, i, s0 ); 44 if a' -:/; nil then Order( Last( L), a', r) 45 TransitiveCiosure(r); 46 if "r is not antire.flexive" then fail 47 return (D, r}; 48 end; {Plan}

The main variables are D, T and r. D is a non­ decreasing set of actions which will eventually be the set of actions in the plan, if the algorithm succeeds. Ev­ ery action ever inserted into D is also inserted into T, and the use of this set will become clear later on. r is a relation on D, and it will eventually be the execution order of the plan.

The function Build Chain has the purpose of trying to find a, possibly empty, sequence of actions in A which, if executable, changes the i:th feature from BF[a1 to sr[i]. If such a sequence is found, it is removed from A and inserted into D and T. Otherwise, the algorithm fails.

The main body of the algorithm first calls Build Chain once for each feature i to find a sequence of action chang­ ing i from s0 [i] to s*[al D now contains all actions primarily needed to change s0 into s*, but all of these actions do not necessarily have their prevail-conditions satisfied. The purpose of the while loop in the algo­ rithm is to achieve that all actions have their prevail­ conditions satisfied. Since all actions in T are eventually removed from T and processed by the body of the while loop, all actions in the final plan will have their prevail­ conditions satisfied. For each action a in T, the body of the while loop tests, for each feature i, whether the prevail-condition of the current action is satisfied in s0 · Nothing need be done if this is the case, but, otherwise, the algorithm checks if there is already a sequence of ac­ tions in D that changes the i:th feature from s0 to /(a). If there is such a sequence, it is ordered before a, and, otherwise, BuildChain is called to find such a sequence. Since the actions needed to satisfy the prevail-condition of a might interfere with the primary actions changing s0 into s*, we must also assure that /(a)[i) is changed into s*[i]. This is done in the second half of the body of the while loop, and in a way analogous to the first part. The difference is that if BuildChain is called, it finds a sequence of actions changing f(a)[i] into s0 [a1, not s*[i). The reason for this is that if s0 [i) -:/; s*[i), then there is already a sequence of actions in D changing s0 [l1 into s*[i], and which is then ordered after the newly found sequence. After computing the transitive closure of r, it is tested for antireflexivity, and the algorithm fails if the order contains circularities. The algorithm is proven sound and complete.

Theorem 4.1 Given a SAS-PUS planning problem, if there is any plan solving the problem then algorithm 4.1 finds a minimal non-linear plan that solves the problem, otherwise it fails. 0

The main reason that the algorithm can be so simple is that the set of action types is single-valued. This gives as a result that any action affecting a certain feature is either ordered before or after all actions defining this feature in their prevail-conditions. In other words, all ac­ tions defining a certain feature in their prevail-conditions can share action sequences achieving this value and as­ suring the final value. This is also the reason that no plan contains more than two actions of each type.

It can also be proven that the plan returned by the algorithm is maximally parallel.

Theorem 4.2 Algorithm 4.1 can be implemented to run in O(m 3 n 3 ) time using O(m 2 n 2 ) space where m = IMI and n = maxseM jS,j . 0

Both complexity figures can be reduced by more de­ tailed analysis of the size of 1i, the difference in domain sizes, and other factors. It should also be noted that the only data structure requiring more than 0( mn) space is the output data, and that we are not likely to be inter­ ested in the transitive closure in practical applications.

The main explanation for the complexity result is that the set of action types is post-unique and single-valued. Post-uniqueness implies that there is never any choice of which action type to use. Single-valuedness implies, as was mentioned above, that no plan contains more than two actions of each type, which thus bounds the number of iterations of the main while loop.

5 Example

This section presents an example that fits in the SAS­ PUS class. The example is a much simplified version of a LEG0 1 car factory which is used for undergraduate laborations in sequential control at Linkoping University [Stromberg, 1990j. The task is to assemble a LEGO car from pre-assembled parts as shown in figure 1.

We represent the problem using three features defined as follows:

s[1] : 1: Chassis in chassis storage, 2: Chassis at work­ station

s[2) : 1: Top in top storage, 2: Top at workstation, 3: Top on chassis

s[3] : 1: Wheels in wheel storage, 2: Wheels at worksta­ tion, 3: Wheels on chassis

Obviously, M = {1, 2, 3} and states are written as (s[1), s[2], s[3)}. We assume that the set 1i consists of the action types in table 1, and that the set A is { a1, ... , a12} where ai and ai+6 are of type hi for 1 ~ i ~ 6.

1 LEGO is a trademark of the LEGO Group.

We also assume that the initial state is s0 = {1, 1, 1}, all parts in storage, and the final state iss*= (1,3,3}, an assembled car in the chassis storage.

The algorithm first calls BuildChain once for each i E M to change s0 [a1 into s*[al BuildChain finds the empty sequence for feature 1, and the sequences as,a4 and a5,a6 for features 2 and 3, respectively. Now, A= {a1,a2,a7, ... ,a12}, D = T = {as,a4, a5, a6} and r consists of a2ra4 and a5ra6.

The actions in T, plus those added toT during the fol­ lowing process, are removed one at a time and processed by the while loop. as and a5 fall straight through the loop body since their prevail-conditions are trivially sat­ isfied. The prevail-condition of a4 is not satisfied in the initial state, and there are no actions in D providing the prevail-condition of a4. BuildChain is thus called, and it returns the action a1 which changes the 1st feature to satisfy the prevail-condition of a4 · Similarly, BuildChain finds the action a2 which assures the desired final value of this feature. Both these actions are inserted into D and T, and a1ra4 and a4ra2 are inserted into r. The action a6 has the same prevail-condition as a4 , so there are already actions, namely a1 and a2 , in D that provide its prevail-condition and assures the final value of the 1st feature. No actions are inserted into D, but r is extended with a1ra6 and a6ra2. The actions a1 and a2 are also removed from T, but their prevail-conditions are trivially satisfied.

The algorithm then computes the transitive closure of r, and, since r is anti-reflexive, it succeeds and returns the plan (D,r}, where Dis {a1, ... ,a6} and r is as de­ picted in figure 2.

6 Discussion

The restriction that 1i be unary is serious for planning problems where two or more features can change simul­ taneously, but it is not always the same combinations of features that change simultaneously. Allowing non­ binary domains does not help much in this case. Al­ though one could represent several feature domains as one multi-valued feature, this would most likely violate the restrictions on action types in the SAS class. Post­ uniqueness need not be a very limiting restriction for applications where there is little or no choice what plan to use, and where the size of the problem is the main difficulty when planning. However, for problems where 1i is non-unary or not single-valued, the major prob­ lem can be to choose between several different ways of achieving the goal. In this case, it will usually be impos­ sible to make a post-unique formalization of the prob­ lem. The most serious restriction for the majority of practical applications is, in our opinion, the restriction that 1i is single-valued. As an example, requiring single­ valuedness prevents us from modelling a problem where one action type requires a certain valve to be open and some other action type requires the same valve to be closed in their prevail-conditions.

The class one gets when relaxing the single-valuedness restriction is likely to be very interesting from a practical point of view. This class is conjectured sufficient for rep­ resenting some interesting classes of real-world problems in sequential control, a subfield of discrete event systems within control theory. Examples of application areas are process plants and automated manufacturing. A par­ ticularly interesting problem here is to restart a process after a break-down or an emergency stop. After such an event, the process may be in anyone of a very large num­ ber of states, and it is not realistic to have precompiled plans for how to get the process back to normal again from any such state. Restarting is usually done manually and often by trial-and-error, and it is thus an applica­ tion where automated planning is very relevant . It is interesting to note that such plans are complex because of their size, not because of complex actions. A process plant like a paper mill can have tens of thousands of sen­ sors and actuators, so the number of features can be very large. It is easy to realize that the complexity issues are very important in this kind of applications.

Since single-valuedness seems to be the most serious restriction, it would be natural to try to eliminate that restriction first. Unfortunately, it can be shown that the resulting class of problems is intractable. However, this is because the plans themselves are of exponential size in the worst case, and such plans are unlikely to be of practical interest. We believe that it is possible to re­ place single-valuedness with other restrictions that are fulfilled for many practical problems, but which reduces the complexity drastically, and we are currently investi­ gating such restrictions.

It would also be interesting to try to combine results along the line in this paper with the work on extended actions structures, allowing interdependent parallel ac­ tions or interval-valued features lBackstrom, 1988a, Backstrom, 1988b, Backstrom, 1988c].

7 Conclusion

We have identified a class of deterministic planning prob­ lems, the SAS-PUS class, which allows non-binary state variables and parallel actions. We have also presented a sound and complete polynomial time algorithm for find­ ing minimal plans in this class. This result provides a kind of lower bound for planning; at least this class of problems is tractable. Since the SAS-PUS class is an ex­ tension of the previously presented SAS-PUBS class, we have managed to take a step upwards in expressibility while retaining tractability.