=Paper=
{{Paper
|id=Vol-375/paper-13
|storemode=property
|title=An Architecture for Multiple Heterogeneous Case-Based Reasoning Employing Agent Technologies (short paper)
|pdfUrl=https://ceur-ws.org/Vol-375/paper12.pdf
|volume=Vol-375
}}
==An Architecture for Multiple Heterogeneous Case-Based Reasoning Employing Agent Technologies (short paper)==
https://ceur-ws.org/Vol-375/paper12.pdf
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