Subgoal Ordering and Goal Augmentation for Heuristic Problem Solving

Subgoal Ordering and Goal Augmentation for Heuristic Problem Solving

Keki B. Irani and Jie Cheng

Robot Systems Division

Center for Research on Integrated Manufacturing Department of Electrical Engineering and Computer Science The University of Michigan, Ann Arbor, MI 48109-2122, USA

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 essence of these two strategies is to make explicit the knowledge embedded in a general prob­ lem 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 is demonstrated by the appli­ cation to robot optimal task planning problems.

1, Introduction

In previous papers ([IrY85], [IrY87]), we have presented a general heuristic problem solving methodology. Recently, this methodology is augmented by two systematic problem solving strategies, namely, problem subgoal ordering and goal augmentation. This paper reports on these two stra­ tegies.

Problem subgoal ordering is an important strategy used to reduce problem space search. Many different subgoal ord­ ering strategies have been reported before ([ErG82], [Sus75], [Tat75], [Wal81], [Sac77], [Das77]). However, in this paper we present a noyel approach to subgoal ordering. In contrast to the previously proposed approaches, our approach is to preorder the problem subgoals systematically by reasoning on the problem formulation. The result of ordering is then imposed on the search control to constrain the search space.

Goal augmentation is another problem solving strategy which systematically discovers goal information that is not explicitly represented but can be inferred from a given prob­ lem formulation. Augmentation can often reduce th .. ambiguity of the specified problem solving goals which enables more accurate estimation of the search heuristic.

Our research on problem subgoal ordering and goal augmentation are both part of an effort to develop a general heuristic problem solving methodology. Previously, we achieved methods for systematically modeling problems and automatically generating admissible heuristics for A *-like best-first search algorithms (see [IrY85], [IrY87]). Currently, the subgoal ordering and the goal augmentation strategies have been integrated with the heuristic generation to con­ strain search through improving the tightness of the heuristic estimation.

· This work w .. supported in part by AFOSR under contran FJ3613-83-C-> IOS and 10 part by SRC under contract l!d-07-083 .

The rest of the paper is organized in the following way. A simple robot planning problem is introduced in section 2. Earlier problem subgoal ordering strategies are briefly reviewed in section 3. Our approaches to subgoal ordering and to goal augmentation are then presented in section 4 and section 5 respectively. The integration of these problem solving approaches with the automatic search-heuristic gen­ eration is reported in section 6. A complete example is given in section 7 and the paper is finally summarized in section 8.

2. A Robot Planning Problem

To illustrate our ideas, we introduce a robot navigation planning problem in this section. In the problem, there are three problem objects, one robqt and two boxes (see Figure 1). The robot is the only active agent which can change its own position as well as move other objects. The valid actions assumed in this problem setting are (l)the robot going to an object in the same room; (2)the robot going into a connected room; and (3)the robot pushing an adjacent box to a con­ nected room.

The problem's initial state and goal state are described in Figure 1. The solution to be found is an optimal sequence of actions for the robot to perform so that the initial state can be transformed into a goal state with the least possible number of actions. Using our formal problem model, this problem can be specified as follows:

1. Three problem objects: robot , boz 11 and boz 2;
2. Two problem attributes modeling relevant problem solv­ ing aspects, namely, the locations of problem objects in refer­ ence to the room configurations and the adjacency relations among problem objects;

• ( 3) Functions which take an object and a state as paramPt.er
• and return a value representing the status of the object in that state in certain aspects. This example uses two func­ tions, lnroom and Neztto. lnroom (obj ,, ) returns a room iden­ tifier indicating in which room the object is located in the state ', while Neztto (obj ,, ) returns a set of objects adjacent to obj in the state ';
• A goal formula specifying conditions which must be satis­ fied by any goal state,

1. An initial state, ';·,

(Inroom (Robot ,11· )=room1) 1\ (In room (bo:rh'i· )=room1)

1\ (In room (bo:r2,·1· )=room2) 1\ (Ntxtto (Robot ,·;.)={})

1\ (Nt:r:tto ( bo:ru·;. )={}) 1\ (Neztto ( bo:r2,·1· )={} );

1. A set of problem rules modeling valid actions, the rules use the IF <precondition> THEN <postcondition> for­ mat. The precondition specifies what must be true for the rule to be applicable. The postcondition specifies the effects of the application of a rule. · 1 and 1 2 are used to represent the states before and after the application of a rule. We assume that if the status of an object with respect to a cer­ tain problem aspect is not in the postcondition part of a rule, then it. is unaffected by the application of the rule.

R1 GOTO(b:r:·): IF: lnroom(Robot,·d=lnroom(b:r:,·d THEN: [ \:/ (by rfbz )(Neztto (by ,·2)=Ntxtto (by ,1 1)-{Robot})) 1\ (Next to (Robot ,1 2)={ b:r}) 1\ (Nt:z:tto ( b:r ,·2)=( {robot }UNt:rtto ( b:z: ,1 1))) R2 GOTHROUGH(r:r: ,ry ): IF: (lnroom(Robot,· 1)=rz) 1\ (Conntettd(rx,ry)) THEN: (lnroom (Robot ,· 2)=ry) 1\ (Neztto (Robot ,·2)={}) 1\ ( \:/ by(Nt:z:tto (by ,·2)=Nt:r:tto (bv ,· 1)-{Robot} )) Rs PUSHTHROUGH(b:r:,rx,ry): IF: (Nt:z:tto (Robot ,1 1)={ b:r }) 1\ (Inroom(Robot ,·!)=rz) 1\ (Inroom ( b:r ,1 1)=rz) 1\ Connecttd (r:r ,ry) THEN: (Inroom (Robot ,· 2)=ry) 1\ (In room (bz ,1 2)=ry) 1\ ( \:/ (by rfb:z: )(Ntztto (by ,·2)=Ntztto (by ,1 1)-{ Robot ,bz})) 1\ (Ntztto (Robot ,· 2)={ bz}) 1\ (Ntztto ( b:z: ,1 2)={ robot})

Although this problem appears to be simple, a heuristic state space search without subgoal ordering is very ineffi­ cient. To illustrate this, we use the automatically generated admissible heuristic function([lrY85]} to control the search in solving the problem. For this problem, 78 nodes are pro­ duced and 35 nodes are expanded for deriving an optimal solution with a length of 6 rules.

On tracing the search tree generated in solving this problem, we find that the generated problem heuristic prefers to move the robot directly towards its own goal rather than moving the robot to first push the boz 1 into room8· This is due to the fact that the difference in the loca­ tions of the robot in any non-goal state and the goal state always dominates the similar difference for the bo:r 1· The inherent ordering constraints between the two problem subgoals are not recognized and used in the heuristic estima­ tion. Consequently, the robot is misled into going into the room, directly. It is not until the robot arrives at room, that the task of moving the boz 1 is noticed.

· bz (or b11) and rz {or rr) are variabl~ which nn&e over ~ rs and rl)nm" retpectively.

The ineffectiveness of the heuristic in this problem is due to the lack of knowledge about subgoal ordering con­ straints and the incompleteness of the goal specification. This motivates us to develop a systematic subgoal ordering approach and a goal augmentation approach. These two approaches reveal implicit knowledge about a problem from its specification, and transform it into explicit problem con­ trol constraints to guide heuristic search.

3. Previous Subgoal Ordering Strategies

Subgoal ordering has been employed in many previous problem solving systems as a strategy for reducing search. These systems can be classified by the degree of commitment. they make towards subgoal ordering. which reflects how early a decision is made on ordering problem subgoals, and how bold a hypothesis is made on the subgoal ordering con­ straints with a given amount of information.

Among the early systems, CPS [Ern69] is the first to apply subgoal ordering to problem solving. In GPS, sub goals are arranged as the row headings in the Table of connection. The system does not start to achieve a subgoal heading for a certain row until all subgoals heading higher rows are achieved. A total ordering is thus imposed on all problem subgoals, which represents the highest possible commitment towards subgoal ordering. This ordering task needs to be carried out by a user.

Many other systems are also over-committed to subgoal ordering, although they operate in quite a different way from that of GPS. Systems like HACKER [Sus75], INTERPLAN [Tat75], WARPLAN [War74], first order subgoals arbitrarily and perform a destructive re-ordering in case a protection constraint violation is detected. Systems like STRIPS [FiN71] and ABSTRIPS [Sac74] achieve subgoals in the order they are given and backtrack if the given order fails. Walciinger's system [Wal81] proposes a goal regression strategy which amounts to "constructive subgoal re-ordering".

NOAH [Sac77J is a system which makes "least commit­ ment" towards subgoal ordering. It first attempts problem subgoals in parallel (unless a sequential order constraint is imposed beforehand in the "SOUP" code). Several "critics" are then applied to detect and handle interactions among subgoals or to find and eliminate redundancies.

Another distinctive approach is presented in [Das77], in which a subgoal is chosen to be achieved next if it least interferes with the subgoals already achieved.

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 inter-subgoal constraints at all, or make a commitment to the ordering too late. The former results in too much backtracking while the latter results in much redundancy as well as conflicts in par­ tial problem solutions. Consequently, these strategies do not reduce search as effectively as expected.

Ernst et al. [ErG82] developed a procedure, DGBS, to mechanize the CPS approach. DGBS represents a reasonable commitment towards problem subgoal ordering. It tries to detect inherent problem subgoal ordering constraints so that they can be put in order properly before the problem solving actually starts. However, DGBS is very inefficient in its con­ struction of the Table of connection. The procedure has to process all t he problem operator instances initially, instead of just considering problem operator schemes as usually given in a problem specification. This may cause DGBS to be computationally intractable when tackling a problem with a few operator schemes but a large number of operator instances. Another problem with DGBS is that it cannot guarantee a correct ordering. When the "superfluous opera­ tor constraint" is violated, and the table of connection is in a diagonal form, the system is unable to order subgoals properly.

The key weakness of all these previous subgoal ordering approaches is their inability to properly reveal and make use of the relationship between problem operator struct ures and problem subgoal orderings. As will be shown later, our research result presents an improvement on this issue over these approaches.

4. A Srstematic Approach to Subgoal Ordering

If a problem goal is represented by a predicate formula in a conjunctive normal form, then we can conceive every conjunct as a problem subgoal. There are usually interac­ tions between such subgoals which determine the natural order of achieving them in solving a problem and these interactions are called subgoal ordering constraints.

Many types of ordering constraints may exist among problem subgoals. We are mainly interested in one such type. However, we discuss two more types of constraints below to intuitively motivate the thi rd type of constraint, which we use for ordering subgoals.

• (1} A subgoal 92 cannot be achieved before a subgoal 91 in any problem solution. There could be two possible situa­ tions. One is when, if 92 is satisfied first, then all those rules which can achieve 91 will not be applicable unless 92 is des­ troyed. The other is when, if 92 is satisfied first, then any rule which can achieve 9 1 will force the violation of 92 as a side effect of that rule.

The subgoal ordering constraint in the robot planning example is an instanrP of t he first situation; if we achieve the subgoal for the robot first, then when we turn to achieve the subgoal for bo:z: 1, we will have to retract the established subgoal for the robot.

An example of 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 g 1 and 92 cannot be achieved simultaneously by the application of a single rule. For instance, in our robot planning example, the robot cannot get into room4 while the box 1 is pushed into room8·
• (3}. A subgoal g 1 must be achieved before a sub goal 92 in any problem solution in which both are satisfied. This con-

straint is actually a conjunction of the constraints ( 1) and (2}.

These three subgoal ordering constraints are intuitively clear . However, it is not intuitively clear how one can sys­ tematically detect these constraints from a problem formula­ tion. 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:

• ·G represents the goal condition formula which is a ground predicate formula specifying the desired state of affairs for a problem. g; represents a subgoal condition formula which is a conjunct in the goal condition formula. SG is the set of all sub goal condition formulas of G.
• ·Sg, is a subset of problem states satisfying g; .
• ·R~r. ( s) is used to denote the resulting state of the applica­ tion of the rule R 1r. to state s .
• ·preclr. and post1r. are ·the precondition formulas and postcondition formulas for the rule R~r. respectively.
• ·problem solution path: a sequence of states (s 1,s 2, ·. · ,sn) such that s 1 - is an initial state, sn is a goal state, and for every state s;(l ~ i < n ), there is a rule which can transforms; into si+l·
• ·a partial solution path in a problem solution path

P = ( s1,s2, ... ,sn) is a subsequence (s 1,s2, .. . ,sP) where p ~ n.

In order to explicitly represent the relation between the problem rule specifications and subgoal ordering constraints, we give the following definitions.

Definition: g; precedes gi in a problem solution path P iff there exists a partial solution path (s 1,s2, ... ,sp) in P which satisfies:

Definition: g; and gi are said to be both achieved in a problem solution path P iff there is a partial solution path (s 1,s2, ... ,sP) in P such that

. . Definition: "<" is a binary relation over SG. g; < gj iff

gi .( g 1 means that for any rule in the problem, if the rule can transform a state, say s, to a new state in which both g; and g 1 are true, then s must satisfy g;. .

The relation < appears to be complicated because of the quantifiers used. However, to construct <, only pattern matching and variable binding are needed. A procedure called SOC (Subgoal Ordering Constraints) has been developed to construct <. A loose upper bound for the com­ plexity of this procedure is ( m X n ) 2 X k, where m, n, and k are the cardinalities of the set of problem objects, the set of problem aspects and the set of rules, respectively.

Now, we present a theorem which links the relation < with the type-3 subgoal constraint. The proof is omitted. In the theorem, we assume that the subgoals 9; and 9; are not both satisfied in the initial state.

Theorem: Let 9; and 9; be two subgoal condition formulas. 9; <. 9; iff 9; precedes 9; in any problem solution in which both subgoals are achieved.

By this theorem, one can see that' if 9; < 9;, then 9; has to be achieved before 9; in any problem solution. Although the relation <. is itself not transitive for a given problem, a partial ordering of subgoals can be created using this rela­ tion. A procedure called GOAL_ORDER has been developed for this purpose. Every subgoal is assigned a rank by the procedure, and all subgoals of a certain rank must be achieved before a subgoal of any higher rank can be achieved. A loose upper bound for the complexity of the pro­ cedure GOAL_ORDER is ( m X n ) 3 1og( 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 a' = G1,G2, ... ,G. , where G; is called the i-th com­ ponent goal of the goal sequence and is a conjunction of all those sub goal condition formulas with rank i. This sequence imposes constraints on t he search for the solution path. It requires that G; be always achieved before G; if i < j.

We illustrate the result of the procedure GOAL_ORDER by giving the following example. Suppose we have a set of sub goals SG ={91, .. . ,96} and the relation

<={ < 96,96>, < 92,9s> , < 92,94>, < 9s.9t >, < 9s·9·>· < 9 1 ,9 3 > }. The procedure GOAL_ORDER will then assigns Rank 1 to 92 and g 5 , Rank2 to 96, and Rank3 to 9t· 93 and 94·

92 and 9 5 are ranked at the first level since ~o other subgoal can precede them and there are no ordermg con­ straints among them. 9 6 alone is ranked at the second level because it is preceded by 95 and 92 and it precedes the rest of the subgoals. Finally, 91, 93 and 9 4 are ranked at the third level because they are preceded by all the other subgoals and they themselves cannot be ordered further.

Notice that since 9t <. 93, 93 has to be preceded by all the subgoals preceding 9t even though 93 may not relate with

any one of them through <.. However, we cannot rank 93 at a different level than 9 1 , because there exist no definite ord­ ering constraints between 91 and 94, and 93 and 94·

Wi th the relation a' = G 1 ,G2,G3, where G3=91 (\ 93 !\ 9·· <, we get a G1=92 (\ 9&, goal sequence G2=96, and

In our robot planning example, the subgoals are:

1. lnroom (robot ,sa )=room4,
2. Inroom(box1,sa)=room6.

The relation <. is derived as { < (2),(1) > }. As a result of applying the subgoal ordering algorithm, the subgoals are ranked into two levels at:td the original goal is transformed into the goal sequence a: =G1,G2, where G1 is the subgoal (2) and G 2 is the subgoal (1). This ordering complies with the constraints inherent in problem specifications.

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 optimality is concerned, only some of them cari actually qualify to be goal states.

For the robot planning configuration in our example, for instance, assume the goal is simply that lnroom ( bozt)=room 6 · It appears that the Robot can bP anywhere in the goal state. However, if an optimal path is pursued, three other conditions also need to be satisfied. These conditions are (1) the Robot is in rooms, (2) the Robot is adjacent to only the box 1, and (3) no object is next to the box 2 · The first condition and the third condition are the immediate consequences of achieving the given goal, namely, Inroom( box 1 )=room6, while the second condition is a necessary precondition for achieving the. given goal and is invariant over the rule that achieves the goal.

This reasoning can be used to augment every com­ ponent goal derived by the subgoal ordering. We have pro­ ven two properties of goal augmentation. The properties are: (l) every state which satisfies the original component goal condition and which is on an optimal solution path, also satisfies the augmented goal condition, (2) the number of nodes expanded during the search for the optimal solution path with the augmented component goal is no more ~han that with the original component goal. Proofs are omttted for consideration of space. In the following, we give the algorithm for the augmentation of all component goals of a goal sequence.

AUGMENT( a' ,G',R):

• (0). If m is the largest index such that G1, ... ,Gm are all already satisfied by s;., then G,'=Gt for 1=1, ... ,m. For each G1(m+1$1$n), do (1) to (6):
• (1). For each conjunct of G1, namely, 9/(1 $ i $ n,), do (2) to (5):
• (2). AUG;+-FALSE ; R'=R.
• . For each R;ER ', if 3 s(sESPm; f\-gf (\ R;(s)ESa,), then AUG; . +-post' (postJ is post; with substitution for variabl~), R ';,R '-{R;} and do (4)-(5).
• For each precMthe k-th conjunct of prec; with substi­ tution), do the following: If precJk is not affected by the operator j, then AUG;; +-AUG;; (\ precfk·
• (5). AUG;+-AUG; V AUG;;
• . G,"+-G 1 (\ (AUG1 V AUG2 V · · · V AUG.,).
• . Return.

In this algorithm, 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 G 1 mainly in steps (3)-(6). For every subgoal g; in the com­ ponent goal G, , every ruleR; is checked to see whether it is applicable in a state in which the subgoal 9; is not satisfied, and whether its application to such a state can satisfy Gk and all those component goals preceding Gk in the goal sequence. If rule R i passes the test, then besides the com­ ponent goal condition formula G1 , 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 R;. These preconditions and postconditions are conjoined into AUG;;. If more than one rule passes the test, then the conditions derived from different rules are dis­ joined and stored in AUG; . The disjunction of aU the AUG; 's is the total augmentation which is finally conjoined with the component goal G1 in step (6). A loose upper bound of the complexity of the procedure AUGMENT is (mXn) 2 Xk, 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 rule schemes 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 illustrate the algorithm. From the subgoal ordering, we derived a goal sequence c' =G 1 ,G 2 with two component goals, namely,

Since G 1 has only one subgoal and that subgoal can only be achieved by R 3 , the augmentation result is

Although the component goal G2 also has only one subgoal, that sub goal can be achieved by applying either R 2 or R 3 · Therefore, the augmentation result is

8..__l_11tegration of Subgoal Ordering, Goal Augmentation and Heuristic Estimation

In our previous research, we proposed a methodology for determining a general and admissible heuristic function h(8) for best-first search (see [lrY85], [lrY87]). According to this methodology, for each state 8, h ( s) returns an under­ estimated minimum cost for the path from 8 to the goal set. In this section, we show that subgoal ordering and goal aug­ mentation can be naturally incorporated into heuristic esti­ mation. The new heuristic estimation is tighter than the ori­ ginal one while the admissibility and monotonicity is still preserved. We first explain the original heuristic function and then describe the integration of subgoal ordering, goal augmentation and heuristic estimation.

The original heuristic function h ( s) is derived as fol­ lows: The problem is first transformed into k simplified problems, where k is the number of problem objects whose status in the state 8 is different from that in the goal state. Each simplified problem contains only one object in its prob­ lem space, with all specifications concerning other objects suppressed. The minimum cost for the optimal path in each simplified problem is then either derived by conducting an exhaustive search in this small space, or simply retrieved from the store of previous derivation results.

Although the derived cost in any simplified problem can be taken as the heuristic for the original problem, further derivations are made to get a tighter heuristic esti­ mation. 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 any 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 ( 8) for the state 8 .

The search heuristic described above assures admissibil­ ity and monotonicity. However, the heuristic does not incor­ porate the knowledge of interactions among problem subgoals and is very sensitive to the completeness of the goal specification. In the following, we describe a a new heuristic function which incorporates subgoal ordering knowledge and goal augmentation.

We first denote the component goal sequence generated by subgoal ordering to be G11G2, ··· ,Gm, the sequence after the augmentation to be c; ,c; I ··· I �~, and the goal sequence for heuristic estimation to be

In the search process for the problem solution, for any state s being evaluated, we define an effective goal subse­ quence �~ which is the remaining sequence of component goals to be fulfilled relative to state s. Formally,

The new heuristic function can now be informally defined. When a state, say s, is to be evaluated, the prob­ lem is decomposed into k simplified problems as before, where k is the number of problem objects which do not have th~; same status in 8 and in all the component goals of the effective goal subsequence �~. 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 h +(8) .is the maximum of the three values computed in the same way as before.

The heuristic function h +( s) is also admissible and monotonic. Furthermore, it provides consistently tighter heuristic estimation than the original function h ( s ). The proof is omitted. With the new heuristic function,. the search becomes very efficient. As can be seen from Ftgure 2(a), for the problem given in Figure 1, without subgoal ord­ ering and goal augmentation the search can go astray for a long time before it touches the right path. For this proble~, 78 nodes are produced and 35 nodes are expanded for denv­ ing an optimal solution with length of 6 ~ules. However, as shown by Figure 2(b), with subgoal ordermg and ~oal aug­ mentaion, the heuristic value discriminates agamst the misleading path at the very outset. The search tree. gen­ erated for this problem contains only 13 nodes, of whtch 6 ··nrlP< are exoanded.

7_. Example

In this section, we give an example to illustrate the application of our proposed integrated problem solving approaches. This example is also a robot navigation plan­ ning problem. The problem is described in Figure 3 and specified by the problem model formalism. The results are shown for each stage and finally, the performance of the search, with and without subgoal ordering and goal augmen­ tation, are compared.

There are seven problem objects in this problem, one Robot, one box and live doors. The problem has three aspects. Two of them are the same as in the previous exam­ ple and we still use functions lnroom and Nextto to represent them. A new problem aspect is the status of a door, for which we represent by the function D_§tate. D_§tate 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'.

There are six types of actions in this problem that are modeled as rules. The costs of all rule applications are assumed to be the same constant. Therefore, a best solution is on~ composed of least number of rules.

The rules are specified as follows:

R 1 GOTO(bx*): IF: In room (Robot ,· J)=lnroom ( bx ,· 1) THEN: ( \f dx(Nextto(dx,s2)={ })) (\ (Nextto(Robot,a2)={bx}) (\ (Nextto(bx,a 2)={robot}) R2 GOTO(dx): IF: ] r:z: ,ry f(/nroom (Robot ,a 1 )=r:z:) (\ (Connect (dx ,rx ,ry ))J

Figure :{. A Robot Planning Example

(a). An initial state

(2). A goal state

THEN: ( \f objrfdx)(Nextto(obj,az)={ }) (\ (Nextto (Robot ,a2)={ dx}) (\ (Nntto (dx ,s2 )=(Robot})

R3 GOTHROUGH(d: ,ry ):

IF: 3 rx [(Inroom(Robot,s 1 )=rx) 1\ (D_ptate(dx,st)=open)

(\ (Connect ( dx ,rx ,ry ))J THEN: (Inroom(Robot ,s 2)=ry) (\ ( \f obj)(Nextto (obj ,sz)=(}))

R, PUSHTHROUGH(bx,dx,ry):

IF: (Nextto(Robot,st)= {bx}) (\ (D_ptate(dx,a 1)=open) (\( 3 rx[(Inroom(Robot,s 1)=lnroom(bx,a 1)=rx)) (\ Connect (dx ,rx ,ry )J

THEN: (Inroom (Robot ,s 2)=ry) 1\ (Inroom (bx ,az)=ry) (\ ( \f dxE{door 13 , ... ,door48}(Nextto (dx,sz)={ }) (\ (Nextto(Robot,s 2)={bx}) (\ (Nextto(bx,a 2)={robot})

R6 OPEN(dx):

IF: (D_ptate(dx,at)=closed) (\ (Nextto(robot,a 1)={dx}) (\( 3 rx,rii [(Inroom(Robot,a 1)=rx) (\ Connect(dx,rx,r11)J) THEN: D_ptate (dx,a 2)=open

R8 CLOSE(dx):

IF: (D_ptate(dx,a 1 )=open) (\ (Nextto(robot,at)={dx}) (\ ( ] r:z: ,ry [(Inroom (Robot ,s 1)= rx) (\ Connect ( dx, rx ,ry )J) THEN: D_ptate (dx ,a 2)=clo.ed

The initial state s;n is specified as follows:

(In room (Robot ,·;. )=room3) (\ (In room (box ,a;. )=room,) (\ (D _ptate( door 13,·;. )= · · · =(D _ptate (door 48,8; 0 )=open)

The problem goal state ·a is specified by the goal con­ dition formula G=g 1 (\ g2 (\ g3 (\ g4, where

g 1:(/nroom (Robot ,sa )=roomz),

g2:(Inroom (box ,a a )=room e),

g3:(D ..§tate (door36,sa )=closed),

g4:(DJtate ( door24,aa )=cloud).

In this problem, there exist inherent ordering con­ straints among subgoals and implicit goal state information in the problem specification. By applying subgoal ordering and goal augmentation strategies, we can detect and make use of the underlying information to make search efficient.

With the procedure SOC, the relation < is derived to be {<g 11 g4>,<g2,g 1 > ,<g3,g 1 > }. Applying GOAL_ORDER to the set of sub goals with the relation <, we then get a goal sequence c' =G11G2,G3 , where G1=g2 (\ gs, Gz=g, and Gs=9··

The procedure AUGMENT is then applied to that goal sequence and the following results are derived.

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 out­ lined a procedure to integrate these two strategies with our previous methodology of automatic generation of admissible search heuristic. The combined package is a new methodol­ ogy of general problem solving.