Stratified Case-Based Reasoning: Reusing Hierarchical Problem Solving Episodes

1 Problem and Proposed Solution

Case-based reasoning (CBR) is a problem-solving paradigm that focuses on the retrieval , revision, and reuse of stored solutions to solve newly presented prob­ lems (Kolodner, 1993; Aamodt & Plaza, 1994) . The rep­ resentation of cases can be simple (e.g., feature vectors) or complex (e.g., semantic networks). An advantage of simple representations is that retrieval and revision algo­ rithms for such representations have comparatively low computational cost . However, this low computational cost comes at the expense of limited representational power. For example, the relational knowledge required for such tasks as planning, design, and analogical rea­ soning is difficult to express in a feature-vector case rep­ resentation. However, more expressive case representa­ tions require more expensive retrieval and revision func­ tions. For example, when cases are represented as se­ mantic networks, case matching requires subgraph iso­ morphism determination, an NP-complete task (Garey & Johnson, 1979).

In this paper, we propose using abstraction to com­ bat the complexity associated with expressive case rep­ resentations . We explain how abstraction can be used to reduce this complexity in Section 2 and describe an example task in Section 3. Section 4 then introduces a set of algorithms that implement our approach. We David W. Aha Navy Center for Applied Research in AI Code 5510

Naval Research Laboratory

Washington, DC 20375

aha@aic.nrl.navy.mil

(202) 767-9006 I FAX: -3172

evaluate their capabilities in comparison with simpler case-based and abstraction approaches in Section 5 and discuss related work in Section 6.

2 Abstraction: Reducing CBR Complexity

Two principal approaches exist for reducing the complex­ ity of indexing and matching complex cases on sequen­ tial machines. 1 One approach is to precompute some portion of the match between cases (e.g. , by organiz­ ing cases into a hierarchy partially ordered by subgraph relations (Levinson, 1991)) . An alternative approach in­ volves using case abstractions for indexing and match­ ing. Previous use of abstraction in indexing has generally focused on thematic abstractions, such as goals (Ham­ mond, 1989) or expectation failures (Schank & Leake, 1989). Use of abstraction in case matching has gener­ ally been limited to feature generalization (e.g., finding common ancestors of new-case and old-case features in a hierarchy that encodes subsumption relations on fea­ tures values (Porter et al., 1990)) .

This paper advocates a new approach for using ab­ straction in CBR. Underlying this approach is the ob­ servation that hierarchical problem solving 2 gives rise to . solutions at multiple levels of abstraction. If the solu­ tions produced by hierarchical problem solving at every level of abstraction are retained, then the more abstract solutions can assist in indexing, matching, and adapting less abstract solutions. We refer to a case whose repre­ sentation has multiple abstractions as a stratified case, and we define stratified CBR as the use of stratified cases in case-based problem solving. The potential benefits of this approach are:

• Indexing and retrieval. A more abstract solution to a problem can provide an accurate index to less abstract solutions to the problem because it consists

1 See (Kolodner, 1988) and (Kettler & Hendler, 1994) for related work on machines with parallel architectures.

2 In hierarchical problem solving, search is performed in an abstraction of the original search space. The solution in the abstract space is then used to guide problem solving in the original space. Where applicable, this technique can lead to significant reductions in search time (Sacerdoti, 1974; Holte et al., 1995; Knoblock, 1994; Bacchus & Yang, 1994).

of the most important aspects of the less abstract solutions.

• Matching. Retaining case abstractions permits cases to be compared in an abstract space in which matching may be much less expensive than at the ground level of abstraction.
• Adaptation. An abstraction of a stored case may be much easier to reuse than the ground-level case itself. Stratified cases can be reused at the most specific level of abstraction at which they can be ap­ plied to the given problem without requiring adap­ tation of less abstract, non-matching facts.

Since stratified CBR involves reusing hierarchical problem solving episodes, its applicability is limited to domains in which there is an abstraction hierarchy suit­ able for hierarchical problem solving. However, several techniques that automatically derive abstraction hierar­ chies have recently been developed, and the development of new techniques is the focus of an active research com­ munity (Knoblock, 1994; Christensen, 1990; Bacchus & Yang, 1994).

3 The Route-Finding Task

We chose a route-finding task to demonstrate the util­ ity of stratified case-based reasoning because this task is an important area of activity in robotics and is amenable to hierarchical problem solving. Our task involves finding an optimal or near-optimal path be­ tween a given pair of start and goal positions through a field containing obstacles. We chose to work with fields described by N x N arrays of positions, where N is a power of 2. This allowed us to define a sim­ ple abstraction hierarchy in which an abstract posi­ tion at Level 1 position (R, C) (zero indexing) ab­ stracts over the following four ground-level positions: (2x R,2 x C),(2 x R,2 x C+ 1),(2 x R+ 1,2 x C), (2 X R + 1' 2 X c + 1).

Figure 1 shows a situation in which S and G denote the start and goal positions. The figure on the left is a ground level field containing 64 positions, where the grey positions denote obstacles, while the field on the right is its Level 1 abstraction.

The goal of this task is to locate a route connecting the start and goal positions. We modeled this as the task of constructing a sequence of straight and curved track segments, or traversal operators, such that the start and goal positions lie at the ends of the connected track. We associate with each position the set of operators that can be used to traverse it. Thus, each unblocked position at the ground level is associated with all possible operators, which are shown in Figure 2. Each blocked position is associated with the empty set of traversal operators since traversal through them is impossible.

Determining the available operator set for each ab­ stract position involves determining (1) what operators are available for each of the four positions it abstracts and (2) which of the six operators, if any, are still possi­ ble after joining these four lower-level positions. For ex­ ample, while all six traversal operators are available for the top-left abstract position, the only operators avail­ able for the position to its right are {A, C, F} (i.e., the others are unavailable because no traversal through this abstract position can reach the position below it) .

We restricted our consideration to fields whose ob­ stacle configurations guarantee that hierarchies created using our abstraction operators satisfy the downward refinement property (Bacchus & Yang, 1994) (i.e., ev­ ery abstract solution can be refined to a concrete solu­ tion, if a concrete solution exists) . 3 Thus, we considered only fields for which hierarchical problem solving reduces search.

The stratified CBR approach to this problem is to re­ tain and reuse the solution paths found at every level of abstraction in hierarchical search. Retaining abstract solutions decreases the cost of finding the most similar stored solution path because the distance from the new start and goal to these paths can be accurately measured at the highest levels of abstraction, where search is much less expensive (i.e., since the fields are smaller in size).

4 Algorithms

This section introduces two non-CBR algorithms and five CBR algorithms (Table 1) that can be applied to the route-finding task. Each of the CBR algorithms retrieves and reuses previously stored solutions while prob­ lem solving. They can be distinguished by (1) whether they access cases stored at only the ground level or at all abstraction levels, and (2) whether they support perfect or partial matching.

3 The downward refinement property is satisfied for our ab­ straction operators if (1) all adjacent obstacles are arranged in rectilinear regions and (2) whenever the length of a se­ quence of adjacent obstacles is at least the size of an abstract region at some level of abstraction, then its width is at least the region size minus 1.

4.1 Non-CBR Algorithms

We considered two non-CBR algorithms for the route­ finding task. The first is best-first search (A ·) using manhattan distance as the heuristic estimation of dis­ tance from the current position to the goal position. The second is hierarchical A ·, which uses A · to find a path from the start position to the goal position in the high­ est level abstraction of the given field . At each lower level of abstraction, search by A · is restricted to posi­ tions falling within the solution path at the next higher level of abstraction.

The cases used by the CBR algorithms described be­ low are generated by hierarchical A ·. Given an abstrac­ tion hierarchy for a particular field and start and goal positions, hierarchical A · generates a path connecting the start and goal positions at every level of abstraction. Each solution at a given level of abstraction is treated as a separate case. A refinement of a case (i .e., a solution at the next lower level of abstraction) is termed a child of the case, and a case is termed the parent of its refine­ ments. Since distinct positions at the ground level may be identical at more abstract levels, distinct cases at a lower level may have identical parents. Cases can there­ fore be organized into a forest of taxonomic trees. A case library consists of a taxonomic forest of cases sharing a common abstraction hierarchy but distinct pairs of start and goal positions.

4.2 Ground level CBR algorithms

The simplest of the CBR algorithms is GROUND CovER (Table 2), which searches the case library for ground solution paths that include the new start and goal po­ sitions. If any are found, then it returns a randomly­ selected shortest solution path. Otherwise, it invokes A · to find a solution.

The second ground level CBR algorithm is GROUND CLOSEST (Table 3), which also searches the case library for ground solution paths that include the new start and

Given: S: start position G: goal position Lib: case library GROUND-COVER(S,G,Lib) = Cases : = ground~eveLmatches (S, G, Lib) IF (Cases =f 0) THEN random( shortest...sol ut ion (Cases)) ELSE best_tirst...search(S ,G)

GROUND-CLOSEST(S ,G ,Lib) = Cases := ground~evel..matches(S,�,Lib) IF (Cases =f 0) THEN random( shortest...solut ion (Cases)) ELSE random(shortest...adapted...solution(S, G ,Lib))

goal positions. If none are found, then GROUND CLos­ EST adapts each ground case (i.e., uses A* to locate the shortest paths joining the new start and goal positions with the stored case's solution) and returns the shortest adapted solution. Thus, this algorithm supports partial matching. To prevent retrieval from increasing in pro­ portion to the size of the case library, GROUND CLOS­ EST uses a modification of A · that prunes each node n for which f(n) is greater than the cheapest adaptation found so far. Thus, GROUND CLOSEST performs best­ first search for the shortest adaptation paths within each case, but branch-and-bound search through the case li­ brary for the case with the shortest adaptation paths.

4.3 Stratified CBR algorithms

The three stratified CBR algorithms can reuse case so­ lutions stored at any abstraction level. Each of these algorithms starts by retrieving from the case library the set of most specific matching cases (i .e., lowest-level cases whose solutions include abstract positions that abstract the given start and goal positions). This search begins at the root of the case library, recurses with its children (i.e., top-level abstractions of solved cases) , and contin­ ues recursing until it reaches the ground level (in which case the segment of a solution connecting the new start and goal positions is returned) or cases that no longer cover both the start and goal positions.

In the latter case, the first algorithm, COVER (Ta­ ble 4), randomly selects one of the most specific match­ ing cases and performs hierarchical A · starting at the next lower level of abstraction, restricting search to posi­ tions falling within the solution path in the most specific matching case.

In contrast, the second algorithm, CLOSEST (Ta­ ble 5), supports partial matching between new problems and previous solutions. Starting with the most specific

CoVER(S,G,Lib) = Cases := most...specific..matches(S,G,Lib) Case := random(Cases) hierarchicaL.solve(S ,G ,Case)

CLOSEST(S,G,Lib) = Cases := most...specific..matches(S,G,Lib) CLOSEST ...RECURSE (S, G, Cases) CLOSEST ...RECURSE (S, G, Cases) = Refined_cases = refine(Cases) Adapted_cases = adapt (S, G, Ref ined_cases) Best_cases = shortest(Adapted_cases) IF (ground....level(Best..cases)) THEN random(Best..cases) ELSE CLOSEST ...RECURSE (S, G, Best_cases)

mat<>hing cases (or the most abstract cases, if no cases match) CLOSEST finds the refinements of each case (i.e., the case's children), adapts each refinement (i .e., uses A · to find the shortest adaptation paths from the start and goal positions to the solution path at that level of abstraction, restricting search to positions in the par­ ent case's adaptation paths), and selects the refinements having the shortest adapted solution paths. 4 CLOS­ EST recursively calls these three steps until the ground level is reached, at which time it randomly selects and returns an adapted case.

The final algorithm, CLOSEST THRESHOLD (Table 6) attempts to recognize situations in which adapting an existing case will be more expensive than problem solv­ ing ab initio. CLOSEST THRESHOLD behaves identically to CLOSEST if there are matching cases. However, if there are no matching cases, then CLOSEST THRESHOLD uses A · to find the shortest path from the start to the goal position at the highest level of abstraction. If there are top-level cases whose adapted solution paths are no longer than the path length found by A · , then CLOSEST THRESHOLD treats these cases in the same manner as CLOSEST. If there are no such cases, then CLOSEST THRESHOLD uses hierarchical A · rather than CBR.

4 To prevent the perlormance of CLOSEST from degrading when there are large numbers of redundant cases (i.e., cases with equally short adapted solutions), CLOSEST perlorms two additional types of pruning. First, among cases with the shortest adapted solution paths, CLOSEST retains only those for which the sum of the lengths of the paths from the start and goal positions to the previous solution path are least. Second, below the highest level of abstraction, if there are multiple cases for which the paths from the start and goal positions to the previous solution path intersect the previous solution path at identical positions (i.e., multiple cases for which the reusable segments of the old solution paths are indistinguishable), then only one such case is retained.

CLOSEST-THRESHOLD(S,G,Lib) = Cases : = most...specific..matches (S, G, Lib) Best : = shortest...solution(S, G) IF ( length...of ...shortest...solut ion (Cases) > length(Best)) THEN hierarchical..sol ver (S, G, Best) ELSE CLOSEST ...RECURSE (S, G, Cases)

5 Empirical Evaluation

Previous work has demonstrated the advantages of hi­ erarchical problem solving over non-hierarchical meth­ ods(e.g., Holte et al., 1995; Knoblock, 1994; Bacchus & Yang, 1994). We focus here on demonstrating the utility of reusing the abstract solutions generated by a hierarchical problem solver. Therefore, this section de­ scribes empirical comparisons of case-based vs. non-case­ based approaches for hierarchical problem solving. We also include comparisons with non-hierarchical methods, both case-based and otherwise, to verify that the more storage-intensive hierarchical approaches deliver better performance.

5.1 Hypotheses and experimental variables

The empirical hypotheses explored in this section are:

1. Reusing stored case solutions decreases search costs.
2. Reusing abstract case solutions decreases costs more than reusing only ground-level solutions.
3. Partial matching yields lower search costs than per­ fect matching.
4. Preventing expensive partial matching (via thresholding) yields the best performance on this task.

We will compare the five algorithms described in Sec­ tion 4 against A · and hierarchical A · . The primary de­ pendent variable of interest is work effort as measured by the number of nodes expanded by A · in the course of executing each algorithm. 5 We will also not discuss the lengths of the algorithms' solutions since they were all very similar. 6 The independent variables are

1. the size of the case base,
2. the number of abstraction levels, and
3. the distribution of selected problems (i.e., start and goal positions).

5 We ignore the additional computational costs incurred by the hierarchical and case-based algorithms. The one-time cost of building a hierarchy is 0( N x 0), where N is the num­ ber of ground level positions and 0 is the number of traversal operators. This cost is amortized over each set of training and testing problems drawn from a single ground level field and obstacle configuration. The cost of case retrieval is reduced to a constant by hashing cases on their abstraction level, start position, and goal position.

6 1n Experiment 2, their averages varied from 154.8 (A") to 157.3 (Ground Closest).

We expected that the benefits of case-based reasoning, as measured by decreased search costs, would increase as the library size increases. Similarly, we expected the cost of searching to .decrease as the number of abstrac­ tion levels increases. Therefore, we expected the utility of stratified CBR to increase with the number of abstrac­ tion levels. Finally, we expected problem distribution to affect problem-solving behavior. 7 Therefore, we experi­ mented with distributions that vary the average solution path length.

5.2 Experiments

We varied one of the independent variables listed above in each of three experiments. The settings for the other two variables were held constant at default values (see Table 7). All the reported results refer to averages over sets of 100 testing problems. Each set is decomposed into ten subsets of ten problems. Each subset refers to a different layout of obstacles, where the layouts are con­ strained as described in Section 3. Each algorithm was applied to the same set of training and test sets.

Varying the number of cases

We varied the number of stored cases while fixing the field size to be 32 x 32 and the number of abstraction levels to three. The problems were selected so that the start and goal positions were on "opposite ends" of the field, meaning that the value of one randomly selected dimension (e.g., row) was chosen randomly and the other (e.g., column) was fixed to maximally distance the two positions.

Figure 3 summarizes the results. Since A* and hi­ erarchical A* do not use stored cases, their results re­ main constant. The five CBR algorithms all outper­ formed A*. GROUND CoVER's work effort decreased lin­ early with library size, indicating that it found almost no stored matching problems for small-sized case bases but occasionally found such matches for larger case bases. GROUND CLOSEST outperformed GROUND CoVER for larger case bases, which indicates the benefits of adapt­ ing stored solutions when they are sufficient in number and similarity to new problems.

The performance improvement delivered by the three stratified CBR algorithms was dramatic. COVER's av­ erage work effort decreased linearly with library size, indicating the utility of reusing stored solutions at differ­ ent abstraction levels. This approach significantly out­ performed GROUND CoVER (p < 0.025 for 50 training cases), indicating that the stratified approach is bet­ ter than the non-stratified CBR approach for this task. Similarly, CLOSEST significantly outperformed GROUND CLOSEST (p < 0.1). Finally, CLOSEST significantly out­ performed CoVER (p < 0.05), indicating that partial matching is preferable to perfect matching on this task. However, no significant difference was found (i.e., for 50 training cases) suggesting that the thresholding algo­ rithm outperforms CLOSEST. Thus, these results sup­ port our first three hypotheses, but not our fourth.

7Past cases with short solution paths at the ground level are less likely to contain segments useful for subsequent prob­ lems. Similarly, the benefit of case reuse is less likely to out­ weigh the overhead of retrieval and adaptation in new prob­ lems involving start and goal positions that are near to each other, since such problems can be inexpensively solved ab initio.

Varying the number of abstraction levels

In this experiment, we fixed the size of the ground level field to be 64 x 64 and varied the number of abstraction levels. The results for A* and the non-stratified CBR · algorithms remain constant since they are not effected by stored cases at varying abstraction levels .

In contrast, Figure 4 shows that the search costs ofthe hierarchical problem solver and the stratified CBR algo­ rithms decrease with the number of abstraction levels. COVER, as expected, performs slightly better than hi­ erarchical A* because it reduces search whenever it finds a perfect (abstract) match and otherwise does not in­ cur additional search costs. The partial matching strat­ ified CBR algorithms perform poorly when only a few abstraction levels are used because adaptation is costly when the positions along a solution path lie far from the start and goal positions. However, they perform signifi­ cantly better than the other algorithms (i.e., at least at the p < 0.1 level) when four abstraction levels are used since adaptation is much less costly in the higher abstrac­ tion levels. Although CLOSEST outperformed CLOs­ EST THRESHOLD, their differences were not significant. These results again support the first three hypotheses described in Section 5.1 and contradict the fourth.

Varying the problem distribution

In Experiment 3, we varied only the way in which prob­ lems (i.e., pairs of start and goals positions) were se­ lected. We used the opposite ends strategy in the other experiments, which chooses positions that are maximally distant in the space along one axis and randomly selected on the other axis. This is a favorable bias for stratified CBR since it guarantees long solution paths, which in­ creases the probability of reuse. We add two strategies here that decrease this probability: random, which se­ lects positions randomly, and opposite sides, which se­ lects positions randomly but guarantees them to be on opposite sides of one of the two dimensions. These three strategies differ in the degree to which they prevent the selection of nearby start and goal positions. Random al­ lows selection of such pairs. Opposite sides prevents this to some degree, and opposite ends prevents this entirely.

Figure 5 summarizes the results for this experiment.

As expected, search costs rise for A · and Hierarchical A · as the average minimum solution length increases (i.e., it was 34.2, 42.9, and 61.4 for random, opposite sides, and opposite ends respectively). This increase also yields abstract solutions that require less search to adapt (i.e., since they cover more of the space), which explains why CBR performance improves as solution length in­ creases. The stratified CBR algorithms again outper­ formed the ground CBR algorithms, and the stratified partial matching algorithms outperform COVER.

5.3 Summary

The results of our experiments provide initial support for the first three hypotheses stated in Section 5.1. The CBR algorithms outperform the non-CBR algorithms on which they are based (i .e., especially for the op­ posite ends problem distribution), which supports the claim that solution reuse can decrease search costs. The stratified CBR algorithms outperform the ground level CBR algorithms, which supports the claim that the reuse of abstract case solutions further improves perfor­ mance. The partial matching algorithms (i.e., CLOs­ EST and GROUND CLOSEST), outperform the perfect­ matching CBR algorithms (i.e., COVER and GROUND CovER) . Finally, the results of CLOSEST THRESHOLD reflects how it mediates between these two extremes, but it does not outperform CLOSEST, contradicting our fourth hypothesis (i.e., that thresholding yields the best results) . However, we conjecture that, for case libraries for which the adaptation cost of the best case is suffi­ ciently high, thresholding will be beneficial.

6 Discussion and Related Work

The distinguishing characteristic of stratified case-based reasoning is its reuse of stored solutions at all abstraction levels. Holte et al.'s (1995) alternating opportunism al­ gorithm similarly uses hierarchical refinement to reduce search costs. It caches, in each state in the search space, information that simplifies A* search (i.e., g(n) and h(n) values). Their approach is complementary to ours in that it reduces search effort from a state-oriented rather than a solution-path perspective.

CBR adaptation methods are typically either trans­ formational, which retrieve solutions and apply adapta­ tion operators to revise them to solve a new problem, or derivational, which replay the derivations of problem­ solving episodes (Carbonell, 1986). Stratified CBR em­ ploys a transformation approach that uses more abstract solutions to index and guide the adaptation of less ab­ stract solutions. Since stratified CBR partitions cases by level of abstraction rather than by stages of goal reduc­ tion, it is applicable to tasks that use problem-solving methods other than goal reduction. Moreover, we hy­ pothesize that in tasks that use goal reduction stratified CBR will often order goals by degree of constraint more effectively than derivational analogy, because abstrac­ tion is often more indicative of degree of constraint than order of appearance in a goal-reduction graph.

The PRIAR (Kambhampati, 1994) framework for plan modification embodies many stratified CBR char­ acteristics. PRIAR retrieves solutions with minimum predicted adaptation costs and uses causal dependency structures to guide adaptation via a minimum-conflict search strategy. These structures function as partially­ ordered abstraction hierarchies for decomposing actions. Retrieved abstract solutions are not guaranteed to be refinable and can be extended during adaptation (i.e., with additional planning). Previous work on PRIAR has focused on its semantics and its applicability rather than on isolating the contribution of resuing abstract so­ lutions. Haigh et al. (1994) integrate derivational anal­ ogy with a limited (i.e., two abstraction levels) stratified CBR approach. Their work focused on a route planning task rather than on isolating the contributions of strat­ ified CBR. Hanks and Weld (1995) describe a similar general framework that permits adaptation of abstract plans. However, unlike stratified CBR, this approach does not use more abstract solutions to index less ab­ stract solutions.

Explanation-based learning (EBL) (Mitchell et al., 1986) resembles stratified CBR in that a macro derived by EBL algorithms from a proof of concept membership constitutes an abstraction of the proof (i.e., a general­ ized example). However, EBL systems typically allow reuse at only a single level of abstraction for each gener­ alized example, whereas stratified CBR allows reuse at any level of abstraction.

We believe that the stratified CBR approach could be beneficially incorporated into EBL algorithms, into hi­ erarchical reinforcement learning approaches (Kaelbling, 1993), and into other AI approaches involving hierarchi­ cal problem solving. We view it as a general contribution to AI research on abstraction and envision its incorpo­ ration into many multi-strategy systems.

7 Conclusion

This paper has described stratified case-based reasoning, an application of case-based reasoning to hierarchical problem solving. An empirical evaluation in a route­ finding task demonstrated that this approach can lead to significantly lower computational costs than either hier­ archical problem solving ab initio or ground-level CBR. Moreover, the evaluation showed that reusing abstract solutions yields better performance than reusing only ground level solutions, that the performance benefit of stratified CBR increases with the size of the case base and with the number of abstraction levels, and that par­ tial matching outperforms perfect matching.

Acknowledgements

Many thanks to Patrick Harrison for supporting this re­ search and for discussions leading to this paper. Rob Holte's input and feedback were also valuable. This re­ search was supported in part by a Visiting Summer Fac­ ulty Research Grant from the Naval Research Labora­ tory.