The Base Selection Task in Analogical Planning

1 Introduction

Analogy is a powerful planning tool. Engineers and sci­ entists rarely attack a problem in an unfamiliar domain from scratch. Instead , then rely on their experience with solving problems in similar domains. They adapt known techniques, map constraints from a solved problem to the new problem, and modify existing solutions to fit t.he cur rent problem specifi cation. Given a. novel problem (the /argel case), an analogical planner selects a similar, solved problem (the base case), computes a mapping be­ tween the base and target problem descriptions, and uses the mapping the adapt the base solution to the current domain. When examples are lacking and domain theory is scarce, the intelligent agent draws on past experience in similar situations to attack a new problem.

Although analogy is considered to be a powerful tool for machine planning, it is also viewed as an expensive task which is rarely applied to large-scale problems. As Buchanan states, analogical reasoning is a "pipe dream when matched against the harsh standards of robust­ ness of commercial applications" [Buchanan, 1990]. A second limitation of analogical planning systems is flexi­ bility. In inductive learning systems, when the learner is not performing well enough more examples can be input to improve the hypothesis. · In analogical learning sys­ tems, the strength of the output plan depends solely on the amount of similarity between base and target and on the strength of the relationship between known and inferred information. If no base cases sufficiently match the target, the system cannot perform as needed .

The purpose of this research is to strengthen the ef­ fectiveness and efficiency of analogical planning, making it a more useful tool for machine learning. This paper describes a method of achieving the stated goal by fo­ cusing on the aspect of analogical planning that is the least researched and perhaps the most limiting: base se­ lection. The base selection process is very expensive, yet the selected base case greatly affects the outcome of the planning process. In this paper, two improve­ ments to base selection are discussed. First, a parallel graph-match base selection algorithm is described that reduces the complexity of the search process. Second, a method of merging congruent base cases when no single base case sufficiently matches the target is demonstrated to improve the fl exibility and applicability of analogical planning. This approach is illustrated on automatic pro­ gramming examples, and is shown to transform analogy into an effective, efficient planner for large-scale prob­ lems.

2 Analogical Planning

Analogy can be defined as an inference that if two or more things agree in some respects they will proba­ bly agree in others. The strength of the analogically­ generated inferences depends on the type and strength of the relationship between the known shared properties and the inferred shared properties.

The three main steps of analogy plan formation are base selection, map formation, and inference generation. Given the target problem that needs a solution, the analogical planner selects a base problem that has a suc­ cessful plan and that shares crucial properties of the problem with the target. When the appropriate base case has been found, the system constructs the analogi­ cal mapping. Once the mapping is formed, the analogy system uses the information describing the base and the base --+target mapping to infer the target plan.

For example, a programmer rarely develops his code from scratch. Instead, he pulls ideas and pieces of code from similar programs he has written in the past, and modifies them to fit the peculiarities of the current goal. If he wants to implement a program that computes real­ number division to a specific accuracy, he may benefit most from analogically deriving the program. First, he finds a program in his database that computes the cube­ root of a real number to a specific precision (base selec­ tion). He senses the underlying similarities between the type of information used and the goal of the programs and pinpoints the correspondences (map formation). Us­ ing these correspondences, he maps the existing code to fit. t.he current situation, and enters the new analogically­ implemented program into his database (inference gen­ eration).

Much of analogy research has focuses primarily on the creation of the base --+ target mapping. Gen­ tner's [Clement and Gentner, 1989; Gentner, 1988; Gentner and Toupin, 1986] theory of systematicity shows that humans use analogies between concepts whose un­ derlying stntctures are the same. Other popular methods of map formation include Carbonell's transformational analogy approach [Carbonell, 1983] which uses means­ ends analysis to reduce the difference between base and target, and the explanation-based approach of Kedar­ Cabelli [Kedar-Cabelli, 1988], which constructs an ex­ planation of the difference between base and target con­ cepts.

Analogical reasoning, though generally considered in­ t.nitive and compelling, is often looked upon a.'3 a com­ fHJt.a.tiona.lly infeasible form of learning. This feeling is fneled by the fact that much attention has been given to the task of finding coherent mappings between base and target. On the other hand, little attention has been given to computationally-complex tasks such as base se­ lect ion. Work focusing on the base selection task in­ cl udes case-based reasoning research [Hammond, 1986a; Hammond, 1986b; Kolodner eta/. , 1985] which uses plan keywords to organize the database and select a base case.

3 Parallel Analogical Planning

A goal of this research is to design an analogical plan­ ning system efficient and effective enough to apply to large-scale problem domains. The implemented system is based on a graph match algorithm, which compares two plans represented as graphs to determine the sim­ il ar ity of the plans. The system is called ANAGRAM (ANAlogical GRAph Match). Given a target problem specification represented in graph form, ANAGRAM's col­ ored graph match technique generates a. plan which will achieve the target goal.

Each plan in ANAGRAM 's database is represented as a directed acyclic graph. The nodes in the graph represent object names and attributes, and the links represent re­ lations between objects. A base case is selected if the structure of the base graph matches the structure of the target graph (embodying Gentner's theory of systematic­ ity).

The system accepts as input two subgraphs, repre­ senting the target problem's initial-state description and goal-state specification. ANAGRAM searches through the database, finding the best match for both subgraphs . Using the output of the individual graph matches, ANA­ GRAM then maps the base plan over to the target domain to generate a solution for the target problem. If the re­ sulting plan is unsuccessful, or if no sufficiently similar base cases are found, the system attempts to merge sev­ eral base cases that are similar to each other and to the target problem. The result is a virtual base graph that eliminates anomalies and generalizes various options in the plan to the extent that it covers the target domain.

3.1 Parallel Graph Match

ANAGRAM's graph match algorithm is implemented on a Connection Machine 2, a Single-Instruction-Multiple­ Data (SIMD) machine with 32,768 processors. The algo­ rithms are implemented in *Lisp, a parallel extension of Common Lisp. ANAGRAM makes use of parallel compu­ tation in two aspects of base case selection . The graph match algorithm which compares a base graph with the target is implemented in parallel, and each base case in the database is examined simultaneously.

In the parallel graph match, the data structure repre­ senting each graph node is stored in a separate CM pro­ cessor. Each node in the first graph looks for a match at the same time with a node at the same level in the second graph. An integer is assigned to each node in the base graph. When a match is found for a node from the base graph, the corresponding target node is assigned the same integer. When testing if node n 1 matches n2, the link labels and the integers a.'3signed to the parents and children of nt are matched with the corresponding labels and integers for n 2 .

The data structure describing each node contains the level of the node in the graph, 1 , the node label, and a tuple which consists of the incoming link labels and cor­ responding parent nodes as well as the outgoing link la­ bels and corresponding child nodes. Initially, nothing is known about parent or child nodes, so the parent/child integer slots are set to "?" . Each node simultaneously looks for a match by comparing levels and tuples . If two complete tuples match (the tuples are complete if they have no "?"s), the match is added to the global map (gmap) and a unique integer is assigned to the two nodes. If a. tuple is incomplete, it generates a list of par­ tial matches. When one or more matches are found , each node in both graphs simultaneously updates its tuples. Assigned integers are propagated across the links . Once the tuples are updated, matches between incomplete tu­ ples are checked once again - if they no longer match , the algorithm returns failure.

1 The level of a node in a DAG is deli ned here as the shortest path length from the node to any leaf in the DAG.

If no unique matches are found for any of the nodes, the algorithm takes one node from the list of nodes hav­ ing more than one candidate match, and randomly se­ lects a match for the node. If there are nodes from the first graph that cannot be matched with any node from t.he second graph, the algorithm returns failure. The process is successfully completed when a match is found for each node in the first graph.

3.2 Parallel Base Selection

Probably the greatest speedup occurs when base selec­ tion is parallelized. Normally, the base selection process is very time consuming because each potential base so­ lution must be compared with the target problem speci­ fication. Fortunately, each of these comparisons is inde­ pendent of the others, so the bases can be examined in parallel.

The time saved by performing base selection in par­ allel is enormous, as would be expected. However, as the database grows large, it is not possible to examine each of the base cases in parallel because of the limit on the number of processors. On the Connection Machine it is possible to create virtual processors (extra proces­ sors which overlay the existing physical processors). Us­ ing the virtual processors eventually degrades the per­ formance of the algorithm, however, and even with the r:xistence of virtual processors it is not possible to ex­ amine a huge database completely in parallel because of 111emory limitations.

For this reason, as the database becomes very large, indices are attached to each ent ry in the database. The indices chosen are ones which do not add new informa­ tion to the graphs; rather, they compress the information contained in the graph. These features include graph in­ variants such as the size of the graph and the degrees of each node. Some indices also encapsulate information contained in the graph such as the list of operators used in the plan. Entries in the database with the same in­ dices are then grouped together . When base selection is performed, the algorithm uses the attributes of the tar­ get. specification to select a group of base cases from the database, and examines these base cases in parallel. In fact. , the number of cases allowed in each database sub­ grollp can be calculated from the size of the individual plans and the number of processors available on the ma­ chine, so that it is always possible to examine the plans within a single group in parallel.

3.3 Example

This section illustrates the application of ANAGRAM's parallel algorithms to automatic programming. Analogy proves to be a valuable tool for automatic programming. Instead of constructing programs from scratch or work­ ing from abstract theories, many scientists start with ex­ isting program segments that achieve similar goals, and n1odify them to meet their current needs.

The following example is based on a program segment d<'scribed by Dershowitz [Dershowitz , 1986] . The base program, a program that computes the cube-root of a within an error tolerance e, is used to generate a program that. computes c/d within an error tolerance e. Figure 1

illustrates the goal-state subgraphs of the base and tar­ get plans .

ANAGRAM successfully matches the initial-state sub­ graphs and the goal-state subgraphs. Tables 1 and 2 show the tuples representing the nodes in the two goal­ state subgraphs at the end of the graph match. The first column represents the node label, the second column lists the integer assigned to the node, the third column shows the corresponding tuple, and the fourth column lists the candidate matches / final match for the node. Note that the tuples are represents as ( { (child-integer outlink­ label) ···}{(parent-integer inlink-label) · · ·}).

The result of the match is the set of node-to-node matches that comprise the global map:

The mapping is used to transform the base program into a program that achieves the target goal. The code segments are shown below.

I* Compute cube-root of a *I begin c ube-root I* Ini tial State *I assert a > 0, e > 0 I* Go;;:l State *I goal I a 1 1 3 - r I< e (r, ·) := (O,a + 1} loop L3 : until · < e end · := ·12 - if r + · ) 3 ~ a then r := r + · end if repeat /* Compute cl d *I begin target /* Initial State *I assert d > c > 0, e > 0 I* Goal S~te *I goal I cl d - q I< e (q,·) := (O,c+ 1} ==> loop L3 : until · ~ e end · := ·12 if a+ ·) X d ~ c then q := q + · endif repeat

After the target plan generation is complete, the plan is tested. If the plan is not successful, ANAGRAM may attempt a new analogy, merging several base cases to form a more flexible analogy. This process is described is section 4. If the plan is successful, the new plan is indexed by its features and added the database.

3.4 Analysis

F'igures 2 and 3 show the results of running the par­ allel and sequential graph match and base selection al­ gorithms. For these experiments, a. database of graphs representing program specifications was created. In the first experiment, the graph sizes range from 4 to 200 nodes. Noise was minimized by generating 50 graphs of each desired size. Three implementations of the graph match algorithm were tested. The first curve represents the sequential version of the algorithm implemented on a Texas Instruments Explorer II. The second curve shows t.he results of the parallel implementation running on a Connection Machine 2. The third curve represents the algorithm running on the CM 2 without taking advan­ tage of the parallelism.

The results shown in the graph match graph come very close to expectation. The actual complexity of the graph match algorithm is O(L n;h J + ((n- h) modp)) , where n is the number of nodes in the graph, h is the height of the graph, and p represents the number of physical proces­ sors residing on the machine. This is linear speedup from the sequential algorithm, which has complexity O(n 2 ).

The second experiment compares sequential and par­ allel implementations of the base selection algorithm. From a. database of 500 graphs, one base case was cho­ sen. When the entire database must be searched, the complexity of the sequential algorithm is proportional to the size of the database, while the parallel algorithm is almost constant . The sequential algorithm actually has complexity O(bn 2 ), while the parallel algorithm is O(lb(n;h}J + (b(n- h) mod p)).

The results of test ing these algorithms reveals that an analogy system implemented on a massively parallel ma­ chine is a powerful and effici ent planning tool. Taking advantage of available hardware allows analogical plan­ ning to be applied to complex problems without unrea­ sonable time expense.

4 Merging Congruent Cases

Implementing an analogy system on a parallel machine transforms analogical planning into an efficient process. However, the tool still suffers from a lack of flexibility. In particular, a base case must be found that is suffi­ ciently similar to the target to analogi cally generate each step of the target plan . Because in actuality there exists a great diversity among graph representations of plans , the chance of finding such a similar base case is slim. Although analogical learning is sometimes preferred to inductive learning because it does not require multiple examples, there are many instances in which multiple base cases would strengthen an analogy.

One example of using multiple base cases is incremen­ tal analogy [Burstein, 1988]. One base case may provide some of the information needed for the target, but not all . Another base case may provide the remaining needed information , but nothing else. An analogy formed be­ tween the target and either one of these bases would be insufficient, but the merging of the two separate analo­ gies results in a complete, useful analogy.

A second way of using multiple base cases is to merge similar base cases, resulting in a "virtual" base case. This virtual base case is more beneficial to the analogy than a single case, because it removes anomalies and generalizes alternative operations. Furthermore, merg­ ing base cases focuses the analogy on the relevant as­ pects of the base cases, because those aspects of previous plans that are beneficial to the target are retained in the vir tual base. Base cases that are sufficiently similar in st ruct. ure to be merged together are termed congruent base cases 2

4.1 The Merge Algorithm

'!'his section describes how ANAGRAM merges congru­ ent base cases to enhance its analogy-formation and problem-solving capabilities. The issue of deciding when t.o merge plans is first addressed, and then the merging rnethod is described .

ANAGRAM uses the graph-merge algorithm in the fol­ lowing cases:

• A match is found between the target initial/goal states and the base initial/ goal states, but the in­ termediate steps in the base case are not mappable or cannot be applied in the target domain.
• No base case matches perfectly, but several match rather closely. Moreover , the unmappable parts ei­ ther 1) are generalizable in a way that map to the target plan, or 2) they do not overlap (the base cases fail to match the target at distinct points in the tar­ get graph).

When selecting bases for merging, the algorithm chooses cases based on ease of generalization. The types of graph merge are (in order of preference):

• I . Merging graphs with distinct base/target differences. The simplest and most benefi cial method of merging occurs when the candidate base graphs match each other and their differences with the target do not overlap, as shown in figure 4. The mappable por­ tions of each base are retained in the virtual base graph .
• Relaxing order constramts . The graph match algo­ rithm looks only for matches between nodes at cor­ responding levels in the graphs. Often an operator

2 This term is borrowed from geometry, where two trian­ gles are congruent if they have the same angles and propor­ tions of side lengths.

re-ordering will make a base case fit the target ex­ actly. Comparing multiple plans whose only differ­ ence is the order of operations, it becomes apparent that maneuvering the operators may also solve the target problem. When this situation arises, Ana­ gram looks for correlations between the order of op­ erations and ordering constraints in the initial or goal state.

1. Disjunction/generalization of subgraphs . When comparing subgraphs whose "defective" parts do overlap, ANAGRAM generalizes the overlapping sub­ graphs. The methods of generalization correspond to those found in most induction systems, such as adding disjunctions and climbing generalization trees. The purpose of the generalization is to ab­ stract the non-mappable subgraphs to th extent that the generalized subgraph will cover the tar­ get case. As the number of base cases included in the generalization increases, the method of merging base graphs begins to behave similar to pure induc­ tion.

4.2 Example

This section describes an application of ANAGRAM's graph merge algorithm to a problem in the domain of au­ tomatic programming. In this example, the target goal is to construct a program that uses inorder traversal to traverse a given binary tree. The initial and goal state descriptions are given :

Among the base cases residing in the database are the algorithms for preorder and postorder tree traver­ sal. The matches are equally good with either base case, so the selection process arbitrarily chooses the preorder plan. However, the resulting program is

begin inorder x := root(tree) unless null(tree) end vlist := append(vlist, x) inorder(left-son(x), vlist) inorder(right-son(x), vlist)

This does not solve the problem (remember that the graph matcher does not consider re-ordering the opera­ tors). The system then compares the preorder and pos­ torder algorithms, and notices that the operators are the same in the two algorithms, but the ·order of applica­ tion is different . The goal description in both base cases places ordering constraints on the output :

goal-preorder: V(y E vlist) (y before left-son(y) before right-son(y)] goal-postorder: V(y E vlist) (left-son(y) before right-son(y) before y]

By comparing the order of operators with the order imposed by the goal description , ANAGRAM observes that the placement of y corresponds with the append operat ion, left-son(y) with the recursive call to the left son, and right-son(y) with the recursive call to the right son. ANAGRAM is able to generate a virtual base graph that contains the correspondences between the three op­ erators and the desired order of elements in vlist. The resulting target plan shown below is successful.

begin inorder x := root(tree) unless null(tree) inorder(left-son(x), v list) vlist := append(vlist, x) inorder(right-son(x), vlist) end

5 Conclusions and .FUture Directions

This paper presents two steps .that make analogical plan­ ning a more effective and efficient machine learning tool. There are many extensions of this research which could push the advancement of the area even further. Search­ ing for and combining partial matches would be a ben­ eficial alternative to merging base cases. Developing a fuzzy graph match would allow a broader range of analo­ gies to be created. Other aspects of the analogical plan­ ning task could be parallelized, such as inference gen­ eration. In addition, other parallel architectures should he analyzed . for their potential to speed up the analogy process. For example, a hypercube MIMD architecture could be used to develop multiple independent analogies for the same target, or expand multiple partial matches simultaneously.

In this paper, the parallel graph match and base se­ lection algorithms were described as implemented on the Connection Machine. The results were substan­ tially faster than results from the comparable sequential method. In addition, a method of combining the benefits of several successful plans by merging multiple base cases was presented. The extension of analogy to utilize mul­ tip le base cases was shown to increase the effect iveness of analogical planning in large problem domains. By designing efficient parallel analogy algorithms, and by extending the applicability of analogical planning, this research offers a valuable step toward the automation of analogical planning.