Using Introspective Reasoning to Refine Indexing

1 Introduction

A number of studies have examined the use of meta­ reasoning to control the application of system domain knowledge and to guide acquisition of domain knowl­ edge (e.g., [Bradzil and Konolige, 1990; Davis, 1982]). A more recent use of introspective reasoning is to moni­ tor a system's own reasoning processes in order to refine those processes by failure-driven learning (e.g., [Collins et al., 1993; Ram and Cox, 1994; Cox and Freed, 1995]). This paper presents an approach to introspective reason­ ing for refining the case retrieval criteria of a case-based planning system.

In the approach we are investigating, an introspec­ tive reasoning component monitors the processing of a case-based reasoning system and evaluates that process­ ing in comparison to expectations for the ideal perfor­ mance of the case-based reasoning process (for exam­ ple, the expectation that the case retrieved will be the one that is easiest to adapt to the new situation). Fail­ ures are detected and learning occurs when performance deviates from the ideal. The failure is explained, an appropriate repair is identified, and the underlying sys­ tem is modified to correct the failure. We have devel­ oped a system that applies this process to refine the indices used for case retrieval in a case-based planning system. Our program, ROBBIE, combines a case-based planner as its performance system with an introspec­ tive reasoning component which monitors its reasoning and guides introspective learning [Fox and Leake, 1995; 1994].

*This work was supported in part by the National Science Foundation under Grant No. IRl-9409348.

1 Re-Organization of Behavior By Introspective Evaluation

Applying introspective reasoning to CBR is novel in that learning in CBR systems is generally focused on acquiring domain knowledge, by acquiring new cases. ROBBIE learns new cases, but its primary focus is on the use of introspective reasoning to refine how its cases are applied. The component described in this paper, which refines indexing, is fully implemented. Our ultimate goal is to apply introspective learning to all parts of the CBR process-retrieval, adaptation, and evaluation of cases.

This paper has two parts. The first describes the ROBBIE system and its approach to introspective learn­ ing. The second presents an evaluation of the effects of introspective reasoning on ROBBIE's learning process. The desired effect is an improved ability to focus on rel­ evant cases: a decreased average number of candidate cases retrieved, and the ability to retrieve cases that the system is more likely to adapt successfully. We evaluate system performance in light of these goals and briefly sketch the new costs that introspective reasoning entails and how the benefits balance against them. We close by relating our approach to other work on re-indexing and learning at a meta-level, and describing future directions for the ROBBIE project.

2 Motivations

. Case-based reasoning systems use stored past experi­ ences to solve current problems, and learn by storing new solutions for future use [Kolodner, 1993; Riesbeck and Schank, 1989]. When a new problem is presented, its description is used to create indices to guide retrieval; the cases in memory with the most similar indices are re­ trieved. The retrieved cases are adapted to fit the new situation and the resulting solution is stored in memory for use under similar circumstances in the future.

The performance of any CBR system depends on using the right features for indexing cases, and having a mea­ sure of similarity that correctly selects adaptable cases from memory. If the wrong case is retrieved, adaptation may be costly or even impossible, depending on the CBR system's adaptation capabilities. The problem of deter­ mining feature relevance and good measures of similarity for retrieving cases may be difficult and time-consuming for the system designer.

One aim in combining an introspective reasoner with a case-based reasoning system is to allow the CBR system itself to determine when and how to refine its indexing criteria. ROBBIE can improve its assessment of simi­ larity over time by learning the correct features to use in indexing, and extensions are underway to enable it to improve other parts of the CBR process as well (such as case adaptation).

3 The ROBBIE System

ROBBIE has two main parts, a case-based planning sys­ tem that develops plans for traveling through an unfamil­ iar city (and applies them through simulated execution), and an introspective model-based reasoner, as shown in Figure 1. The planner carries out its low-level task and interacts with the simulated world, and in parallel the introspective reasoner monitors the planner's reasoning processes. If a problem is detected, the introspective rea­ soner may suspend planning while it repairs the reason­ ing problem, or it may permit the planner to continue and wait until more information becomes available to make a repair.

3.1 The Performance Task: Pedestrian Navigation

The performance task of ROBBIE is to navigate around a simulated set of city streets as a pedestrian. ROB­ BIE is given a starting location and a goal location and must create a plan for getting from the one to the other. Because the system does not have a perfect map nor a perfect retrieval mechanism, generation of a candidate plan does not assure successful execution. After plans are generated, ROBBIE executes them, using a sim­ ulated robot based on Firby's reactive planner [Firby,

• A Adaptation will finish in less than "max­ steps-taken" number of steps
• B Similarity assessment will rank cases cor­ rectly (the truth of this assertion is defined by the truth of three specific assertions it is linked to)
• C The retrieved case will be correctly formed (this also depends on more specific asser­ tions for its truth, including D)
• D The retrieved case will contain some plan steps (this communicates its truth up to C: the value is found by examining underlying knowledge structures)

Table 1: Assertions from the ROBBIE model

1989]. This plan execution serves as a means of eval­ uating the quality of the CBR-created plan, as well as permitting ROBBIE to arrive at a solution despite flaws in the CBR-produced plan, providing a way to augment its case base. In addition, the reactive planner handles facets of the simulated world that cannot be predicted by the CBR system, such as traffic lights and blocked streets.

The plans in memory are indexed by their starting and ending locations, as well as other features ROBBIE has learned to use through its introspective reasoning. Plan retrieval in ROBBIE is a two-stage process: first ROB­ BIE gathers a pool of generally similar candidate cases, then it selects the best candidate from that pool. Plans describe navigational actions in terms of high-level plan steps such as "Move north on Oak to Birch" or "Turn east on Fir." These steps are then used as sequential goals for reactive execution, which breaks the problem down into individual steps for the simulated robot to execute.

3.2 The Introspective Task

The higher level task for ROBBIE is to improve its reasoning processes in response to detected reasoning failures. ROBBIE's approach uses an explicit, declara­ tive model describing the underlying system's reasoning processes [Fox and Leake, 1994; Birnbaum et al., 1991; Freed and Collins, 1994]. The model provides expecta­ tions about the ideal reasoning behavior of the system; the actual reasoning of the system is compared to this ideal as a means of detecting reasoning failures. Once a reasoning failure is detected the model is used to cre­ ate an explanation of the failure and to suggest a repair (See [Fox and Leake, 1994] for a discussion of ROBBIE's failure detection). Currently, ROBBIE can learn new features to use in indexing memory, and can re-index its memory to pay attention to those features.

The introspective model consists of a structured set of "assertions" about portions of the CBR reasoning pro­ cess. Each assertion describes a feature that would be true of an ideal CBR system. Table 1lists a few of the as­ sertions from the model for ROBBIE. Assertions range in specificity from implementation details of ROBBIE, such as assertion A in table 1, to abstract descriptions of the CBR process and the flow of control between its components, such as assertions B and C.

The assertions are organized by the component to which an assertion refers, by the level of specificity of the assertion, and by connections to other related asser­ tions. Dividing by component facilitates monitoring; the only assertions which must be monitored refer to the cur­ rent component of processing. Assertions are arranged hierarchically to simplify the task of updating the model. Each assertion is linked to the other assertions which are related to it: as an abstraction, a specification, coming in sequence, or because a failure in one suggests a failure in the other. These links are used in explaining failures and finding repairs by focusing on the most fruitful ar­ eas of inquiry. Assertions C and D in table 1 show an abstract assertion and its specification. The vocabulary for representing assertions uses simple rredicate calculus formulations. In [Fox and Leake, 1995 we provide a de­ tailed description of the model and the representation it uses, and describe in more detail the need for a hierarchy of assertions.

After generating a successful solution, most CBR sys­ tems will simply store the solution and stop processing, while ROBBIE evaluates its retrieval process by retriev­ ing the case in memory with the closest solution. If it is not the case that was retrieved originally, a retrieval fail­ ure occurred during the original retrieval. In repairing a retrieval failure ROBBIE must determine what, if any, relevant feature was overlooked. ROBBIE currently con­ siders a pre-defined set of feature types such as "starts at location X", "ends on street Z", or "moves straight along street Y", which are ranked by a fixed feature hi­ erarchy. ROBBIE uses the feature types to compare the new solution with the closest solution in memory, and explains the failure according to the missing features. In the future we plan to expand this mechanism to more general features using explanation-based generalization.

3.3 An Example

In this section we will present an implemented exam­ ple illustrating the model of introspective reasoning we are developing and its benefits. Figure 2 shows the por­ tion of the world map relevant to this example. The goal is to get from location L3 to location L2. ROBBIE has in memory plan A for going from L1 to L2 (Turn south, Move south to south side of Birch, Turn west, Move west to L2) and plan B for going from L2 to L3

(Turn east, Move east to L3) . Using only starting and ending locations to judge similarity, plan A appears to be the closest because it shares the same ending location (ROBBIE's retrieval criteria do not include reversals of known routes). Plan A is selected and adapted to cre­ ate plan C (dashed line in Figure 2): Turn south, Move south to south side of Birch, Turn west, Move west to L2.

During this process, the introspective reasoner mon­ itors the system's behavior but detects nothing wrong. When the plan is executed, however, the wasted plan steps will be eliminated, producing a straight-line plan: Turn west, Move west to L2. When this resulting plan is stored into memory, a reasoning failure is detected: the final solution's steps are most similar to a plan (plan B) other than the retrieved case.

In explaining the cause of this failure, ROBBIE re­ considers related assertions in its model of the desired system behavior: that retrieval will operate successfully; that the index for retrieval will produce the closest case; that the index will include all the relevant features to re­ trieve the closest case. In re-testing the last assertion (in the context of a failure), the system discovers a feature of the case it had not used before: that each involves moving straight east or west. This failed assertion sug­ gests a repair: add "moving east or west" to the features used in the index, and re-index all cases in memory to include the new feature.

4 Empirical Evaluation of Re-indexing

There has been little evaluation of the quantitative ef­ fects on performance from introspective reasoning; argu­ ments for introspective reasoning have tended to focus on the capabilities provided in principle illustrated by par­ ticular examples. Although such work is important, we believe it is also important to define concrete measures which demonstrate the benefit of introspective reasoning, and weigh those against the costs of additional process­ ing. For adding introspective reasoning to case-based reasoning, this requires examining whether isolated ex­ amples map onto a general trend of improvement beyond that accounted for by case acquisition alone.

We ran a series of tests on the ROBBIE system to eval­ uate introspective learning versus case learning alone. 2 We looked at two measures of ROBBIE's performance: the number of successfully completed plans at the end of a test run and the percentage of cases in memory consid­ ered for each retrieval. The number of successful plans provided a comparative measure of the level of success, and we predicted that introspective reasoning and re­ indexing should enable ROBBIE to be more successful on a sequence than case learning alone. The percentage of plans considered during retrieval measured the effi­ ciency of ROBBIE's processing over the course of a test run; we expected that the percentage should drop with re-indexing as new features allowed finer-grained distinc­ tions between cases. In sum, we expected introspective re-indexing to increase the success of ROBBIE at the same time as it decreased the work done in considering cases for retrievaP

2 ROBBIE was presented with a total of 41,600 goals: 26 sequences, each 40 goals long; and 20 runs with introspection 20 without. '

The experiments were designed to test performance from a knowledge-poor starting point, the most difficult situation for both case-based and introspective learning. ROBBIE started with an extremely small initial case base, spanning only three cases. The model used dur­ ing testing contained a restricted set of assertions, to streamline the diagnosis process.

ROBBIE treats a sequence of locations as sequential goals: it starts at the first position, plans from there to the second, from the second to the third, and so on. For the purposes of these tests, when ROBBIE fails to reach a goal and is unable to recover, ROBBIE's location is set to the failed goal and the sequence continues from that point. When this occurs, no case is added to the case base: the size of the case base therefore matches the number of successes ROBBIE has.

We used a set of 40 randomly-created locations as goals for this experiment. These locations did not corre­ spond exactly to locations in any plan in the initial case base. From these locations, we generated a set of 26 test sequences; each sequence was an ordering of the 40 lo­ cations with each locatibn appearing exactly once. One sequence was designed by hand to extend the case base a little bit at a time: it started with goal locations similar to those in the case base, and gradually moved to goals further away from the initial cases. From the handmade sequence we created five groups of five sequences each, where each group varied from the handmade sequence by a different amount (25%, 50%, 75%, and 100% per­ muted; 25% permuted means 25% of the locations in the sequence were randomly swapped with other loca­ tions). In addition, we generated 5 completely random sequences to avoid any residual bias of the original se­ quence.

ROBBIE chooses at random between two candidate cases which appear equally similar. It is often the case, however, that the two cases produce different results which may affect later processing: one might fail or cause a new feature to be learned. To factor out these differing results, we ran each sequence twenty times with intro­ spective re-indexing and twenty times without.

5 Empirical Results

5.1 Success Rate

We will first consider the success rate with and without re-indexing, defined by the number of successfully com­ pleted plans for a run. Figure 3 shows a breakdown of the results. The numbers for each sequence were aver­ aged across the twenty runs; the averages for a partic­ ular sequence with and without re-indexing are side by side with the darker shaded bars indicating introspec­ tive re-indexing and the lighter shaded, no re-indexing. For all but one sequence, ROBBIE with introspective learning did succeed more often than ROBBIE with only case learning, as we expected. This reflects the retrieval of more appropriate cases. The average of successful · cases varied widely across the sequences, as did the dif­ ference between runs with introspective reasoning and those with case learning alone. In some cases, the dif­ ference between the two was very large; in others, very small. In one anomalous sequence, introspective reason­ ing performed slightly worse than case learning alone. That unexpected result is clearly troublesome and we will return to discuss the anomaly after consid~ring the second measure of ROBBIE's performance.

3 It wo~ld also be possible for introspective learning to cause retneval to become too restrictive, decreasing success; verifying that this is not commonly the case is another reason for empirical tests.

5.2 Improved Retrieval Efficiency

We will now consider the second measure of ROBBIE's performance, the extent to which learning new indices improves the efficiency of its retrieval. We measured this by considering what percentage of stored plans ROBBIE considered similar for each retrieval made during a test run. We graphed the course of the run on the x-axis as a time measure by counting each successive retrieval as the next point in time. The percentage of memory considered at each retrieval was graphed on the y-axis.

The effect of re-indexing can be seen in Figure 4, where we graphed a run with re-indexing alongside a represen­ tative sample of runs without it. The heavy line shows the percentage of cases considered in retrieval with intro­ spective learning; each point where introspective learn­ i~g took place is marked with an asterisk. The light hnes are five runs without introspective learning. The runs without re-indexing varied from each other only in minor ways (which is why often only one line is visi­ ble). The introspective run began in the same way but the percentage of cases considered dropped sharply after learning the first new feature. While the percentage con­ sidered rose in some instances to match the runs with­ outre-indexing, it returned to a consistently low level at other points. Early in the sequence, and again around retrieval 30, the trends in percentages considered mim­ icked the rise and fall of the runs without re-indexing, but at a much lower level. It is interesting to note that most of the learning took place at low points instead of 1)eaks. This suggests that at the low points retrieval might have been over-restricted, and new fe~tures are learned to bring other cases into consideration. It also suggests that when no cases in memory are similar to a goal, large percentage retrievals are appropriate.

As is clear from Figure 4, the percentage considered from one goal of a sequence to the next fluctuated be­ tween very high and very low levels. This fluctuation made it difficult to analyze the trend of retrievals. We gained a better perspective by graphing "successive aver­ ages" of the percentage considered: the x-axis represents th: ~ourse of the run as before, but each value on they­ axis iS the average of the percentages from the beginning of the sequence to that point. Figure 5 shows typical re­ sults: twenty runs with introspective re-indexing on the left and twenty without it on the right . The averages with re-indexing declined over time to a much lower level than those without: 30-45% instead of 60-70%. A simi­ lar pattern of decline appeared in every sequence except the anomalous one. In some cases the decrease was much more dramatic, both in how low the percentage became and in how consistently runs displayed that low percent­ age. The best performance correlated with sequences with higher overall success rates, and with those having a greater difference between the success rates with and without re-indexing.

5.3 The Anomalous Sequence

The most compelling explanation for the anomalous se­ quence is that the introspective learning simply did not create new features whiCh would be useful in later situ­ ations. This is supported by the anomalous sequence's retrieval efficiency with and without re-indexing: the av­ e~ag.e percenta?e consi~ered i~ retrieval did not change sigmficantly with or without mtrospective re-indexing. This suggests that, for this case, the new features learned introspectively did not apply to later situations and so could not provide any benefit. Consequently, the fea­ tures learned through introspective reasoning did not group together useful cases, but rather caused an oc­ casional additional failure by restricting retrieval so that a useful case might not be considered at all. This limit­ ing effect of re-indexing would be magnified by the small size of the initial case base, together with the fact that few cases were being learned during the course of the run. Because ROBBIE's re-indexing depends on having a case in memory which shares important features with the c.urrent solution, the fewer the cases in memory, the less hkely a good match will be found and a useful feature learned. Characterizing sequences like this one further and determining their frequency is an important task for the future.

5.4 Summary of Benefits and Costs

From the results discussed above, we can conclude that introspective reasoning does provide a tangible bene­ fit under most circumstances, though further study is needed to characterize its failure for one sequence. In the other trials, the benefits we expected were demon­ strated across a broad set of examples. ROBBIE gener­ ated more successful plans when using re-indexing, while at the same time improving the efficiency of its retrieval. While the percentage of cases considered in retrieval with re-indexing remained at a high level for goals which were dissimilar to cases in memory, the average percentage de­ clined to a significantly lower level than with case learn­ ing alone.

We must address the other side of the coin: the costs of introspective reasoning. Monitoring for failures and ex­ plaini~g ~hem require some amount of processing over­ ?ea~; if it we~e sufficiently high it might make apply­ mg mtrospectlve reasoning infeasible. Re-indexing also takes time to reconsider cases in memory. However, in ~OBBIE we have seen no severe performance degrada­ tion because of the use of introspective reasoning. In­ trospective reasoning can improve the efficiency of the system's reasoning, in this case by reducing the effort of considering similar cases. If ROBBIE's plans were executed in the real world, the execution time lost by se­ lecting the wrong plan and recovering could overwhelm the cost of introspective reasoning which would avoid re­ peating such failures. Combining these advantages with the extension of the set of problems the system can solve introspective reasoning seems highly promising. 4 '

6 Relationship to previous research

There has been a significant amount of work in the ~ast few y~ars on methods for implementing introspec­ tive r~asonmg. Our work was inspired by the proposals for usmg model-based reasoning to improve the perfor­ mance of CBR systems made by [Birnbaum et al. 1991]. In a si?lilar spirit, Freed implements an intros~ective model m RAPTER, a reactive planning system[Freed and Collins, 1994]. RAPTER focuses on analysis of the reasoning trace of the planner, using "justification struc­ tures" which trace the chain of assumptions made by the system used to determine what to repair.

Stroulia uses a "Structure-Behavior-Function" model a form originally designed for diagnosis of device failures:

4 The cost in development time expended to construct the introspective model is another issue, see [Fox and Leake 1995) for a detailed discussion of model transfer. '

to perform introspective reasoning about an underlying system[Stroulia and Goel, 1994]. Her introspective rea­ soner, Autognostic, has been applied to two underlying systems, showing that transfer of introspective models is feasible. The SBF model provides strategies for as­ signing blame for the failure, and provides information about the device being modeled beyond that included in ROBBIE's model. ROBBIE's model is designed to sup­ port failure detection as well as recovery, and facilitates that process through the types of assertions included and their organization.

Oehlmann integrates introspective reasoning with the overall domain task in IULIAN: discovering answers to questions through experience or experimentation [Oehlmann et al., 1994]. IULIAN contains plans for solv­ ing domain tasks, and introspective plans for controlling its reasoning process. It learns by applying these plans to its domain and reasoning tasks, and remembering the resulting successes or failures.

Cox implements introspective reasoning in Meta­ AQUA by maintaining a set of reasoning trace tem­ plates (Meta-XPs) that describe different reasoning fail­ ures, and detecting reasoning failures that match a template[Ram and Cox, 1994]. Meta-XPs provide the means for determining the failure and suggestions for repairs.

In CBR research outside of introspective reasoning, multiple methods have been proposed for determining relevant indices. For example, explanations are often used to determine the relevance of features :when assign­ ing indices to new cases (e.g., [Barletta and Mark, 1988; Leake and Owens, 1986; Ram, 1993]). However, less at­ tention has been devoted to the central questions ad­ dressed by ROBBIE: when and how an existing case in memory should be re-indexed. Some approaches alter in­ dices in response to external feedback [Redmond, 1992; Veloso and Carbonell, 1993]; ROBBIE instead uses after­ the-fact introspective analysis of its reasoning perfor­ mance to determine whether new indices should be learned. In addition, when ROBBIE chooses new in­ dices, it uses knowledge of both the faulty retrieval and the case that should have been retrieved to guide the choice of new indices. This allows it to select indices that are useful to discriminate between the cases cur­ rently in its memory [Fox and Leake, 1994].

7 Conclusions

The ROBBIE system combines introspective reasoning with a case-based planner to create a system that not only learns new plans in response to its experiences, but also learns to plan better by learning new features to use in indexing. ROBBIE uses a declarative model of the case-based reasoning process which provides expec­ tations about its reasoning performance through asser­ tions about the ideal reasoning and results. This model contains both general and specific assertions; the frame­ work is designed to be applicable to other underlying systems and failures [Fox and Leake, 1995] .

In previous research, little has been done to quan­ titatively evaluate introspective reasoning beyond iso­ lated examples. We have performed empirical analysis of ROBBIE to determine its performance by measuring the success rate and the reasoning efficiency. We discovered that across a range of inputs, ROBBIE with introspec­ tive re-indexing improved the efficiency of its retrieval process by learning features to constrain the cases con­ sidered and to focus on the best cases. With one ex­ ception, ROBBIE was also more successful in creating plans when using introspective re-indexing than when doing case learning alone.

Many questions still remain to be answered. Perhaps most important is a detailed analysis of the reasons for ROBBIE's successes, and its failure. We must charac­ terize the sequence which caused ROBBIE to perform worse with introspective re-indexing, and determine how common such a failure might be. We believe that the failure is due to the sparse introspective learning oppor­ tunities with a small case base that remained small due to many failures over time, combined with the possible over-constraining of the retrieval process due to learning irrelevant features.

As future research, we plan to expand the model of ROBBIE to include diagnosis and repair of other por­ tions of the CBR system, such as the weighting of fea­ tures in retrieval, the choice of strategies for adaptation, and the choice of plan execution steps. We plan even­ tually to transfer the introspective framework we have developed to other underlying systems, and to consider more qualitative measures of ROBBIE's introspective reasoner such as the quality of reasoning, the quality of plan produced, and its value as a cognitive model.

While much work remains to be done in creating the best method for introspective reasoning and evaluating its performance, the work described here clearly demon­ strates that learning based on introspective reasoning is a feasible addition to a case-based planning system such as ROBBIE and provides a tangible benefit over fixed reasoning. We are encouraged by ROBBIE's success to expect introspective learning to provide more advantages for CBR and elsewhere in the future.