In has been argued that ontologies play a key role in multiagent communication because they provide and define a shared vocabulary to be used in the course of communication. In real-life scenarios, however, the situation where two agents completely share a vocabulary is rather an exception. More often, each agent uses its own vocabulary specified in a private ontology that is not known by other agents. In this paper we propose a solution to this problem for the situation, where agents share at least parts of their vocabulary. We argue that the assumption of a partially shared vocabulary is valid and sketch an approach for re-formulating terms from the private part of an agent's ontology into a shared part thus enabling other agents to understand them. We further describe how the approach can be implemented using existing technology and proof the correctness of the re-formulation with respect to the semantics of the ontology-language DAML+OIL.
An important aspect of multi-agent systems is the
communication among different agents, because communication
is the basis for cooperation. Ontologies are a technology to
support inter-agent communication by providing a definition
of the world, an agent can ground his beliefs and actions
as well as by providing terms that can be used in
communication [
In this paper, we adopt the view of [
In this paper, we propose an approach to facilitate agent communication in the situation, where agents share some but not all of their terminology. In the next section, we describe our approach in an informal way. In section 3 we describe the formal framework our framework is build upon in terms of the ontology language DAML+OIL, its semantics and the formal foundation for inter-ontology mappings. The approach for approximating concepts in a language with a limited vocabulary in described in section 4 and a correctness proof is given. In section 5 we describe how the approximation approach can be used to re-formulate agent messages in such a way that another agent can understand it. We summarize with a discussion and some hints towards future research.
In order to get a clearer notion of the problem to be solved we make some simplifying assumptions. First of all we will only consider two agents that want to communicate. Then we assume that there are only two ontologies involved, a shared one and a private one of the agent trying to communicate. We further assume that both ontologies are encoded on the same language, preventing us from the problem of integrating the ontology languages. Figure 1 illustrated the situation.
extended to more realistic scenarios as communication is
mostly bi-lateral even in complex multi-agent systems.
There might be more than two ontologies involved in the
communication, but they will all either be shared or
private to one on the agents. The only assumption that really
is a simplification is the existence of a single ontology
language. Investigating this problem, however, is out of the
scope of this paper. For an approach to overcome language
heterogeneity, we refer to [
In order to perform a task, an agent will use one of more ontologies as an explicit representation of the domain of interest. These ontologies will normally supplement each other to form a sufficiently complete model. Though being supplementary, we can assume that they have sufficient overlap to allow a single agent to find mappings between them. In the following we give a toy example illustrating this idea.
problem (see figure 2). This ontology is shared by the two agents in figure 1. Therefore, the agents can use terms from this ontology (e.g. Animal, Domestic-Animal or Cow ) to communicate with each other. A communication problem arises, because the agent on the left hand side of figure 1 also uses a second ontology that contains different classifications of animal like Pet or Farm-Animal. While the terms from this ontology are closely related to the ones in the shared ontology, the agent on the right-hand side will not be able to understand them.
tology establishes internal mappings between these ontologies. In our example, these mappings would specify Pet as being a subclass of Domestic-Animal which is disjoint from Production-Animal, Farm-Animal to be a subclass of Domestic-Animal and of Production-Animal as well as Zoo
2.2
find information about the concepts specified in its private ontology (figure 3) In order to be able to communicate this information need to other agents that might have valuable information it has to use terminology from the shared ontology (figure 2).
As an example we take the following query
(Animal ∧ ¬(Farm − Animal ). This query cannot be
directly answered, because the term Farm-Animal is not
understood. The idea of our approach is to re-write this
query in such a way that it covers the same set of answers
using terms from the other ontology. In general, an exact
re-writing is not possible because the concepts of the private
ontology do not have exactly matching concepts in the
shared one. In this case, we have to look for re-writings that
approximate the query as closely as possible. Re-writings
that are an upper approximation of the original query
are know from the database area as minimal subsuming
mappings [
The idea of the re-writing is the following. Based on the mappings between of the classes in both ontologies, we can find those concepts in the ontology of figure 2 that are most closely related to a query concept. Taking a concepts from our query, we can for example decide that Domestic-Animal and Production-Animal are upper approximations for Farm-Animal while Cow and Pig are lower approximations. Using these concepts, we can define lower boundaries for farm-animals (Cow ∨ P ig) and use this expression instead of the original concept still getting correct results. In our example, however, the concept occurred in a negated form. In order to return a correct result, we therefore cannot use the lower bound because not all irrelevant resources might be excluded. Based on the considerations made above we can replace the concept farm-animal within the scope of the negation by its upper bound (Domestic − Animal ∧ P roduction − Animal).
that can be shown to return only correct results: (Animal ∧ ¬(Domestic − Animal ∧ P roduction − Animal).
results, we need a formal basis for representing and
reasoning about the ontologies involved. Recently, the benefits
of semantically well-founded ontology languages have been
discussed by many authors in connection with the so-called
Semantic Web (see e.g. [
guage that has been developed in the DAML programme in order to support intelligent agents to communicate and reason about annotated information on the World Wide Web.
3.1.1
The only possibility to define class structures in RDF schema was the rdfs:subClassOf property. DAML+OIL adopts this relation also allowing for multiple inheritance and provides a property for stating that two classes are disjoint. <daml:Class rdf:ID="Domestic-Animal">
<rdfs:subClassOf rdf:resource="#Animal"/> </daml:Class> <daml:Class rdf:ID="Foreign-Animal"> <rdfs:subClassOf rdf:resource="#Animal"/> <daml:disjointWith rdf:resource="#Domestic-Animal"/> </daml:Class> <daml:Class rdf:ID="Cow"> <rdfs:subClassOf rdf:resource="#Domestic-Animal"/> <rdfs:subClassOf rdf:resource="#Production-Animal"/> </daml:Class>
The expressiveness of the subclass relation in DAML+OIL is further enriched be the possibility of defining a class to be equivalent to a logical expression over class names. <daml:Class rdf:about="#Animal"> <daml:disjointUnionOf rdf:parseType="daml:collection"> <daml:Class rdf:about="#Domestic-Animal"/> <daml:Class rdf:about="#Foreign-Animal"/> </daml:disjointUnionOf> </daml:Class>
Beside the daml:disjointUnionOf property, classes can also be defined to be equivalent to another class, to equivalent to a Boolean expression over classes using daml:intersectionOf, daml:unionOf and daml:complementOf or by enumerating its elements with the daml:oneOf property. 3.1.2
DAML+OIL defines two kinds of relations. daml:ObjectProperty relates members of different classes to each other. daml:DatatypeProperty relates a member of a class to a legal value of a certain data type. The first type of relation is very similar to an RDF property. It has a unique name and can have RDF schema range and domain restrictions like the following example: <daml:ObjectProperty rdf:ID="has-origin"> <rdfs:domain rdf:resource="#Animal"/> <rdfs:range rdf:resource="#Country"/> </daml:ObjectProperty>
DAML+OIL is the possibility of defining one relation to be the equivalent or the inverse of another relation. Using this feature, we can define the has-child relation using the one specified above: <daml:ObjectProperty rdf:ID="is-origin-of">
<daml:inverseOf rdf:resource="#has-origin"/> </daml:ObjectProperty>
3.1.3
Classes define common properties of its members. Different from RDF schema, DAML+OIL provides means for defining these characteristic properties of class members in terms of restrictions on the objects they are related to. In principle there are two kinds of restrictions, type restrictions and number restrictions:
The restriction daml:toClass from the example claims that every object related to a member of the class has be be of a certain type. Beside this restriction, daml:hasClass claims that every member of the class is related to one object of a certain type, daml:hasValue even claims that every object of the class is related to one specific object. Number restrictions daml:minCardinality, daml:maxCardinality and daml:cardinality define lower and upper boundaries and exact values for the number of objects the member of a class is related to via a certain relation. Several restrictions may apply to a relation. 3.2
abstract domain. More specifically, every concept name is mapped on a set of objects, every property name is mapped on a set of pairs of objects. Individuals (in or case resources) are mapped on individual objects in the abstract domain.
Definition 1 (Interpretation). An Interpretation consists of a pair (Δ, .E ) where Δ is a (possibly infinite) set and .E is a mapping such that: • xE ∈ Δ for all individual names x. • CE ⊆ Δ for all concept names C • RE ⊆ Δ × Δ for all role names R We call .E the extension of a concept, a role, or an individual, respectively.
This notion of an interpretation is a very general one and does not restrict the set of objects in the extension of a concept. This is done by the use of operators for defining classes. In our example, we used the subClassOf and the hasValue operator for restricting the set of objects that are members of the class zoo animals. These kinds of operators restrict the possible extensions of a concept. Figure 4 summarizes the specific interpretations of a part of the operators of DAML+OIL.
Operator intersectionOf
unionOf complementOf oneOf toClass hasClass hasValue minCardinalityQ maxCardinalityQ cardinalityQ
Extension .E C1E ∩ · · · ∩ CnE C1E ∪ · · · ∪ CnE
Δ − CE {x1, · · · , xn} ⊂ Δ {y ∈ Δ|(y, x) ∈ P E =⇒ x ∈ CE } {y ∈ Δ|∃x((y, x) ∈ P E ) ∧ x ∈ CE }
{y ∈ Δ|(y, x) ∈ P E } {y ∈ Δ| |{x|(y, x) ∈ P E ∧ x ∈ CE }| ≤ n} {y ∈ Δ| |{x|(y, x) ∈ P E ∧ x ∈ CE }| ≥ n} {y ∈ Δ| |{x|(y, x) ∈ P E ∧ x ∈ CE }| = n}
subsumption: C1 v C2 ⇐⇒ C1E ⊆ C2E membership: x : C ⇐⇒ xE ∈ CE
3.3
scription logics, which provide the semantic basis for
DAML+OIL, has only been investigated in terms of a
single homogeneous model. Recently Borgida and Serafini
proposed an extension of the formal framework of
description logics to distributed knowledge models [
the concept C in ontology Ti are mapped to a subset of the instances of the concept D in ontology Tj (i : CE ⊆ j : DE ) in the case of the second rule the superset relation is asserted to hold between the instances of the two concepts.
Zoo − Animal
P et F arm − Animal v −→ v −→ v −→ ¬Domestic − Animal Domestic − Animal ∧ ¬P roduction − Animal (2) Domestic − Animal ∧ P roduction − Animal (1)
transform a distributed knowledge base into a global one and apply existing description logic reasoner in order to derive new knowledge. In the following, we build on this result whenever we mention terminological reasoning.
with respect to the subsumption relation. In a distributed
for separate ontologies that are connected by bridge rules.
of direct subclasses of a class c1 from the private ontology.
to the shared ontology as upper and lower approximation for c1 in the shared ontology:
Definition 2 (Lower Approximation). Let C1 be a set of private concepts, C2 a set of shared concepts of an agent and c ∈ C1 a class, then a class cglb ∈ C2 is called a lower approximation of c in IS2, if the following assertions hold: 1. cglb v c 2. (∃c0 ∈ C2 : c0 v c) =⇒ (c0 v cglb) The greatest lower bound glbIS2 (c) denotes the set of all lower approximations of c in C2.
Definition 3 (Upper Approximation). Let C1 be a private classes , C2 a set of shared classes of an agent and c ∈ C1 a private class, then a class club ∈ C2 is called an upper approximation of c in IS2, if the following assertions hold: 1. c v club 2. (∃c0 ∈ C2 : c v c0) =⇒ (club v c0) The least upper bound of lubIS2 (c) is the set of all least upper bounds of c in C2.
The rational of using these approximations is that we can decide whether an entity x is a member of a class in the private ontology based on its membership in classes of the shared ontology. This decision in turn provides us with an approximate result on deciding whether x is the result of a query stated in terms of a private ontology, based on the following observation: • If x is member of a lower bound of c1 then it is also in c1 • If x is not member of all upper bounds of c1 then it is not in c1
about upper and lower boundaries for theory approximation.
Definition 4 (Concept Approximation). Let C1 be a set of private concepts, C2 a set of shared concepts of an agent and x the member of a shared concepts then for every c1 ∈ C1 we define M 0 such that: • M 0(x, c1) = 1 if x : • M 0(x, c1) = 0 if x : ¬ • M 0(x, c1) = ?, otherwise
V c∈lubIS2 (c1) ! c Where the semantics of disjuction and conjunction is defined in the obvious way using set union and intersection .
Proposition 1 (Correctness of Approximation). The approximation from definition 4 is correct in the sense that: 1. If M 0(x, c1) = 1 then xE ∈ c1E 2. If M 0(x, c1) = 0 then xE 6∈ c1E
Proof. (1) If the classification returns M 0(x, c1) = 1 then x : ( W c). Using definition 2 we get that for c∈glbIS2 (c1) all c we have c v c1 and therefore also (
W c) v c1 c∈glbIS2 (c1) (by set theory). Using the definition of subsumption we can conclude that xE ∈ c1E . xE ∈ c1E only if xE ∈ ( V
c∈lubIS2 (c1) cation returns M 0(x, c1) = 0 then x : ¬(
(2) Using definition 3 we deduce that for all c we have c1 v c and therefore c1 v V c. This means that c∈lubIS2 (c1)
V c) which c∈lubIS2 (c1)
V c∈lubIS2 (c1) is equivalent to xE 6∈ ( have xE 6∈ c1E . 5.
basis for re-writing concepts using in messages an agent uses to communicate with other agents. Having proven the correctness of the approximation we can use them to re-write a concepts by replacing their names by their approximation.
Definition 5 (Concept Re-Writing). The rewriting of a query c over concepts from a private ontology to an expression over concepts from a shared ontology is defined as as follows: • replace every non negated concept name c by:
V c0 c0∈lubIS2 (c) • replace every negated concept name c by:
W c0∈glbIS2 (c)
any available Description logic reasoner. We used the
B[t] := racer.directSupers(t) B0[t] := B[t] ∩ S
Q(t) := (c1 ∧ · · · ∧ cn) for ci ∈ B0[t] else
B[t] := racer.directSubs(t) B0[t] := B[t] ∩ S
C(t) := (c1 ∨ · · · ∨ cn) for ci ∈ B0[t] end if
C’ := proc Replace t in C0 by C(t) end for return C’
As the re-writing builds upon the approximations discussed in the last section we can guarantee that the result of the query is correct. Moreover, we can use subsumption reasoning in order to determine this result. To be more specifically, a resource x is indeed a member of the query concept if membership can be proved for the re-written query.
works using an example translation. We assume that the message contains the request for information:
’Give me information about Farm-Animals and Animals that are not Pets.’
a list of shared concepts. In this case these concepts are all concepts from figure 2. Further, the algorithm will need the DAML+OIL definitions of the classes involved as well as specifications of the mappings. These together form the terminological knowledge base mentioned in the algorithm.
Farm-Animal, Animal and Pet. As Animal is contained in the shared ontology it does not have to be translated. We therefore only discuss the translation of Farm-Animal and Pet.
In the second step, the algorithm tests whether the concepts are negated or not. As Farm-Animal is not negated, the algorithm collects all direct subclasses of Farms-Animal from the knowledge base. These are Cow and Pig (compare equation 3 and figure 2). These are connected by disjunction to form the lower bound (Cow ∨ P ig). Next, the negated term Pet is handled. The algorithm computes the direct superclasses Domestic-Animal (compare equation 2 and figure
Animals that are not Domestic Animals.’
6.
cial capabilities of a remote system is first reported in [
ontologies in multi-agent communication by translating private concepts into shared ones while ensuring some formal properties. Our approach enables agents on the
relying on internally provided mappings between ontologies.
So far, we consider our results as a basic mechanism for
facilitating agent communication. However, a lot of work is
still necessary in order to apply it in practice. We only want
to mention two specific aspects that have to be addressed
in this context: First of all, sophisticated communication
protocols have to be developed that agents can use in
order to find out, which are the ontologies they share and
what are the options for re-writing. First investigations in
ontology negotiation are reported in [
Further steps in the direction of this research will be taken in the context of intelligent peer-to-peer networks which are the main topic of the IST project SWAP (Semantic Web and Peer-to-Peer). We will investigate how the approach behaves at a larger scale using two case studies. These case studies will provide us with a better understanding of the validity of the assumptions we made about the existence of shared ontologies and the integration of ontologies within a single agent. Further, a larger network of agents will enable us to investigate the use of third parties for mediating between agents that only share ontologies with this third party, resulting in a more complex scenario.