Subgoal Protection and Unraveling During Plan Synthesis

1. Introduction

One of the subtler issues of automatic problem solving and program synthesis is sub~oal annihilation or infr~ngement. Subgoal annihila ion occurs wheni during the course of solving one aspect of a arger problem, some other aspect of the problem whose solution has already been ob­ tainea is interfered with, or undone completely. Subgoal infringement is a milder form of subgoal ann~hilation in which the prior solution of one subgoal causes the solution of another later sub­ goal to become more difficult or tedious.

In this paper, we describe a uniform procedure for detecting and resolving subgoal annihilations. The scheme is applicable to both small-domain and general problem solvers, and relies on an associa­ tive style of computing which we call "spontaneous computation" for the detection phase, and a tech­ nique we call "unravelling" for the correction phase.

We first provide a brief motivation of the sub­ ject and a review of existing techniques for sub­ goal protection. Then we describe the problem solving framework from which we have approached the problem, and present the paradigm for spontaneous computation. Next, we describe the protection­ unravelling theory and illustrate it on a small blocks-world example run on our system. Finally, we discuss the implications and extent of our scheme, pointing out some possible future develop­ ments and related applications of the theory.

2. Hotivation and Background

In solving a co'mplex problem 1 it is nearly al­ ways necessary to break the ~nitial problem down into smaller problems such that, if each subproblem were to be solved, the initial problem would also be solved. This approach is commonly called problem reduction or means-ends analysis (see e.g. [ENl] or [Nl]) and has been the paradigm for most problem solving systems in AI.

Problem reduction is an intuitively adequate ap­ ~roach to problem solving, especially if tne point ~s to propose models of human problem solving. However! problem reduction suffers from an inherent difficu ty. This is that the act of delegating re­ sponsibilitl for the solution of the initial prob­ lem to smal er subproblems must obviously give some degree of autonomy to the processes which solve the suoproblems· (Otherwise, there would be no point in reducing the initial problem.) At one extreme, there is total autonomy, where each subgoal solver has complete freedom to generate whatever type of solution seems best for the subproblem, disregard­ ing the fact the tne-suoproblem participates in a larger plan which must eventually be consistent. At the other extreme, every subgoal solver takes ut­ most care in interacting and cooperating with all other subgoal solvers so that harmony of the overall plan will be ensured.

The first extreme suffers from too much independence; the second extreme suffers from too little independence. However, the first approach is conceptually and computationally much cleaner than the second, because it makes possible a more modu­ lar representation of problem solving strategies. If there were some uniform method of noticing and resolving conflicts among relatively autonomous subgoal solvers, then we could have the best of both worlds: modularity in problem solving know­ ledge, yet harmony in the synthesis of large plans.

Subgoal annihilation problems are extraordinari­ ly pervasive, both in expert domains, and in every­ day human problem solving. Consider a simple exam­ ple from the blocks world:

GOAL: Achieve the state (AND (ON A B) (ON B C)) starting from the state shown below under the constraint that only one block at a time can be lifted.

part of the plan for the first goal in order to solve the secona goal, as shown above.

If the problem solver attempts to solve the A subgoals (ON A B) and (ON B C) in the order given in the stateC ment of the goal, then it will back it­ ~~~L-------------------L----L self into a corner in which it must undo

To illustrate an analogous annihilation problem in everyday problem solving, consider the midnight snack scenario: . an AI researcher has just made a d7licious (but greasy) cold-~ut .san~wich, an~ w~shes to clean up before consum~ng ~t. Clean up might mean: (a) wash his hands, and (b) throw the areasy cuttings away. Obviousli, if he solves these subgoals in this oraer, he wil not only have to wash his hands twice, he might also lose his job at the AI lab!

The central problem in both these examples, and indeed in many instances of subgoal annihilation, is ordering. In the absense of any prior knowledge, it is difficult to see how to have the problem solver prefer any particular order for the solution of subgoals. Hence, it must undertake them in some arbitrary order, simply to begin. The object of any system. of subgoal protection must therefore be {a) to detect when following the simple syntactic ordering leads to subgoal annihilations or infringements, and (b) to recover from such viola­ tions with the minimum degree of resynthesis.

Not all subgoal annihilations stem from ordering proble1~. The . other major source ?f anni~ilations is inappropr~ate strategy select~on. Th~~ occurs when, having several alternative strateg~es for some subgoal, the solver selects one (perhaps even the best, based on the local evidence surrounding the subgoal) which turns out to be inimical to some other subgoal in the larger plan. For example, if aur-Al researcher wishes to insert a stake in his garden for the purpose of nailing a cookie tin to its t~p as a bird feeder, selecting and, applying the 'pound it in with a sledgehammer strategy might severely splinter th~ top of th~ stake,. mak­ ing it impossible or diff~cult to na~l anyth~ng to the stake. In this case, selecting some other stra­ tegy would be called for. l~e will comment on this type of subgoal violation later, but concentrate principally on annihilations stemming from bad orderings.

Huch attention has been paid recently to the subgoal annihilation prob!ern. ~his attenti~n seem­ ingly stems from Sussman s HACKER system [S2]. In fact, the predisposition to the blocks world by r~­ searchers in this area may be somewhat Sussman s doing; he was able to cite some conceptually simple but theoretically troublesome blocks world problems. The very nature of HACKER as a system which produces plans under the assumption of abso­ lute subgoal independence, and then proceeds to de­ bug them for the errors they inevitably have because of subgoal interaction, points out the need for subgoal interaction schemes.

Several interesting subgoal interaction schemes have been devised. In Sacerdoti' s NOAH sys tern [S1], subgoals are solved independently and in parallel. At each step in the planning process, the plan is incrementally made more detailed. After each such step, procedural experts examine the plan to remove any potential interaction errors or redundant operations. A po~erful idea here is the use of a two-dimensional (non-linear) represen­ tation for plans, also a central feature of our Commonsense Algorithm system.

Waldinger [Wl] and Tate [Tl] both advocate the modification of partial plans to alleviate detected protection violations. Their schemes involve de­ tecting that the current goal violates a previously protected goal and that tfie violation can be re­ lieved by specifying that the solution to the cur­ rent goal occur before the violated goal.

Because of space constraints, we must omit a de­ tailed discussion of the relative merits of the various problem solving strategies dealing with subgoal annihilation problems. Such discussions, formulated from various points of view can be found, for example, in [S1] or [W1]. What should be pointed out, however, is that there is general agreement that some form of dynamic subgoal in­ teraction scheme is required for solving even bare­ ly complex problems. We expect that tfie scheme we are proposing will provide us the latitude to ex­ plore the subtler issues of violation detection in complex domains and the relation of strategy selec­ tion errors to subgoal violation.

3. Theoretical Framework

There are two aspects of our subgoal protection theory that relate to ongoing work within our Commonsense Algorithms (GSA) Proiect at i1aryland. These are {1) the plan synthesizer and its repre­ sentation for plans and cause-effect knowledge, and (2) our paradigm of spontaneous computation. We de­ scribe each of these briefly in this section. For more comQlete discussions, the reader is referred to [R1], LR2], and [R3].

3.1. GSA Problem Solver Representation

The basis of the problem solver's representation both for the strategies it will use in constructing plans, and for the final plans themselves, is a set of 16 links. Each link connects two or more events and represents one of the primitive causality­ related event-event relations in the GSA theory. We will not discuss all the links in this paper, but instead concentrate on one of the constructions of most interest to our problem solver.

This construction is the gated causal link with explicit enablements. It,-----, is represented graphically'-----,/ as shown to the right. The central vertical link with the bulb is the causal relation. Its "syntax" de­ mands that the event on its tail be an action-like event· and that the event on its head be either a state or statechange event. The events feeding into the bulb from the right are called the gat-

ing states, in that they represent a collection of states which must be true in order for the action to ~ffect the state or statechange on the causal link s head. Semantically, these are the condi­ tions that govern not the action itself, but the influence the action will have on·its surroundings. As such, the interpretation is that the gates must all be true simultaneously, and for tfie duration that "causality must flow" from the action to the caused state or statechange. In this sense, gates will constitute subgoals to be solved before per­ forming the action.

The wavy links are enablement links. These indi­ cate explicit enabling conditions that must be in effect to initiate and sustain the action itself. The syntax of the enablement link demands that its tail be a state and its head be an action-like event. Enablements and gates are distinct in theory, because the enablernents are prerequisite to the action itself, whereas the gates are prerequi­ site to the causal influence of the action on its environment. Enablements will also contribute sub­ goals to be solved before performing the action.

To illustrate, to express one simple strategy ~or pick~ng up a small physical object by grasping 1t, we wr1te a pattern such as:

($STRATEGY (

(NAHE *GRASP-IT)

(VARIABLES hand object)

(EVENTS ( 1 S (FREE hand) )

(2 A (GRASP hand))

(3 S (SllRROUtWS hand object))

(4 S (GRASPING hand ooiect)))

{OS-ENABLE (1 2)))

(LiN.t-:5 (C-CAUSE (2 4) (3))

(ACCOHPLISHES 4)

(APPKOPRIATE-UHEN

($FEATURE (SIZE object *) HANDFUL)

($FEATURE (CLASS object *) PBYS-OBJ)) ))

We express this in the LISP form shown to the left of the diagram, and enter it into the database of p,roblem solver strategies each of which we call an 'abstract algorithm". Each such strategy is a sche­ ma that can be as simple as this one, or as complex as we desire. More complex patterns typically in­ clude additional levels of specification on the gates and enablements, providing more than one lev­ el of solution within the strategy itself. Roughly speaking, the larger the strategy pattern is, the more stereotyped a solution it represents, in that it provides a more thorough specification of the next several levels of the plan at once. Smaller patterns contribute only the central causal idea and the gates and enablements, leaving the strate­ gies for solving all subgoals up to the synthesizer.

3.2. Operation of the GSA Synthesizer

In the GSA system, the act of ins~rting a ne~o~ strategy pattern in the synthesizer s database of strategies inherently also suggests to the system where to store the pattern and when to retrieve it as a relevant strategy for some goal. This organ­ ization occurs via the APPROPRIATE-WHEN feature in the strategy's input description.

The APPROPRIATE-WHEN conditions specify the cir­ cumstances under which it might be most appropriate to prefer this strategy over the possibly numerous other strategies available to the system for the same general goal. For example, the APPROPRIATE­ IJHEH conditions for the "send it by mail" strategy are diffenent from the appropriateness conditions for the hand carry it" stragegy, even though both strategies accomplish the same goal of causing a change in location of a small object.

The system uses the APPROPRIATE-WHEN conditions to decide where in one of the system's discrimina­ tion networks to situate the strategy. There is one discrimination network for each goal predicate (e.g. LOG) in the system. It is the purpose of a network, whenever a goal involving the net's predi­ cate appears during plan synthesis, to select the most appropriate strategy in that particular instance. For this reason, we call these networks "causal selection networks" (GSN's). GSN's are de­ scribed in more detail in [R1].

The selection process is sensitive to the fea­ tures of all known strategies which best differen­ tiate those strategies according to their contex­ tual relevance. The nodes of a GSN therefore are intended to probe as much as necessary of the con­ text of the goal whose solution is sought and its environment to make a "most appropriate" selection in that environment. In using a central GSN struc­ ture for this selection process, rather than adopting a more distributed scheme in which strate­ gies compete (e.g. as do PLANNER theorems [SW1] or production rules [DK1]), we are reflecting our very strong theoretical bias that intelligent, coor­ dinated selection from among alternate strategies is one of the central issues of AI.

Our system therefore consists of a · potentially large number of CSN's, each of which contains (at

.

its terminal nodes) a set of strategies. Each strategy is expressed via cause-effect patterns si­ nular to the one illustrated above.

In this enviro1~ment, the plan synthesizer's overall behavior 1s as follows. The initial goal (there may be several concurrent goals, but we will consider the simplest case where there is just one) causes the relevant CSN to be called up and applied. The CSN poses queries to the database­ deductive component in order to select the most ap­ propriate strategy, within the limits of its avail­ able strategies and available information about the context of the problem. Once selected, the synthe­ sizer creates as its subgoals any gating and enabling states (as specified by the gates and enablements of the selected strategy) which cannot be expected to be true at plan execution time. In this manner, the synthesizer recursively attacks the initial goal until no details remain or until a specified level of det~il (depth bound) is achieved. The paradigm is that of problem reduction, where the reduction operators are (possibly quite complex) GSA strategy patterns, and where alternate strategy selection occurs "intelligently" via the CSN's.

The most comr.lon source of subgoal violation in this environment seems to be (contextually) bad orderings on the gating and enable1nent states in one or more subgoal strategies. Although it seems to be feasible to learn and record good orderings, initially, the synthesizer cannot be assumed to know anything about potential ordering problems. By definition 1 therefore, in the absence of explicit ordering 1nformation, the synthesizer always at­ tacks tne gating and enablement conditions in the order they appear in the internal representation. Similarly, for compound initial goals (represented by another of our links), the components are at­ tacked in the order specified.

We will return to the overall synthesizer tegy later. We now turn to a description spontaneous computation component of synthesizer, and describe how it relates synthesizer strategy just outlined. stra­ of the the to the

3.3. Spontaneous Computation

The spontaneous computation (SC) conponent of the GSA system provides us with a demon-like, asso­ ciative access mechanism. It is of use and inter­ est in other phases of our project (especially as a model of certain categories of inference in lan­ guage comprehension). However, we focus here only on the aspects which relate to the synthesizer.

The GSA SC component is a generalized implemen­ tation of the notion of pattern-directed invocation in that it provides for more complex invocation patterns and for a more sophisticated hierarchical organization of invocation patterns. A GSA SC in­ vocation (trigger) pattern is a collection of nested n-tuples composed via AND, OR, and MIY rela­ tions to v1rtually any complexity. Each nested n­ tuple is i~entified as (1) an associative component of the trigger pattern, (2) a non-associative com­ ponent of the trigger pattern, or (3) a "computa­ ble", an S-expression wh1ch must evaluate non-NIL. Associative components are those that have the po­ tential for triggering the execution of the spon­ taneous computation. Non-associative components are patterns that must be true (i.e. in the aatabase or deducible) in order for an SC to run but which themselves have no potential for initially trigger­ ing the computation. We denote associative compo­ nents by the symbol "+", non-associative components by the symbol "-", and computables by any other LISP predicate.

In a system with this type of invocation pattern, an important issue is how to organize the associative parts of trig~ers so that, given some stimulus, all "nibblers , i.e. trigger patterns which contain a component that matches the stimulus, can be accessed all at once. For this purpose, we employ a construction called a "trigger tree", and use the metaphor Qf "plantin~" a trip;ger pattern in a trigger tree. The 1nternal structure of trigger trees are irrelevant to this discussion, and are described in [R3]. We need only the term here, and that is because each trigger tree will correspond to a population of SC's, namely the col­ lection of SC's whose trigger patterns' associative co11ponents have been planted in the tree.

To illustrate, suppose we wish to create an SC which reacts associat1vely whenever SLOCKl comes to be located at location A while ~LOCK2 is located at location B, or whenever any block greater than 10 em in height comes to be located at location c. Then we would define this SC to our system as follows:

($PLAiH '(OR (A!W ~+ 1 ~LO� BLOCK! A))

(A!W + 1 LOG - X C) )

- 1 LOG ilLOCK2 B))) - 1 HEIGHT - X -Y)) (GREATEttP - Y. 10) ))

<some body> <some trigger tree>)

This illustrates all three types of trigger compo­ nents (associative, non-associative and computable). The body is any CVAL-able LISP S­ expression, and the trig~er tree is the name of the trigger tree (e. g. "TTl ) in which we want the as­ sociative components of this pattern planted. The integers (all l's in this case) in the pattern are used by the database-deductive component, and represent the energy budget (measured in database fetches) which can be expended in attempting to de­ monstrate that the associated component of the pat­ tern is true after an initial trigsering by some other component. Atoms prefixed w1th hyphen signs denote variables. Variables are global to the en­ tire trigger pattern, in that two variables with the same name must be consistently bound to the same constant in a stimulus pattern (as in PLAllllEK and CONNIVER [HSl] ).

Associative access to all SC's which "nibble" at a stimulus pattern is caused by a call having either of the following forms:

($ACTIVATE <trigger-tree> <stimulus>)

or (<trigger tree> ~stimulus>)

(i.e. trigger trees can be used semantically as functions also). In either case, <stimulus> is a fully constant nested n-tuple.

Application of a trigger tree in this manner r e ­ sults in a queue of SC bodies which are ready to run. In the process of activation and the deten.·­ ination of which nibblers are actually ready to run, there is considerable interaction with the database-deductive component in determining which patterns are fu£1¥ satisfied (beyond the superfi­ cial associative r1ggering). Some other theoreti­ cal applications of this interaction are discussed in [lU].

Trigger trees can then be rega~ded as popula­ tions of contextually related SC s to p,articipate in a larger construct we call a "channel'. It is the channel construct that gives us a final pattern directed invocation facility akin to PLANNER and COtUHVER, except that channels provide for more generality in the hierarchical control over popula­ tions of SC's. Since we use channels only trivially in the plan synthesizer at present, we do not dis­ cuss them further here. Interested readers are re­ ferred to [R3].

\~e now return to the main topic of the paper, first describing the subgoal annihilation detection strategy .

4. Subgoal Violation Detection

As the synthesizer attacks and solves each sub­ goal in the manner described earlier, it trotects that subgoal by planting one or more violat on pat­ terns in a central synthesizer-related trigger tree. A violation pattern, conceptually, is any pattern which would be directly inimical to the pattern representing the subgoal -which is being protected. For this reason, we call protection patterns "guardian clusters." It is the respons­ ibility of a guardian cluster, for the duration of ·its existence, to ensure the continuation of the state it protects, spontaneously firing when inimi­ cal patterns materialize.

To illustrate, to protect the state (LOG BLOCK! A), we would plant a relatively simple pattern such as:

(AND (+ 1 (LOG BLOCK! -X)) (NOT-E~UAL -X 'A))

i.e. a guardian that would react if the location of BLOCK1 is ever predicated to be anywhere but loca­ tion A, the protected state.

The planting of a guardian cluster occurs im­ mediately upon the successful solution of the state the cluster is designed to protect. (i.e. all gat­ ing and enabling states). Gating and enabling states which are found to exist already, and which therefore require no synthesis, are also protected as though they had been solved oy the synthesizer.

The point of guarding each subgoal as it is solved ~s to ensure that at the end of all the gate and enab lement solutions, all sub goals \iill still be in effect so that (a) the action of the GSA schema can be performed (actually, added to the output action stream) in the presence of all its enablements, and (b) performance of the action will achieve the intended result in th~ presence of all its gates. Therefore, guardian SC s are destroyed (actually, masked) after the synthesizer finally generates the action. Semantically, since the ac­ tion has been performed, the protected states are no longer needed for the time being.

There are some interesting theoretical questions about what, exactly, constitutes a guardian cluster of SC's for any given state. In its simplest form, . '"e conceptualize the guard to trigger on "the negation" of the guarded state. However, things are seldom so simple that planting just the syntactic negation of the pattern will be adequate.

We do not yet have what we would call a general theory of guardian cluster generation. However, we expect the semantics of the predicate in the pro­ tected state can provide the synthesizer with direction in constructing the guardian cluster. For example, for those predicates which are uni-valued, but which have a continuous range (such as LOG), we plant a pattern of the form shown earlier~ namely: Protect (LOG X Y) ------> (NlD (+ 1 (LOG x Z)) (NOT-EQUAL Z Y))

For predicates which are either true or false, we plant a pattern involving the predicate which is the opposite of the protected state's predicate, e.g. to protect the state (FREE <hand>), we plant: Protect (FREE -H) ------> (+ 1 (GRASPIHG -H))

Guardian Clusters vs. Inference

It is difficult-;t this time to assess the range of problems involved in planting ~ood guardian clusters. However, one requirement ~s assured: we must rely heavily on a good inference system which generates a moderatell rich set of inferences from each event arising dur ng synthesis, i.e. meaning l?araphrases, implications, and so forth. Our bias ~s to keep the guardian cluster fairly concise, re­ lying on inference to hit this violation target in a shotgun fashion.**

** \Je feel that studying the processes of subgoal annihilation detection will shed some light on the interesting question of how problem solving and inference interact. As an example of problem solver - inference interaction, reconsider the mid­ night snack example. There, the two goals are (1) have clean hands, and (2) get the greasy leftovers (GL) into the trash can. How, the essence of the model concept that represents the greasy leftovers is SC-like itself; namely, it represents an object, one of whose features is: whenever this object is touched (i.e. whenever an assertion rna tching (GRASP IHG -H GL) is made), the grasping object will become greasy. This is an inference wh~ch plays the role of an "active" component in the object's de­ finition (similar to an "imp" in \linograd's ter­ minology [W2] ),

If our synthesizer were to srnthesize and pro­ tect the plan for clean hands f rst, one state that would be directly asserted at some point during the "throwing away" subgoal (the second one) would be (GRASPING HAND GL), where GL is the model concept £or the leftovers. This grasping state, being a component of the trigger pattern for this active feature of GL, would cause the inference (GREASY HAND) to be generated. That in hurn would ~et off the guardian cluster for the clean hands state, assuming of course that this cluster were suffi­ ciently rich to include (GREASY HAND) as a component. This could be arranged, for instance, by including a relatively exhaustive definition of the state "clean hands", namely, an enumeration of all closely-related inimical states (UIRTY, GREASY, etc.) Alternatively, some of these problems might be avoided if we were to break all these concepts down into further primitives, and arrange to trigger on the more primitive syt~bols rath~r than the nigher level ones. In any event, the po~nt is that without this inference that connects a grasping of something greasy to the resulting grea­ siness of the graSJ?er, the grasping state asserted during the soluuon of one of tne subgoals wo~ld not trigger the guardian cluster. However 1 w~th such an inference, the guardian cluster ~s hit. Thus, details aside, we get a glimpse of how infer­ ence can interact with plan synthesis.

To summarize there are two issues relating to spontaneous su~goal guardians: (l) how to express the guardian cluster, and (2) how much responsibil­ ity to delegate to tile guardian vs. how much to place on a more general inference facility.

5. Unravelling

The protection l?aradigm described above sug­ gested ~tself relat~vely soon after the development of the SC coml?onent of the GSA system. We then puzzled for a wh~le about what should actually hap­ pen at subgoal vi"olation time. Our criteria were twofold: (1) that violations be detected at the earliest possible phase of synthesis, and (2) that as much as possible of the plan up to the violation point be salvaged.

The first criterion seems to be solved by the SC detection paradigm. The general motivation for early detection is that, during the earlier phase~, there is more fundamental knowledge about the how s and why's of the plan's construction. This makes possible both more accurate diagnosis of violations and more accurate analysis of the implications of plan rearrangement. The second criter~on of maximum plan salvage has more practical motivations, but also coincides with our intuition that human prob­ lem solving involves considerable salvaging and stitching together of plans.

Since the source of conflicts we are primarily considering is bad orderings, the repair of a con­ flict will amount to reordering parts of the plan in a way that avoids the conflict. The simplest and most obvious strategy would be simply to start over with a new order, possibly resynthesizing many gate and enablement suboals. This is not a . good approach, because it is inherently combinatorial, and because it duplicates effort. It would be more desirable to have a give-and-take arrangement wherein conflicts can be resolved by having one subgoal back off for a moment to allow the other subgoal to complete, then having the retreated.sub­ goal simply rejoin without having to resynthes~ze.

Our theory of correction follows these ideals. We call the technique that implements this give­ and-take strategy "unravelling". The unravelling scenario goes as follows (see figure below). Suppose gating state A has been achieved as a subgoal, and has been protected. Suppose that dur­ ing the synthesis of another brother subgoal B (e.g. a brother gate), A's guardian cluster is triggered, indicating that some state iust achieved in tfle partially completed synthesis of B has vio­ lated state A. The plan which leads up to A then unravels one level by reverting to the context which existed immediately prior to the attainment of A, i.e., the unravelling mechanism undoes the action which causes A. It then removes A, alleviat­ ing the immediate violation, and notes that it will have to reconstruct this last step in the plan leading up to A.

As A is unravelled, the gates on A's causal link and the enablements of A's causing action, once protected themselves during the earlier part of the synthesis, are re-firotected by reawakening their guardian clusters. T ese gates and their clusters are then melded into the current CQntext (i.e. that in which B is being synthesized}. Then B is al­ lowed to proceed. When B completes, A rejoins (n.b. A does not resynthesize, but rather simply closes in "around" the plan for B, which now has concep­ tually been spliced in) by reissuing the action which achieves state A. A's gates and enablements are then once again unprotected, and A itself is again protected. At that point, both A and B will coexist, permitting the synthesizer to get on with the next gate or enablement, or, in case all have been completed, issue the action at the level awaiting such a completion.

The semantics of this unravelling-rejoining are this: Ordinarily, brother subgoals do not have to know of each· other's existence. Ho1;ever, when one does something which is inimical to the other, they must at that point become aware of each other. By unravelling the first one a single level, we alle­ viate the immediate problem, but at that point also force pieces of the two goals (actually, the plans leading up to them) to coexist in the same context . T9is is because the process of unravelling A casts A s gates and enablements into the population of currently guarded states.

Unravelling is free to occur wherever and whenever it is needed to permit the current subgoal to pr.oceed. This means that one unravelling can set off other unravellings, e.g., that subgoal B mi~ht cause more than one unravelling inside of A's plan after being allowed to proceed past the first con­ flict, that the melding of A's prior context (i.e. its gating and enabl~ng states) into the existing context could in turn trigger an unravelling of part of B's plan, and so forth . All problems arise because of now having to force two brothers (or in the limit, distant cousins) which previously ~new nothing of each other to live in the same environment.

This give and take paradigm is, we feel, the best possible conflict resolution paradigm. At one end of the spectrum, unravelling amounts to one simple backof f, while at the other end of the spectrum, it can amount to multiple backoffs which in the limit amount to a complete reversal of all subgoals (i.e. each later one comes to be spliced in before former ones) . The important point (and the feature that we feel gives this approach elegance) is that only the unravellings that have to be done are actually done. There is no wholesale reordering of subgoals, and (conceptually) little overhead for conflict-free plans.

6. Example

lie now illustrate the theory via a simple blocks world example which conveys some of the subtleties of the unravelling process. Starting with an ini­ tial configuration as shown in Figure 1(a), we pick up the action as it stands in Figure 1(b), solving the goal (otl A H). The synthesizer has been able to construct a standard synthesis without any pro­ tection violations u~ to this point and is about to attack the subgoal (FREE-HAND) -- state 511.

First let us remark that there are two CSA links (shown to the right) in this graph that have not been previously mentioned in this paper. They are the "state-coupling" link, and the "gated one-shot byproduct" link. (See [R1], [R2] and [RG1] for a com­ plete coverage of the CSA links.) The state-coupling link connects two states

and implies that the state at its head can be con­ sidered to be true because of the truth of the state at its tail. The gated byproduct link is identical in syntax and semantics to the gated cau­ sality link. However1 the intent of the causality link distinguishes ~t fro~yproduct link, in that the state caused by the action on a byproduct link is not the state intended by the performance of the action, but merely a byproduct. Thus, the fate of a oyproduct state is irrelevant to plan synthesis and it need not be ?rotected. But· a by­ product state can cause a v~olation as decisively as any other state. Therefore, byproduct states must be treated as other achieved states with re­ spect to violation detection.

In attempting to solve the goal (ON A B), the synthesizer has set up subgoals (GRASPING A), (LOC HAHD B), and (CLEARTOP B). (GRASPING A) has been solved (its subgoals 53, 54, and 55 were already true in the initial configuration) by performing the action (GRASP A) . Similarly, the second sub-

goal1 56, has been solved by per­ form~ng action A3. (56 had no subgoals) . To this point, the -----~. Jsynthesizer has ~reposed an ac­ ~--' .. Jtion sequence (A ,A3).

The last subgoal to be solved is (CLEARTOP ll), 57. The action A4 can only achieve this goal after the subgoals 59, 510, and 511 have been solved. 59 is true because 56 is true and this fact is explicitly denoted by a state coupling link (built by the synthesizer). 510 is true in the initial configuration and nothing has negated it. Now the synthe­ sizer attempts to solve 511,

(FREE-HM~D). The currently protected states 52, 56, 59, and 510 are marked with '+' in Figure 1(b). Since 511 is a violation of the protected state 52, let us describe the steps taken by the synthesizer to complete this plan.

-- The action (A2) which causes the violated state (52) is unravelled. This leaves a new action se­ quence (A3). The context in which 52 's subgoals were protected is exhumed and melded in with the current context, yielding a set of protected states S3,S4,S5,S6,S9,S10. An item (S2.A2) is pushed onto an "unravel stack".

--A test for secondary violations is made (i.e. a test to determine whether any of the currently ac­ tive states (S6,S9,510) violate any of the newly reprotected states (53,54,55)). This is done in the order of the most recently solved state first (i.e. 510, then 59, then 56). The violation of 59 violating 53 is detected, 53 is unravelled, and its entry is pushed onto the unravel stack. The unravel stack now looks like: (S3.NIL), (S2.A2). The action entry for 53 is NIL because there is no action to be un.ravelled for 53. This tHL entry will 10ignify that the synthesizer must construct a plan tor S~ at the time 53 is rejoined. (The reason for this new synthesis is that 53 is no longer true -- that is why it was violated!)

-- No more secondary violations are detected and 511 can now be protected. Since all the subgoals

'-' DENOTES: UIIPROTECTED

'+' DEIIOTES: PROTECTED

NUMBERS IN NODES DENOTE SEQUEilCE OF ACTIOIIS

5.1. Context Requirements

When an unravelling occurs, previously protected states come to be unmasked and reprotected. The de­ mand on the context mechanism therefore is that it be able to revert to the context immediately prior to the first masking of those subgoals. As the re­ protection occurs and the prior context is exhumed, items from that context are melded into the ex­ isting ·context. This process can itself trigger other subgoal violations pending in· the current context. Although any given example can grow to be quite complex in its unravelling behavior, unravel­ ling seems to be a uniform process that eventually ~ettles down if, in fact, the initial goal itself ~s consistent.

Clearly, a pure chronological context mechanism (i.e. a stack) is inadequate for this scheme, since any prior context may eventually have to be exhumed. Our implementation of context lies be­ tween PLANNER and CO NIH VER in complexity, in that it is primarily chronological, but higher contexts are not discarded as tfiey are el(ited. AQBarently we do not require the full generality of C NNlVER ~ tree. (We are presently exploring the use of de­ pendencies as an alternative to the stack and tree-like context mechanism.)

INITIAL WORLD

(a)

Figure 1.

(b)

for S7 are no~ solved, these subgoals' guardian clusters can be hidden (by popping contexts), leav­ ing only states S4 1 S5,S6 ~rotected. The ac~ion A4 is appended to tne act~on sequence, y~elding (AJ,A4). A test must no~ be r.Jade to see if S7 or the byproduct state 58 cause a violation of any of the currently protected states.

-- It is detected that 58 violates SS. SS is unra­ velled, yielding an unravel stack: (S5.NIL), (53. tliL), (52. A2). No secondary violations need be considered since secondary violations are caused only by the reactivation of hidden guardian clusters. S5 has no subgoals and, thus, no guard­ ian clusters are reactivated. The action sequence r emains (A3~A4). The currently protected states are S4,S6,St.

-- Since subgoals of. 57 caused violations, The top' entry on the unravel stack, (SS.NIL), is_popped. If the action slot it is time t o start reJoin~ng . on the unravel stack entry is not NIL, the action is threaded onto the action sequence and the vio­ lated state is reprotected. In this case, the ac­ tion slot is UIL, so that there is no action to be threaded. Thus, the synthesizer is called recur­ sively to generate a solution to the goal S5. Of course, there is the possibility of a new prote~­ tion violation which is exactly what happens . ~n this case. fhe plan generated by the synthes~zer as a solution to (FREE-HANU), S5, involves state Sl2 and actions A6 and A7 as seen in Figure 2. A6 is threaded onto the action sequence (A3~A4,A6), but when a test is made to determine if Sl<: causes any violations, the contradiction between (LOG HAND FREE-SPACE) and (LOG HAND B) is detected. Since 56 was protected, a violation occurs.

-- As in this case, when a violated goal is state­ coupled to another, special care must be taken in unravelling. It should be recalled that the reason for the coupling is to denote the fact that, for example, S9 is true only because S6 is true. Thus, if we were to unravel 56 by splicing A3 out of the action sequence, then 59 \Wuld not have been true when we thought it was. The solution is to break the causal link between the unravelled action (A3) and the unravelled state (S6), and construct a causal link between the action and the coupled state (S9). This transformation is depicted below. State 56 is left without a causing action as its entry is pushed onto the unravel stack: (S6.NIL)i(S3.NIL),(S2.A2). The protected states are

-- The synthesis for S5 now continues with A7 being threaded onto the action sequence: (A3,A4,A6, A7). The guardian for (LOG HAND FREE-SPACE) is hidden and S6 can be rejoined.

""""'·f~ =~

-- The entry for 56 is popped off the unravel stack and the synthesizer is again called recursively to generate a new solution for (LOG HAND B). This process does not cause any further violations. Figure 2 displays the new plan; A8 is threaded onto the action sequence, yielding (A3,A4,A6,A7,A8). (LOG HAND B) is again protected and the synthesizer returns to the level that was solving S5.

-- S5 is reprotected, leaving the set of states S4,S5,S6,S7 protected. The synthesizer exits from this recursive call, returning to the level that ·was \larking on S 7 (remember?). It was at this lev­ el that 58 violated S3.

..

-- At this level, there are still two entries on the unravel stack; (S3.NIL),(S2,A2). Again, the first entry is popped off, the synthesizer is called recursively to take care of its NIL action slot, and then tests for violations~ detecting 53 violates 56. The new action, A~ (Figure 2), is threaded, and 53 is reprotected. If the synthesiz­ er were to return at this point and attempt to un­ ravel 56, we would run into a major problem; 56 and 53 would alternately violate one another indefi­ nitely. This is because unravelling 56 at this point violates the Golden Rule of Unravelling, namely, that an unravelled state cannot be rejoined until the state which violated it has been used as a subgoal, i.e. until it has been unprotected. (The complexities of the algorithm described here me rely serve the purpose of preserving the integri­ ty of the Golden Rule.) Thus if all the subgoals of an unravelled state (e.g. S~) have been solved, then that state must be rejoined. Therefore, the unravel stack entry for 52 is removed, A2 is added to the action sequence, S3, S4, and S5 are unpro­ tected, 52 is protected, and the synthesizer returns. The action sequence is now (A3~A4,A6,A7,AS,A2). The protected goals are 52,::. 7.

-- The last unravel entry (S6.A8) is popped. AS. is threaded onto the action sequence, . S6 is reprotected, and the synthesizer returns. The ac­ tion sequence is (A3 1 A4~A6,A7,A5,A2,A8). The pro­ tected goals are S2,So,St.

--The synthesizer has returned to the level of Sl, (UN A B). All of this goal's subgoals are solved, so its action, Al can be threaded onto the action sequence, and the truth of (ON A B) can be asserted.

The final result of this synthesis is the com­ plete plan representation of Figure 2 and an action sequence (MOVE-TO B), (GRASP C), (MOVE-TO FREE­ SPACE )f (PUT-DOWN C) 1 (HOVE-TO A), (GRASP A), (HOVE- 0 B), and (PUT-uOW!l A).

7. Advanced Subgoal Infringement Problems

We are beginning to consider some of the more sophisticated (but more common) problems of subgoal violation. One of the most tenacious of tfiese p,roblems, that of of "fuzzy violation" or 'infringement", requires the introduction of costs into what is otherwise a discrete, symbolic pattern matching annihilation detection facility. To illustrate sub~oal infringement in our everyday donain, consider the Battle of the Trousers scenario: :iost of us know that it is easier to put long pants on before shoes! Strictly speaking, putting the shoes on first does not violate the gating condition for pulling the pants on: "path is unobstructed". However, it certainly increases the cost of the subsequent operation. Sonehow, the synthesizer must have access to nominal efforts re­ quired for strategies, be able to halt synthesis whenever the nominal effort for some strategy seems to have been seriously exceeded, then identify and unravel the c.ulprit. We consider subgoal infringe­ ment to be an open topic.

H. Other Applications

The associative detection aspect of our design is applicable to certain forms of plan optimization as well as subgoal violation detection. One in­ terestin¥1 form concerns a process we call "object adoption · This is the process wherein the synthe­ sizer comnits itself to particular objects, times, locations, etc. in the instantiation of a plan in the concrete terms required for actual execution.

One instance of object adoption that provides an interesting example of SC-based plan optimization is that of free area selection. Consider the blocks problem illustrated below. A computer-wise mundane solution is to place B on the table! place A on B, attempt to place B on C, by c earing B's top, generating a subgoal violation, and proceeding as described above. The plan eventually gets built, but contains a superfluous intermediate location for B, namely the table. Clearly, the simpler solu­ tion would have been to place B directly on C in the first operation of clearing A's top, then placiog A~ B.@] CU ""~ 0<1\ Jfi_

The ~roblem here could have been avoided had the synthes1zer been willing to leave B's location "floating" after clearing A's top in the first step (i.e., to defer the object adoption). In our system, this can be accomplished by describing some features of B's location, together with a default recommendation, via a CSA descriptor:

(*D* X ((CLASS X AREA)

(XYSIZE X <the xy-size of the block>))

(REC (PART-oF X TABLE)))

and by delegating responsibility to this descriptor TOr eventually ensuring that it binds itself to some concrete object (a location in this case) be­ fore the end of the synthesis. This responsibility is phrased by associating with the descriptor an SC which will react to patterns (Otl B -X), since the descriptor is willing to commit itself to any -X.

How, each time the synthesizer is about to un­ dertake the synthesis of a subgoal, it first shouts at this population of "concretization" sc's, in es­ sence asking whether there are any floating refer­ ences which would make short shrift of the subgoal, i.e. obviate a standard synthesis. In this example, the synthesizer eventually shouts (OH B C) before .undertaking it as a subgoal. This shout ex­ cites our floating concretization SC, it responds affirmatively, committing itself at that point to C (since the tops of blocks are legitimate areas also), and, voila!, the synthesizer is spared the synthesis!

There are some other interesting forms of sub­ goal optimization in this fashion. A future report will treat them in more detail.

9. Discussion and Conclusions

We have presented a general theory of detection and correction for subgoal annihilation problems which stem from bad orderings. The theory is, we feel, efficient, uniform, and general. It is effi­ cient in the sense that it does only the minimum amount of work necessary to ameliorate annihilations, and does not incur resynthesis. It is uniform in the sense that it is a theory of con­ trol that will function with any suitably formatted problem solving representation (in our case, CSA cause-effect schemata). It is general in the sense that it does not rely on any sort of domain­ specific knowledge, with the possible exce~tion of having to know tne semantics of the system s predi­ cates when planting appropriate guardian clusters.

There are many complex issues of subgoal annihi­ lation that remain to be explored. One problem with any performance system such as ours is that it oft­ en has a myopic vie\/ of what it is doin~. There seems to be a need for "meta" watchers (SC s) whose responsibility it is to watch the overall detection-unravalling process for recurring pat­ terns of activity. Since our scheme is a form of relaxation, such an overseer would presumably in­ tervene when it perceived the unravelling to be looping (i.e. trying to solve an insoluble ordering problem), and so forth.

Other interesting problems have to do with bad strategy selection, as opposed to bad ordering. We have steered clear of this topic in this phase of our research, primarily because switching strate­ gies in mid-stream seems to call for more radical reconsideration of the total plan, possibly leading to partial or complete resynthesis. We do not pro­ pose to leave this problem at rest, only to side­ step it temporarily. In short, we will be working on our synthesizer for quite some time to come.

Acknow ledgr.~ents

We wish to thank the other members of the llaryland CSA group (t1ilt Grinberg, Hache Creeger, John Boose, and Georgy Fekete) for their participa­ tion in numerous discussions and for their suggestions. We wish also to thank NASA for the support of this research under Grant NSG-7253.

10. References

• [DK1] Davis, R. and J. King, An Overview of Production Systems, Stanford AIH 271, 1975.
• [Etll] Ernst, G., and Newell, A., GPS: A case ~tu~y in Generality and Problem SOIVing,--xca em c Press, 1969 ---
• [HS1] HcDermott, Drew V. and G.J. Sussman, The CONNIVER Keference Hanual. MIT AI Memo 259a, Jan. 1974.
• [N1] Nilsson, Nils J. i Problem Solving !1ethods in Artificial Intel igence. McGraw-H1II, 19~
• [R1] R1eger, C., An Organization of Knowledge for Problem Solving and Language Comprehension, Artificial Intelligence, vol. 7, no. 2, 19 lb.
• [H.2] Rieger, C., The Representation and Selection of Commonsense Knowledge for Natural Language Comprehension, Proc. Georgetown University Linguistics Roundtable, 1975.
• [R3] Rieger, c., Spontaneous Computation in Cognitive Hodels, to appear in Cognitive Science.
• [RG1] R1eger, c., and Grinberg, M., The Declarative Representation and Procedural Simulation of Causality in Physical Mechanisms, Proc. IJCAI-77, HIT, August 1977.
• [S1] Sacerdoti, Earl 1 The Nonlinear Nature of Plans, Proc. 4IJCAI, Tbilisi, USSR, Sept. 1975.
• [S2] Sussman, Gerald J., A Computer Model of Skill Acquisition. MIT AI-TR 297, Aug. 1973.
• [SW1] Sussman Gerald Jay and Terry Winograd., Micro-Planner Reference }~nual. MIT AI Memo 203, July, 1970.
• [T1] Tate, A., Interacting Goals and their Use, Proc. 4IJCAI Tbilisi, USSR, Sept. 1975.
• [W1] Waldinger, Richard, Achieving Several Goals Simultaneously, SRI Tech. Note 107, July, 1975.
• [W2] Winograd, Terry, Frame Representations and the Procedural-Declarative Controversy.._ in ReEresentation and Understandin~, u.G. Bo row and A. CoTTins, ed. Academ c Press, 1975.