Learning Planning Heuristics through Observation

1 Introduction

In the real world, tasks cannot always be accomplished by using simple sub-goal partitioning and recursive problem analysis. Both real world agents and narrative characters often must apply plans that require cooperation or information from other agents. A classification of real world plans is found in [Schank and Abelson, 1977]. A taxonomy of goal/plan interactions can be found in [Wilensky, 1978]. In addition, successful real world planners often use adages to guide them in avoiding bad plans. Adages warn against both specific and general planning errors. Poor Richard's Almanac [Franklin. 1733-1758] gives many examples of adages. such as "A stitch in time saves nine· (error avoidance), and "Don1 burn your bridges behind you: (error recovery) .

Dyer [1983a] showed how a class of planning errors could be represented by Thematic Abstraction Units (TAUs), and how these planning errors might be recognized in stories. This paper will present a representation for planning error recognition that also facilitates the combination of planning descriptions into new thematic structures. The combination method requires an example narrative situation that contains a new planning error. The example is conceptually analyzed to discover whether known planning errors, present in the story, can be combined into new structures.

In addition to the representations for TAUs, goals, and plans mentioned above, the examples here also rely on Schank's Conceptual Dependency theory [Schank, 1972]. Other relevant work on memory organization includes [Schank, 1982], [Kolodner, 1980], and [Lebowitz, 1980].

2 An Example Planning Situation

Here we will see a planning situation that contains three planning errors whose descriptions are already known to the system. From this situation we will see how we can generate two specializations of planning errors, and one novel planning construct. This situation is an Aesop's fable".

The Fox and the Crow

The Crow was sitting in the tree with a piece of cheese in her mouth. The Fox walked up to the bottom of the tree and said to the Crow, ·crow what a beautiful voice you have; please sing for me." The Crow was very flattered and began to sing. When she did, the cheese dropped out of her mouth. The Fox grabbed the cheese and ran away laughing.

This work was supported in part by a grant from the Hughes Aircraft AI Center and a grant from the Keck foundation. This worK was also supported in part by the UCLA Center for Experimental Computer Science.

··Other work dealing w~h Aesop's fables is TALESPIN [Meehan, 1979] a program which generated stories by simulating a character's planning and problem-solving behavior. TALESPIN, however, lacked a theory of planning errors and had no sense of the moral of the story.

Learning Planning Heuristics through Observation·

Charles Dolan Artificial Intelligence Lab Computer Science Department UCLA and Hughes Aircraft AI Center

Michael Dyer Artificial Intelligence Lab Computer Science Department UCLA

Note that this story can be looked at in two ways: 1) as an instance of bad planning on the part of the Crow and 2) as an instance of good planning on the part of the Fox. The is an instance of planning errors as counter planning as defined in [Carbonell, 1979].

The first of the three planning errors we will discuss is the simplest. When the Crow sings, she does not realize that she is already using her mouth to hold the cheese. This planning error is characterized at an abstract level by TAU-CONF-ENABL (confused enablement). The full representation for TAU-CONF-ENABL is given below.

In each TAU, the representation of a planning error consists of two parts: (1) the binding-spec: a list of conceptual patterns which occur in the story; (2) the constraints : a list of logical constraints among the patterns occurring in the binding-spec and other concepts from the story.

TAU name TAU-CONF-ENABL 1 binding-spec 2 [?standing-goal (P-GOAL actor ?x 3 obj (POSS-BY actor ?x 4 5 6 7 8 9 10 11 12 13 manner FAIL) ] [?interfering-goal2 (GOAL actor ?x)] [?mistake (ACT actor ?x)] constraints obj ?y) intention(?interfaring-goal,?plan), realization(?mistake,?plan), resulting(?mistaka,?disabling-state), achievement(?desirable-state,?standing-goall). disablement(?disabling-stata,?desirable-state) .

The abstract situation this structure characterizes is one where an agent has a goal, ?standing-goal, which has failed and where the goal was to preserve possession of some object. The cause of the goal failure is an act, ?mistake, which attempted to accomplish another goal, ?interfering-goal.

The representation presented here enables us to create new TAUs from existing ones. The processes of recognizing and indexing TAUs are covered more fully in [Dyer 1983] and [Dolan 1984]. [Dolan 1984] also covers the comprehension process model which allows the recognition of TAUs in this format when planning errors are encountered in stories.

As we mentioned above, The Fox and the Crow instantiates two other TAUs: (1) TAU-VANITY is the planning error of allowing personal vanity to dictate plan choice; (2) TAU-ULTERIOR is the planning error of not considering another agent's possible motives before acting. Both of these TAUs display an important characteristic of TAUs as planning heuristics; not only do TAUs provide admonitions against bad planning, but they can also be turned around and used as plans to try and force other agents into situations where thsy will make mistakes.

These TAUs can be combined to form new planning heuristics. There are two key problems in TAU acquisition: (1) How does a program know which TAUs to select and examine for combination attempts; and (2) Once selected, how are TAUs actually combined to form new planning and indexing structures?

Both (1) and (2) are non-trivial. A sophisticated planner will know many stories each indexed by multiple TAUs. Attempting to combine TAUs arbitrarily would lead to combinatoric problems. Fortunately, memorable stories (such as Aesop's fables) are designed to give novel planning advice through illustrating planning errors. Thus, TAU selection can be governed by the following strategy:

WHENEVER two TAUs share concepts in an observed planning situation, TRY to combine them to form a novel planning construct

This heurist ic can only be applied after reading a story. The comprehension of the story thus makes available TAUs for combination and indicates which concepts are shared.

There are two ways to combine TAUs based on the way they share concepts: (1) specialization and (2) combination (chunking).

Recent work in specialization learning includes [DeJong, 1983) and [Kolodner, 1980). Both workers formulate methods for creating new planning knowledge through specialization. Most research in learning by chunking has been in domains where there is no counterplanning [Laird, 1984). However there are some element of chunking in DeJong's work and in Mitchell's [Mitchell , 1983).

3 Creating New TAUs through Specialization

The type of sharing which exists between TAU-UL TEROR and TAU-CONF-ENABL is called containment . In order to see how containment works, examine the representation for TAU-ULTERIOR given below,

TAU nama TAU-ULTERIOR 1 binding-opec 2 [ ?otanding- goal (GOAL actor ?x 3 otatuo FAILED) ] [?daoirabla-atata (STATE)] 5 [ ?mtrano (MTRANS actor ?y 6 to ?x 7 obj ?z)] [?miotaka (ACT actor ?x)] 9 conatrainta 10 achiavamant(?deoirabla-otata,?otanding-goal), 11 motivation(?z, ?intarfaring-goal) , 12 achiavamant(?miotaka, ?intarfaring-goal) , 13 dioablaa(?miotaka, ?deoirabla-otata), 14 goal-conflict (?goal, (GOAL actor ?y 15 obj ?v)) , 1 6 achievement ( ?miotaka, (_GOAL actor ?y 17 obj ?v)) , 1B unaxpectad(?mtrano,?miotake) .

TAU-ULTERIOR represents the situation in which ?y tells ?x information that motivates x to perform an act which results in the disablement of one of x's goals, while at the same time achieving a goal of ?y's which ?x did not forsee.

One constraint above needs some additional explanation. The last constraint, unexpected ( ?mtrano , ?miotaka), states that there is no short causal inference chain from the information told (?mtrano) to the disabling act (?miotaka). In the current implementation of this model a "short" inference chain is one formed by the application of a single inference rule·.

By looking at the bind-opec for both TAUs the reader will see that TAU-ULTERIOR contains all the concepts from TAU-CONF-ENABL. Thus we can form a new TAU which is a specialization of TAU-ULTERIOR.

The new TAU is formed by taking the extra constraints from TAU-CONF-ENABL ("extra" meaning those not already in TAU-ULTERIOR) and conjoining them with those in TAU-ULTERIOR. This creates new planning advice specific to possession goals and ulterior motives. For more details on forming TAUs thourgh specialization the reader is directed to [Dolan and Dyer~ 1985).

4 Creating New TAUs through Combination

As we saw above, we can get a non-trivial specialization of a TAU by discovering containment in a particular situation. In general, however, neither TAU contains the other. In these cases we must examine the relationships or constraints among the concepts not shared between the two TAUs. For an example, consider TAU-VANITY. The representation for this TAU is given below.

TAU nama TAU- VANITY 1 binding-opec 2 [?belief (KNOW actor ?x 3 obj (APPRAISAL obj (BODY-PART owner ?x) 4 value GOOD))] 5 6 [?otanding-goal (GOAL actor ?x otatuo FAILED)] [?interfering-goal (GOAL actor ?x)] B [?miotake (ACT actor ?x)] 9 conotrainto 10 intantion(?intarfaring-goal, ?plan), 11 raalization(?plan, ?miotaka), 12 anablamant((APPRAISAL obj (BODY-PART actor ?x) value GOOD) , 13 14 ?miotaka), 15 thvarting(?miotaka, ?otanding-goal) .

TAU-VANITY represents a situation in which ?x believes he has a special skill' and is thus motivated to have a goal (of "showing off" in The Fox and Crow story) which will interfere with pre-existing goals.

TAU-ULTERIOR shares a number of concepts with TAU-VANITY. The concepts which the two TAUs share in The Fox and the Crow are, ?otanding-goal, ?miotaka , and ?interfering-goal .

A novel TAU we can learn by combining TAU-VANITY and TAU-ULTERIOR is TAU-SUCKERED. The representation for TAU-SUCKERED is given below.

1 2 3 5 6 B 9 10 11 12 13 14 15 16 TAU nama TAU-SUCKERED binding-opec [?otanding-goal (GOAL actor ?x otatuo FAILED) ] [?interfering-goal (GOAL actor ?x)] [?act (ACT actor ?y)] [?miotaka (ACT actor ?x)] conatrainta intantion(?intarfaring-goal, ?plan), raalization(?plan,?miotaka), thvarting(?miotake, ?otanding-goal) , achiavamant(?miotaka,?intarfaring-goal) , anablamant(?plan,?oub-goal), raoulting(?act , ?otata) , achievement(?otate, ?oub-goal), goal- conflict (?otanding-goal, (GOAL actor ?y obj ?v)) 17 achievement (?miotaka, (GOAL actor ?y 18 obj ?v)) 19 not-obvioua-reault(?act , ?miatake).

TAU-SUCKERED embodies the planning failure of allowing someone else to take advantage of your dormant goals by providing one of the missing enablement conditions on that goal. In the case of The Fox and the Crow the dormant goal is the Crew's goal to show off. The missing enablement condition is a receptive audience. The Fox provides that audience and so tricks the Crow into defeating her standing goal of keeping the cheese.

Clearly there are many ways (structurally) of combining TAU-VANITY and TAU-ULTERIOR. Only one (or perhaps a few) will turn into an "interesting" TAU such as TAU-SUCKERED. If so, then how is it that just the right concepts get combined? The process of combining TAU is called "justification". There are a set of heuristics for jus@cation given in next section.

The representation for "skill" presented here is greatly simplified.

In order to dynamically construct TAU-SUCKERED, there are two major steps. The first is to find the concepts which are common to the binding-apeca of both TAU-VANITY and TAU-ULTERIOR, namely, ?atandinq-qoal, ?interfering-goal, and ?miatake .

These concepts are included in the binding-spec for the new TAU, lines 2-4 and 8 in TAU-SUCKERED. Also, constraints that involve only these concepts and free variables are included in the conatrainta part of the new TAU, lines 8-11 in TAU-SUCKERED. The second step is to take the remaining concepts from the binding-specs and justify them; that is, make sure they are accounted for either in the new binding-apec or in the conatrainta.

5 Justification

In this example the concepts which are not shared are ?deairable-atate and ?belief from TAU-VANITY and ?mtrana from TAU-ULTERIOR. Justification takes a concept from one TAU and finds out where it fits in the causal structure for the instantiation of the other TAU.

First ?deairable-atate is found to be already subsumed by constraint number 10 of TAU-SUCKERED. This is so because an ACT which thwarts a goal may negate a state that previously achieved the goal. In this case, the craw's singing thwarts her goal of keeping the cheese because it negates the state of having her mouth holding the cheese.

The achievement condition is found in constraint 10 of TAU-ULTERIOR. The heuristic which is used here is,

IF a constraint can possiblly subsume concepts, TRY matching the constraints on subsumed concepts against those in the component TAUs.

All that is left is to justify ?belief and ?mtrana. Intuitively what we want to see is a causal relation established between ?belief, the Crow thinking she has a good voice, and ?mtrana, the Fox's flattery of the Crow. Further we want to see ?belief as an enablement condition on the Craw's dormant goal to show-off.

One thing to note here is that the intention relation is transitive. The rule for intention transitivity is represented as in the figure below.

The system knows which relations are transitive, and can look up the particular kind of transitivity for a relation, i.e. what the intermediate relations are. Thus, another heuristic for justifying concepts is:

IF a transitivity rule was applied in satisfying a constraint of 'TAUt' TRY opening up the transitive path and look for concepts of 'TAU2' that need to be justified

In this case we see that the transitive path is in constraint (line 1 0) from TAU-VANITY which is reproduced as constraint (line 8) in TAU-SUCKERED, so a new constraint (line 12) is added to TAU-SUCKERED for sub-GOAL. In the story this represents the fact that, in order to show off, a character must believe he has something to show-off; the Fox flattering the Crow provides this enablement condition. The satisfaction of this enablement condition is given in lines 14-15 of TAU-SUCKERED.

The constraints in lines 14-18 are added because they meet various criteria for relating concepts in the binding- spec. For a detailed discussion of these criteria see [Dolan and Dyer, 1985].

The result of this constraint analysis is the creation of a new TAU, TAU-SUCKERED, which represents someone being fooled into having a goal failure by being motivated to satisfy another, currently dormant, goal. This TAU serves as a new indexing structure for The Fox and the Crow story and is now available for use in future planning and comprehension tasks .

6 Progress and Future Work

A program, CRAM, is under development as part of this research. Currently, CRAM is able to understand stories that are input as unconnected Conceptual Dependency [Schank 1972] structures. CRAM finds the planning errors in each story and characterizes them in terms of one or more TAUs. These TAUs are then used to index the story in memory for later retrival.

In the future CRAM will be able to give advice to correct characters' planning errors. Also planned for CRAM are a natural language parser and generator so that CRAM can take in stories as verbatim input and later generate English explanation of new TAUs it has discovered.

7 Conclusions

The approach presented here allows both specialization learning and chunking learning of planning errors in multiple planning agent domains. The structures learned can be used both for critiquing plans and also for generating counterplanning advice.