An Architecture for Multiple Heterogeneous Case-Based Reasoning Employing Agent Technologies. Elena I Teodorescu and Miltos Petridis1 Abstract. This paper presents an investigation into applying petence and the contextualisation of the cases. Past research at Case-Based Reasoning to Multiple Heterogeneous Case Greenwich [2][3] has shown the need to combine knowledge en- Bases using agents. The adaptive CBR process and the ar- coded in cases from various heterogeneous sources to achieve a chitecture of the system are presented. A case study is pre- competent, seamless CBR system. Ontanon and Plaza [7] looked at a way to “improve the overall sented to illustrate and evaluate the approach. The process of performance of the multiple case systems and of the individual creating and maintaining the dynamic data structures is CBR agents without compromising the agent’s autonomy”. They discussed. The similarity metrics employed by the system present [8] a framework for collaboration among agents that use are used to support the process of optimisation of the col- CBR and strategies for case bartering (case trading by CBR laboration between the agents which is based on the use of a agents). Nevertheless, they do not focus at the possibility of cases blackboard architecture. The blackboard architecture is having different structures and what impact this will have on ap- shown to support the efficient collaboration between the plying CBR to heterogeneous case bases. Leake [5] states that “An agents to achieve an efficient overall CBR solution, while important issue beyond the scope of this paper is how to establish using case-based reasoning methods to allow the overall correspondences between case representations, if the representa- tions used by different case-bases differ.” system to adapt and “learn” new collaborative strategies for Given several case bases as the search domain, it is very likely achieving the aims of the overall CBR problem solving that they have different structures. Ideally, accessing Multiple Case process. Bases should not require a change to their data structures. In order for an MCBR system to effectively use case-bases that may have been developed in different ways, for different tasks or task envi- ronments, methods are needed to adjust retrieved cases for local 1 Introduction1 needs. Leake and Sooriamurthi [4] proposed a theoretical “cross-case- Case-based reasoning (CBR) is now an established artificial intel- base adaptation” which would adapt suggested solutions from one ligence paradigm. Given a case-base of prior experiences, a CBR case base to apply to the needs of another. They are currently system solves new problems by retrieving cases from the case- exploring sampling methods for comparing case-base characteris- base, and adapting their solutions to comply the new require- tics in order to select appropriate cross-case-base adaptation strate- ments[1]. gies. Multiple Case Based Reasoning (MCBR) is used to retrieve so- lutions for a new problem from more than one case-base. Methods for managing sharing of standardized case bases have been studied in research on distributed CBR (e.g. [13]), as have methods for 2 Adaptive CBR facilitating large-scale case distribution [10]. Leake and Sooria- muthhi propose a new strategy for MCBR - an agent selectively In order to enable effective solution retrieval across autonomous supplements its own case-base as needed, by dispatching problems case bases with differing structures, it is essential to have access to external case-bases and using cross-case-base adaptation to and a good understanding of each of the different case base struc- adjust their solutions for inter-case-base differences [4, 5, 6,13 ]. tures involved. This would make it possible to identify the com- In many problems in modern organisations, the knowledge en- monalities, equivalences and specific characteristics of every case capsulated by cases is contained in multiple case bases reflecting base associated with the system. the fragmented way with which organisations capture and organise knowledge. The traditional approach is to merge all case bases into a central case base that can be used for the CBR process. However, this approach brings with it three challenges: 2.1 The process of adaptive CBR • Moving cases into a central case base potentially sepa- rates from its context and makes maintenance more diffi- Instead of trying to adapt the suggested solutions from one case cult. base to the needs of another, the approach investigated in this study will be to create a “dynamic structure” of a general case. This • Various case bases can use different semantics. There is dynamic structure would be modified every time a new case base therefore a need to maintain various ontologies and map- with a new structure is added. pings across the case bases. The process of adaptive CBR, within the architecture of the • The knowledge content “value” of individual cases can HMCBR System (Figure 1), will incorporate a number of steps. be related to its origination. This can be lost when merg- Firstly, in order for the system to work with a particular case ing into a central case base. base, it will need to know the structure of that case base. Every Keeping the cases distributed in the form of a Heterogeneous newly added case base will therefore have to publish its structure to Multiple Case Based Reasoning system (HMCBR) may have a a Registry System. The published structures are required to have number of advantages such as increased maintainability and com- their own data dictionaries attached to enable the creation of a dynamic Data Dictionary. 1 Department of Computing Science, University of Greenwich, Park Row, London SE10 9LS email:{ E.I.Teodorescu , M.Petridis}@gre.ac.uk 65 3 Creating the Dynamic Structure Creating and maintaining a dynamic structure makes the self- adaptive multi case base reasoning system possible. By adding a new case base to the existing ones, new attributes are added to a global dynamic structure and new relations linked to these attrib- utes are established. CBS1. Apartment Studio Detached type house DCBS name House 0 0 1 Flat 1 0.8 0 Fig. 3. Data Dictionary includes relations between some of the attributes. A data dictionary is required to keep all the metadata for the dy- namic structure. This data dictionary would have multiple func- tions: It records the location and the name of every attribute from the Case Base Structures (CBS) and how these are translated into the Dynamic Case Base Structure (DCBS). It also stores the type Fig. 1. The Architecture of the HMCBR System and any default value for every single attribute. The Data Dictionary will reflect any relationships between the The published structure will be retrieved by the Dynamic CB Dynamic Case Base Structure attributes. These relationships can be System and used to adapt the local dynamic structure to accommo- mathematical relationships or look-up tables (figure 3). date any new elements and map existing ones. We will use the presented case study to show how a dynamic When the dynamic structure reflects all participating case bases, structure is created and how it is continuously changed by adding a case query can be submitted. The system would then reformulate new case bases to the search domain. the target case structure into each provider’s case base structure. Let us suppose that our general structure (the initial state of the The target case structure will be a subset of the dynamic structure. Dynamic Structure containing few main attributes of a property) is The reformulated cases are submitted to each provider and solu- already built (see figure 4). The structure has attached a basic Data tion cases are retrieved using KNN techniques [1]. The structures Dictionary mainly containing the data types of the existing attrib- of these solutions will be translated into the dynamic structure, thus utes. creating a dynamic case base. Finally, the system will apply the We will show how this initial structure will be dynamically classical CBR process to the dynamic case base. changed by consecutively adding the three agents to the search The whole process is intended to provide a transparent view of domain. the CBR process across the heterogeneous system. Adding the Case Base Structure 1 to the system implies map- ping of the attributes ParkingSpace, Area and Type into the Dy- namic Structure (these attributes are already existing in the initial 2.2 Case Study structure) and also adding more attributes to it (i.e. NoOfRooms, NoOfBathrooms, GardenLength, GardenWidth) This case study requires searching for a property from three estate agencies without amalgamating their case bases structures. Let us suppose that the estate agencies have different case base structures (figure 2). A possible buyer should be able to search for a property and get all the suitable solutions from all three agencies. A search should retrieve the best matches from all case bases as if it was dealing with a single case base in a way transparent to the buyer. Data Dictionary Size: Double NoOfBedrooms: Integer Location: String ParkingSpace: double Name: house flat house 1 0 flat 0 1 Case Bases Structures 1(CBS1) Fig. 4. Initial state of the Dynamic Structure and Data Dictionary The Data Dictionary will reflect the mapping of attributes: CBS1.ParkingSpace = DCBS.ParkingSpace; Case Bases Structures 2(CBS2) CBS1.Area = DCBS.Location CBS1.type= DCBS.name The following attributes will be added to the dynamic data dic- tionary: NoOfRooms: integer; GardenLength: double; GardenWidth: double Case Bases Structures 3(CBS3) Any other relevant relationships such as look-up tables for de- fining mappings between the values of attribute Type of CBS1 and Fig. 2. Three different Case Base Structures 66 the values of the attribute Name of the dynamic structure will be 4 Optimising the agent collaboration process captured. Case Base Structure 2 will add another attribute, GardenSize, to the Dynamic Structure and the data dictionary will record mapping In order to optimise the process of collaboration between the of attributes: agents to achieve an efficient solution from the overall CBR proc- CBS2.Name = DCBS.Name, ess when applied across the heterogeneous case bases, an overall CBS2.Location = DCBS.Location , similarity metric is required. Additionally, an overall process to CBS2.NoOfBedrooms = DCBS. NoOfBedrooms; enable collaboration between the agents is necessary based on a The mathematical relationships are recorded: flexible architecture to enable this collaboration. DCBS.GardenSize = DCBS.GardenLength * DCBS.GardenWidth, Functions can be applied, for example to keep the same metric system: 4.1 Defining an overall similarity metric DCBS.GardenSize= CBS2.GardenSizeInFeet/(3.281)2 The Data Dictionary would also include a look-up table show- The overall similarity metric between a target and a source Case ing the conversion of values of CBS2.Name to values of can be defined as: DCBS.Name. Attention has to be paid to the meanings of the names of the at- , , 1 tributes. For example, if the attribute “Type” in CBS1 and the where: attribute “Name” in CBS2 have the same meaning (they would be σ: overall similarity translated as “Name” in DCBS, with values found in a look-up σCBy: similarity from case base provider CBy table), the attribute “Name” from CBS3 has not the same meaning CT: target case as the one from CBS2. It is actually translated into DCBS.Location CS: source case (similar to CBS2.Location) : weighting for a case base provider y for case CT To allow for defining locally optimised similarity metrics for different providers, the following metric can be defined: , , , 2 where: : the weighting from case base provider CBy for at- tribute x , , : the local similarity metric for provider CBy for attribute x. This extended similarity metric takes into account the level of trust that the HMCBR system attributes to the competence of each case base provider. The level of trust is determined by applying CBR to the case-base of the history of queries. Additionally it allows to adjust the trust to particular providers to different “re- gions” in the case base allowing for case base providers to be Fig. 5. Adapted Dynamic Structure after CBS3 was added “specialised” on particular types of domain knowledge. Finally, the extended metric allows for different ways of defining similarity By adding the third estate agent case base to the search domain, based on possible particularities pertaining to individual case base the dynamic structure will grow even more (see figure 5) and the providers. Data dictionary will reflect it by adding the attributes Let us assume that in our case study the third estate agent is DSBS.Garage and DSBS.View. specialised in city apartments. After a few searches for country side The following attributes are mapped: houses with gardens, reasoning can be applied to the History case- CBS3.Name = DCBS.Location base. Results will show that, for this particular query, the estate CBS3.Description = DCBS.Name agent’s level of trust is not high, i.e. there will be less solutions for CBS3.GardenSizeInMeters = DCBS.GardenSize this particular case base added to the Dynamic case-base. Another look-up table can be created and added to the Data Dic- A global level of trust of a provider’s case-base can be calculat- tionary to record the relationship between the Garage and Parking- ing taking in consideration the results of all the previous enquiries Space. Figure 6 shows the state of the Dynamic data Dictionary for that provider. after CBS1, CBS2 and CBS3 are added. Dynamic Data Dictionary CBS1.Area = DCBS.Location 4.2 An architecture and process to support effective NoOfRooms: integer collaboration between case base agents CBS1.type= DCBS.name DCBS.GardenSize: double The architecture of the HMCBR system shown in figure 1 contains DCBS.GardenSize = CBS2.GardenSizeInFeet the dynamic CB system, which incorporates a blackboard architec- DCBS.GardenSize = DCBS.GardenLenght * ture. Blackboards have been used very effectively in the past for DCBS.GardenWidth ... the construction of hybrid and agent based AI systems [11], [12]. CBS3.Name = DCBS.Location The dynamic CB system is where the process for agent collabo- CBS3.GardenSizeInMetres = DCBS.GardenSize ration is controlled. It is based on a blackboard architecture incor- Garage ParkingSpace porating the blackboard containing the target and retrieved cases Garage 1 0.7 from various providers together with similarity calculations and ParkingSpace 0.7 1 rankings. The blackboard also contains a log of the solution proc- ess and the reconciliation strategy followed, thus representing the Fig. 6. Adapted Dynamic Data Dictionary after CBS1, CBS2 state of the overall CBR solution process at any point in this proc- and CBS3 are added ess. Figure 7 shows the structure of the dynamic CB module incor- porating the blackboard architecture. 67 use the translated query to match it to its local cases and retrieve AgentCB1 AgentCB2 AgentCB3 the best matches. A Data Dictionary is created in order to manage the Dynamic Structure. This contains the metadata for the Dynamic Structure, such as mapping details of the case base provider’s structures to the Dynamic Structure, type information and relationships between Query attributes of the dynamic structure. BB Blackboard History The dynamic case base system manages the overall process, in- Manager cluding controlling the agents, reconciling and optimising the retrieved cases and feeding back into its strategy by continuously adjusting weights representing confidence levels on individual case base providers. A prototype system to evaluate the efficiency of using a heterogeneous Multiple Case Based Reasoning system is currently being evaluated. Preliminary findings are encouraging. Dynamic Dynamic Data Further work will concentrate into optimising the process of Structure Dictionary collaboration between the agents and methods and strategies for the reconciliation of retrieved cases. Fig. 7. The Dynamic CB system incorporating the blackboard architecture References The blackboard manager manages the overall solution process, communicates with and keeps track of the CB agents, selects and [1] Kolodner, J.: Case-based Reasoning, Morgan Kaufmann, 1993 implements a solution strategy and monitors and evaluates the [2] Knight B, Petridis M, Mileman T: Maintenance of a Case-Base solutions achieved. Given a new target case, the blackboard man- for the Retrieval of Rotationally Symmetric Shapes for the De- ager decides on strategy for finding similar cases from the CB sign of Metal Castings LNAI 1998: Springer Verlag. Advances providers. The blackboard system decides which CB providers to in Case-Based Reasoning, 5th European Workshop, Trento, It- use and the number of cases to retrieve from each one and other aly, Sept. 6-9.2000 pp 418-430 requirements, such as the requirement for diversity, similarity [3] Knight B, Petridis M, Mejasson P, Norman P: A Intelligent thresholds etc. The system then initialises the agents and assigns to design assistant (IDA): a CBR System for Materials Design them a mission. On return, the results (cases) are mapped using the Journal of Materials and Design 22 pp 163-170, 2001 dynamic data dictionary and written to the blackboard. A “global” [4] David Leake & Raja Sooriamurthi: “Automatically Selecting CBR process is used to decide on the retrieved cases. The system Strategies for Multi-Case-Base Reasoning” - Proceedings of the then selects and presents the shortlisted cases after the reconcilia- Sixth European Conference on Case-Based (ECCBR) , Aber- tion process and provides these to the user, together with links to deen, Scotland, September, 2002 their original forms for the user to explore. Finally, the system [5] David Leake & Raja Sooriamurthi : “Managing Multiple Case “reflects” on the process by updating the query history and confi- Bases: Dimensions and Issues” (Proceedings of the Fifteenth dence weights for each provider. Florida Artificial Intelligence Research Society (FLAIRS) Con- The system described here has been implemented and tested on ference , Pensacola, Florida, May 2002), a set of case bases from three different estate agent case bases, all [6] David Leake & Raja Sooriamurthi: “When Two Case Bases using different structures. Experiments with the system have shown are Better Than One: Exploiting Multiple Case Bases” (Pro- that the system can retrieve useful cases combining cases from all ceedings of the Fourth International Conference on Case-Based case bases to provide a more efficient overall solution when com- Reasoning (ICCBR) , Vancouver, Canada, July, 2001). pared to using the case bases separately or mapping them to one [7] Enric Plaza, Santiago Ontañón: Cooperative Multiagent Learn- central case base. Additionally, the system has shown that it can ing. Adaptive Agents and Multi-Agents Systems 2002 provide a more diverse retrieved case population in both cases. A [8] Santiago Ontañón, Enric Plaza: A bartering approach to im- full scale evaluation of the system, including using a different prove multiagent learning. AAMAS 2002 application domain is under way. [9] Francisco J. Martín, Enric Plaza, Josep Lluís Arcos: Knowledge and Experience Reuse Through Communication Among Com- petent (Peer) Agents. International Journal of Software Engi- 5 Conclusion neering and Knowledge Engineering 1999 [10] Hayes, C., Doyle, M., Cunningham, P.: Distributed CBR Using XML, Proceedings of the Fourth European Conference At a time of increasing web-based communication and sharing of on Case-Based (ECCBR) , Dublin, Ireland, June 1998 knowledge between organisations and organisational units within [11]R Engelmore, T Morgan : Blackboard Systems, Addison- enterprises, heterogeneous CBR applied to Multiple Case Bases Wesley, 1988 seems to be the natural progression in this area of research. [12] Petridis M, Knight B, (2001): “A blackboard architecture for a The paper investigates an approach based on agents operating hybrid CBR system for scientific software” in Proceedings of on different structures/views of the problem domain in a transpar- the Workshop Program at the 4th International Conference in ent and autonomous way. In this approach all data is kept locally Case-based Reasoning ICCBR01, Vancouver 2001, Eds R. We- by each case base provider in its native form. Agents can be dy- ber, G. von Wagenheim, pp 190-195, NCARAI, Naval Research namically added to the system, thus increasing the search domain Laboratory, Code 5510 Washington DC. and potentially the competence and vocabulary of the system. [13] Case Dispatching versus Case-Base Merging: when MCBR This research proposes a new architecture for a self-adaptive matters: David Leake and Raja Sooriamurthi. MCBR system which involves the use of a dynamic structure based International Journal on Artificial Intelligence Tools: Architec- on the blackboard architecture. The Dynamic Structure reflects all tures, Languages and Algorithms (IJAIT). Special issue on re- participating case base provider structures. As new agents are cent advances in techniques for intelligent systems. Vol 13, No added to the system, their case base structure is published and is 1, 2004 used to adapt the Dynamic Structure accordingly. The Dynamic Structure is used at runtime to translate search queries into the local structures of each agent. Each agent can then 68