Ordering Problem Subgoals

1 Introduction

Subgoal ordering plays such an important role in plan­ ning and problem solving that a great amount of re­ search has been dedicated to detecting subgoal order­ ing constraints and applying the constraints to problem space search control [Chapman, 1987, Dawson and Sik­ lossy, 1977, Ernst and Goldstein, 1982, Sacerdoti, 1974, Sacerdoti, 1975, Sacerdoti, 1977, Tate, 1975, Waldinger, 1981 , Warren , 1974]. However, most of the reported approaches are heuristic and the subgoal ordering con­ straints are not well-defined. Further , very little attempt has been made to reveal the inherent relationship be­ tween subgoal ordering constraints and problem opera­ tor schemata. Chapman [1987] was the first who gave a formal account to the subgoal ordering problem, but he has not addressed the relationship between ordering constraints and problem operator schemata. Ernst and Goldstein [1982] tried to elucidate the relationship be­ tween ordering constraints and problem operators, but their approach requires the use of instances of problem operator schemata and cannot guarantee the correct­ ness of the generated ordering of subgoals in general (see [Irani and Cheng, 1987]). Consequently, subgoal ordering strategies previously developed tend to be ei­ ther overly committed, imposing ordering on subgoals subjectively or randomly, or overly restricted, ordering subgoals only after a violation of ordering constraints becomes explicit during the development of a problem solution or plan.

In our research, an approach is developed to explicitly represent subgoal ordering constraints. Based on this representation, procedures are then constructed to sys­ tematically detect the constraints. This approach makes it possible to detect ordering constraints without getting involved in planning or problem solving.

Our approach proves to be advantageous in that once a representation for a class of constraints is constructed, its properties can be studied and the representation can be manipulated to extend its generality or to produce formulations for new types of constraints. Another ad­ vantage of our approach over the old ones is that much time formerly devoted to detecting violations of con­ straints and ordering/reordering partial problem solu­ tions or plans can now be saved. The constraints can be derived from problem specifications via reasoning and henceforth, problem subgoals can be properly ordered even before problem solving or planning. Finally, con­ straints among a group of problem subgoals, once de­ rived, can be stored and applied to multiple problems as long as they share the same problem operators and involve at least these subgoals. The complexity of the approach is measured to be polynomial with respect to the number of subgoals involved, with the assumption that in any rule schema, all that is implied by the pre­ conditions or the postconditions is explicitly represented.

In [Irani and Cheng, 1987], our initial results in sub­ goal ordering have been reported. In this paper, we present an extension to our previous work. The paper is organized as follows. First , an extended representa­ tion schema for subgoal ordering constraints is defined. The features of the represented constraints are then dis­ cussed. A method to reduce the complexity of constraint detection is described and then several procedures for detecting such constraints are presented. Finally, an ex­ ample is used to further illustrate this approach .

2 Representing Subgoal Ordering Constraints

In this section, basic notations used in the paper are introduced, the initial results of our research reported in (Irani and Cheng, 1987] are briefly reviewed, and then an extended schema for representing subgoal ordering constraints is presented.

2.1 Notations

To represent subgoal ordering constraints, three compo­ nents of a problem model are needed, namely, a state space, a set of problem operators and a goal specifica­ tion. It is assumed that each state is represented by a conjunction of propositions. G is a conjunction of lit­ erals each of which is a subgoal. With this restriction, the goal G can be equivalently represented as a set of sub goal literals .

In this paper, s is a symbol representing a state. T (with a suitable subscript) denotes a problem operator which transforms one state into another. preck and postk are the precondition formula and postcondition formula respectively of operator Tk. S 1 stands for a subset of states in which predicate formula f holds true. g (with a suitable subscript) denotes a subgoal . A problem so­ lution is a sequence of states, (s1,s2, ... ,sn), where s1 is an initial state and Sn is the first state that satisfies the goal condition. We say "a subgoal g is achieved at the m-th step of a solution (s1,s2, .. . ,sn) if s; E 8 9 for m ~ i ~nand if m > 1 then sm_1 ¢ 8 9 . g is said to be trivially achieved in a solution if m = 1. We say "a sub­ goal g; precedes a sub goal 9; in a solution ( s1, s2, ... , Sn )" if g;(g;) is achieved at the m1 (m2)-th step ofthe solution and m1 < m2.

2.2 Review

In our previous paper [Irani and Cheng, 1987] , a bi­ nary relation <* over a set of subgoals G was defined . . This relation was then proved to be a formal character­ ization of a type of strong ordering constraints among the subgoals, namely, the constraint that a subgoal g; must precede another subgoal g; in all problem solutions in which both ar~ non-trivially achieved. In later discus­ sion, this type of constraints will be referred to as the constraints of type <*.

As demonstrated in our earlier work, the relational representation of problem subgoal ordering constraints facilitated the development of procedures for systemati­ cally detecting the constraints. Furthermore, the repre­ sentation reveals that there exists a generic relationship between subgoal ordering constraints and a problem op­ erator schema. Therefore, it is possible to detect a class of ordering constraints among subgoals without getting involved in problem solving or planning processes.

The relation <*, however, has two weaknesses. First, the relation is binary, so only pairs of subgoals are ex­ amined for the detection of ordering constraints. In this way, the relation cannot be used to identify a con­ straint among two subgoals if that constraint is depen­ dent on the coexistence of other subgoals. For exam­ ple, let three subgoals be defined for a robot planning problem. The first subgoal is for the robot to place a block, b1, next to another block, b2 . The second subgoal is for b1 to be in room1 and the third is for the robot to be in another room, say, room2 . It is obvious that the robot has to achieve N extto(b1, b2) before it achieves Inroom(robot, room2) . However, < Nextto(b1,b2), lnroom(robot,room2) >is not in there­ lation <*, because in this case, the ordering constraints can be identified only when all the three subgoals are taken into consideration.

Another weakness of the relation <* is that in order to detect ordering constraints ahead of planning or prob­ lem solving, every pair of subgoals has to be screened. This is not very economical because constraints often exist among only a few problem subgoals. These weak­ nesses of the previous approach motivated us to extend the representation of sub goal ordering constraints to cir­ cumvent the limitations while preserving the declarative feature and the simplicity of relation <* .

2.3 Extension

The extension to the constraint representation is basi­ cally to let more subgoals be considered simultaneously for the detection of constraints. This extension should not only make it possible to detect constraints among pairs of subgoals that are dependent on the coexistence of other subgoals, but also pave the way for an efficient top-down approach in detecting subgoal ordering con­ straints. In the following, we define a relation -(+ . Here, {gkJ and {gh;} represent sets of arbitrary subgoals and 1\;gk, represents the conjunction of the elements of {gkJ ·

Definition 1 {Extension 1} -(+ is a binary relation over G', where G' = 2G . For any {gk,} E G' and any {gh;} E G', {gkJ-(+{gh;} iff

This relation can be verbally stated as follows : {gkJ-(+ {gh;} if and only if, for every rule, say 11 , if the rule can transform a state s into a state Tt( s) satis­ fying all subgoals of {gkJ U {gh;}, then 1\;gk, must have already been satisfied in s , whereas for each subgoal g in {ghi }, there exists at least one rule and one states such that 9 is not satisfied in the state s . For example, if we take the problem goal to be the conjunction of the three subgoals we mentioned before, and we use the same set of problem operators as used by Sacerdoti [1974], then we can derive relation -(+ to be like:

Inroom(Robot , room2) >}

Obviously, the constraint that was missed by<* is now identified by -(+, namely, 91 must be achieved before 93 , given the coexistence of 92· The type of constraints characterized by -(+ is given by theorem 1 and will be referred to as the constraints of type -(+.

Theorem 1 1 {9kJ-<+ {9h;} iff {1} each 9 E {9kJ precedes the complete accomplishment of /l.j9hi for any problem solution in which /1.;9k; and !l.j9hi are non­ trivially achieved,

{2} for each 9 E {9h, }, there exists at least one problem solution in which all subgoals of {9k;} U {9hi} are non­ trivially achieved and in which 9 does not precede the complete accomplishment of the subgoals in {9h;} - {g}.

The relation -<+ has three desirable properties as de­ scribed in the following:

Property 1 If {9kJ-<+ {9h,}, then the relation -<+ re­ stricted to 2{ 9 "i} is empty.

The implication of this property is that, once we de­ rive a constraint of type -<+ among two sets of sub goals, namely, {9kJ-<+{9h,}, we do not need to go further to search for the constraints of type -<+ among the sub goals in {gh1} .

Property 2 is the uniqueness property of the relation -<+ . It is equivalent to saying that there is at most one partition of a set of subgoals into two blocks such that there is a constraint of type -<+ between the two blocks of the subgoals.

Property 3 If for any partition { G1, G2} of a set G of subgoals 1 G1 -/-+G2 and G2 -/-+ G1 1 then -<+ restricted to G is empty.

The three properties of -<+ can be used to greatly expedite the process of detecting subgoal ordering con­ straints. Specifically, a top-down approach can be used which starts by detecting constraints among a set of sub­ goals and then, only if a constraint is found, proceeds to detect constraints among the subsets of subgoals. The rest of the extension work makes the constraint detection even more efficient .

It is clear from the above discussion that -<+ is much more useful than relation <*. However, -<+ still has one disadvantage. As can be seen from theorem 1, -<+ identifies much more than we actually need. What we need is the precedence relation between pairs of sub goals that are nontrivially achieved. Therefore, it will be a waste to detect the constraints we need via the derivation of relation -<+ . This problem leads to the introduction of a new relation as follows:

Definition 2 (Extension 2:) -<"' is a binary relation from 2G to G. For any {9kJ E 2G and any 9 E G 1 {9kJ-<"' 9 iff

Actually, -<"' is a sub-relation of -<+, because -<"' -<+ n 2G X G. The link between the relation -<"' and the constraint it identifies is as follows:

1 Proofs of theorems have not been given here due to space restriction. Interested readers are referred to [Cheng, 1989].

Let {9kJ U{9} ~ G. {9kJ-<"' g if and only iffor each 9' E {9kJ, 9 1 precedes 9 in any problem solution where all sub goals of {9k;} U {9} are non-trivially achieved.

The improvement of -<"' over -<+ is that -<"' can di­ rectly identify ordering constraints among pairs of sub­ goals that are dependent on the existence of other sub­ goals. However, as indicated by its three properties, -<+ has the potential of speeding up the the process of con­ straint detection. Therefore, both relations are employed in our development of constraint detecting procedures.

3 Detecting Subgoal Ordering Constraints

Now that a type of sub goal ordering constraints is explic­ itly represented, we can proceed to build procedures to systematically detect the constraints from problem spec­ ifications. In this section, we first present procedures for detecting constraints of type -<"' among a set of sub­ goals , and then, a procedure for detecting constraints of type -<+. To reduce the complexity of detecting the constraints, we first introduce a notion called "the most effective subrelation of -<"'" which is a special subset of -<"' 0

3.1 -<"'min: A Special Subrelation of-<"'

The constraints that concern us are of the following type: a subgoal 9; must precede another subgoal 9i in any so­ lution in which a set of subgoals including g; and 9j are nontrivially achieved. The relation -<"' is used to detect this type of constraints. For example, if {91 , 92 }-<"' 93, then 91 will precede 93 and 92 will precede 93 in any so­ lution in which 91,92 and 93 are non trivially achieved. Note that {91, 92} -<"' 93 will be true for any problem with goal G such that {91,92,93} ~ G, as long as all other parts of the problem specification are the same. The in­ teresting point is that, as will be shown, there always exists a minimal subset of -<"' which can identify all the constraints that are identified by -<"'. Such a subset is called the most effective subrelation of -<x . In this section, this subset is defined and its properties de­ scribed. First, we define a set Ca which contains the constraints that we are interested in.

Definition 3 Ca is a binary relation over G. For 9; E G and 9i E G1 < 9i,9j >E Ca iff there exist 9k 11 9k, ... , 9km 1 such that 9; E {9kJ 1 9i f/. {9kJ and {9kJ-<"'9i ·

Next, we define a mapping F which relates the Ca with the relation -<"'.

Definition 4 F : 2-<"' --> 2Ca is an injective function . F( { < /1.;9k;, 9 >}) = U;{ < 9k;, 9 >} and for any S ~ -<"'1 F(S) = UeEsF({e}).

With these definitions, it is now possible to compare the relative effectiveness of any two subsets of-<"' in their identification of sub goal ordering constraints.

Definition 5 Let -<"' wb1 and -<"' ·ub2 be subsets of -<"'. -<"' ·ub1 is more effective than -<"' ·ub2 1 de­ noted by -<"' wb1 C -<"' ·ub2 1 if !-<"' ·ub11 < I-<"' ·ud and F( --<~ ·ubi) 2 F( --<~ ·ub2)· A subset of --<~ is the most effective subrelation of --<~, denoted by --<~min, if for any --<~ ·ub ~ --<~, --<~min C --<~ ·ub ·

We state without proof the following theorem:

Theorem 2 The relation --<~min exists and is unique.

We are only interested in the relation Ca as defined in definition 3. The following theorem shows that the relation Ca can be obtained from --<~min.

Theorem 3 F(--<~min) =Ca.

Taking as an example the simple robot planning prob­ lem we used in section 2.2, we can derive the following:

and

3.2 GENCON and GENCON2

In this section, two recursive procedures called GENCON and GENCON2 are described. GENCON is the main procedure which generates --<~min for a given goal G. GENCON2 is called by GENCON. Another procedure, ON ECON, which is a called by both GENCON and GENCON2, detects a--<+ relation among a set of subgoals, if any. ON ECON is described in the next section. The parameters GS and Rmin for GENCON are initially set toG and ¢J respectively.

Procedure: GENCON(GS, Rmin)

Input: GS - a set of subgoals;

Output: Rmin =--<~min ·

VAR: C- holds ON ECON's return value which is ei­ ther a member of--<+ or ¢J.

1. If IGSI = 1, then RETURN;
2. Call ON ECON(GS, C);
3. If C = ¢J, namely, there exists no --<+ relationship among the subgoals of GS, then RETURN;
4. If C = {gk 1--<+{g} (equivalently, {gkJ--<~g), where {gkJ E 2as, g E GS and {gkJ U {g} = GS, then Rmin = Rm;n U { < {gkJ, g > };
5. If C = {gkJ--<+ {ghJ, where {gkJ E 2GS, {ghJ E 2G 5 , {gkJ U {gh } = GS, and l{gh }I> 1, then for all g E {gh;} call GENCON2( {gk,}. g, Rmin);
6. call GENCON( {gkJ, Rmin);
7. RETURN

GENCON2 is a procedure called by GENCON. It is used to generate all the --<~ constraints among subgoals of GS U {g} with the knowledge that g cannot precede any of the subgoals in GS.

Procedure: GENCON2( GS, g, Rmin)

Input: GS - a set of subgoals; g - a single subgoal;

Output: Rmin ~ --<~min·

VAR: C- holds ON ECON's return value which is ei­ ther a member of--<+ or ¢J.

1. Call ONECON(GSU {g},C);
2. If C = ¢J, namely, there exists no --<+ type con­ straints among the sub goals of GS U {g}, then RE­ TURN;
3. IfC = {gkJ--<+{g} (equivalently, {gkJ--<~g), where {gkJ = GS, then Rmin = Rmin U { < {gkJ, g > };
4. If C = {gkJ--<+ {gh;}, where {gkJ E 2Gs, {ghJ E 2GSu{g}, {gkJ U {gh;} = GS U {g }, then call GENCON2( {gkJ, g, Rmin);
5. RETURN

The two procedures listed above are developed follow­ ing the guidelines provided by the properties of the re­ lation --<+ . For example, in GENCON, step 3 follows from property 3; step 4 follows from property 2; step 5 and step 6 follow from property 1. It has been proved that, as desired, the set of elements generated by the procedure GENCO N is exactly --<~min .

3.3 ONECON

A basic component of the procedures GENCON and GENCON2 is a procedure, named ONECON, which identifies a member of --<+, or a constraint of type --<+, for a set of subgoals . This section describes the develop­ ment of 0 N EGO N. A new membership criterion for the relation --<+ is constructed. The reason is that, although the original definition of--<+ provides a simple character­ ization of constraints, it cannot be directly implemented in detecting the constraints because that would necessi­ tate exhaustive search of the whole problem space. The new membership criterion provides an operational def­ inition for --<+ which is almost directly translated into the procedure 0 N EGO N.

We use Strips-like problem representation for the fol­ lowing discussion, although our procedure can be applied to other representations as well. postk will henceforth be used to denote the formulas in the Add-list of rule Tk .

Definition 6 A binding 1r of postk with a goal G is de­ noted by post'k and is the result of assigning constants in G to corresponding variables of matching formulas in postk and assigning arbitrary constants to the rest of the variables. A binding 1r of preck with a goal G is denoted by prec'k and is the result of passing the binding from postk to preck and assigning arbitrary constants to the remaining variables.

Definition 7 A goal G is consistent with a post­ condition postk under binding 1r, or simply, con(postz, G), if ( 1) for all g E G, it is not true that -.g is a logical consequence of post'k and the preserved prec'k formulas2;

2 Preserved prec;; formulas are the predicates in prec;; that are not deleted by the rule T~;.

(2} None of the problem constraintr is violated by the conjunction of post'k, G, and the preserved prec'k fonnu­ las.

It is clear from the above definition that logical rea­ soning is necessary for the detection of sub goal ordering constraints . Such a requirement may make computation infeasible in a complicated problem domain. Therefore, to make this approach feasible, it is necessary to impose the following assumption: In problem operator specifica­ tions, everything implied by post"' (preck) is also explic­ itly represented in post"' (preck) .

Theorem 4

\:lk'r/1r [(con(postk,l\;gA:,Ajgh;)--+ (Prec'k--+ 1\;gA:.)] 1\ \:lg E {gh; }{3k37r [(con(postk, 1\;gA:, 1\ g) 1\ ...,(Prec'k--+ g)]} if and only if Vk\:ls(TA:(s) E 8",. ; 9.,,9~; --+ s E 8", 9.,) 1\ Vg E {gh;}3k3s(TA:(s) E 8", 9 ., ,9 1\ s ¢ S9 )

where Prec'k is the conjunction of prec'k and those sub­ goals of G which do not match anything in post"'.

This theorem provides an equivalent membership cri­ terion for the relation -<+ . The new criterion leads di­ rectly to the procedure, ON ECON, for detecting sub­ goal ordering constraints.

Procedure: ONECON(GS,C) Input : GS- - a set of subgoals; Output : C- - a member of-<+ over 2as . fail= 4>; For each problem operator schema rk do: Begin {For rk} For each binding 1r of post"' with GS do If con(post'k, GS) then Begin {If} GS' = GS- fail For each g E GS' do if Prec'k --+ g then passk,1r = passk,1r U {g }; else fail= fail U {g}; End{If} ; paSSk = n,.passk,., ; End{For rA:} ; . pass= nkpassk ; if pass= 4> then Return 4> else Return(< pass , GS- pass>) .

Based on the assumption made on problem operator representation, the complexity of ON ECON is linear in n . The upper bound for the worst case complexity of GENCON is then O(n 3 ) .

3 An example of a problem constraint is: no problem object can ever reside in two rooms simultaneously .

4 An Example

In this section, we use a simple robot planning exam­ ple to illustrate our approach. The problem involves one robot , four blocks , six rooms and five doors. The prob­ lem operators are chosen from those used by Sacerdoti [1974] . The names of these operators are: GOTOB(bx), GOTO(dx), PUSHB(bx,by) , PUSHD(bx,dx), OPEN(dx), CLOSE(dx) , GOTHRUDR(dx,rx) and PUS HT H RU DR( bx, dx, rx) . The specifications for these operators are not listed here because of space re­ striction. A possible goal state is shown in Figure 1 and the problem subgoals comprising the problem goal are given as follows:

(gt) : Inroom(robot, r3); (g3 ) : Inroom(b2, r6); (g5) : Inroom(b4, r4) ; (g7) : Nextto(robot , b1); (g9) : closed(d56) ; (g2) : Inroom(b1, r3) (g6) : Nextto(b2 , b3) ; (g8) : closed( d23) ; (g1o) : closed(d45) ;

(g4) : Inroom(b3 , r6) ; After applying the procedure GENCON, we get Rmin = { < g1 1\ g2 1\ g3 1\ g4 1\ g5 1\ g6 1\ g8 1\ g9 1\ g1o, g7 >, < g1 1\ g2 1\ g31\ g4 1\ g51\ g6 1\ g91\ g1o, g8 >, < 93 1\941\95 1\96 1\99 1\910 , 91 >, < 931\941\96 >, < 931\94,99 >, < 95,910 >}

From Rm;n, the constraint graph can be generated as shown in figure 2. In the figure , a directed arc repre­ sents the constraint that the subgoal in the source node must precede the subgoal in the destination node for this problem.

5 Conclusion

The main issue brought up by this research is that an explicit representation of subgoal ordering constraints can greatly facilitate the development of sub goal order­ ing strategies. The representation makes it clear what type of constraints one is dealing with and how the con­ straints can be detected by analyzing problem specifica­ tion. Based on that representation, many generic prop­ erties of the constraints can be easily inferred. Further­ more, the representation helps one to understand the capabilities of the subgoal ordering approaches.