ARI Research Note 87-50

N~ LEARNING BY EXPERIMENTATION

Jaime G. Carbonell

Carnegie-Mellon University

DTIC

ELECTE

I DEC 08 S87

for

Contracting Officer' s Representative

Judith Orasanu

BASIC RESEARCH LABORATORY

Michael Kaplan, Director

M FAI

U. S. Army

Research Institute for the Behavioral and Social Sciences

October 1987

Approved for public release; distribution unlimited.

87 1 1
U. S. ARMY RESEARCH INSTITUTE

FOR THE BEHAVIORAL AND SOCIAL SCIENCES

A Field Operating Agency under the Jurisdiction of the

Deputy Chief of Staff for Personnel

WM. DARRYL HENDERSON

EDGAR M. JOHNSON COL, IN

Technical Diector Conuading

Research accomplished under contract

for the Department of the Army

Carnegie-Mellon University

Ace~i For

Technical review byCR&

Dan Ragland Uric 1A3 1

U; . a -- )- :

IThis #*Port. as submitted by the Contractor. has been cleared for release to Delene Technical information Center 4DTICI to Comply With regulatory requitrmeni. it has been given no Primary distribution other than to OTIC and -ell be available only through DTIC or other reference services such as te National Technical Infotion service (NTIS I. The viccws cpjnii ns. arse/Iof findings contained in this report are those of the authorl and should nOt be C~rssrueu as An Offe#Cis; Department of the Army Position. policy. or decision. unless so designated by other official documeintation.
UNCLASSIFIED_ _ _ _ _ _

SECURITY CLASSIFICATION OF THIS PAGE (Uhen Data Efnterd __________________

REOTDCMNAINPAGE READ INSTRUCTIONS REPOR DOCMENTTIONBEFORE COMPLETING FORM

1REPORT NUMBER 2.GOVT ACCESSION No. 3. RECIPIENT'S CATALOG NUMBER

4. TTLE and ubtile)S TIPE OF REPORT &PERIOD COVERED

In erim Report

LEARNING BY EXPERIMENTATION January 86 - January 87

6. PERFORMING ORG. REPORT NUMBER

7. AUTNOR() S. CONTRACT OR GRANT NUMSER(.)

Jaime G. Carbonell MDA93-85-C-0324

9. PERFORMING ORGANIZATION NAME AND ADDRESS 10. PROGRAM ELEMENT. PROJECT, TASK

Carnegie-Mellion University AREA A WORK UNIT NUMBERS

Computer Science Department 2Q161102B74F

Pittsburgh, PA 15213

11. CONTROLLING OFFICE NAME AND ADDRESS 12. REPORT DATE

U.S. Army Research Institute for the Behavioral October 1987

Social Sciences, 5001 Eisenhower Avenue, 13. NUMBER OFPAGES

Alexandria, VA 22333-5600 13

14. MONITORING AGENCY NAME & ADORESS(If different from Controllind Office) 1S. SECURITY CLASS. (of this report)

Unclassified

IS. DECL ASSI FIC ATION/ DOWN GRADING SCHEDULE n/a

16. DISTR18UTION STATEMENT (of tisl Repott)

Approved for public release; distribution unlimited.

17. DISTRIBUTION STATEMENT (of the abstraect entered In Block 20. if different from Report)

III. SUPPLEMENTARY NOTES

Judith Orasanu, contracting officer's representative

19. KEYW!ORD otilue anu reverse side it necessary and Identify by block nu mb er)

:;oirificial Intelligence Planning

Machine Learng 0 PRODIGY

xperin

,Problem Solving dg21L AUSTRACT (Catfm M eyfm side it ,ueeey md ideriifr by block nembetI

,-This research inote, addresses the issue of learning by experimentation as an

integral component of PRODI-GYa a flexible planning system augmented with

capabilities for execution mon-itomij and dynamic replanning upon adverse

feedback. A detailed example of inte~va.te.d experiment formulation is presented

as the basis for a systematic approach ieto ending an incomplete domain theory

or correcting a potentially inaccurate one. -

DI 'j~1J75 3 EDTornoo I Nov 65 is OBSOLETE UNCLASSIFIED

1 SECURITY CLASSIFICATION OF' THIS PAGE (When Data Entered)
1. Introduction: The Need for Reactive Experimentation

l.earning in the context of problem solving can occur in multiple different ways. ranging from macrooperator formation [7, 16, 51 and generalized chunking [91. to analogical transfer of problem solving strategies

[3.41 and pure analytical or explanation-driven techniques [17, 6, 14]. All of these techniques, howcver. focus

on the acquisition of control knowledge to solve problems fastcr, more effectively, and to avoid pitfalls

encountered in similar situations. Ncwly acquircd control knowledgc may be cncodcd as prcferred operator

sequences (chunks and macroopcrators). improved heuristic le-hand sides on problem solving opcrators (as

in I F.X 1181). or explicit search-control rulcs (as in PROI)IGY [14Dl.

However important the acquisition of search control knowledge may be, the problem of acquiring factual

domain knowledge and represcnting it effectively for problcm solving is of at least equal significance. Most

systems that acquire new factual knowlcdge do so by some form of inductive generalization', but opcratc

independently of a goal-driven problem solver, and have no means of proactive interaction with an external

environment (with the exception of some work in robotics learning and the world modelers project [1).

When one observes real-world learners, ranging from children at play to scientists at work, it appears that

active experimentation plays a crucial role in formulating and extending domain theories, whether everyday

"naive" ones, or formal scientific ones. Many actions are taken in order to gather information and learn

whether or not predicted results come to pass, or unforeseen conscquences occur. Of course, experimentation

can yield search control preferences, as well as factual knowledge, as we see in our later example.

In order to endow a problem solver with the capability to experiment on the external world, we start by

interleaving planning and execution monitoring, so that external feedback is immediate. If the plan does not

unfold as expected (e.g., unforeseen interactions take place, actions have unexpected consequences, etc.) the

system rcplans dynamically using better-known methods, or suspends planning in order to determine the

source of the discrepancy. Here is where experimentation is triggered: divergence from expected results that

interfered with carrying out a plan for the active goal. The objective of the experiment is to augment the

domain theory (e.g., record previously unknown consequences, after determining what conditions are needed

to bring them about), or to correct that domain theory (e.g.. deleting or altering the expected effects or

applicability conditions of operators, in order to force the internal model to accord with external reality).

Fxperimentation is used to isolate the cause of each discrepancy, and make the minimal modification possible

to the internal model in order to establish external consistency. Moreover, this meaprinciplc of "cognitive

inertia" dictates that monotonic changes (adding new information) be preferred over non-monotonic ones

(changing previous information) if both are of equivalent scope.

rllecadcr it rnf(rred to the two efent machn e karning broia for v'erl good ezampIcs of inductivc mcthodnoies and systems

buift upon them 112. 13).

.1
2

The rest of this paper describes the experimentation methods under development in a simplified version of

the PRODIGY problem solver [IS] by tracing their operation on an example planning problem. Whereas

PRODIGY is a complete working problem solver, and other learning techniques such as explanation-based

specialization for the analytic acquisition of control knowledge have been fully implemented, the

experimentation techniques are in the midst of development, and are only partially functional as of this

writing.

2. Background: The Role of Experimentation in PRODIGY

The PRODIGY system [15, 14] is a general-purpose planner at CMU that serves as the underlying basis for

much machine-Icarning research. In essence. PRODIGY learns incrementally through experience in solving

increasingly more complex problems in a task domain, and gradually transitions from naive student, to

apprentice, to journeyman, and eventually (we hope) to domain expert. "lhus far we have experimented

successfully with a version of cxplanation-bascd learning (FBI.) [171 that can learn from failed instances (to

avoid future failures that share the same underlying cause), as well as the standard EBL based on deductively

provable generalization from positive instances. We are also studying the role of case-based learning in

PRODIGY, and are exploring interactive knowledge acquisition from a domain expert who looks over the

shoulder of the planning system, making concrete suggestions on the current plan being synthesized, and

occasionally providing more general advice.

"his paper focus on learning by experimentation, with three primary objectives:

" Experimentation to acquire and refine control knowledge - When multiple sequences of actions

appear to achieve the same goal, experimentation and analysis are required to determine which

plan is the most cost-effective or robust one, and to generalize and compile the appropriate

conditions so as to formulate the preferred plan in future problem solving instances where the

same goal and relevant initial conditions are present. Thus, experimentation may be guided

towards producing far more effective use of existing domain knowledge.

" Experimentation to augmeat an Incomplete dommin theory - Experiments may be formulated to

synthesize new operators, learn new consequences of existing operators or determine previously

unknown interactions among existing operators. Also, performing known actions on new objects

in the task domain in a systematic manner, and observing their consequences, serves to acquire

properties of these new objects and classify them according to pragmatic criteria determined by

the task domain. Thus, experimentation may be guided towards acquiring new domain

knowledge from the external environment.

" ExperimenaMtim to refine an Incorrect domain thewry - No comprehensive theory is ever perfect,

as the history of science informs us, whether it be Newton's laws of motion or more ill-structured

domain theories embedded in the knowledge bases of expert systems. However, partially correct

theories often prove useful, and arc gradually improved to match external reality (and are

occasionally totally replaced by a newer conceptual structure). Here we deal only with minor

errors of commission in the domain theory, which when locally corrected improve global

- * - - " 
3

performance. We believe automated knowledge refinement is a very important aspect of

autonomous learning not hcretoforc invcstigatcd in At. and one where success is potentially much

closcr at hand than the far morc difficult and scldomly cncountercd phenomenon of formulating

radically new theories from ground zero. Thus, experimentation may be guidcd at incrcmental

correction of a domain theory. 2

Wc start with the hypothesis that a universal mcthod to direct cxperimcntation exists in thc acquisition of

both domain and control knowledge - since are developing precisely such a method, as illustrated in our

worked-out example below. The central thesis is that experimentation is invoked when missing domain

knowledge prevents the fonnulation of a plan to solve the problem at hand; thus "idle curiosity" is not our

target. Moreover, the entire planning context is used to formulatc and guide the experiment, in order to focus

on the most direct and economical way of inferring the missing knowledge. Finally, concessions must be

made to other protectcd goals in the course of the cxpcrimentation: assuring safety of the experimenter. not

consuming a resource in the experiment that will be required to carry out the rest of the plan, etc. Thus,

experiment formulation, once invoked with the appropriate constraints, becomes itself a meta-problem

amenable to all the methods in the general purpose planner. The EGL method (or perhaps a similarity-based

method - SBL) may then be invoked to retain not just the result of the instance experiment, but its provably

correct generalization (or empirically appropriate one if SBL is used).

3. The Base-Level System: Knowledge Required for Planning

Considcr an examplc domain of expertise: crafting a primary telescope mirror from raw materials (such as

pyrex glass, pure aluminum, distilled water, etc.) and pertinent tools (such as grinding equipment, aluminum

vaporizers,3 etc.). The operators in the domain include: GIND-CONCAVE, POLISH, ALUMINI7., and CLEAN.

A complete domain theory would include, in addition to these four operators themselves, knowledge of:

* all the relevant preconditions for each operation to proceed successfully,

" all the consequences of applying each operator (stated as changes to the global world state),

" and all the objects to which these operators may be applied to achieve the desired effects (for

instance. wood may be ground into a concave shape, but the result would not be an optical-quality

telescope mirror).

2

We ante that a iogally bmeon'c theory. requiring wholesale reconceptualittion, will not be addressed b)' our incrementa methods.

Sudh a paradigm itift. is Kuhn would call it Ill. requires a difTerent approacl, one along the lims of the more futuristic work in Machine

D [stemy 110, 11).

3Aluminum is placed on the prnurry reflecting surrace of a glass mirror blank by placng the blank in a vacuum chamber and passing a

tron current through a thin pure aluminum strip. which then vapuites and is deplited evenly, several molecules thick, oti the glass

surface to produce optiml-quality minors. For implicity in our discussion, thes details of the aluminizing proes are supprasd. as are

iternal details of the grnding and polishing process. I lence. though the domain we have chow is very much a real one. we ducut. it at

uitable level of abstraction and simplication.

!.." '', '... . .
4

In addition to the domain theory, an optimal-performance system needs to know control rules (hard and

fast ones, as well as heuristic ones). These rules perform the following tasks:

* When multiple goals are present, determine which goals to work on first - or which ones to work

on at all. For instance, if the goals is-polished and is-ground-concave arc both present. it is better

to work on the latter first so as not to undo polishing by later grinding. Similarly, if the goal of

reduce-weight of the glass and is-ground-concave arc both present, it may prove unnecessary to do

more than grind, as that reduces weight as a sidc-effect of grinding away some of the glass in the

process of making it concave. Such interactions have been investigated before, albeit if not in a

very systematic manner [20, 2,21]. Herc we arc focusing on an integrated architecture to acquire

knowledge of plan interactions through ohscrvation of the consequences of its actions on ihe

external environment, and when necessary through focused experimentation.

* When multiple operators may be chosen in order to make progress towards the active goal,

determine which one(s) to apply. This is the standard role of a heuristic evaluation function 119],

but we propose to do the selection by compiling explicit symbolic reasoning, rather than a-priori

numerical metrics. The notion of learning operator preferences in the context of an active goal

was the central task of I.EX [181. and is one of the major effects of chunking and universal

subgoaling in SOAR (9]. At one end of the spectum one can view a string of purely deterministic

preferences as equivalent to a linear macro-operator 17, 16, 5], and at the other extreme as guiding

search in preferential directions based on past experience.

* When multiple objects may be chosen on which to apply the operators, determine which one(s) to

select. Again, these can be categorical (polishing and alureinizing the wrong surface of a mirror

will never yield desired results) or preferential (choosing a fast rough-grinding tool, vs choosing a

slow fine-grinding one, vs choosing both - the former for rough shaping, followed by the lauer

for fine adjustment). Preferences may be stated in terms of achieving higher quality plans (more

efficient ones to execute, or ones more likely to succeed), or in terms of minimizing planning

effort (producing a working solution quickly, even if it may be far from an optimal plan).

4. Learning by Experimentation: A Detailed Example

Let us return to our telescope mirror example, and assume that we have only a partial domain theory and

virtually no control knowledge. How can PRODIGY through its attempts to solve the problem learn to plan

better the next time? Can learning be improved by formulating subtasks just fbr the sake of acquiring

knowledge, in addition to pursuing externally-given tasks? Suppose we start with the following (greatly

simplified) knowledge base:

p ~ *

! 4
OPERATORS PRECONDITIONS CONSEQUENCES

1) GRIND-CONCAVE(<obJ>) ISA(<obj>. solid) IS-CONCAVE(<obj>)

2) POLISH(<obj>) ISA(<obj>, glass) IS-POLISHED(<obj>)

IS-CLEAN( <obj>)

3) ALUMINIZE(<obJ>) IS-CLEAN(<ob>) IS-REFLECTIVE(<obj>)

ISA(<obJ>. solid)

4) CLEAN(<obJ>) ISA(<obj>, solid) IS-CLEAN(<obj>)

INFERENCE RULES:

1) IS-REFLECTIVE(<obJ>) & IS-POLISHED(<obj>) --> IS-MIRROR(<obJ>)

2) IS-MIRROR(<obJ>) & IS-CONCAVE(<obj>) --> IS-TELESCOPE-MIRROR(<obJ>)

Given the operators and inference rules above, let us suppose that the goal of producing a telescope mirror

arises, and we have a glass blanks and a wood pieces to work with, none of them with clean or polished

surfaces. PRODIGY starts backchaining by matching the goal state against the right hand side of operators

and inference rules, concluding that in order to make a telescope mirror it should first make a mirror, and

then make its shape concave. Then seeing how to make a mirror, it concludes that it should make it reflective

and then polish it (by matching IS-MIRROR against the right hand side of the second inference rule). Let us

assume for now that PRODIGY correctly selected the glass blank (it was listed first) as the starting object.

Now it must apply the operator ALUMINIZE to the glass, which requires that it be a solid (see figure 2 for

the object hierarchy), and that it be clean. The first precondition is satisfied (glass is a solid), and the second

one requires applying the CLEAN operator, which succeeds because any solid thing may be cleaned. These

successes enable the ALUMINIZE operator to apply successfully, and go on to the next goal in the

conjunctive subgoal set: IS-POLISHED (again, see figure 1). Thus far, there have been no surprises and no

learning, just locally successful perfomance.

However, whereas PRODIGY believed that the POLISH operator preconditions were satisfied (it believes

In temporal persistence of states, such as IS-CLEAN, unless it learns otherwise), the environment states the

contrary: the glass is not clean. The first learning step occurs in the attribution of this state change to one of

the actions that occurred since the state IS-CLEANED was brought about. Since there was only one

intervening operator invocation (ALUMINIZE), it infers that a previously unknown consequence of this

operator Is -IS-CLEAN (meaning retracting IS-CLEAN from the current state). If there had been many

intermediate operators, specific experiments to perform some but not other steps would have been required to

Isolate the culprit operator. After applying the CLEAN operator once more, it again attempts to POLISH,

i ill l
6

but the operator does not result in the expected state IS-POLISH-D. This means that either it is missing

some knowledge ( ome other precondition for POLISH is required), or its existing knowledge is incorrect

(IS-POLISHED is not a consequence of POLISH). Always preferring to believe its knowledge correct unless

forced otherwise, it prefers to examine the former alternative. But. how can it determine what precondition

could be missing?

Well, time to formulate an experimcnt: Arc there other objects on which it could attempt thc POI.ISH

operation? The only possibilities are un-aluminized dirty glass blanks, and dirty wood blanks. It can only

polish glass (see the precondition table), and all the glass blanks are identical to each other, but different from

the current object in that they are both dirty and unaluminized, so it choses a glass blank. After cleaning it,

the POLISH operator succeeds, and once again it must establish a reason for the operator succeeding this

time, but failing earlier: the only difference is the glass not being aluminized. Thus a new precondition for

POLISH is learned as a result of a simple directed experiment: -IS-REFLECTIVE(<OBJ)), meaning that

once coated with aluminum, it cannot polish the substrate substance.

Now back to the problem at hand. In order to POLISH the glass it must unaluminize it, but there is no

known operator that removes aluminum.4 So the IS-POLISHED subgoal fails, and failure propagates to the

IS-MIRROR subgoal, with the cause of failure being that the IS-REFLECTIVE prevented POLISH from

applying. Here one may apply a criterial subgoal-ordering heuristic:

If the cause of failure of one conjunctive subgoal is a consequence of an operator in an earlier

subgoal in the same conjunctive set. try reordering the subgoals.

That heuristic succeeds by POLISHing before ALUMINIZing. Having obtained success in one ordering and

failure in another, the system tries to prove to itself that this ordering is always required, and succeeds by

constncting the proof: ALUMINIZE will always produce IS-REFLECTIVE which blocks POLISH, and

since there are no other known ways to achieve IS-POLISHED, failure is guaranteed. The present version of

PRODIGY is capable of producing such proofs in failure-driven EBL mode. Thus, a goal-ordering control

rule is acquired for this domain: always choose POLISH before ALUMINIZE, if both are in the same

conjunctive goal set and both are apply to the same object

Now, once again, back to the problem at hand. The system succeeded in producing a mirror, but now

needs to make it concave. The only operator to make IS-CONCAVE true is GRIND-CONCAVE. Its only

precondition is thai the object be solid, and so it applies. At this point the system checks whether it finally has

achieved the top-level goal IS-TELESCOPE-MIRROR, and discovers (much to its dismay, were it capable of

41f dfs domain knowledge were grater. it would know that grinding would remove aluminum and well as changing the shape and

removing wrfacc polish. In faCL this knowledge is acquired later in the exuamplc, as an unonunatc side cffect oraucmpin to make a nai

iwnror ooncave by Srnding it.

1 6, A
emotions), that all its work on POLISHing and ALUMINIZing has disappeared. The only operator that

applied since the mirror was polishcd and aluminized was GRIND-CONCAVE. and so it learns two new

consequences for GRIND-CONCAVE: -IS-POLISHED and -IS-REFLECTIVE. No explicit experiment

was nccded as only one opcrator (GRIND-CONCAVE) could have caused thosc changes. At this point

PRODIGY would spawn off the subgoal to make the concave glass back into a mirror, and all that it learned

when making the flat glass into a mirror applies (POLISH before ALUMINIZE, ctc.) producing the plan

more efficiently. Finally, the top level goal of IS-TELESCOPE-MIRROR is achieved.

The learning system, however, is seldom quiescent, and though global success was achieved, some states

(IS-MIRROR, IS-REFLECTIVE, IS-POL[SIIED, IS-CLEAN) had to be achievee multiple times.

Retrospective examination of the less-tLhan-optimal solution suggests that another goal reordering heuristic

applies:

If a the result of a subgoal was undone when pursuing a later subgoal in the same conjunctive se& try

reordering these two subgoals.

So, PRODIGY goes off and tries the experiment of achieving IS-CONCAVE before achieving IS-MIRROR,

resulting in a more efficient plan.5 A proof process would again bc invoked to determine whether to make it a

criterial reordering rule, concluding that it is always better to achieve IS-CONCAVE first. "he chart below,

summarizes the new knowledge acquired (in italics) as a result o? the problem solving episodes, experiments,

and proofs. Such is the process of fleshing out incomplete domain and control knowledge through experience

and focused interaction with the task environment. Although in the example all the preconditions are

consequences learned are negated predicates, the same process applies to acquiring simple atomic predicates.

The process of acquiring logical combinations of atomic predicates is significantly more complex.

SIn general we are measuring relativ efficiency by requiring fewer total steps and no repeated subloalr In the instance case we have a

gartl;cr c ndiliot: fhc e.,if-ondc .k-i ioiIm of ihc morc efficicnt plan con,,iItic a proper subset of the lcaf-nodc actinni of the preaous less

cfficnt plan.
8

OPERATORS PRECONDITIONS CONSEQUENCES

1) GRIND-CONCAVE(<obJ>) ISA(<obJ>, solid) IS-CONCAVE(<obj>)

-IS-POLISHED((obj))

~IS-R EFLECT! VE(obft)

2) POLISH(<obj>) ISA(<obJ>. glass) IS-POLISHED(<obj>)

IS-CLEAN(<obJ>)

~-IS-RErLECTI VE((obj))

3) ALUMINIZE(<obJ>) IS-CLEAN(<obj>) IS-REFLECTIVE(<obj>)

ISA(.<obj>, solid) -IS-CLEAN(KobWJ

4) CLEAN(<obj>) ISA(<obj>, solid) IS-CLEAN(<obJ>)

INFERENCES:

1) IS-REFLECTIVE(<obJ>) & IS-POLISHED(<obj>) --> IS-MIRROR(<obJ>)

2) IS-MIRROR(<obJ>) & IS-CONCAVE(<ob>) --> IS-TELESCOPE-MIRROR(<obJ>)

NEWLY ACQUIRED CONTROL RULES for SUBGOAL ORDERING:

1) Select IS-POLISHED{(obj)) before IS-REFL EC Ti VE((obj)) if both are

present in the same conjunctive subgoal set.

2) Select IS-CONCA VE((obj)) before JS-MRROR((obj)) if both are

present in the same conjunctive subgoal seL

4.1. Concluding Remark: Beyond Simple Experimentation

Additional learning could occur by attempting to generalize the newly acquired preconditions and

consequences to other sibling operators in the operator hierarchy (see figure 3). For instance, the newly

learned consequences of destroying a polished or aluminized surface apply not just to GRIND-CONCAVE,

but to any GRIND operation (such as GRIND-CONVEX, GRIND-PLANAR). However, these

consequences do not apply to other RESHAPE operations such as BEND, COMPRESS, etc. The process to

determine the appropriate level of generalization again requires experimentation (or asking focused questions

to a human expert). For instance, observing the consequences of GRIND-PLANAR on a previously

aluminized mirror, provides evidence that all GRINDs behave alike with respect to destroying surface

attributes, and observing the consequences of bending a polished reflective glass tube without adverse effects

prevents generalization above GRIND.

In addition to proposing experiments to guide generalization, we are starting to investigate tradcoffs

between experimentation and resourcc consumption (minimizing the latter, while maximizing the

V!
9

information gained from the former), and tradeoffs between experimentation and other goals such

jeopardizing safety of the robot or person conducting the experiment. Our ultimate aim is to develop a set of

general techniques for an Al system to acquire knowledge of its task domain systematically under its own

initiative, starting from a partial domain theory and little if any a-priori control knowledge. The impact of this

work should be felt in robotic and other autonomous planner domains, as well as in expert systems that must

deal with a potentially changing environment of which they cannot possibly have complete and accurate

knowledge beforehand.

5. References

1. Carbonell, J. G. and Hood, G., "The World Modelers Project: Learning in a Reactive Environment," in

Machine Learning: A Guide to Current Research. Mitchell, T. M., Carbonell, J. G. and Michalski, R. S.,

eds., Kluwer Academic Press, 1986, pp. 29-34.

2. Carbonell, J. G., Subjective Understanding: Computer Models of Belief System. Ann Arbor, MI: UMI

research press, 1981.

3. Carbonell, J. G., "Learning by Analogy: Formulating and Generalizing Plans from Past Experience," in

Machine Learning, An Artificial Intelligence Approach R. S. Michalski, J. G. Carbonell and

T. M. Mitchell, eds., Tioga Press, Palo Alto, CA, 1983.

4. Carbonell, J. G., "Derivational Analogy: A Theory of Reconstructive Problem Solving and Expertise

Acquisition," in Machine Learning, An Artificial Intelligence Approach, Volume II. Michalski, R. S.,

Carbonell, J. G. and Mitchell, T. M., eds., Morgan Kaufmann, 1986.

5. Cheng, P. W. and Carbonell, J. G., "Inducing Iterative Rules from Experience: The FERMI

Experiement," Proceedings of A A A 1-86, 1986.

6. DeJong, G. F. and Mooney, R., "Explanation-Based Learning: An Alternative View," Machine Learning

Journal Vol. 1, No. 2, 1986.

7. Fikes, R. E. and Nilsson, N. J., "STRIPS: A New Approach to the Application of Theorem Proving to

Problem Solving," Artificial Intelligence, Vol. 2, 1971, pp. 189-208.

8. Kuhn, T. S., The Essential Tension: Selected Studies in Scientific Tradition and Chang4 U. of Chicago

Press, 1977.

9. Larid, J. E., Rosenbloom, P. S. and Newell, A., "Chunking in SOAR: The Anatomy of a General Learning

Mechanism," Machine Learning Vol. 1, 1986.

10. Langley, P. W, Simon, H. A. and Bradshaw, G. L., "Rediscovering Chemistry with the BACON System,"

in Machine Learnin& An Art/icial Intelligence Approach, R. S. Michalski, J. G. Carbonell and

T. M. Mitchell, eds., Tioga Press, Palo Alto, CA, 1983.

11. Lenat, D. B., 'he Role of Heuristics in Learning by Discovery: Three Case Studies," in Machine

Learning An Artficial Intelligence Approach, R. S. Michalski, J. G. Carboncll and T. M. Mitchell, eds., 'ioga Press, Palo Alto, CA, 1983.

12. Michalski. R. S., Carboncll, J. G., and Mitchell, T. M. (Eds), Machine Learning An Artificial InIcIligence

Approach, Tioga Press, Palo Alto, CA, 1983.
10

13. Michalski, R. S., Carbonell, J. G., and Mitchcll,T1. M. (Eds), Machine Learning, An Arificial Intelligence

Approach. Volume IL, Morgan Kaufmann, Los Altos, CA. 1986.

14. Mintoni, S. N. and Carbonell, J. 0., "Strategies for Learning Search Control Rules: An Explanation -Based

Approach." Proceedings of IJCA 1-87. Milan. Italy, 1987. (submitted).

15. Minton, S. N., Carbonell, J. G., Knoblock, C. A. and Kuokka. D. R., 'The PRODIGY System: An

Architecture for Analytical Learning in Planning and Problem Solving," Machine Learning Journal. Vol.

2, 1987, (submitted).

16. Minton. S.. "Selectively Generalizing Plans for Problem Solving," Proceedings of AAAI1-8S, 1985, pp.

596-599.

* 17. Mitchell, T. M., Keller, R. M. and Kedar-Cabelli, S. T., "Explanation-Based Generalization: A Unifying

View," Machine Learning, Vol. 1, 1986, pp. 47-80.

18. Mitchell, T. M., Utgoff, P. E. and Bancrji, R. B., "Learning by Experimentation: Acquiring and Refining

Problem-Solving Heuristics," in Mfachine Learning An Artificial Intelligence Approach. R. S. Michaiski,

J1. G. Carbonell and T. M. Mitchell, eds.. Tioga Press, Palo Alto, CA. 1983.

19. Nilsson, N.. Problemn-Solving Methods in Artificial Intelligence, McGraw-Hill, 1971.

20. Saccrdoti, E. D., A Structure for Plans and Behavior, Amsterdam: North-Holland. 1977.

21. Wilcnsky, R., Planning and Understanding Addison Wesley, Reading. MA, 1983.
FLECT% X -OL%

~i~' ~VOL. S14 I

T~ 

J IS 9 

CL tv 

is 

-yt 

A

C c "jo

LSA11

IS-so*
00 L FUSL

W~OOD mr* E .

LUPIFACI-VIOLEp ~A'

12