A Process Model of Cased-Based Reasoning in Problem Solving

A PROCESS MODEL OF CASED-BASED REASONING IN PROBLEM SOLVING

Janet L. Kolodner Robert L. Simpson, Jr. Katia Sycara-Cyranski

School of Information and Computer Science Georgia Institute of Technology

Atlanta, Georgia 30332

(e.g., Gick and Holyoak, 1980: Polya, 1945: Reed and Johnson, 1977: Rissland, 1982). It plays an especially important role in learning new tasks (e.g., Anderson, et al. 1984: Ross, 1982), and is an important part of making predictions in unders­ tanding (Schank, 1982) .

The example below· illustrates several places where analogy to a previous case can help in under­ standing and solving a current one.

A reasoner reads about the Sinai dispute (before the Camp David Accords) . She is reminded of the Korean War since both are over land, both are competitive, in neither can the conflict be resolved completely for both sides, and in both, military force had been used previous to negotiations. Based on this remin­ ding, she predicts that Israel and Egypt wil 1 divide the Sinai equally.

She later reads that this advice was given and rejected by both sides. She is reminded of her daughters' quarrel over an orange. She had suggested that they divide it equally, and they had rejected that, since one wanted to use the entire peel for a cake. Realizing that she hadn't taken their real goals into account, she then suggested that they divide it agreeably by parts one taking the peel, the other the fruit. This provides the suggestion that fail­ ures may occur because the goals of the disp­ utants are misunderstood. She therefore at­ tempts a reinterpretation of Israel's and Egypt's goals, and decides that Israel wants the Sinai as a military buffer zone in support of national security, and Egypt want· the land back for national integrity. Further reasoning aided by analogy to the orange dispute leads to the conclusion that an "agreeable division" based on the real goals of the disputants is appropriate.

She is reminded of the Panama Canal dispute since the disputants, disputed object, participant goals, and selected resolution plan are similar to those in the current dispute. Analogy to that incident guides refinement of the "agreeable division" plan. Replacing the US by Israel (the party currently in control of the object) and Panama by Egypt (the party who used to own it and wants it back), she predicts that Egypt will get economic and political con­ trol of the Sinai, while its normal right of military control will be denied.

As the example shows, case-based reasoning can aid in initial understanding of a problem: in genera­ tion of solutions: and in cases of misunderstanding

ABSTRACT

Much of the problem solving done by both novices and experts uses "case-based" reasoning, or reasoning by analogy to previous similar cases. We explore the ways in which case-based reasoning can help in problem solving. According to our model, transfer of knowledge between cases is guided lar­ gely by the problem solving process itself. Our model shows the interactions between problem sol­ ving processes and memory for experience. Our com­ puter program, called the MEDIATOR, illustrates case-based reasoning in interpreting and resolving

common sense disputes.

l· USING PREVIOUS CASES~ PROBLEM SOLVING

Most approaches to problem solving in AI treat each problem as a unique case. One deficiency of such problem solvers is that they cannot rely on previous experience. The same problem presented two different times requires the same (possibly long and complex) set of reasoning steps. Nor can such systems learn from the mistakes they have made. Suppose, however, that our systems could augment their problem solving capabilities by making analogies to previous similar cases. Reference to a previous case focuses reasoning on those parts of a current problem which were im­ portant in analysis of the previous case, poten­ tially reducing the number of features that need to be considered. When the process of reaching a sol­ ution to a problem involves many steps, analogy to a previous case can often reduce the number of steps required to reach a solution. Furthermore, if the set of cases used in problem solving include those where errors had been detected and later fixed, then analogy to a previous case can not only help in recovering from similar errors, but also in avoiding similar failures in the future.

The problem solving process which solves problems by analogy to previous or hypothetical cases is a "case-based reasoning" process. Ap­ plication of previous experiences in problem sol­ ving is something people seem to do in areas as diverse as mathematics, physics, medicine, and law or plan failure, in reinterpretation and selection of alternate 1 ines of reasoning. A problem solver must have several capabilities to employ case-based reasoning. It must locate previous similar cases in a potentially large long term memory of past problem solving episodes. It must integrate new cases into memory for future use. It must determine whether or not a recalled case is ap­ plicable in solving the new problem, and if many previous cases are available, which are potentially the most applicable. Finally, it must transfer knowledge correctly from the previous case to the current one.

* This research has been supported in part by NSF Grant Nos. IST-8116892 and IST-8317711 and in part by the Air Force Institute of Technology. The views expressed are solely those of the authors.

Much work is being done currently in the area of making analogies across domains (e.g., Burstein, 1983; Gentner, 1982; Winston, 1980), mostly for making automatic knowledge acquisition of a new domain easier. In general, the analogous concept is given and the computer's job is to do the tran­ sfer correctly. Our goals are somewhat different. Though analogy to a previous similar case results in acquisition of new or more refined knowledge in a domain the system already knows about, we focus on analogy's roles during problem solving. We thus consider the requirements it places on the problem solving system and the constraints put on the analogical process by the task demands of the problem solver. Since we investigate a process that is meant to be part of a problem solver, we require that the computer locate, choose, and figure out how to apply appropriate analogies by itself.

ll· THE CASE-BASED REASONING PROCESS

The case-based reasoning process works as fel­ lows: (l) Locate and retrieve potentia 11 y ap­ plicable cases from long term memory. (2) Evaluate selected cases to determine the applicable ones. (3) Transfer knowledge from the old case(s) to the current one. We begin by explaining memory structures and processes that allow previous cases to be remembered. We then consider the roles those cases can play in problem solving and how problem solver task domains guide transfer of knowledge from one case to another. We consider the types of memory schemata necessary to support our model, and the choice of cases when several are available. Finally, we present our program, the MEDIATOR, which uses analogy to previous cases to resolve disputes. For more information about other aspects of the process, see (Kolodner & Simpson, 1984 or Simpson, 1985) .

_1 1_1. LOCATING CASES .!1! MEMORY

In order to use previous experience, a problem solver must be able to interact with a memory for experience (Ko 1 odner & Simpson, 1984) . The memory we use organizes experiences (cases) based on oener a 1 i zed episodes (Ko 1 odner, 1984, Schank, 1982). These structures hold generalized knowledge describing a class of similar episodes. An in­ dividual experience is indexed by features which differentiate it from the norms of the class (those features which can differentiate it from other simi 1 ar experiences) · As a new experience is in­ tegrated into memory, it collides with other ex­ periences in the same generalized episode which share its differences. We call such a collision a "reminding" (Ko 1 odner, 1984, Schank, 1982) · This triggers two processes. Expectations based on the first episode can be used in analysis of the new one (analogy). Similarities between the two episodes can be compiled to form a new memory schema with the structure just described (generalization).

Figure 1 shows how the "orange dispute" (from the example above) is organized in a generalized episode associated with "physical disputes" (i.e., those over possession of a physical object). At the top of the figure are the norms for "physical disputes." Below that, the "orange dispute" is in­ dexed by those features which specialize it in the "physical dispute" generalized episode. It is in­ dexed by features of both of its interpretations. As new cases are added to the memory structure, sub categories will be created in the structure at the places in which other cases correspond to this one. The "orange dispute" will help form the basis of norms associated with those categories.

Retrieval of cases from memory and integration of new cases into memory are accomplished through a traversal process. As a new case is processed, ap­ propriate generalized episodes are identified. Features differentiating the new case from others organized in the same category are used to create new indices. Indices associated with features already present in the indexing structure are traversed. Any previous cases the new case col­ lides with are available for further evaluation. A previous experience can thus be "remembered" if it is organized in the same generalized episode a new case is being integrated into and also shares a set of differences with that case. The "orange dispute" can be recalled from the "physical disp­ utes" generalized episode shown above by any physical dispute for which "divide equally" fails (e.g., the Sinai dispute), any time the object of dispute is edible, etc.

Memory processes are integrated with problem solving processes as follows: As a case is being considered, it is represented by a set of schemata (frames) which detail features of the case (in the slot fillers). At any moment, memory has available to it the current problem representation. A memory traversal process running concurrently with problem solving processes uses the current problem representation as a key into memory. Cases the memory encounters in traversing memory using the current case as its search key are ava1 lable for case-based reasoning. As the problem representa­ tion changes, search is directed to p 1 aces in memory referenced by the most current problem representation.

lY· CASE-BASED REASONING'S VARIED ROLES

Before discussing the roles case based reasoning can play in problem solving, we need to duscuss the problem solving framework into which we enter our case based processes. In order to use case-based reasoning, a problem solver must be able to receive and evaluate feedback about the results of its decisions. A problem solver that suggests solutions to problems but never knows the outcome of its advice has no basis for evaluating its decisions, and thus cannot be expected to use its experience reliably in dealing with later cases. This suggests that the problem solver must have fo 11 ow-up procedures, inc 1 ud i ng procedures for recogn1z1ng, explaining, assigning blame, and at­ tempting to correct failures. In addition to that and plan generation procedures normally included in problem solvers, we also include a problem unders­ tanding phase in which a partially-specified problem description is elaborated to the extent necessary for problem resolution. These processes are depicted in Figure 2. Case-based reasoning can play a role in any of these tasks.

PHYSICAL DISPUTES

norms: dispute is over possession of object object is physical object party-a party-b plans: has goal of possession of has goal of possession of "divide equally", "divide object object agreeably"

\ "orange dispute"

original interpretation:

goal (sisterl) =ingest (orangel)

==>goal (sisterl) =possess (fruit (orangel))

goal (sister2) =ingest (orangel)

==>goal (sister2) =possess (fruit (orangel))

dispute over possession of same object

chosen plan: "divide equally"

later interpretation:

goal (sisterl) = ingest (orangel)

==>goal (sisterl) =possess (fruit (orangel))

goal (sister2) = prepare (cakel)

==> goa 1 (sister 2) = possess (pee 1 (orange l))

dispute over possession of parts of same object

chosen plan: "divide into different parts"

explanation of failure of original interpretation: "wrong goa I inference"

remediation plan used:

"infer goals from resulting events"

Figure 1

PROBLEM SOLVING WITH FOLLOW-UP

A· Case-based reasoning lQ interpretation

Before a problem can be solved, 1t must be un­ derstood. Details not presented in the problem description must be filled in through inference or query, and schemata (genera 1 i zed episodes) for representing the problem must be chosen. Problem schemata point to potential solution plans and thus are crucial to deriving good solutions. Analogy to a previous case can direct these processes in the following two ways:

1. by suggesting additional features . to be investigated
2. by suggesting alternative interpretations

The first step in understanding a problem is to make a hypothesis about a schema that might describe the problem. A doctor, for example, may make a hypothesis about the disorder a patient has by focussing on reported symptoms. After represen­ tation hypotheses are made, case-based reasoning can help in verifying them. An attempt is made to integrate the new case into the hypothesized generalized episodes, causing remindings. If the current case is missing details necessary to verify a hypothesized schema, and a remembered case incl­ udes those details, an attempt is made to transfer those detai Is to the current case. If their assum­ ption is consistent with the current case, they are fi lied in, and the relevant hypothesis (the schema associated with the remembered case) is verified. A case one is reminded of may also have had features important to its proper resolution that were not predicted by the schema. These features are investigated. On the other hand, traversal may result in reminding of a case that initially was thought to be represented by the hypothesized schema, but was later found to need a different representation. In this situation, the current case is evaluated to see whether it might also be represeQted the second way, thus avoiding the previous interpretation error.

~· Case-based reasoning lQ ~ generation

After a case is understood, a plan for its resolution must be generated. Our approach, which we refer to as plan instantiation, consists of two major stages: plan selection and plan refinement. Plan selection involves choosing the best from among a set of known plans or constructing a plan by combining appropriate pieces of known plans. Plan refinement involves role binding and adjusting the plan for the particular situation. When several plans are feasible, the expected results of using the "plan must be generated and evaluated to choose the best one. Analogy to previous cases can help plan generation in four ways:

1. suggestion of procedures to be followed
2. suggestion of procedures to be avoided
3. selection of a means of implementing a plan
4. prediction of the outcome of a selected plan

Plans associated with cases remembered during interpretation are available to suggest plans to be followed or avoided. The preconditions of any suc­ cessful plan are checked, and if applicable, the plan is attempted. At the same time, any plan used in a previous case and resulting in failure is prohibited in the current case.

If more than one p 1 an is suggested, the utility of potential plans must be evaluated and the most appropriate one chosen. Plan evaluation involves simulating the results of alternative courses of action and evaluating them. Evaluation can be done taking previous experiences into ac­ count. Simulating the results of using a plan provides a hypothetical situation which may be similar to a previous real one. The results of previous attempts at implementing the same plan under similar conditions provide a way of eval­ uating a potential course of action. Additional information leading to a better strategy may also be provided during evaluation. This process is an extension of what Schank (1982) refers to as inten­ tional reminding, and is a component of Wilensky's (1983) Projector.

Any chosen plan must be refined or adjusted for the current situation. A suitable plan im­ plementation can be derived by considering now it was effected in a previous case. We see this in the Sinai example when the Panama Canal agreement is used in deciding how to carry out the "divide agreeably" plan.

~· Case based reasoning lQ error recovery

Problem solving errors usually appear as plan failures, but they can result from initial misin­ terpretation, poor implementation of the plan, incorrect prediction of the results, new unexpected _occurrences, or bad plan selection. When similar failures have happened previously, the work involved in error recovery can be cut down. In a sense, error recovery can be viewed as another ins­ tance of problem solving, this time interpreting the failure (explaining it) and fixing the faulty knowledge (remediation). A previous case can thus play roles similar to those played in initial in­ terpretation and planning:

1. suggestion of an · explanation for the failure
2. suggestion of a plausable new interpretation
3. suggestion of a plan for recovery

The procedure by which a previous similar failure may provide a clue to tracking down the error in the current case is as follows: Upon failure recognition, the reasoner will first at­ tempt to recall a similar previous error. Indices corresponding to the features of the case, the chosen plan and the failure, are traversed. If a similar failure has occurred previously, the ex­ planation from that failure acts as a guide to con­ structing a hypothesis to explain the current failure. The reminding may also include suggested plans for error recovery.

Consider again our example in section one. The error recovery that occurs after the mother's failure to correctly predict a solution to the Si nai dispute is as follows: The mother remembers her previous failure with respect to the orange dispute. This reminding guides the construction of the following hypothesis: Perhaps the goals of the disputants have been inferred incorrectly. If so, use "agreeable d ivision" based on their real goals.

In this case, an alternate classification is sug­ gested (one based on concordant rather than com­ petitive goals), an explanation for the failure is suggested (the wrong goa 1 s were being considered) , and a plan for recovery is suggested (f i nd the real goals and apply the plan "agreeable division").

y. GUIDING THE TRANSFER OF KNOWLEDGE

Treating analogy as part of a problem solving process allows task demands of the problem solver to guide the transfer of knowledge from one case to another one. During interpretation, the problem solver needs to infer missing information and to choose problem classifications. When inferring missing i nformation, it looks at those features of a previous case designated by the hypothesized generalized episode as necessary for clas­ sification. When enough information to make a definitive classification is available, the problem solver attempts to transfer the classification, cheaking to make sure that conditions for recogni­ tion are met. During plan generation, the problem solver attempts to transfer plans associated with previous cases. To decide if a particular plan can be transferred, its preconditions are checked against the features of the current case. Error recovery involves failure classification and then replanning. Missing information about the failure necessary to classify and possibly explain it is investigated and transferred from a previous case. Previous means of resolving the error (i.e., the remediation plan) are checked during replanning. Preventing the inappropriate transfer of knowledge is complementary to enabling its transfer. Knowledge transfer is prohibited when it violates designated consistency constraints (e.g., precon­ ditions and exclusionary principles).

VI. MEMORY SCHEMATA

There are two important issues to discuss with respect to locating cases in memory: what kinds of indices are necessary, and what kinds of generalized episodes have proven useful?

Two types of features are used for index ing: features of the case and features describing any failures encountered during analysis of a case. If blame is assigned for a fa i lure and a correction has been found, the case is indexed by those features which caused the failure. When a second s i tuation with those features is encountered, reminding of the first provides a means of avoiding fa i lure the second time. When blame has not been assigned, the features indexing the case by its differences will serve to direct reminding to a similar case. Though a particular procedure for avoiding failure may not be found, the failed ins­ tance will alert the reasoner of a potential problem . These two types of indices allow remin­ ding of (1) cases which are similar descriptively to a current one and (2) those which failed similarly.

Two types of generalized episodes have proven useful for case-based problem solving: descriptive and tactical ones. Descriptive categories describe the types of problems the problem solver wi 11 encounter. Each specifies descriptive features and suggested remedies. In our problem solving framework, two types of problems are dealt with by the problem solver: domain problems and failures. Generalized episodes correspond i ng to each of these problem types are necessary. In tha mediation domain, these include dispute types (e.g., physical, economic, political) and types of media­ tion failures (e.g., "wrong goal inference", "incorrect classification", "wrong planning po 1 icy") · Figure 1 shows some of the norms and ap­ plicable plans for "physical disputes." Similarly, the descriptive failure category "wrong goal in­ ference" holds a normative description and specifies plans for inferring the right goal (e.g., "infer goal from resulting events"). Descriptive categories are used during understanding tasks problem interpretation and failure explanation.

Tactical classifications of experience cor­ respond to particular plans. They describe precon­ ditions, implementation detai Is, and expected results of plans, and organize cases in which the plan was used. In the mediation domain, we use tactical generalized episodes corresponding to mediation plans (e.g., "divide equally", "divide into different parts") and remediation plans, i.e., plans for recovery from particular planning errors (e.g., "change planning policy", "infer goal from later actions"). Tactical generalized episodes are

used during the planning stages to determine

whether a suggested plan is appropriate (using its preconditions), to find a means of implementing a plan, and to predict and evaluate the consequences of using a suggested plan. During error recovery, classifications associated with remediation plans help in creating new problem interpretations and selecting alternative resolution plans.

lli· CHOOSING THE BEST CASE

In a richly indexed episodic memory, many remindings may occur during problem solving. While the memory structure constrains the possibilities to some extent, there must be a way of choosing potentially relevant previous cases from the set of remindings. There are two ways to do this. In the first method, the best case is chosen from the sei of remindings---through--;n ~a--priOr~vaTUation procedure, i.e., one that takes only closeness of fit to the current case into account. Using this method, if the selection later proves to be inap­ plicable (e.g., due to incompatible preconditions for the suggested plan), a second choice is made by the same evaluation procedure. This method is ac­ ceptable if failures are not expensive or ir­ recoverable. Because "a priori" evaluation may not always be reliable, however, another method of choice must be used when more carefully thought-out solutions are necessary. In this case, an evalua­ tion procedure is used to rank cases, and a set of highly-ranked ones are chosen. Suggestions from each of the selected cases are considered, a plan is generated based on each one, the generated plans are evaluated, and ~best 2l!n l! chosen.

Since the mediation domain is one where failure has little consequence, we use the first method. The best previous case is chosen using an evaluation procedure based on Carbonell's (1982) invariance hierarchy. Priority is attached to different feature types. Alternative cases are evaluated according to a series of elimination and ranking tests. Our set of tests is as follows:

1. Eliminate those cases where the goal relationship is different from that in the current case.
2. Eliminate those where the goal relationship is that of the current case. the derivation of different from
3. Order the remaining cases by the following rankings: similar disputant argument>> similar disputants>> similar disputed ob­ ject

Consider how these work for the following example:

The third-world and industrial nations both want rights to the minerals in the world's sea beds. It has already been decided that they will be divided. Neither side, however, trusts the other to divide the resources.

Suppose our reasoner were reminded of three cases: (1) two children fighting over a candy bar-- the so 1 uti on is "one cuts the other chooses", (2) the dispute between Israel and Egypt over the Sinai, and (3) the dispute between the US and Russi a over fishing rights off the US coast. Using rule 1, (2) is eliminated since it involves a concordant goal relationship rather than a competitive one. Rule 2 eliminates (3) since the goals of the disputants are derived differently · . In the current case, the goal is derived from the disputants' desire to con­ tro 1 and use a consumab 1 e resource, wh i 1 e in (3) , the goal derives from an intention to control a renewab 1 e resource. Case ( 1) is chosen as most ap­ plicable, and an analogy based on the superfici~l similarities between the current case and case (3) is eliminated.

Ylll· AN EXAMPLE FROM THE MEDIATOR

In the following example, we see the MEDIATOR (Simpson, 1985) resolving the Sinai dispute based on analogies to several disputes it already knows about. Initially, the MEDIATOR is told that Egypt and Israel both want physical control of the Sinai, and that military means have been used previously to attempt to achieve that. In attempting to clas­ sify the dispute into one of its known dispute types, the MEDIATOR is reminded of two previous cases, the Panama Canal dispute and the Korean con­ flict. Using its evaluation function (not ex­ plained here), it chooses the Korean conflict as most applicable since it shares more important features. Since that dispute doesn't help it further interpret the problem, it goes on to the planning phase and attempts to transfer the plan used successfully to resolve the Korean conflict. It checks that plan's preconditions for ap­ plicability to the new case.

RECALLING PREVIOUS DISPUTES TO CLASSIFY THIS ONE .·

reminded of the "Panama Canal Dispute" because both disputants are of type M-POLITY. reminded of the "Korean Conflict" because both objects are of type M-LAND and both used M-MILITARY-FORCE to attempt *PHYS-CONTROL* Choosing the "Korean Conflict" ATTEMPTING TO SELECT A MEDIATION PLAN TO RESOLVE THE "Sinai Dispute" Using the "Korean Conflict" which was resolved using "divide equally" Checking for applicability of that plan .·. I suggest "divide equally" be used.

The MEDIATOR asks for feedback about its decision and is told both Egypt's and Israel's reactions. It attempts to come up wi th a new solution, and considers the failure of the suggested plan as the current problem to be resolved. It applies the same problem solving process to the failure to ex­ plain it and reinterpret.

Is this a good solution? (Y or N) No. **** DIVIDE EQUALLY not acceptable **** What happened? -(we show the English equivalent) Israel says the want the Sinai for security Egypt says they want it for integrity ATTEMPTING TO EXPLAIN FAILURE AND FINO NEW SOLUTION.

RECALLING PREVIOUS FAILURES ..·.

reminded of "two sisters quarrel over an orange" because in both "divide equally" failed

and both objects are of type M-PHYS-OBJ Failure was because of M-WRONG-GOAL-INFERENCE. Transferring that classification to this failure. Attempting to use remedy called

"i nfer goal from resulting actions" Unable to use previous remedy. Considering other remedies M-WRONG-GOAL-INFERENCE Looking at "infer goal from respon~e"

Based on the feedback, I replace ISRAEL's goal with aM-NATIONAL-SECURITY goal and EGYPT's

goal with aM-NATIONAL-INTEGRITY goal. Remediation complete.

---------------------------------------------------

The MEDIATOR next reprocesses the dispute. Because the problem has been re-interpreted, there is no need to reference previous cases unti 1 plan selection. The reminding process (left out this time) retrieves the same two cases as before. This time the addition a 1 information about the goa 1 s of the disputants causes the MEDIATOR to focus on a d i fferent exemplar, the Panama Canal dispute. Using that as a model, i t suggests g1v1ng Egypt pol itical control of the Sinai but giving military control to Israel.

-------------------------------------------------- Reconsidering the problem using new information. Considering the re-interpreted problem:

Israel and Egypt both want the Sinai,

which has been presented as ako M-PHYS-OlSPUTE. ATTEMPTING TO SELECT A MEDIATION PLAN

TO RESOLVE THE "Sinai Dispute"

RECALLING SIMILAR DISPUTES . ··

Reminded of the "Panama Canal Dispute" resolved using "div ide into different parts". Checking for applicability of that plan .. . 1 suggest "divide into different parts" be used. Using the ,·,Panama Canal Dispute" to create plan matching ISRAEL with USA ..· matching EGYPT with PANAMA ·.· matching SINAl with PANAMA-CANAL ..· matching

(*GOAL* (*NAT-SECURITY* (ACTOR ISRAEL)

(OBJECT SINAl))) with

(>'<GOAL1< (>'<MIL-CONTROL>'< (ACTOR USA)

matching

(OB.JECT PANAMA-CANAL))) ...

(>'<GOAL>'< (>'<NAT-INTEGRITY>'< (ACTOR EGYPT)

(OBJECT SINAl))) with

(*GOAL* (*POL-CONTROL* (ACTOR PANAMA)

(OBJECT PANAMA-CANAL))) ···

transferring other components unchanged.

Jl.. SUMMARY

Though we have presen.ed a framework for using case-based reasoning in problem solving, we have not covered all parts of the process in this paper. The problem solver must be able to keep track of attempted solutions so that it does not repeat bad attempts. It is also necessary to develop criteria to evaluate the feasibility of a case-based ap­ proach for any given problem. Transfer must also oe given more consideration. Direct transfer is often not enough. Sometimes only part of a solu­ ti on should be transferred, and often transfer it­ self is analogical. Multiple cases representing a combination of analogies must also be considered in interpreting or creating a plan to solve a problem. Multiple cases may each provide parts of a solution which must then be pieced together.

This work derives from research in the cognitive modell;,,g of long term memory (Kolodner, 1984, Schank, 1982) and uses those theories as it s basis. At the same time, we maintain consistency with relevant psychological work (e.g., Ross, 1982). Like Hammond (1983), who also bases his work on those models, we provide a model of case based reasoning which integrates problem solving, understanding and memory. While his work uses previous cases for plan selection and avoidance, we use them additionally for problem interpretation and error recovery. Carbonell (1983) is closest to our research, though his problem solving follows the search paradigm. In our approach, traditional notions of search are absent. Rather, we combine analogical transfer with plan instantiation.