A Computational Model of Analogical Problem Solving

1. Introduction

Analogical reasoning has been a sparsely-investigated phenomenon in Artificial Intelligence (7, 12, 8, 20) . Nonetheless, analogy promises to be a central inference method in human cognition as well as a powerful computational mechanism. In this paper, I discuss a computational model of problem solvin~ by analogy based on an extension of means-ends analysis (MEA). My central hypothesis (based in part on Schank's theory of memory organization (18, 17)) is the following: When encountering a new problem situation, a person is reminded of past situations that bear strong similarities (at different levels of abstraction) to the present situation. This type of reminding experience serves to retrieve behaviors that were appropriate in earlier situations, whereupon past behavior is adapted to meet the demands of the current situation.

Commonalities among previous and current situations, as well as successful applications of modified plans can serve as the basis lor generalization. Similarly, performing an inappropriate behavior in a new situation can lead to discrimination (among the ways in which situations are organized in memory and/or the mechanisms that adapted an existing plan to the new situation) . However. a reac tive environment that informs the problem solver of success. failure, or partial success is an absolute requirement for any generalization or discrimination process to apply. I consider problem solving by analogy and experiential learning to be inalienable components of a unified cognitive model. Analogical problem solving exploits knowledge of plans indexed under situations similar to the current one, generating new purposive behavior potentially relevant to future problem solving. And, the learning component creates the memory structures to encode experiential knowledge (generalizing where appropriate)

1 This research was sponsored in par1 by the Office of Naval Research (ONR) under grant number N00014· 79·C·066 t . The author would like to thank Allen Newell, David Klahr and Monica Lam for their useful suggestions in various discussions.

A Computational Model of Analogical Problem Solving

Jaime G. Carbonell

Carnegie-Mellon University Pittsburgh , PA 15213

that enable the problem solver to retrieve and compare relevant situations and plans from memory. The bulk of this paper focuses on developing a computationally·elfective mechanism lor problem solving by analogy. A detailed discussion of experiential learning processes is beyond the scope of this presentation (but see (3)) .

2. Problem Solving by Analogy

Traditional AI models of problem solving (e.g., GPS (13), STRIPS (6), and NOAH [15)) approach every problem almost without benefit of prior experience in solving other problems in the same or similar problem spaces. Hence, GPS will perform the same Means-Ends Analysis (MEA) process to solve the monkey· and·bananas problem (where a monkey needs to place a box underneath some bananas suspended from the ceiling in order to climb on the box, reach the bananas and eat them) and to solve the experimenter·and-bananas problem (where the experimenter must move the same box enabling him to reach the hook in the ceiling where he will hang the bananas .. then he must move the box away to create a problem lor the monkey) . However, an intelligent monkey observing the experimenter hang the bananas, may directly conclude which parts of the experimenter's behavior he should replicate in order to reach the bananas. Similarly, an experimenter who becomes hungry alter watching an unenlightened monkey repeatedly fail in his attempts to reach the bananas, should know how to reach the bananas himself without planning from ground zero.

Clearly, the bulk of human problem solving takes place in problem spaces that are either well known or vary only slightly from familiar situations. It is rare for a person to encounfer a problem that does not remind him of potentially applicable solutions to similar problems solved or observed in past experience. New puzzles (such as Rubik's magic cube) are such exceptional problems, where initially the only tractable solution procedure is the application of weak methods (13) without benefit of (non-existent) past experience. Therefore. my investigations center on simplified versions of ~eal - world problems, rather than more abstract mathematical puzzles.

Now, let us turn to problem solving in familiar problem spaces. What mat<.es a problem space "familiar"? Clearly, knowledge of solved problems in that space is a major aspect. This knowledge must have been acquired. and must be brought to bear in the problem solving process. There is no other way to account lor the fact that humans solve problems in familiar situations much faster, and with more self-assurance. A computer model should exploit the same skill ·acquisition process; i.e., it should learn to adapt its problem·solving behavior to known problem spaces .. falling back on the application of weak methods when more direct recall-and· modification of existing solutions fails to provide an answer. How might a problem solver be augmented to exhibit such adaptive behavior? Below, I illustrate a tractable mechanism for problem solving by analogy.

2.1. The Plan· Transformation Problem Space

First, consider a traditional Means-Ends Analysis (MEA) problem space [13) , populated by:

• A set of possible problem states.
• One state designated as the Initial State
• One or more state(s) designated as goal states ·· for simplicity, assume there is only one goal state.
• A set of operators with known preconditions that transform one state into another state in the space.
• A difference function that computos differences between .two states (typically applied to compute the difference between the current state and the goal state).
• A method for indexing operators as a function of the difference(s) they reduce (e.g., the table of differences in GPS) .
• A set of global path constraints that must be satisfied in order for a solution to be viable. (E.g., a path constraint may disallow particular subsequences of operators, or prevent an operator that consumes K amount of a resource from applying more than N times, if there is only NxK amount of the resource available to the problem solveri

Problem solving in this space consists of standard MEA: Compare the current state to the goal state; choose an operator that reduces the difference; apply the operator if possible ·· if not recurse on the subgoal(s) of establishing the unsatisfied precondition(s) of that operator.

How can we exploit knowledge of solutions to previous problems in this problem space? First, consider the simplest case; knowledge consists only of solutions to previous problems. Each solution consists of a sequence of operators and intermediate states, including the initial and final states, together with the path constraints that the solution was designed to satisfy. One rather simple idea is to create "macro-operators" from sequences and sub-sequences of atomic operators that have proven useful as solutions to earlier problems. For instance, STRIPS with MACROPS exploited this idea (6) using its· "triangle table" to store all partial sequences of operators encountered in a solution to a previous problem. However, the simple creation of macro­ operators suffers two serious shortcomings. First, the combinatorics involved in storing and searching all possible subsequences of all solutions ever encountered becomes rapidly unmanageable. Searching for applicable macro-operators can become a more costly process than applying MEA to the original problem. Second, path constraints are ignored in this process. If the new problem must satisfy a different set of path constraints, most previous macro-operators may prove invalid. Therefore, let us think not in terms of creating more and more powerful operators that apply to fewer and fewer situations, but rather think in terms of gradually transforming an existing solution into one that satisfies the requirements of the new problem.

Consider a reminding process (a search for solutions to problems similar to the one at hand) that compares differences among the following:

2 rhe introduction of path constraints in this manner constitutes a slight modification of the standard MEA problem space.

1. The initial state of the new problem and the initial state of previously-solved problems
2. The final state of the new problem and the final state of previously-solved problems
3. The path constraints under which the new problem must be solved and path constraints present when previous similar problems were solved.
4. 4 . The differential applicability of the retrieved operator sequence in the old and the new problem situations.

The difference function used in comparing initial and final states may be the very same function used for difference reduction in standard MEA. Here, I advocate using the .difference function as a similarity metric to retrieve the solution of a previously-solved problem closely resembling the present problem. The difference function applied to path constraints is a generalization of the problem-state difference function, as it must address operator-sequence differences in addition to state information. Hence. reminding in our problem-solving context consists of recalling a previously solved problem whose solution may transfer to the new problem under consideration. A more sophisticated method of computing similarities among episodic memory structures is based on a relative -invariance hierarchy among different components of recalled problem solutions, as discussed in (4).

Reminding is only the first phase in analogical problem solving . The second phase consists ol transforming the old solution sequence into one satisfying the criteria for the new problem. How does this transformation process proceed? I submit that it is equivalent to problem solving in the space of solutions. 3

3 Here I apply my previous definition ol a solution to be a sequence of operators and ontermediate states together with the set of path constraints that sequence is known to salosfy . Thus, I advocate applying MEA to the space ol potential solution seQuences rather than the original problem space. However . the reminding process should generate an mihal solution seQuence close to the goal solution sequence, where closeness ·s det~rmtned by the difference metric above.

Finding an appropriate analogical transformation is itself a problem solving process, but in a different problem space. The states of the transform problem space are solutions to problems in the original problem space. where the initial state is the retrieved solution to a similar problem, and the goal state is a solution satisfying the criteria for the new problem. The operators in the transform problem space are the atomic components of all solution trans.formations (e.g., substitute an operator in the solution sequence for another operator that reduces the same difference, but requires a different set of preconditions or entails different side effects, etc. ·· see below). The differences that the problem solver attempts to reduce in the new problem space are precisely those computed by the similarity metric in the reminding process. In other words, progress towards a goal is determined by transitions in the solution space towards "solution sequences" corresponding to problems increasingly similar to the original problem. Intermediate states in the transform space need not correspond to viable solutions in the original (object) space, in that intermediate solution sequences may not be executable due to unsatisfied operator preconditions. The diagram in figure 2·1 gives an intuitive flavor of this problem-solving process. More precisely, the analogy transform problem space (T-space) is defined as follows:

• States in the transform space are potential solutions to problems in the original problem space (i .e., sequences of states and operators including the initial and final states, plus the path constraints under which those solutions were computed.)
• The initial state in the transform space is the solution to a similar problem retrieved by the reminding process.
• A goal stale in the transform space is the specification of a solution that solves the new problem, satisfying its path constraints.
• An operator in the transform space (labeled a "T-operator" to avoid confusion) maps one solution sequence into another potential solution sequence in the untransformed problem space. The following is a partial list of useful T-operators:
• o Genera/Insertion. Insert a new operator into the solution sequence.
• o General deletion. Delete an operator from the solution sequence.
• o Subsequence Splicing. Splice a solution to a new subproblem into the larger established solution sequence. This T-operator is useful in the following situation: If an operator in the original problem sequence cannot be applied under the new problem specification because one of its preconditions is not satisfied, problem solve in the original (object) space to find a means of satisfying this precondition . If successful, splice the precondition­ fulfilling subsequence into the original solution sequence.
• o Subgoal-preserving substitution. Substitute an oper.ator in the original solution sequence by another operator (or sequence of operators) that reduces the same difference. This T-operator is particularly useful if either a precondition of an operator in the original sequence cannot be satisfied. or if the presence of a particular operator in the solution sequence violates a path constraint 4

·Note that a subgoal -preserving substitution is much more restrictive than a general delete T-operator followed by a general rnsert T-operator. Therefore, this T-operator is more ·apt to yield useful transformations, a fact reflected in the orderrng of operators under each appropriate entry in the difference table.

• o Final-segment concatenation. Treat the solution sequence as a macro-operator in the original problem space and apply MEA to reduce the difference between the old final state and the new final state. If successful, concatenate the solution to this subproblem at the end of the original solution sequence.
• o Initial-segment concatenation. Apply the process above to find a path in the original problem space from the new initial state to the old initial state. If successful, concatenate at the beginning of the original solution. [Note that in this case we start with the initial state for the new problem and seek a path to the initial state for the retrieved solution, whereas in the final segment­ concatenation operator the inverse process applies.]
• o Sequence meshing. If two solutions to previous problems were retrieved in the reminding process, each solution differing from the new problem specification in non-identical aspects, merge their operator sequences. The resultant solution sequence should differ from a solution to the new problem by the intersection of the differences between each retrieved solution and the new problem specifications If the differences bet~een the two retrieved solutions and the new problem specification form disjoint sets, sequence meshing yields a complete solution.
• o Operator reordering. Often a path constraint in the new problem specification can be met by simple reordering of operators (when allowed by their preconditions) in the retrieved solution.
• o Parameter substitution. The objects to which operators were applied in the retrieved solution may be substituted for objects in the new problem (that do not violate the preconditions of the operators) .
• o Solution-sequence truncation. If the final state of an operator subsequence of the retrieved solution exhibits a smaller difference with the new problem specification, use this subsequence as the new basis for mapping into the desired solution sequence.
• The difference function in the transform .space (D ) is a combination of the difference measures between initiaT states (of the retrieved and desired solution sequences). final states, path constraints, and degree of applicability of the retrieved solution in the new problem scenario. Hence, the values of DT are 4-vectors, with the interpretation that all four component differences must be reduced (independently or jointly) in the transform space (T-space) problem-solving process.

D 0 is the difference function between states in the original space. DP computes differences between path constraints (PC's} . D A measures the applicability of the old solution in the new scenario by determining the fraction of operators in the initial solution sequence (SOL 1 ) whose preconditions are not satisfied under the new problem specification. S 1 denotes an initial state, and SF denotes a final state. The subscript 1 indexes the retrieved solution, and 2 indexes the specifications on the desired solution to the new problem. DT is reduced when any of its four components is independently reduced.

5 Merging two partial operator sequences is an interesting and potentially complex problem in itself . Procedural networks. developed in the NOAH system [15] . lacilitate computations ol operator rnteractrons when meshrng two plans. It is not always the case that two partial solution sequences can be merged effectively (e.g .. each subsequence may violate necessary preconditions lor the other subsequence). Non-algorithmic T-operalors, such as sequence meshing, define therr own internal problem space.

The problem-solving process in T-space succeeds when Dr = <NIL, NIL, NIL, NIL>. Interesting search problems occur when, in order to reduce one component in the difference vector, one or both of the other components must be increased. For example, the insertion of new operators into the solution sequence may have the unfortunate side-effect of violating an established precondition of an operator in the original sequence. In this case reducing 0 0 (1) or D 0 (F) results in increasing DA. Our first-pass solution is to define a (linear) combination of the lour components and choose the operator that maximally reduces this value, backtracking when necessary. Fortunately, it is often the case that differences in the 4-vector can be reduced in a componentwise-independent manner. Moreover, a modified version of the tl-MIN method [2) may apply, focusing the backtracking process when backtracking proves necessary.

• A difference table for indexing the T-operators is needed. Entries in the difference table take the form "To reduce <DIFFERENCE>. apply a member of <T-OPERATOR­ S E T>". The operators in the applicable set are usually ordered as a function of the heuristic measure of their utility in reducing the given difference. A sample difference table entry would be:
• o II the preconditions to an operator in SOL 1 are not satisfied (i.e. D A is non-null), try (first) subgoal-preserving substitution on the inapplicable operator, or try solution-sequence splicing to satisfy the violated preconditions.
• There are no path constraints in the transform space. Since we are mapping from one solution sequence to another, the intermediate states and T-operators do not necessarily correspond to actual operations performed on an external world, and therefore are not subject to its restrictions. This simplification is offset by the more complex difference metric in T-space.

2.2. An example

Reconsider the monkey-and-bananas and experimenter-and­ bananas problem, in light of the analogical problem-solving model.

• A monkey watches a behavioral psychologist (i.e., the experimenter) pick up a wooden box and place it under a hook in the ceiling. Next, the experimenter climbs on the box, places some bananas on the hook, climbs off the box. and returns the box to its original location. Then, the experimenter releases the (hungry) monkey and leaves the room. How does the monkey plan to reach the bananas? Can he benefit from having observed the experimenter?

As we mentioned earlier, a "smart monkey" ought to learn from his observations of the experimenter. Let us see how analogical problem solving applies here. For simplicity, assume the monkey does not have prior experience solving similar problems beyond his recent observation of the experimenter. The monkey's problem is: initial state = monkey on the floor, bananas on the ceiling, box in the room; final state = monkey in possession of the bananas; path constraints = physical abilities of the monkey. However, the solution to the experimenter's problem cannot be applied directly. (His problem was initial state = possession of the bananas, box in the room, experimenter on the floor; final state = Bananas on the ceiling, box not under the bananas; path constraints = physical abilities of the experimenter.)

Assuming the path constraints match, the differences between the initial states (and the differences between the final states) are so large as to preclude any reasonable attempt at direct analogical transformation. Therefore, the monkey must resort to standard MEA (in the object problem space). He selects the operator GET-OBJECT (applied to bananas) . This operator suffers an unsatisfied precondition: The monkey cannot reach the bananas. Therefore. the active subgoal becomes: Reach the ceiling where the bananas are located. How may the monkey proceed at this junclure?

The entire problem can, of course. be solved by standard MEA. However. there is a more direct solution method. II the monkey recalls his observation of the experimenter, he may realile that the problem of reaching the ceiling has already been solved (by the experimenter, as a subgoal to placing the bananas there - although the monkey need not understand the experimenter's higher-level goals). The monkey can apply the pMameter­ substitution T-operator (substituting "monkey" lor "experimenter"), and optionally the solution-sequence truncation T-operator (eliminating the need to return the box to its original location after having used it). This problem-solving process in T-space results in a plan that the monkey can apply directly to reach the bananas, and thus achieve his original goal of having (and presumably eating) the bananas.

The significant aspect of the experimenter-monkey-and­ bananas example is that standard . MEA and T-space MEA were combined into a uniform problem-solving process where standard MEA calls on analogical problem solving to solve a subproblem more directly. The converse process is also possible, and potentially significant. Hence. Analogical reasoning adds a powerful dimension to standard problem solving when prior experience can be brought to bear. but remains largely unobstrusive when no relevant prior knowledge suggests itself.

Additionally, it would be useful lor the problem solver to remember his observations and problem-solving experiences to use as a basis lor future analogical reasoning. These could be remembered directly or abstracted into episodic traces, much like Schank and Abelson's scripts [16, 5]. and hierarchically organized as a function of the goals they fulfill.

3. Evaluating the Analogical Reasoning Process

In an informal experiment, not meant to withstand statistical significance tests, I gave the following problem to .five undergraduate history-and-art students:

Prove that the product of two even numbers is even.

Somewhat to my surprise. none of the live was able to solve this simple algebraic problem, although all live made serious attempts. Later I explained the solution carefully enough to insure that all live understood it:

First, recall the definition of an even number: a number that is divisible by 2.

Second, write down an expression that represents an even number: You may write "2N" where N is any integer, to represent a number divisible by 2.

Next, multiply two even numbers, writing: 2N x 2M, where M is also any integer. Multiplying we get 4NM.

Now, recall the representation of an even number: 2 x any integer. Therefore you can write 4NM = 2 x 2NM, which by closure of integers under multiplication matches the representation of an even number. Hence, the product of two even numbers is even.

At this point, all five students claimed they understood the proof, and moreover expressed some feeling of embarrassment for not having derived such an "obvious" proof themselves. Then, I suggested they try the following problem:

Prove that the product of two odd numbers is odd.

With a grim determination to redeem their previous poor performance all five attempted the problem and three of them succeeded. Briefly:

Odd numbers can be represented as "even + 1" = 2N + 1 for any integer N.

The product, therefore: (2N + 1) x (2M + 1) 4NM + 2N + 2M + 1 = 2(2NM + N + M) + 1, which is the representation of an odd number. 6

This informal experiement strongly indicates that the second problem was solved by analogy from the solution of the first problem. The scratch papers collected from the students suggest direct attempts at transfering and modifying steps of the first solution. The insertion of an extra algebraic step 7 illustrates an appl ication of the subsequence splicing T-operator. Moreover, the mere fact that three of five students were able to solve a problem more complex that the one where all five failed previously, argues very convincingly for an analogical process exploiting the previous solution (or some abstraction thereof) . However, It should be noted that this type of experiment does not in itself demonstrate dominance of analogical reasoning in human problem solving, but rather it provides strong evidence for the ex istence of analogical processes in cognitive activities. Demonstrating the conjecture that analogy is the central inference mechanism for human problem solving would require a much more thorough _(and perhaps more controlled) set of psychological observations.

As a test of the computational feasibility of the analogical problem solving process, . a simple version of MEA was programmed to operate on the transform space, and given a subset of the T-operators with a corresponding difference table. It solved the product -of-two-odds problem starting from the solution for two even numbers. 6 The initial program is not too interesting -­ tt demonstrates that the analogical problem solving process "actually works", but does little else. The truly interesting issues will arise when:

• a much fuller implementation is available allowing comparisons among different problem solving methods over a representative corpus of problems,
• issues of learning from experience are further investigated,
• and the analogical problem solver is integrated with a dynamically-changing long term memory.

6 tnterest·ngly , one student chose to represent odd numbers as 2N + 3, which ts co~r ect but rcquues a bit of additional algeb1aic man·pulation. Of the two students who did not present an adequate proof . one etrcd i·' an algebraic manipulation step, the other was unable to represent odd numbers correctly.

7 1 e .. drstrillutrng the product of the two odd numbers is required to fulfill a precondition of the factoring -a.constant operator that factors 2 from three of the four terms in: 4NM + 2N + 2M + 1.

6 1t used N-1 to . represent an odd nunrber. since the SUB 1 operator was rnadvertently listed· before ADD1 in the obtect·space difference table, and therefore had to splrce rn an addrtionol algebraic step in the solution.

4. Learning as Part of the Problem Solving Process

Let us examine briefly the learning processes inherent in analogical problem solving. My central hypothesis is that human learning occurs as an integral, inalienable aspect of problem solving and comprehension. This does not imply that disembodied concept acquisition and pure grammatical inference are ineffective processes. Such processes are computationally valid but psychologically implausible. Since I am primarily interested in cognitive modeling, I find the creation of a computational model that incorporates both learning and performance as inseparable processes to be an intellectually appealing endeavor. Analogical reasoning provides the basis for such an integrated model. The fact that humans learn in real­ world tasks (by practice, observation, trial and error, etc.) with little or no discernible cognitive effort lends credence to my integration-of-learning-and-performance hypothesis. Moreover, there is evidence that for cognitive as well as_ physical motor­ coordination tasks humans cannot help but learn in the process of repeated practice (14]. This clearly suggests that at least some forms of human learning cannot be separated from cognitive­ performance or motor-coordination systems.

Learning can occur in both phases of analogical problem solving: 1) the reminding process that organizes and searches past experience, and 2) the analogical transformation process itself. The first phase is discussed briefly below, and at greater length by Schank and Lebowitz [9]. The second phase is analyzed in [3] . Environmental feedback (such as success or failure of the planned solution) can trigger solution analysis, where solutions to several similar problems can be considered exemplars for the task of synthesizing a general plan to deal with future problems of the same general type. Simon and others [1, 19] discuss this form of reducing a learning·by-doing problem to a learning·from­ examples task.

4 .1. Episodic Memory Organization

Memory of solutions to previous problems, whether observed or directly experienced, must be organized by similarities in goal states, initial states, and means available (or path constraints present) . Otherwise, there can be no reasonable reminding process when solving future problems of a similar nature. Hence, a hierarchical indexing structure on an episodic memory must be dynamically constructed and extended as the system gradually accumulates new experience. Thus, continuously expanding and ztructuring episodic memory is a relatively simple, but absolutely essential, aspect of learning that proceeds concurrent with analogical reasoning.

5. Concluding Remark

The objective of this paper has been to lay a uniform framework for analogical problem solving capable of incorporating skill refinement and acquisition processes. Most work· in machine learning does not attempt to integrate learning and problem solving into a unified process. (However, Mitchell [11] and Lenat [10] are partial counter-examples.) Past and present investigations of analogical reasoning have focused on disjoint aspects of the problem. No past investigation has resulted in a unified analogical problem solving method. For instance Winston [20], investigated analogy as powerful mechanism for classifying and structuring episodic descriptions. Kling (7] studied analogy as a means of reducing the set of axioms and formulae that a theorem -prover must consider when deriving new proofs to theorems similar to those encountered previously. In his own words, his system " .. . derives the analogical relationship between two (given) problems and outputs the kind of information that can be usefully employed by a problem·solving system to expedite its search." However, analogy takes no direct part in the problem­ solving process itself. Hence, the extension of means-ends analysis to an analogy transform space is, in itself, a new, potentially-significant problem-solving method, independent of the learning mechanisms that it can support.