Interacting Goals And Their Use

Abstract

Current means-end analysis problem solvers are not capable of solving problems which have certain kinds of goal interaction. The goal inter­ action problem is described and an example given on a block stacking task. Finally, mention is made of a method of using the information gained by the discovery of goal interactions to guide the search for a problem solution.

Interacting Goals

A problem is given to a means-end analysis based problem solver, such as STRIPS (Fikes & Nils­ son, 1971) and the planning part of the HACKER (Sussman, 1973) system, as a conjunction of goals

which must be true for the problem to be solved. Since the individual goals are solved sequentially, they must, once achieved, hold together for a per­ iod of time. The time for which an achieved goal must remain true will be called the goal's "hold­ ing pe:ciod". I will illustrate this as in figure 1.

---------------------------------FIGURE 1

The horizontal dimension of this "Holding Period" diagram represents time during which ac­ tions will be applied in a final plan to achieve the given goals. Approach should be interpreted as: if Gl not true achieve it using some operator sequence, then do likewise for G2.

STRIPS assumes, in the absence of other in­ formation, that it can achieve the individual goals by relevant plan sequences, say, in the ord­ er in which the goals are given (Sussman calls this a linear assumption). Thus, as shown in figure 1, it assumes Gl can be solved first by some relevant plan sequence and then that G2 can be solved by a plan sequence following on from the first. If STRIPS can find no way to achieve the goals in the order given, it is capable of reversing the order it has attempted to achieve goals, which were init­ ially not true, at the failure level (e.g. at the top level Gl and G2 could be reversed to give an expected holding period diagram as in figure 2).

Austin Tate Machine Intelligence Research Unit University of Edinburgh Edinbur&h, Scotland

FIGURE 2 --

STRIPS further assumes that for the goals not already true at the time required, the precondi­ tions, which are required to be true for someoper­ ator to be applied to achieve the goal, can all be made true immediately before the time the goal is required to be true. Again, reversals amongst these preconditions can be made on failure backup. Thus, if the preconditions for some operator to achieve a goal Gi are Gil and Gi 2 ' then STRIPS initially assumes an approach as in figure 3 can be taken.

---------------FIGURE 3 --

Note that the holding period diagram represents the goals to be worked upon for ~ chosen opera­ tor sequence. There is really a 3rd dimension to the diagram representing different choices of operators.

Reversals allow certain other orderings of these goals to be attempted. However, limiting reversals to goals at a particular level of the search tree hierarchy means that STRIPS (these ar­ guments also apply to HACKER) can only tackle cer­ tain problems. Specifically, those in which inter­ actions between top level goals can be avoided by suitable ordering of the goals and the choice of suitable operator sequences.

Since STRIPS and HACKER also allow attempts to achieve goals to be repeated if interactions have occurred, they can also handle thoseproblems in which the interactions leave the world in some situation from which the interacted goals can be re-achieved. STRIPS will often produce longer than necessary solutions if it repeats attempts to achieve goals.

Even for very simple worlds, such as the blocks world used by Sussman, interactions can occur. To be able to deal with all types of interaction between a set of goals, we could con­ sider the search space as containing approaches with every interleaving of the goals and the sub­ goals needed to achieve those goals. Thus, a holding period diagram and approach as shown in figure 4 is necessary to resolve some types of interaction.

FIGURE 4--

The 3-Block Problem

The 3-block problem is an example used by Sussman (1973) in his description of HACKER. It is regarded by HACKER as an Anomalous Situation. The problem is useful as it s1ngles out the inter­ action difficulty in a simple task.

A world is described by two predicates ON(x,y) and CL(x).

ON(x,y) asserts block x is on top of the (same size) blocky.

Note that ON is not transitive.

CL(x) asserts block x has a clear top.

There are two operators:-

PUTON(x,y) asserts ON(x,y) and deletes CL(y).

If :3u.ON(x,u) before the application of the operator then assert CL(u) and delete ON(x,u).

It can be applied if are true. CL(x) and CL(y)

ACTCL(x) asserts CL(x).

If 3u.ON(u,x) before the application of the operator then assert CL(u) and delete ON(u,x) and

repeat if 3 v.ON(v,u) etc.

(This operator therefore clears all blocks from the top of block x.)

It can always be applied.

Given an initial situation ON(C,A) & CL(C) & CL(B) as shown in figure S(a) a goal of ON(A,B) & ON(B,C) is given as shown in figure S(b).

----------------FIGURE 5 -

STRIPS can tackle (ON(A,B) & ON(B,C)) both of which are not true initially. The goals may, at first, be attemp­ ted as shown in the holding period diagram of figure 6.

----------------- FIGURE 6 --

The earlier achieved goal (ON(A,B)) does not now hold (its expected holding period is broken), but this is not noticed by STRIPS, and problem solving proceeds as in figure 7.

FIGURE 7-

So, STRIPS produces the longer than necessary solu­ tion:-

ACTCL(A), PUTON(A,B), ACTCL(B), PUTON(B,C), PUTON(A,B).

Attempting the initial goals in the opposite order would make the final solution longer still, though if the interactions in the first ordering produced a situation in which the interacted goals could subsequently not be achieved, this would be attemp­ ted on failure backup. STRIPS is incapable of pro­ ducing a shorter plan for this problem.

HACKER has a mechanism, called Protection, which remembers achieved goals and looks out for actions which violate them. It would notice that the previously achieved goal (ON(A,B)) ceased to hold (as a protection violation) and would try to reverse the order of the top level goals (to ON(B,C) & ON(A,B)) at that time. However, another Protection Violation with the reversed approach will direct the HACKER planner to allow the Pro­ tection to be violated, and the result will be the same as STRIPS in this example.

The search space should have included an ap­ proach as shown in figure 8.

FIGURE 8

STRIPS, by re-achieving the ON(A,B) goal, can solve this problem with a longer than necessary plan because the world produced after interaction is such that the goals can still be achieved. A problem I have been considering - the Keys & Boxes problem (Michie, 1974) - has interactions which would preclude a STRIPS-like problem solver from finding any solution. Interactions occur in other problems, a simple example being the problem of swapping the values of two registers of a computer.

Using goal interactions to suggest new approaches to tackling a problem

Current means-end ·analysis problem solvers are uot capable of solving problems which have certain kinds of goal interaction. Also, with the exception of some systems at MIT (e.g. HACKER), they do not use interactions amongst goals to guide the search for a solution. I mentioned earl­ ier that all interleaving& of goals, and the sub­ goals needed to achieve those goals, should have the potential of being considered. Generally, only very few of the possible interleavings need be considered. An assumption, such as is made by many existing problem solvers, that goals can be achieved in the order given without interaction (linearily) is, however, a very powerful heuristic. My own work in problem solving (Tate, 1974) is based upon the powerful heuristics used in STRIPS and other problem solvers, but I am anxious not to let these assumptions rule the type of problems which can be dealt with. Proven contradictions of these assumptions during problem solving can dir­ ect the search to consider appropriate inter­ leavings of plan parts to remove interactions.

The information gained from the discovery of an interaction can be used to suggest appropriate continuations. As an example, the interactions discovered during attempts to solve the goals Gl & G2 linearily can lead us to the point, in figure 9,

Initial Situation

----------------FIGURE 9 --

where the expected holding period for Gl is broken by the achievement of a subgoal G21 required for an action to achieve G2. We have tried and found that Gl and G21 cannot both hold together when they have been achieved by some operator sequences in the or­ der Gl and then G21· We can either try an approach in which the goals at a higher (here the top) level are reversed to stop the conflicting goals' holding periods overlapping altogether (by reversing Gl and G2) or try to achieve the conflicting goals in the opposite order. It is sufficient to try to achieve the conflicting goals in the other order only once . This can be done whilst still preserving linearity as far as possible by moving the precondition (G21) whose achievement made a previously achieved goal (Gl) not hold, immediately in front of the goal as shown in figure 10.

Approach: Gu; Gl2; G21; Gl;

. . . . . . . .

FIGURE 10--

We shall say that we PROMOTE the precondition. Moving it further back through the goals to be worked upon would still try to achieve the con­ flicting goals in the opposite order but would risk further possibilities for other intermediate goals to interact with the precondition being pro­ moted. Note that the promoted precondition (G21> may interact with earlier goals and may need to be shifted again due to different interactions. Sub­ goals intermediate between G2 and G21 if they exist may need to be promoted also.

If in both orders the same goals achieved by suitable operator sequences still interact andean­ not hold together, the problem cannot be solved by this approach.

The technique described above has been incor­ porated into a problem solver, INTERPLAN (described in Tate, 1974), which has been applied to a vari­ ety of problems. A trace of INTERPLAN on the )­ blocks problem is given in figure 11.

: COAL <<ON A I>> <<ON I C>>;

ENTEUNC INTERPLAN WITH INITIAL SITUATICII 1

** ACHIEVE << ON A I >> IN 1

** ACHIEVE << CL A >> IN 1

** APPLY << ACTCL A >> TO 1 TO GIVE 2

** APPLY « PUTON A I >> TO 2 10 GIVE 3

** ACHIEVE << ON I C >> IN 3

** ACHIEVE << CL I >> IN 3

** APPLY << ACTCL I >> TO 3 TO GIVE 4 PIOTECTION VIOLATION REORDER

** APPLY << PilTON I C » TO 1 TO GIVE 5 aDd thetl cc(ll A I»

** ACHIEVE « ON I C » IN 1

** ACHIEVE <c ON A I >> IN 5

** ACHIEVE cc CL A >> IN 5

** APPLY « ACTCL A » TO 5 TO GIVE 6 PIOTECTICII VIOLATION PROMOTE

** APPLY « ACTCL A » TO 1 TO GIVE 7

** ACHIEVE <c CL A >> IN 1

** ACHIEVE « 011 I C » IN 7

** ACHIEVE « Ill A I » IN 8

** APPLY « PUTO!f I C » TO 7 TO GIVE 8

** APPLY « PUTON A I » TO 8 TO GIVE 9

att..,ti .. cc(ll A 1>>

aDd thetl «Ill I C»

att .... tiaa «Ill I C»

att..,ti .. ccCL A>>

then «011 I C»

aDd then <<011 A I>>

** CPU TIM! · 2 .109 SECS

.,.,

« ACTCL A »

« PUTCII I C »

« PilTON A I »

: APPaOACII

-1001 cc CL A >>

2 «OIIIC»

1 «CIIAI»

-1001 indicate· ·· CL A ·· ia a precoodition for the aoal ref.1

--------------FIGURE 11 --