RSD-TR-1 4-87 Subgoal Ordering and Goal Augmention for Heuristic Problem Solving Keki B. Irani Jie Cheng Department of Electrical Engineering and Computer Science The University of Michigan Ann Arbor, Michigan 48109 August 1987 Center for Research on Integrated Manufacturing Robot Systems Division College of Engineering The University of Michigan Ann Arbor, Michigan 48109-2110

RSD-TR- 14-87 TABLE OF CONTENTS 1. Introduction........................................ 1 2. Previous Subgoal Ordering Strategies........................................ 2 3. A Robot Planning Problem........................................ 4 4. A Systematic Approach to Subgoal Ordering............................ 7 5. Goal Augmentation.............................................. 12 6. Integration of Subgoal Ordering & Heuristic Estimation.......... 15 7. Example........................................................................................ 18 8. Summary...................................................................................... 23 References.............................................................................................. 23 i

Subgoal Ordering and Goal Augmentation for Heuristic Problem Solving Keki B. Irani Jie Cheng Division of Computer Science and Engineering Department of Electrical Engineering and Computer Science The University.of Michigan Ann Arbor, MI 48109, USA Tel: (313)-764-8517 E-Mail: KekiBIrani@um.cc.umich.edu ABSTRACT: In order to improve the performance of heuristic search for finding optimal solutions, two high level problem solving strategies, namely, subgoal ordering and goal augmentation, have been developed. The purpose of these two strategies is to make explicit the knowledge embedded in a general problem formulation which can be used to constrain the solution search space. These two strategies have been incorporated into a methodology, which we previously developed for automatically generating admissible search heuristics. The effectiveness of these strategies are demonstrated by the application to robot optimal task planning problems. paper type: full-paper track/topic: engineering/reasoning, planning subtopic: subgoal ordering; goal augmentation; automatic search heuristic generation; robot planning.

1 December, 1986 1. Introduction We have now augmented our previously published([IrY85]) general heuristic problem solving methodology by two systematic problem solving strategies, namely, problem subgoal ordering and problem goal augmentation. This paper reports on these two strategies. These strategies, however, are not dependent on our previous work and may be incorporated into any other problem solving methodology. Our goal with these two strategies is to make explicit the knowledge embedded in a problem formulation which can be used to conduct a solution search effectively. Problem subgoal ordering is an important strategy used to reduce problem space search. Many different subgoal ordering strategies have been reported in the past([Das77], [ErG821, [Sac77], [Sus75], [Tat75], [Wal81], [War74]). However, we present in this paper a novel approach for subgoal ordering. In contrast to the previously proposed approaches, our approach is to preorder the problem subgoals correctly and systematically by efficiently reasoning on the problem formulation. The result of ordering is then imposed on the search control to constrain the search space. Goal augmentation is an approach to systematically discover the goal information which is not explicitly represented but which can be inferred from the given problem formulation. The augmentation reduces ambiguity and enables more accurate estimation of the search heuristic. Our research on problem subgoal ordering and goal augmentation are both parts of the effort devoted to developing a general heuristic problem solving methodology. Previously, we achieved a method for systematically modeling problems and automatically generating admissible search heuristics for the A'-like best-first search(see [IrY853, [IrY86'). Now, the subgoal ordering and the goal augmentation strategies have been

2 December, 1986 integrated with the search heuristic generation to constrain search by improving the tightness of the heuristic while still preserving its admissibility and monotonicity. The rest of the paper is organized in the following way. In section 2, the earlier problem subgoal ordering strategies are reviewed. In section 3, a simple robot planning problem is introduced to illustrate the ideas. The subgoal ordering problem is discussed in section 4 while section 5 introduces the principles and procedures for goal augmentation. Section 6 reports the work on the integration of the aforementioned problem solving strategies with the search heuristics automatic generation. An example illustrating the power of the two stratgies is given in section 7. A summary is given in the last section. 2. Previous Subgoal Ordering Strategies Subgoal ordering has been employed in many early problem solving systems. GPS[ErN69] was the earliest to apply the subgoal ordering strategy. Subgoals are arranged as row headings in the "Table of Connection". The system waits to achieve the subgoal heading at a certain row until all the subgoal headings at the higher rows are achieved. A total ordering is thus imposed on the problem subgoals. In ordering problem subgoals this way, one has to be sure that achieving a new subgoal does not violate all the previously achieved subgoals. Originally, the subgoal headings were determined and ordered by the users. Ernst et al.[ErG82] later developed a procedure DGBS to mechanize this approach. Although DGBS correctly generates subgoal ordering for several problems such as the Fool's disk, Tower of Hanoi, etc., this approach cannot always guarantee correct ordering of the problem subgoals. For example, when the superfluous operator constraint is violated, and the table of connection is in a diagonal form, the system is not able to judge the correct

3 December, 1986 order of subgoals. Another problem with DGBS is that in constructing a table of connection, it must initially consider all the problem operator instances, instead of just the problem operator schemes as usually specified. This may cause DGBS to be computationally intractable when encountering a problem with small number of operator schemes but large number of operator instances. Some systems, such as HACKER [Sus75], INTERPLAN[Tat75j, WARPLAN[War741, order subgoals arbitrarily and then perform destructive reordering in the case that a protection constraint violation is detected. Waldinger[Wal8ll suggests a goal regression strategy which amounts to a constructive subgoal reordering. All these strategies make over commitment to subgoal ordering. In NOAH[Sac77], on the other hand, least commitment is made towards subgoal ordering. Subgoals are attempted in parallel unless sequential order constraints are imposed on them by the problem dependent knowledge in the SOUP code. Several critics are then applied to detect and handle interactions among subgoals or to find and eliminate redundancies. Another approach is the combination of sequential and parallel methods. In this approach, a plan is expanded by choosing a subgoal to be achieved which least interferes with the existing partial solution[Das77]. The subgoal ordering strategies of these systems either make too strong an initial commitment to subgoal ordering without making use of the knowledge of the intersubgoal constraints at all, or make a commitment to ordering too late. The former results in too much backtracking while the latter results in much redundancy as well as conflicts in partial problem solutions. Consequently, these strategies, do not effectively reduce search effort. Unlike these methods, the method of ordering subgoals that we pro

4 December, 1986 pose is based on actively detecting the inherent constraints among problem subgoals. 3. A Robot Planning Problem In this section, we introduce a robot navigation planning problem. The goal of the problem can be stated as follows: The Robot is to move from room1 to room4 while boxz is to be pushed from rooml into room6. The initial state and the goal state of the problem are depicted in Figure 1. In this problem, there are three pertinent problem objects, namely, Robot, boxz and boX2. A state of this problem has two aspects. One is that of an object being in a certain room and the other is that of an object being next to other objects. In order to represent the status of the problem objects in a state, we define the functions INROOM and NEXTTO. Each function takes a problem object and a state as two arguments and returns a value to indicate the corresponding status of the problem object in that state. Assume obj is an object and s is a state. Then INROOM(obj,s) gives a room identifier indicating in which room the object is located in the state s. NEXTTO(obj,s) returns a set of objects whose positions are next to obj in the state s. The legal actions in this planning problem are modeled as rules. The rules use the IF <precondition> THEN <postcondition> format. The precondition specifies what must be true for the rule to be applicable. The postcondition specifies the effects of the application of a rule. s1 and 82 are used to represent the states before and after the application of a rule. We assume that if the postcondition part of a rule does not contain the status of an object with respect to a certain problem aspect, then that status of the object is unaffected by the rule. The rules for our problem are given below:

6 December, 1988 room 3 room 2 room1 rom 3 room2 room 1 room 4 room 5 room 6 room 4 room 5 room 6 (a) I i (b) robot box 1 box 2 Figure 1. A Robot Planning Problem (a). Initial state (b). A goal state RI GOTO(bz'): F: INR M0f (Robot,a 1)=lNROOM(bz,s ) THEN: [ V by E({ bozi,boz2}-{ b })(NVEXTTO(by,J2)=iVEXTTO(by,al)-{Robot })] A (,VEXTTO (Robot,32) (b2 }) A (NVErTTO (b,2)=(( robot }UNEXTTO(bx,sa))) R2 GOTHROUGH(rz,ry): IF: (NlROOM(Robot,s )= r) A (COvNNECTED (n,ry)) THEN: (LVROOM.(Robot,2)=ry=) A(.rEXTTO(Robot,2)={}) A ( V by E{ bo 1,box2}(NEXTTO(by,,2)=NEXTTO(by,s,)-{Robot })) R3 PUSHTHROUGH(bz,r,ry): IF: (NVEXTTO(Robot,s )={bz}) /\^IVROO.M(Robot,s)=r) A (IVNROOM,(bz s)=rz) A CONNECTED (rz,ry) THEN: (INROOM(Robot.a2)= ry) rINROOMV(bz,2)=ry) A ( V by=({0box,boX2}-{ b})(NE.YTTO(by,J2)=NVEXrTTO(by,Jl)-{Robot,bz })) A (NVEXTTO (Robot 2)={ bx }) A (EYTTO (bx,s2)={ robot }) 6 bz(or by) xad rz(or ry) are the variables which represent a bo: and a room respectively.' We are ass.mnig that in a state the robot can be near one box only, while a box can be near both;he.obot and the other box.

S December, 1986 The initial state ji, is given by (INROOM(Robot,J, )= room 1) /\INROOM( boz,,, )= room i) /AINROOM( boz 2,.n )=room2) 1ANEXTTO (Robot,J, )=({) NEXTTO (bo 8jn)j={})) /1NEXTTO(boz2,i, )= {}) The goal state 8G of the problem is specified by the following formula, called the goal condition formula: (INROOM(bo l,s )= roome,) /INR OOM(Robot,a )= room 4) Although this problem appears to be very simple, a heuristic state space search can be very inefficient. We tried to use the automatically generated admissible heuristic function([IrY85]) to control the search in solving the problem. The search tree generated is depicted in Figure 2. For this problem, 78 nodes are produced and 35 nodes are expanded for deriving an optimal solution with length of 6 rules. On tracing the search tree generated in the problem solving, we find that the heuristic prefers to move the robot directly towards its own goal rather than moving the robot to boxl and then pushing boxl into room5. This is caused by the fact that the difference in the locations of the robot in any non-goal state and the goal state always dominates that for the boxl. The inherent ordering constraints between the two problem subgoals are not recognized and used. Consequently, the robot is misled into going into room4 directly. It is not until the robot arrives at room4 that the task of moving the boxz is noticed. The ineffectiveness of the heuristic in this problem is due to the lack of knowledge about the ordering constraints among the subgoals. This motivates us to develop a systematic subgoal ordering strategy and to incorporate it into the automatic heuristic generation.

7 December, 1986 4. A Systematic Approach to Subgoal Ordering If a problem goal can be represented by a predicate formula in a conjunctive normal form, then we can conceive every conjunct as a problem subgoal. There are usually interactions between subgoals which determine the natural order of achieving them in solving a problem. Many types of constraints may exist among problem subgoals. We use only one type of constraint to order subgoals. However, we mention two more types of constraints below to intuitively motivate the third type of constraint which we use for ordering subgoals. Actually, the third type of constraint is a conjunction of the first two. (1). A subgoal 92 cannot be achieved before a subgoal 91 in any problem solution. There could be two possible situations. One is when g92 is satisfied first and the precondition of achieving g1 cannot be established without violating 92. The other is if 92 is satisfied first then any rule which achieves gl will force the violation of 92. The subgoal ordering constraints in our robot planning problem is an instance of the first situation. If we achieve the subgoal for the robot first, then when we turn to achieve the subgoal for box1, we will have to retract the established subgoal for the robot. An example for the second situation is the following. Suppose our goal is to have clothes washed and dried. The actions we can use are'wash clothes in a washer' and'dry clothes in a dryer'. If we achieve the'dry' subgoal first, then although we can still'wash clothes in a washer' to satisfy the other subgoal, the'dry' subgoal would be wiped out because the clothes become wet after washing. (2). Subgoals g1 and g2 cannot be achieved simultaneously by the application of a single rule. For example, in our robot planning problem, the robot cannot get into room4

8 December, 1986 while the bozx is pushed into room8. (3). A subgoal g1 must be achieved before a subgoal g2 in any problem solution in which both are satisfied. As mentioned before, this constraint is actually a conjunction of the constraints (1) and (2) and it is this constraint which is used in ordering problem subgoals. These three subgoal ordering constraints are intuitively clear and practically useful. However, it is not intuitively clear how we can systematically detect these constraints from a problem formulation. In order to automate the process of detecting these kinds of constraints from the basic problem formulation and to order problem subgoals systematically, we have developed relations and procedures. In the following, the proposed approach and the results are presented. First we introduce some notations: 3G represents the goal condition formula which is a ground predicate formula specifying the desired state of affair for a problem. gi represents a subgoal condition formula which is a conjunct in the goal condition formula. SG is the set of all subgoal condition formulas of G. *Sg, is a subset the problem states in which the condition gi holds. *Rk(s1) is used to denote the resulting state of the application of the rule Rk to the state s1 in which Rk is applicable. *preck and postk are the precondition formulas and postcondition formulas for the rule Rk respectively. *problem solution path: a sequence of states (sl,,...sn) such that s1 is an initial state, s, is a goal state, and for every state si(l<i<n), there is a rule which can transform si into si,+1. A partial problem solution path in a path P=(Sls2s...S, ) is a subsequence (s1,s 2...Sp) such that p < n.

9 December, 1986 We now define a binary relation over SG. A theorem is then provided which relates this relation to the type-3 constraint. Definition: "<" is a binary relation over SG. g, <g iff V k V s[ ((R,(s)ESg, ) A(sESpct)) -sES1,] g, < Ky means that for any rule in the problem, if the rule can transform a state, say 8, to a new state in which both yg and gi are true, then s must satisfy gi. The relation R. appears to be complicated because quantifiers are used over the rules and the states. However, in constructing this relation, only pattern matching, variable binding and easy evaluations are needed. A procedure called SOC(Subgoal Ordering Constraints) has been developed for constructing R.. A loose upper bound for the complexity of this procedure is (m Xn)2X k, where m, n, and k are the cardinalities of the set of problem objects, set of problem aspects and set of problem rule schemes, respectively. In the following, we give two definitions and then give a theorem which relates the relation R. to the type-3 ordering constraint among problem subgoals. Definition:., precedes g; in a problem solution path P iff there exists a partial solution path (s81s2,...,8p) in P which satisfies: (SpE Sg /) A 3 k((lIk<p) A(SkESg) AV A((k<h<p)-(s^ES. /gj))). Definition: g9 and g, are said both achieved in a problem solution path P iff there is a partial solution path (ss,82,...,sp) in P such that'In later discussions, the notations < and R, will be used interchangably.

10 December, 1988 (sES, k/) A V k((l<k<p)-85kES,, Vy, ) Now, we present the theorem which links the relation R. with the type-3 subgoal constraint. The proof is omitted. In the theorem, we assume that the two subgoals g, and gj are not both satisfied in the initial state. Theorem: Let 9g and gj be two subgoal condition formulas. g, <gj if g, precedes gj in any problem solution in which both subgoals are achieved. By this theorem, it is clear that if gi <9j, we have to achieve gi before achieving g9 in any problem solution. Although the relation R. is itself not transitive, for a given problem, a partial ordering of subgoals can be created using this relation. A procedure called GOAL ORDER has been developed for that purpose. Every subgoal is assigned a rank by the procedure. All subgoals of a certain rank must be achieved before a subgoal of any higher rank can be achieved. As the example below will show, it is not necessary that if gi <gi, then gi has a lower rank than that of gj. However, in that case, the rank of gi is at least as high as that of gO. A loose upper bound for the complexity of the procedure GOAL_ORDER is (m X n)31og(m X n), where m and n are the cardinalities of the set of problem objects and the set of problem aspects, respectively. With the ranked subgoals, we can construct a goal sequence G =G1,G2,...,G", where Gi is called the i-th component goal of the goal sequence and is a conjunction of all those subgoal condition formulas with rank i. This sequence imposes constraints on the search for the solution path. It requires that G, always be achieved before Gj if i<j. It also ensures that in achieving GC, all the component goals G,'s(i<j) which have been achieved will be protected.

11 December, 1986 We illustrate the result of the procedure GOALORDER by giving the following example. Suppose we have a set of subgoals SG={gl,...,g^} and the relation R.-={<g596>, <g2,96>, <92,94>, <g6,91>, <g6,g4>, <919,3>}. The procedure GOAL_ORDER assigns ranks to the subgoals as follows: Rankl: g5, 92 Rank2: 96 Rank3: 1, 93, g4 g5 and g92 are ranked at the first level because no other subgoal can precede them and there is no ordering constraints among them. go alone is ranked at the second level because it has to be preceded by g5 and 92 and it must precede the rest of the subgoals. Finally, g1, 93 and g9 are ranked at the third level because they have to be preceded by all the other subgoals and they themselves can not be ordered further. Notice that since g1<93, 93 has to be preceded by all the subgoals preceding g1 although g3 may not relate with any one of them through R.. However, we cannot rank 93 at a different level than g1, because there exist no definite ordering constraints between g1 and 94, and g3 and g4. With this ordering result, we can get a goal sequence G =G1,G2,G3, where G1=g2 A/s G2=g6 G3=91 /\93 Ag4 In our robot planning example, there are two subgoals as follows: (1) INROOM(robot,scG)=room4, (2) INROOM(boxl,sc)=room6.

12 December, 1986 The relation R, is R. ={<(2),(1)>}. After applying the subgoal ordering algo< < rithm, the subgoals are ranked into two levels and the original problem goal is transformed into the goal sequence G =G1,G2, where G1 is the same as the subgoal (2) and G2 is the same as the subgoal (1). This ordering complies with the constraints inherent in the problem specifications. Unlike NOAH which makes least commitment, the approach described in this section represents an undercommitment to the ordering of problem subgoals, which means that subgoals are always arranged in a correct order, although the ordering may not be complete. Therefore, the ordering results can be used to guide the search and never needs to be retracted. 5. Goal Augmentation In a problem formulation, goals are often not specified completely in the sense that many things are left as "don't care". Therefore, more than one state can be a candidate goal state. However, as far as the optimality is concerned, only some of them can actually qualify to be the goal states. For the robot planning configuration in our example, for instance, assume the goal is simply that INROOM(boxz)=room6. It seems that the Robot can be anywhere in the goal state. However, if an optimal path is to be achieved, three other conditions need to be also satisfied. These three conditions are (1) the Robot is in rooms, (2) the Robot is next to only the box1, and (3) no object is next to the boxz. The first condition and the third condition are the immediate consequences of achieving the given goal, namely, INROOM(bozl)= room6, while the second condition is a necessary precondition for

13 December, 1988 achieving the given goal and which is invariant over the rule that achieves the goal. This reasoning can be used to augment every component goal derived by the subgoal ordering. We have proved that for the goal with one component goal(and the proof can be extended to multiple component goals) that the goal augmentation has two properties. These properties are: (1) every state which satisfies the original component goal condition formula and which is on an optimal solution path, also satisfies the augmented goal condition formula, (2) the number of nodes expanded during the search for the optimal solution path with the the augmented component goal is no more than that with the original component goal. We do not present the theorems and proofs in this paper for space consideration. In the following, we give the algorithm for the augmentation of all component goals of a goal sequence. AUGMENT ( G, G,R): G G,,G2,...,G,, R is the set of problem rules. Define G, =9 /\A * * * /\Al.(1<l<n) Defme G'=Gi A G2\ * A G,. (0). If m is the largest index such that G1,...,G, are all already satisfied by si,, then Gl=-G for =l,...,m. For each G (m +1 < < n), do (1) to (6): (1). For each conjunct of GI, namely, g'(1 < i < ni), do (2) to (5): (2). AUG — FALSE; R =R. (3). For each R,ER', if 3 a(aES c.,\ ARi(J)ESGC), then AUG,.-post! (post] is post, with substitution for variables), R *=R -{R, } and do (4)-(5). (4). for each prec,9(the k-th conjunct of preC, with substitution), do the following: If precut

14 December, 1986 is not affected by the operator j, then AUGii,-AUGii /\prec/h. (5). AUG.-AUG, V AUGi (6). GC.- I /jA UGC V AUG2 V.. V AUG,,). Return. In the algorithm AUGMENT, step (0) finds the first component goal which is not already satisfied in the initial state. The algorithm achieves the augmentation of each component goal Gk mainly in steps (3)-(6). For every subgoal g, in the component goal Gk, every rule Ri is checked to see whether it is applicable in a state in which the subgoal gi is not satisfied, and whether its application to such a state can satisfy Gk and all those component goals which precede Gk in the goal sequence. If the rule Rj passes the test, then besides the component goal condition formula Gk, all its preconditions which are unaffected by the application of the rule and all its postconditions are true in the state resulting from the application of Ri. These preconditions and postconditions are conjuncted into AUGi. If more than one rule passes the test, then the conditions derived from different rules are disjuncted and stored in AUGi. The disjunctions of all the AUGi's is the total augmentation which is finally conjuncted with the corresponding component goal in the step(6). A loose upper bound of the complexity of the procedure A UGMENT is (m X n)2X k, where m, n, and k are the cardinalities of the set of problem objects, set of problem aspects and set of rules. Since usually only a few rules are related with each possible subgoal in a problem, the computation of the goal augmentation is often very efficient. We again use our robot planning problem to explain the algorithm. From the subgoal ordering, we derived a goal sequence G =G1,G2 with two component goals, namely, G-l=INROOM(bozl,scG-)=room6, and G2=INROOM(Robot,G2)=00room4. Since C1 has only one subgoal and that subgoal can only be achieved by R3, the

15 December, 1986 augmentation result is G =(INROOM(bozx,sGl)=roomo) /NINROOM(Robot,s8c)=room6) NANEXTTO (Robot as,)={ bozl) /NEXTTO (boxj,al)= {Robot }) ANEXTTO(boox,sc,)={ }) Although the component goal G2 also has only one subgoal, that subgoal can be achieved by applying either R2 or R3. Therefore, the augmentation result is G =(INROOM(Robot,s,)= room,) A\{[(NEXTTO(Robot,s8G)={ }) 1/Robot 0NEXTTO (box l,2,)) /AR obot NEXTTO (box 2,SG,))I V [(INROOM(bo2,sG,)=room0 ) /NEXTTO(box2,sG,)=(Robot }) A (NEXTTO (Robot,,)={(box}) /NEXTTO(boxl,sc,)={ })]} 6. Integration of Subgoal Ordering and Heuristic Estimation In our previous research, we proposed a methodology for determining a general and admissible heuristic function h(e,) for the best-first search for a problem solution(see [IrY85], [IrY86]). According to this methodology, for each state ec, h(es) returns an under-estimated minimum cost for the path from e. to the goal set. We can now show that the subgoal ordering constraints can be naturally incorporated into the heuristic estimation. The new heuristic estimation is tighter than the original one while the admissibility and monotonicity is still preserved. In this section, we first briefly explain the original heuristic function and then introduce the integration of subgoal ordering with the heuristic estimation. Properties of the new heuristic estimation are then presented.

16 December, 1986 The original heuristic function h(es) is derived as follows: The problem is first decomposed object-wise and parallelly transformed into k simplified problems, where k is the number of problem objects whose status in the state ec is different from that in the goal state. Each simplified problem contains only one object in its problem space, in goals and in operators. The specifications concerning other objects are simply suppressed. The minimum cost for the optimal path in each simplified problem is then easily derived by conducting an exhaustive search. Although the derived cost in any simplified problem can be taken as the heuristic for the original problem and this heuristic is both admissible and monotonic, further derivations are made to get a tighter heuristic estimation. Three functions are evaluated. The first gives the maximum value of all the minimum costs for solving the simplified problems. The second is the sum of all the minimum costs divided by the maximum number of objects affected by one operator in the original problem model. The third is the same as the second except that the objects which are affected by all operators are excluded from consideration. The maximum of the three computation results is taken to be the final value of h (e:) for the state e. The search heuristic described above assures the admissibility and monotonicity. However, as has been demonstrated, it may not be effective in guiding search for some of the problems. The heuristic does not incorporate the knowledge of interactions among problem subgoals. Therefore it sometimes leads search to achieve subgoals in a roundabout order and consequently the search becomes very inefficient. We now introduce a new heuristic function which incorporates the subgoal ordering knowledge. We denote the component goal sequence generated by subgoal ordering to be Gi,G2,...,G^, the sequence after the augmentation to be G,G2,..., Gm, and finally

17 December, 1986 we denote the goal sequence for heuristic estimation to be m-l G[,G2,.,G' —G-G2 AG1,.* * * A... G,, G,) In the search process for the problem solution, for any state e being evaluated, we define an effective goal subsequence G, which is the remaining sequence of component goals to be fulfilled. Formally, G, -= GG,, l,.. I I Gm iff V i((l<i<iz)-*eESc,) AezSGc In the following, we informally introduce the new heuristic function. When a state, say e., is to be evaluated, the problem is decomposed into k simplified problems as before where k is the number of problem objects which do not have the same status in e, and in all the component goals of the effective goal subsequence G. In the simplified problem for an object a, the effective goal subsequence is relaxed such that only the specification about the status of a is retained in each of the elements of the sequence. The cost of the optimal solution path passing through each of the elements of this simplified sequence is then determined. The final value of the new heuristic Ah(e,) is the maximum of the three values computed in the same way as before. The properties of the heuristic function h+(e2) are presented in the following two theorems. Theorem: The heuristic function h+(e.) as given above is admissible and monotonic. Theorem: The heuristic function hA(e,) as given above is tighter than the original heuristic estimation hA(e,). With the new heuristic function, the search becomes very efficient. As can be seen from Figure 2(a), without the subgoal ordering and goal augmentation, the search goes

18 December, 1988 78 nodes generated 13 nodes generated 35 nodes expanded 6 nodes expanded (a) (b) Figure 2. Comparison of Search Tree Diagrams (a). without subgoal ordering and goal augmention (b). with subgoal ordering and goal augmentation astray for a long time before it touches the right path. For this problem, 78 nodes are produced and 35 nodes are expanded for deriving an optimal solution with length of 6 rules. However, as shown by Figure 2(b), with the subgoal ordering incorporated, the heuristic value discriminates against the misleading path at the very outset. The search tree generated for this problem contains only 13 nodes of which, only 6 nodes are expanded. This demonstrates the advantage of the subgoal ordering when it is incorporated into heuristic estimation. 7. Example In this section, we give an example to illustrate the application of the subgoal ordering, goal augmentation and the integration of these two strategies with the admissible

19 December, 1986 heuristic generation. The example problem is again a robot navigation planning problem. The problem is both described in Figure 3 and specified by the problem model formalism in the following. The results of applying each strategy are shown and finally, the performance of the search with using and without using the subgoal ordering and the goal augmentation are compared. There are 7 problem objects involved in this problem, one Robot, one box and 5 doors. The problem has three aspects. Two of them are the same as in the previous example and we still use the functions INROOM and NEXTTO to represent them. A new problem aspect is the status of a door, for which we choose to use the function D-STATE to represent. D-STATE takes a door object and a state as its arguments and returns the status of that door in that state. The value of the door status is either'open' or'closed'. room 5 room 3 room 1 room 5 room 3 room 1 room 6 room 4 room 2 room 6 room 4 room 2 (a) * Z(b) robot box Figure 3. A Robot Planning Example (a). An initial state (2). A goal state

20 December, 1986 There are 6 pertinent actions that are modeled as rules. The first rule is for the Robot to walk to a box if they are in the same room. The second rule is for the Robot to walk to a door if the Robot is in one of the rooms connected by that door. The third rule is for the Robot to go from one room to another if these two rooms are connected by a door and the door is open. The fourth rule is for the Robot to push a box from one room to the other. For this rule to be applicable, besides satisfying the preconditions for action 3, the Robot must also be near the box to be pushed. The last two rules are opening and closing a door by the Robot which stands next to that door. It is assumed that the cost of applying each rule is a constant. Therefore, a best solution is one composed of least number of rules. The rules are specified as follows: Rl GOTO(bt*): IF: INROOM (Robot, 1)=INROOM(bx,j1) THEN: (V dzE{door13,...,door4}(NEXTTO(dz,2)={ })) A (NEXTTO (Robot,82)= { b})) A (NEXTTO(bz,'2)={robot}) R2 GOTO(dz): IF: 3 rx,ry [(INROOM(Robot,8 1)=rz) /1ACONNECT(dz,rx,ry))] THEN: ( V objE({box,doorl3,...,door4}-{dx})(NEXTTO(obj,82)={ }) /A (NEXTTO (Robot,2)={ dx }) /NNEXTTO (dx,s8)=(Robot}) R3 GOTHROUGH(dz,ry): IF: 3 rz [(INROOM(Robot, i)= rz) A (CONNECTED (dz,rz,ry ))] NDSTA TE (dz,8l)=opn ) THEN: (INROOM(Robot,2)=ry) A ( V obj(NEXTTO (obj, 2)={})) R4 PUSHTHROUGH(bx,dx,ry ): * bz(or b), r(or ry) and dx(or dy) are the variables which represent a bo. a room and a door respectively. X We are assuming that in any state, the robot cannot be near both a door and a box and the box is never near any door.

21 December, 1986 IF: (NEXTTO (Robot,,s)={bz}) /'A 3 rz[(INROOM(Robot,i)=INROOM(b6, i)=rz)) A CONNECTED (dz,rz,ry)] /D STA TE (dx,J i)=opcn) THEN: (INROOM(Robot,s2)=ry) A(INROOM(bz,s2)= ry) A ( V dzE{doorls,...,doorA}(NEXTTO(dz,52)={ }) A (NEXTTO (Robot,s2)={ b }) A (NEXTTO (bz,2)={ robot }) Rs OPEN(dz): IF: (DSTA TE(dz,8 l)=closed) A (NEXTTO (robot,s)={dz }) A (,3 rtr [(INROOM(Robot,s,)=rz) A CONNECT(d,z,r y)]) THEN: DSTA TE(dz,82)=open R6 CLOSE(dz): IF: (DSTA TE(dz,8 )=open ) A (NEXTTO(robot,se)={dz}) 3 rz,ry [(INROOM(Robot,i)=r) A CONNECT(dxz,,ry)]) THEN: DSTATE (dz, 2)=closed The initial state si, is specified as follows: (INROOM(Robot,si, )-=room3) N/INROOM(boz,si, )=room 4) A (DSTATE(door13,s,,)=open) A * * D / SDTATE(door46,si, )=open) The problem goal state sG is specified by the goal condition formula G=g A92 A93 A94, where g 1:(INROOM(Robot,G )= room 2), g2:(INR OOM( bo,G )= room), g3:(D STA TE (door 35,G )= closed), g 4:(DSTA TE (door 24,s )= closed). When trying to solve this problem by heuristic search without using the subgoal ordering and goal augmentation, we find that the efficiency is very poor. However, there exist inherent ordering constraints among the problem subgoals and there also exists

22 December, 1986 implicit goal state information in this problem formulation. By applying the subgoal ordering and the goal augmentation strategies, we can detect and make use of this information to enable a tighter search heuristic and to make the search efficient. Using the procedure SOC, the relation R. is constructed as follows: R* ={<9194>,<9291>,<<9g391>} Applying the procedure GOAL ORDER to the set of problem subgoals with the relation R., we get a goal sequence G =G1,G2,G3, where G1=g2 A93, G2=91 and G3=9g4 The procedure AUGMENT is then applied to that goal sequence and the following results are derived. To make it easy to understand, we have simplified the augmentation results. G =(INROOM(box,sGc)=room ) ADSTA TE (door 35s,s)= closed) /\ [(D STA TE(door46,scG)=open) /VINROOM(Robot,sG)=room8) A (NEXTTO(Robot,.G)={bo }) /NNEXTTO (box,sGl)={Robot }) A (V dx(NEXTTO(dxs,)={ })] V [(INROOM(Robot,sG)E{room3,roomS}) A(NEXTTO(Robot,SG,)={d35} A NEXTTO(door35,c,)={Robot } A V (dxz door35)(NEXTTO(dx,SG1)={ } G =(INROOM(Robot,SG,)=room2) /(DSTATE ( door24,sG,)open) A ( V obj(NEXTTO(obj,G,)={ }) G =(DSTA TE (door 2, sG,)=closed) /IINROOM(Robot,sG,)=room2) A (NEXTTO (Robot sc,)=(door,},) /ANEXTTO (door24,sG,)={Robot })

23 December, 1986 Finally, we incorporate the above results into the heuristic generation and conduct the heuristic search to solve for the optimal solution path. The effectiveness of the search heuristic is greatly improved. Using the original methodology without subgoal ordering and goal augmentation, 321 nodes are generated and 138 nodes expanded. However, with the new methodology, 140 nodes are generated and 60 nodes expanded. 8. Summary This paper is a contribution to the development of a general methodology for automated heuristic problem solving. We have presented an improved procedure for subgoal ordering and a novel procedure for goal augmentation. We then outline a procedure to integrate these two strategies with our previous methodology of automatic generation of admissible search heuristic. The combined package is a new methodology of general problem solving. REFERENCES [Das77] Dawson, C., and Siklossy, L., "The Role of Preprocessing in Problem Solving Systems", Proc. IJCAI 5, Cambridge, Mass., August 1977. [ErG82] Ernst, G. W., and Goldstein, M. M., "Mechanical Discovery of Classes of Problem Solving Strategies", JACM, Vol. 29, No.1, January 1982. pp. 1-23. [ErN69] Ernst, G. W., and Newell, A., GPS: A Case Study in Generality and Problem Solving. ACM Monograph Series. Academic Press, New York, 1969. [IrY85] Irani, K.B and Yoo, Suk I., "Problem Solving: A Methodology for Modeling and Generating Heuristics". Second International Conference on Artificial Intelligence Applications., December 1985. [IrY86] Irani, K.B. and Yoo, S. I., "A Methodology for Solving Problems: Problem Modeling and Automatic Heuristic Generation". Submitted to IEEE Transactions on PAMI, 1986. [Sac77] Sacerdoti, E. D., "A Structure for Plans and Behavior", Elsevier NorthHolland, New York, 1977. [Sus75] Sussman, G. J., A Computer Model of Skill Acquisition, New York: American Elsevier. 1975.

24 December, 1986 [Tat75] Tate, A., "Interacting Goals and Their Use", The proceeding of the 4th IJCAI, 1975, pp. 215-218. [Wal81] Waldinger, R., "Achieving Several Goals Simultaneously". Readings in Al. pp. 250-271. (1981). [War74] Warren, David H.D., "WARPLAN: A System for Generating Plans", Department of Computational Logic Memo 76, U. of Edinburgh, July, 1974.