A Formal Model for Situated Semantic Alignment Manuel Atencia Marco Schorlemmer IIIA, Artificial Intelligence Research Institute CSIC, Spanish National Research Council Bellaterra (Barcelona), Catalonia, Spain {manu, marco}@iiia.csic.es ABSTRACT Ontology matching is currently a key technology to achieve the semantic alignment of ontological entities used by knowledge-based applications, and therefore to enable their interoperability in distributed environments such as multiagent systems. Most ontology matching mechanisms, however, assume matching prior integration and rely on semantics that has been coded a priori in concept hierarchies or external sources. In this paper, we present a formal model for a semantic alignment procedure that incrementally aligns differing conceptualisations of two or more agents relative to their respective perception of the environment or domain they are acting in. It hence makes the situation in which the alignment occurs explicit in the model. We resort to Channel Theory to carry out the formalisation. Categories and Subject Descriptors I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence-coherence and coordination, multiagent systems; D.2.12 [Software Engineering]: Interoperability-data mapping; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods-semantic networks, relation systems. General Terms Theory 1. INTRODUCTION An ontology is commonly defined as a specification of the conceptualisation of a particular domain. It fixes the vocabulary used by knowledge engineers to denote concepts and their relations, and it constrains the interpretation of this vocabulary to the meaning originally intended by knowledge engineers. As such, ontologies have been widely adopted as a key technology that may favour knowledge sharing in distributed environments, such as multi-agent systems, federated databases, or the Semantic Web. But the proliferation of many diverse ontologies caused by different conceptualisations of even the same domain -and their subsequent specification using varying terminology- has highlighted the need of ontology matching techniques that are capable of computing semantic relationships between entities of separately engineered ontologies. [5, 11] Until recently, most ontology matching mechanisms developed so far have taken a classical functional approach to the semantic heterogeneity problem, in which ontology matching is seen as a process taking two or more ontologies as input and producing a semantic alignment of ontological entities as output [3]. Furthermore, matching often has been carried out at design-time, before integrating knowledge-based systems or making them interoperate. This might have been successful for clearly delimited and stable domains and for closed distributed systems, but it is untenable and even undesirable for the kind of applications that are currently deployed in open systems. Multi-agent communication, peer-to-peer information sharing, and webservice composition are all of a decentralised, dynamic, and open-ended nature, and they require ontology matching to be locally performed during run-time. In addition, in many situations peer ontologies are not even open for inspection (e.g., when they are based on commercially confidential information). Certainly, there exist efforts to efficiently match ontological entities at run-time, taking only those ontology fragment that are necessary for the task at hand [10, 13, 9, 8]. Nevertheless, the techniques used by these systems to establish the semantic relationships between ontological entities -even though applied at run-time- still exploit a priori defined concept taxonomies as they are represented in the graph-based structures of the ontologies to be matched, use previously existing external sources such as thesauri (e.g., WordNet) and upper-level ontologies (e.g., CyC or SUMO), or resort to additional background knowledge repositories or shared instances. We claim that semantic alignment of ontological terminology is ultimately relative to the particular situation in which the alignment is carried out, and that this situation should be made explicit and brought into the alignment mechanism. Even two agents with identical conceptualisation capabilities, and using exactly the same vocabulary to specify their respective conceptualisations may fail to interoperate 1278 978-81-904262-7-5 (RPS) c 2007 IFAAMAS in a concrete situation because of their differing perception of the domain. Imagine a situation in which two agents are facing each other in front of a checker board. Agent A1 may conceptualise a figure on the board as situated on the left margin of the board, while agent A2 may conceptualise the same figure as situated on the right. Although the conceptualisation of ‘left" and ‘right" is done in exactly the same manner by both agents, and even if both use the terms left and right in their communication, they still will need to align their respective vocabularies if they want to successfully communicate to each other actions that change the position of figures on the checker board. Their semantic alignment, however, will only be valid in the scope of their interaction within this particular situation or environment. The same agents situated differently may produce a different alignment. This scenario is reminiscent to those in which a group of distributed agents adapt to form an ontology and a shared lexicon in an emergent, bottom-up manner, with only local interactions and no central control authority [12]. This sort of self-organised emergence of shared meaning is namely ultimately grounded on the physical interaction of agents with the environment. In this paper, however, we address the case in which agents are already endowed with a top-down engineered ontology (it can even be the same one), which they do not adapt or refine, but for which they want to find the semantic relationships with separate ontologies of other agents on the grounds of their communication within a specific situation. In particular, we provide a formal model that formalises situated semantic alignment as a sequence of information-channel refinements in the sense of Barwise and Seligman"s theory of information flow [1]. This theory is particularly useful for our endeavour because it models the flow of information occurring in distributed systems due to the particular situations -or tokens- that carry information. Analogously, the semantic alignment that will allow information to flow ultimately will be carried by the particular situation agents are acting in. We shall therefore consider a scenario with two or more agents situated in an environment. Each agent will have its own viewpoint of the environment so that, if the environment is in a concrete state, both agents may have different perceptions of this state. Because of these differences there may be a mismatch in the meaning of the syntactic entities by which agents describe their perceptions (and which constitute the agents" respective ontologies). We state that these syntactic entities can be related according to the intrinsic semantics provided by the existing relationship between the agents" viewpoint of the environment. The existence of this relationship is precisely justified by the fact that the agents are situated and observe the same environment. In Section 2 we describe our formal model for Situated Semantic Alignment (SSA). First, in Section 2.1 we associate a channel to the scenario under consideration and show how the distributed logic generated by this channel provides the logical relationships between the agents" viewpoints of the environment. Second, in Section 2.2 we present a method by which agents obtain approximations of this distributed logic. These approximations gradually become more reliable as the method is applied. In Section 3 we report on an application of our method. Conclusions and further work are analyzed in Section 4. Finally, an appendix summarizes the terms and theorems of Channel theory used along the paper. We do not assume any knowledge of Channel Theory; we restate basic definitions and theorems in the appendix, but any detailed exposition of the theory is outside the scope of this paper. 2. A FORMAL MODEL FOR SSA 2.1 The Logic of SSA Consider a scenario with two agents A1 and A2 situated in an environment E (the generalization to any numerable set of agents is straightforward). We associate a numerable set S of states to E and, at any given instant, we suppose E to be in one of these states. We further assume that each agent is able to observe the environment and has its own perception of it. This ability is faithfully captured by a surjective function seei : S → Pi, where i ∈ {1, 2}, and typically see1 and see2 are different. According to Channel Theory, information is only viable where there is a systematic way of classifying some range of things as being this way or that, in other words, where there is a classification (see appendix A). So in order to be within the framework of Channel Theory, we must associate classifications to the components of our system. For each i ∈ {1, 2}, we consider a classification Ai that models Ai"s viewpoint of E. First, tok(Ai) is composed of Ai"s perceptions of E states, that is, tok(Ai) = Pi. Second, typ(Ai) contains the syntactic entities by which Ai describes its perceptions, the ones constituting the ontology of Ai. Finally, |=Ai synthesizes how Ai relates its perceptions with these syntactic entities. Now, with the aim of associating environment E with a classification E we choose the power classification of S as E, which is the classification whose set of types is equal to 2S , whose tokens are the elements of S, and for which a token e is of type ε if e ∈ ε. The reason for taking the power classification is because there are no syntactic entities that may play the role of types for E since, in general, there is no global conceptualisation of the environment. However, the set of types of the power classification includes all possible token configurations potentially described by types. Thus tok(E) = S, typ(E) = 2S and e |=E ε if and only if e ∈ ε. The notion of channel (see appendix A) is fundamental in Barwise and Seligman"s theory. The information flow among the components of a distributed system is modelled in terms of a channel and the relationships among these components are expressed via infomorphisms (see appendix A) which provide a way of moving information between them. The information flow of the scenario under consideration is accurately described by channel E = {fi : Ai → E}i∈{1,2} defined as follows: • ˆfi(α) = {e ∈ tok(E) | seei(e) |=Ai α} for each α ∈ typ(Ai) • ˇfi(e) = seei(e) for each e ∈ tok(E) where i ∈ {1, 2}. Definition of ˇfi seems natural while ˆfi is defined in such a way that the fundamental property of the infomorphisms is fulfilled: ˇfi(e) |=Ai α iff seei(e) |=Ai α (by definition of ˇfi) iff e ∈ ˆfi(α) (by definition of ˆfi) iff e |=E ˆfi(α) (by definition of |=E) The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1279 Consequently, E is the core of channel E and a state e ∈ tok(E) connects agents" perceptions ˇf1(e) and ˇf2(e) (see Figure 1). typ(E) typ(A1) ˆf1 99ttttttttt typ(A2) ˆf2 eeJJJJJJJJJ tok(E) |=E ˇf1yyttttttttt ˇf2 %%JJJJJJJJJ tok(A1) |=A1 tok(A2) |=A2 Figure 1: Channel E E explains the information flow of our scenario by virtue of agents A1 and A2 being situated and perceiving the same environment E. We want to obtain meaningful relations among agents" syntactic entities, that is, agents" types. We state that meaningfulness must be in accord with E. The sum operation (see appendix A) gives us a way of putting the two agents" classifications of channel E together into a single classification, namely A1 +A2, and also the two infomorphisms together into a single infomorphism, f1 +f2 : A1 + A2 → E. A1 + A2 assembles agents" classifications in a very coarse way. tok(A1 + A2) is the cartesian product of tok(A1) and tok(A2), that is, tok(A1 + A2) = { p1, p2 | pi ∈ Pi}, so a token of A1 + A2 is a pair of agents" perceptions with no restrictions. typ(A1 + A2) is the disjoint union of typ(A1) and typ(A2), and p1, p2 is of type i, α if pi is of type α. We attach importance to take the disjoint union because A1 and A2 could use identical types with the purpose of describing their respective perceptions of E. Classification A1 + A2 seems to be the natural place in which to search for relations among agents" types. Now, Channel Theory provides a way to make all these relations explicit in a logical fashion by means of theories and local logics (see appendix A). The theory generated by the sum classification, Th(A1 + A2), and hence its logic generated, Log(A1 + A2), involve all those constraints among agents" types valid according to A1 +A2. Notice however that these constraints are obvious. As we stated above, meaningfulness must be in accord with channel E. Classifications A1 + A2 and E are connected via the sum infomorphism, f = f1 + f2, where: • ˆf( i, α ) = ˆfi(α) = {e ∈ tok(E) | seei(e) |=Ai α} for each i, α ∈ typ(A1 + A2) • ˇf(e) = ˇf1(e), ˇf2(e) = see1(e), see2(e) for each e ∈ tok(E) Meaningful constraints among agents" types are in accord with channel E because they are computed making use of f as we expound below. As important as the notion of channel is the concept of distributed logic (see appendix A). Given a channel C and a logic L on its core, DLogC(L) represents the reasoning about relations among the components of C justified by L. If L = Log(C), the distributed logic, we denoted by Log(C), captures in a logical fashion the information flow inherent in the channel. In our case, Log(E) explains the relationship between the agents" viewpoints of the environment in a logical fashion. On the one hand, constraints of Th(Log(E)) are defined by: Γ Log(E) Δ if ˆf[Γ] Log(E) ˆf[Δ] (1) where Γ, Δ ⊆ typ(A1 + A2). On the other hand, the set of normal tokens, NLog(E), is equal to the range of function ˇf: NLog(E) = ˇf[tok(E)] = { see1(e), see2(e) | e ∈ tok(E)} Therefore, a normal token is a pair of agents" perceptions that are restricted by coming from the same environment state (unlike A1 + A2 tokens). All constraints of Th(Log(E)) are satisfied by all normal tokens (because of being a logic). In this particular case, this condition is also sufficient (the proof is straightforward); as alternative to (1) we have: Γ Log(E) Δ iff for all e ∈ tok(E), if (∀ i, γ ∈ Γ)[seei(e) |=Ai γ] then (∃ j, δ ∈ Δ)[seej(e) |=Aj δ] (2) where Γ, Δ ⊆ typ(A1 + A2). Log(E) is the logic of SSA. Th(Log(E)) comprises the most meaningful constraints among agents" types in accord with channel E. In other words, the logic of SSA contains and also justifies the most meaningful relations among those syntactic entities that agents use in order to describe their own environment perceptions. Log(E) is complete since Log(E) is complete but it is not necessarily sound because although Log(E) is sound, ˇf is not surjective in general (see appendix B). If Log(E) is also sound then Log(E) = Log(A1 +A2) (see appendix B). That means there is no significant relation between agents" points of view of the environment according to E. It is just the fact that Log(E) is unsound what allows a significant relation between the agents" viewpoints. This relation is expressed at the type level in terms of constraints by Th(Log(E)) and at the token level by NLog(E). 2.2 Approaching the logic of SSA through communication We have dubbed Log(E) the logic of SSA. Th(Log(E)) comprehends the most meaningful constraints among agents" types according to E. The problem is that neither agent can make use of this theory because they do not know E completely. In this section, we present a method by which agents obtain approximations to Th(Log(E)). We also prove these approximations gradually become more reliable as the method is applied. Agents can obtain approximations to Th(Log(E)) through communication. A1 and A2 communicate by exchanging information about their perceptions of environment states. This information is expressed in terms of their own classification relations. Specifically, if E is in a concrete state e, we assume that agents can convey to each other which types are satisfied by their respective perceptions of e and which are not. This exchange generates a channel C = {fi : Ai → 1280 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) C}i∈{1,2} and Th(Log(C)) contains the constraints among agents" types justified by the fact that agents have observed e. Now, if E turns to another state e and agents proceed as before, another channel C = {fi : Ai → C }i∈{1,2} gives account of the new situation considering also the previous information. Th(Log(C )) comprises the constraints among agents" types justified by the fact that agents have observed e and e . The significant point is that C is a refinement of C (see appendix A). Theorem 2.1 below ensures that the refined channel involves more reliable information. The communication supposedly ends when agents have observed all the environment states. Again this situation can be modeled by a channel, call it C∗ = {f∗ i : Ai → C∗ }i∈{1,2}. Theorem 2.2 states that Th(Log(C∗ )) = Th(Log(E)). Theorem 2.1 and Theorem 2.2 assure that applying the method agents can obtain approximations to Th(Log(E)) gradually more reliable. Theorem 2.1. Let C = {fi : Ai → C}i∈{1,2} and C = {fi : Ai → C }i∈{1,2} be two channels. If C is a refinement of C then: 1. Th(Log(C )) ⊆ Th(Log(C)) 2. NLog(C ) ⊇ NLog(C) Proof. Since C is a refinement of C then there exists a refinement infomorphism r from C to C; so fi = r ◦ fi . Let A =def A1 + A2, f =def f1 + f2 and f =def f1 + f2. 1. Let Γ and Δ be subsets of typ(A) and assume that Γ Log(C ) Δ, which means ˆf [Γ] C ˆf [Δ]. We have to prove Γ Log(C) Δ, or equivalently, ˆf[Γ] C ˆf[Δ]. We proceed by reductio ad absurdum. Suppose c ∈ tok(C) does not satisfy the sequent ˆf[Γ], ˆf[Δ] . Then c |=C ˆf(γ) for all γ ∈ Γ and c |=C ˆf(δ) for all δ ∈ Δ. Let us choose an arbitrary γ ∈ Γ. We have that γ = i, α for some α ∈ typ(Ai) and i ∈ {1, 2}. Thus ˆf(γ) = ˆf( i, α ) = ˆfi(α) = ˆr ◦ ˆfi (α) = ˆr( ˆfi (α)). Therefore: c |=C ˆf(γ) iff c |=C ˆr( ˆfi (α)) iff ˇr(c) |=C ˆfi (α) iff ˇr(c) |=C ˆf ( i, α ) iff ˇr(c) |=C ˆf (γ) Consequently, ˇr(c) |=C ˆf (γ) for all γ ∈ Γ. Since ˆf [Γ] C ˆf [Δ] then there exists δ∗ ∈ Δ such that ˇr(c) |=C ˆf (δ∗ ). A sequence of equivalences similar to the above one justifies c |=C ˆf(δ∗ ), contradicting that c is a counterexample to ˆf[Γ], ˆf[Δ] . Hence Γ Log(C) Δ as we wanted to prove. 2. Let a1, a2 ∈ tok(A) and assume a1, a2 ∈ NLog(C). Therefore, there exists c token in C such that a1, a2 = ˇf(c). Then we have ai = ˇfi(c) = ˇfi ◦ ˇr(c) = ˇfi (ˇr(c)), for i ∈ {1, 2}. Hence a1, a2 = ˇf (ˇr(c)) and a1, a2 ∈ NLog(C ). Consequently, NLog(C ) ⊇ NLog(C) which concludes the proof. Remark 2.1. Theorem 2.1 asserts that the more refined channel gives more reliable information. Even though its theory has less constraints, it has more normal tokens to which they apply. In the remainder of the section, we explicitly describe the process of communication and we conclude with the proof of Theorem 2.2. Let us assume that typ(Ai) is finite for i ∈ {1, 2} and S is infinite numerable, though the finite case can be treated in a similar form. We also choose an infinite numerable set of symbols {cn | n ∈ N}1 . We omit informorphisms superscripts when no confusion arises. Types are usually denoted by greek letters and tokens by latin letters so if f is an infomorphism, f(α) ≡ ˆf(α) and f(a) ≡ ˇf(a). Agents communication starts from the observation of E. Let us suppose that E is in state e1 ∈ S = tok(E). A1"s perception of e1 is f1(e1 ) and A2"s perception of e1 is f2(e1 ). We take for granted that A1 can communicate A2 those types that are and are not satisfied by f1(e1 ) according to its classification A1. So can A2 do. Since both typ(A1) and typ(A2) are finite, this process eventually finishes. After this communication a channel C1 = {f1 i : Ai → C1 }i=1,2 arises (see Figure 2). C1 A1 f1 1 ==|||||||| A2 f1 2 aaCCCCCCCC Figure 2: The first communication stage On the one hand, C1 is defined by: • tok(C1 ) = {c1 } • typ(C1 ) = typ(A1 + A2) • c1 |=C1 i, α if fi(e1 ) |=Ai α (for every i, α ∈ typ(A1 + A2)) On the other hand, f1 i , with i ∈ {1, 2}, is defined by: • f1 i (α) = i, α (for every α ∈ typ(Ai)) • f1 i (c1 ) = fi(e1 ) Log(C1 ) represents the reasoning about the first stage of communication. It is easy to prove that Th(Log(C1 )) = Th(C1 ). The significant point is that both agents know C1 as the result of the communication. Hence they can compute separately theory Th(C1 ) = typ(C1 ), C1 which contains the constraints among agents" types justified by the fact that agents have observed e1 . Now, let us assume that E turns to a new state e2 . Agents can proceed as before, exchanging this time information about their perceptions of e2 . Another channel C2 = {f2 i : Ai → C2 }i∈{1,2} comes up. We define C2 so as to take also into account the information provided by the previous stage of communication. On the one hand, C2 is defined by: • tok(C2 ) = {c1 , c2 } 1 We write these symbols with superindices because we limit the use of subindices for what concerns to agents. Note this set is chosen with the same cardinality of S. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1281 • typ(C2 ) = typ(A1 + A2) • ck |=C2 i, α if fi(ek ) |=Ai α (for every k ∈ {1, 2} and i, α ∈ typ(A1 + A2)) On the other hand, f2 i , with i ∈ {1, 2}, is defined by: • f2 i (α) = i, α (for every α ∈ typ(Ai)) • f2 i (ck ) = fi(ek ) (for every k ∈ {1, 2}) Log(C2 ) represents the reasoning about the former and the later communication stages. Th(Log(C2 )) is equal to Th(C2 ) = typ(C2 ), C2 , then it contains the constraints among agents" types justified by the fact that agents have observed e1 and e2 . A1 and A2 knows C2 so they can use these constraints. The key point is that channel C2 is a refinement of C1 . It is easy to check that f1 defined as the identity function on types and the inclusion function on tokens is a refinement infomorphism (see at the bottom of Figure 3). By Theorem 2.1, C2 constraints are more reliable than C1 constraints. In the general situation, once the states e1 , e2 , . . . , en−1 (n ≥ 2) have been observed and a new state en appears, channel Cn = {fn i : Ai → Cn }i∈{1,2} informs about agents communication up to that moment. Cn definition is similar to the previous ones and analogous remarks can be made (see at the top of Figure 3). Theory Th(Log(Cn )) = Th(Cn ) = typ(Cn ), Cn contains the constraints among agents" types justified by the fact that agents have observed e1 , e2 , . . . , en . Cn fn−1 A1 fn−1 1 99PPPPPPPPPPPPP fn 1 UUnnnnnnnnnnnnn f2 1 %%44444444444444444444444444 f1 1 "",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, A2 fn 2 ggPPPPPPPPPPPPP fn−1 2 wwnnnnnnnnnnnnn f2 2 ÕÕ f1 2 ØØ Cn−1 . . . C2 f1 C1 Figure 3: Agents communication Remember we have assumed that S is infinite numerable. It is therefore unpractical to let communication finish when all environment states have been observed by A1 and A2. At that point, the family of channels {Cn }n∈N would inform of all the communication stages. It is therefore up to the agents to decide when to stop communicating should a good enough approximation have been reached for the purposes of their respective tasks. But the study of possible termination criteria is outside the scope of this paper and left for future work. From a theoretical point of view, however, we can consider the channel C∗ = {f∗ i : Ai → C∗ }i∈{1,2} which informs of the end of the communication after observing all environment states. On the one hand, C∗ is defined by: • tok(C∗ ) = {cn | n ∈ N} • typ(C∗ ) = typ(A1 + A2) • cn |=C∗ i, α if fi(en ) |=Ai α (for n ∈ N and i, α ∈ typ(A1 + A2)) On the other hand, f∗ i , with i ∈ {1, 2}, is defined by: • f∗ i (α) = i, α (for α ∈ typ(Ai)) • f∗ i (cn ) = fi(en ) (for n ∈ N) Theorem below constitutes the cornerstone of the model exposed in this paper. It ensures, together with Theorem 2.1, that at each communication stage agents obtain a theory that approximates more closely to the theory generated by the logic of SSA. Theorem 2.2. The following statements hold: 1. For all n ∈ N, C∗ is a refinement of Cn . 2. Th(Log(E)) = Th(C∗ ) = Th(Log(C∗ )). Proof. 1. It is easy to prove that for each n ∈ N, gn defined as the identity function on types and the inclusion function on tokens is a refinement infomorphism from C∗ to Cn . 2. The second equality is straightforward; the first one follows directly from: cn |=C∗ i, α iff ˇfi(en ) |=Ai α (by definition of |=C∗ ) iff en |=E ˆfi(α) (because fi is infomorphim) iff en |=E ˆf( i, α ) (by definition of ˆf) E C∗ gn A1 fn 1 99OOOOOOOOOOOOO f∗ 1 UUooooooooooooo f1 cc A2 f∗ 2 ggOOOOOOOOOOOOO fn 2 wwooooooooooooo f2 ????????????????? Cn 1282 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 3. AN EXAMPLE In the previous section we have described in great detail our formal model for SSA. However, we have not tackled the practical aspect of the model yet. In this section, we give a brushstroke of the pragmatic view of our approach. We study a very simple example and explain how agents can use those approximations of the logic of SSA they can obtain through communication. Let us reflect on a system consisting of robots located in a two-dimensional grid looking for packages with the aim of moving them to a certain destination (Figure 4). Robots can carry only one package at a time and they can not move through a package. Figure 4: The scenario Robots have a partial view of the domain and there exist two kinds of robots according to the visual field they have. Some robots are capable of observing the eight adjoining squares but others just observe the three squares they have in front (see Figure 5). We call them URDL (shortened form of Up-Right-Down-Left) and LCR (abbreviation for Left-Center-Right) robots respectively. Describing the environment states as well as the robots" perception functions is rather tedious and even unnecessary. We assume the reader has all those descriptions in mind. All robots in the system must be able to solve package distribution problems cooperatively by communicating their intentions to each other. In order to communicate, agents send messages using some ontology. In our scenario, there coexist two ontologies, the UDRL and LCR ontologies. Both of them are very simple and are just confined to describe what robots observe. Figure 5: Robots field of vision When a robot carrying a package finds another package obstructing its way, it can either go around it or, if there is another robot in its visual field, ask it for assistance. Let us suppose two URDL robots are in a situation like the one depicted in Figure 6. Robot1 (the one carrying a package) decides to ask Robot2 for assistance and sends a request. This request is written below as a KQML message and it should be interpreted intuitively as: Robot2, pick up the package located in my Up square, knowing that you are located in my Up-Right square. ` request :sender Robot1 :receiver Robot2 :language Packages distribution-language :ontology URDL-ontology :content (pick up U(Package) because UR(Robot2) ´ Figure 6: Robot assistance Robot2 understands the content of the request and it can use a rule represented by the following constraint: 1, UR(Robot2) , 2, UL(Robot1) , 1, U(Package) 2, U(Package) The above constraint should be interpreted intuitively as: if Robot2 is situated in Robot1"s Up-Right square, Robot1 is situated in Robot2"s Up-Left square and a package is located in Robot1"s Up square, then a package is located in Robot2"s Up square. Now, problems arise when a LCR robot and a URDL robot try to interoperate. See Figure 7. Robot1 sends a request of the form: ` request :sender Robot1 :receiver Robot2 :language Packages distribution-language :ontology LCR-ontology :content (pick up R(Robot2) because C(Package) ´ Robot2 does not understand the content of the request but they decide to begin a process of alignment -corresponding with a channel C1 . Once finished, Robot2 searches in Th(C1 ) for constraints similar to the expected one, that is, those of the form: 1, R(Robot2) , 2, UL(Robot1) , 1, C(Package) C1 2, λ(Package) where λ ∈ {U, R, D, L, UR, DR, DL, UL}. From these, only the following constraints are plausible according to C1 : The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1283 Figure 7: Ontology mismatch 1, R(Robot2) , 2, UL(Robot1) , 1, C(Package) C1 2, U(Package) 1, R(Robot2) , 2, UL(Robot1) , 1, C(Package) C1 2, L(Package) 1, R(Robot2) , 2, UL(Robot1) , 1, C(Package) C1 2, DR(Package) If subsequently both robots adopting the same roles take part in a situation like the one depicted in Figure 8, a new process of alignment -corresponding with a channel C2 - takes place. C2 also considers the previous information and hence refines C1 . The only constraint from the above ones that remains plausible according to C2 is : 1, R(Robot2) , 2, UL(Robot1) , 1, C(Package) C2 2, U(Package) Notice that this constraint is an element of the theory of the distributed logic. Agents communicate in order to cooperate successfully and success is guaranteed using constrains of the distributed logic. Figure 8: Refinement 4. CONCLUSIONS AND FURTHER WORK In this paper we have exposed a formal model of semantic alignment as a sequence of information-channel refinements that are relative to the particular states of the environment in which two agents communicate and align their respective conceptualisations of these states. Before us, Kent [6] and Kalfoglou and Schorlemmer [4, 10] have applied Channel Theory to formalise semantic alignment using also Barwise and Seligman"s insight to focus on tokens as the enablers of information flow. Their approach to semantic alignment, however, like most ontology matching mechanisms developed to date (regardless of whether they follow a functional, design-time-based approach, or an interaction-based, runtime-based approach), still defines semantic alignment in terms of a priori design decisions such as the concept taxonomy of the ontologies or the external sources brought into the alignment process. Instead the model we have presented in this paper makes explicit the particular states of the environment in which agents are situated and are attempting to gradually align their ontological entities. In the future, our effort will focus on the practical side of the situated semantic alignment problem. We plan to further refine the model presented here (e.g., to include pragmatic issues such as termination criteria for the alignment process) and to devise concrete ontology negotiation protocols based on this model that agents may be able to enact. The formal model exposed in this paper will constitute a solid base of future practical results. Acknowledgements This work is supported under the UPIC project, sponsored by Spain"s Ministry of Education and Science under grant number TIN2004-07461-C02- 02 and also under the OpenKnowledge Specific Targeted Research Project (STREP), sponsored by the European Commission under contract number FP6-027253. Marco Schorlemmer is supported by a Ram´on y Cajal Research Fellowship from Spain"s Ministry of Education and Science, partially funded by the European Social Fund. 5. REFERENCES [1] J. Barwise and J. Seligman. Information Flow: The Logic of Distributed Systems. Cambridge University Press, 1997. [2] C. Ghidini and F. Giunchiglia. Local models semantics, or contextual reasoning = locality + compatibility. Artificial Intelligence, 127(2):221-259, 2001. [3] F. Giunchiglia and P. Shvaiko. Semantic matching. The Knowledge Engineering Review, 18(3):265-280, 2004. [4] Y. Kalfoglou and M. Schorlemmer. IF-Map: An ontology-mapping method based on information-flow theory. In Journal on Data Semantics I, LNCS 2800, 2003. [5] Y. Kalfoglou and M. Schorlemmer. Ontology mapping: The sate of the art. The Knowledge Engineering Review, 18(1):1-31, 2003. [6] R. E. Kent. Semantic integration in the Information Flow Framework. In Semantic Interoperability and Integration, Dagstuhl Seminar Proceedings 04391, 2005. [7] D. Lenat. CyC: A large-scale investment in knowledge infrastructure. Communications of the ACM, 38(11), 1995. [8] V. L´opez, M. Sabou, and E. Motta. PowerMap: Mapping the real Semantic Web on the fly. Proceedings of the ISWC"06, 2006. [9] F. McNeill. Dynamic Ontology Refinement. PhD 1284 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) thesis, School of Informatics, The University of Edinburgh, 2006. [10] M. Schorlemmer and Y. Kalfoglou. Progressive ontology alignment for meaning coordination: An information-theoretic foundation. In 4th Int. Joint Conf. on Autonomous Agents and Multiagent Systems, 2005. [11] P. Shvaiko and J. Euzenat. A survey of schema-based matching approaches. In Journal on Data Semantics IV, LNCS 3730, 2005. [12] L. Steels. The Origins of Ontologies and Communication Conventions in Multi-Agent Systems. In Journal of Autonomous Agents and Multi-Agent Systems, 1(2), 169-194, 1998. [13] J. van Diggelen et al. ANEMONE: An Effective Minimal Ontology Negotiation Environment In 5th Int. Joint Conf. on Autonomous Agents and Multiagent Systems, 2006 APPENDIX A. CHANNEL THEORY TERMS Classification: is a tuple A = tok(A), typ(A), |=A where tok(A) is a set of tokens, typ(A) is a set of types and |=A is a binary relation between tok(A) and typ(A). If a |=A α then a is said to be of type α. Infomorphism: f : A → B from classifications A to B is a contravariant pair of functions f = ˆf, ˇf , where ˆf : typ(A) → typ(B) and ˇf : tok(B) → tok(A), satisfying the following fundamental property: ˇf(b) |=A α iff b |=B ˆf(α) for each token b ∈ tok(B) and each type α ∈ typ(A). Channel: consists of two infomorphisms C = {fi : Ai → C}i∈{1,2} with a common codomain C, called the core of C. C tokens are called connections and a connection c is said to connect tokens ˇf1(c) and ˇf2(c).2 Sum: given classifications A and B, the sum of A and B, denoted by A + B, is the classification with tok(A + B) = tok(A) × tok(B) = { a, b | a ∈ tok(A) and b ∈ tok(B)}, typ(A + B) = typ(A) typ(B) = { i, γ | i = 1 and γ ∈ typ(A) or i = 2 and γ ∈ typ(B)} and relation |=A+B defined by: a, b |=A+B 1, α if a |=A α a, b |=A+B 2, β if b |=B β Given infomorphisms f : A → C and g : B → C, the sum f + g : A + B → C is defined on types by ˆ(f + g)( 1, α ) = ˆf(α) and ˆ(f + g)( 2, β ) = ˆg(β), and on tokens by ˇ(f + g)(c) = ˇf(c), ˇg(c) . Theory: given a set Σ, a sequent of Σ is a pair Γ, Δ of subsets of Σ. A binary relation between subsets of Σ is called a consequence relation on Σ. A theory is a pair T = Σ, where is a consequence relation on Σ. A sequent Γ, Δ of Σ for which Γ Δ is called a constraint of the theory T. T is regular if it satisfies: 1. Identity: α α 2. Weakening: if Γ Δ, then Γ, Γ Δ, Δ 2 In fact, this is the definition of a binary channel. A channel can be defined with an arbitrary index set. 3. Global Cut: if Γ, Π0 Δ, Π1 for each partition Π0, Π1 of Π (i.e., Π0 ∪ Π1 = Π and Π0 ∩ Π1 = ∅), then Γ Δ for all α ∈ Σ and all Γ, Γ , Δ, Δ , Π ⊆ Σ.3 Theory generated by a classification: let A be a classification. A token a ∈ tok(A) satisfies a sequent Γ, Δ of typ(A) provided that if a is of every type in Γ then it is of some type in Δ. The theory generated by A, denoted by Th(A), is the theory typ(A), A where Γ A Δ if every token in A satisfies Γ, Δ . Local logic: is a tuple L = tok(L), typ(L), |=L , L , NL where: 1. tok(L), typ(L), |=L is a classification denoted by Cla(L), 2. typ(L), L is a regular theory denoted by Th(L), 3. NL is a subset of tok(L), called the normal tokens of L, which satisfy all constraints of Th(L). A local logic L is sound if every token in Cla(L) is normal, that is, NL = tok(L). L is complete if every sequent of typ(L) satisfied by every normal token is a constraint of Th(L). Local logic generated by a classification: given a classification A, the local logic generated by A, written Log(A), is the local logic on A (i.e., Cla(Log(A)) = A), with Th(Log(A)) = Th(A) and such that all its tokens are normal, i.e., NLog(A) = tok(A). Inverse image: given an infomorphism f : A → B and a local logic L on B, the inverse image of L under f, denoted f−1 [L], is the local logic on A such that Γ f−1[L] Δ if ˆf[Γ] L ˆf[Δ] and Nf−1[L] = ˇf[NL ] = {a ∈ tok(A) | a = ˇf(b) for some b ∈ NL }. Distributed logic: let C = {fi : Ai → C}i∈{1,2} be a channel and L a local logic on its core C, the distributed logic of C generated by L, written DLogC(L), is the inverse image of L under the sum f1 + f2. Refinement: let C = {fi : Ai → C}i∈{1,2} and C = {fi : Ai → C }i∈{1,2} be two channels with the same component classifications A1 and A2. A refinement infomorphism from C to C is an infomorphism r : C → C such that for each i ∈ {1, 2}, fi = r ◦fi (i.e., ˆfi = ˆr ◦ ˆfi and ˇfi = ˇfi ◦ˇr). Channel C is a refinement of C if there exists a refinement infomorphism r from C to C. B. CHANNEL THEORY THEOREMS Theorem B.1. The logic generated by a classification is sound and complete. Furthermore, given a classification A and a logic L on A, L is sound and complete if and only if L = Log(A). Theorem B.2. Let L be a logic on a classification B and f : A → B an infomorphism. 1. If L is complete then f−1 [L] is complete. 2. If L is sound and ˇf is surjective then f−1 [L] is sound. 3 All theories considered in this paper are regular. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1285
ontology semantic web disjoint union sum infomorphism constraint distributed logic semantic alignment
multi-agent system federated database knowledge-based system information-channel refinement distribute logic channel refinement