Integrating and Revising Knowledge in a distributed environment Aldo Franco Dragoni, Paolo Giorgini Istituto di Informatica, Universita di Ancona, via Brecce Bianche, 60131, Ancona (Italy) dragon@inform.unian.it Report It is generally recognized that the abilities to detect contradictions, identify their culprits and readjust the knowledge base to remove them are important features to embed in an intelligent information system. Trying to develope a method to perform belief revision in a multi-source enviroment) [1], we realized that three relevant items are: 1 consistency (hopefully maximal) of the revised knowledge base 2 credibility of the information items 3 reliability of the information sources [2]. Achieving maximal consistency is a symbolic process and could be accomplished by an ATMS-like device. On the other hand, the credibility of the beliefs and the reliability of the agents can hardly be estimated without numerical processing. In a previous paper [3] we introduced the idea of Distributed Belief Revision (DBR). With DBR, nodes interact with each others in order to accomplish their own task. Since they can be affected by some degree of incompetence (eventually also insincerity), part of the information running through the network may be incorrect. Occasionally, incorrect information may cause contradictions in the knowledge base of some nodes. To manage these contradictions, each node should be equipped with a BR module which makes it able to discriminate among more or less credible information items and more or less reliable information sources. DBR may be seen as a generalization of BR since it regards the emergent effects (i.e.from a global perspective) of the local adoption of a some particular BR mechanism. In a forthcoming network of interacting information systems some nodes could join the network with low degrees of competence or non-cooperative intentions (may be destructive ones). In these cases we need good strategies to protect the overall Global Information Agency from the introduction of information pollution, making it able, as far as possible, to detect its unreliable member agents. In such a realistic multi-agent scenario it becomes necessary to enlarge the classical idea of BR. In fact, to detect contradictions and identify their sources it is sufficient to maintain information about what has been told; but to properly "solve" a contradiction it is necessary to keep information about who said it or, in general, about where did that knowledge come from!1 The BR system cannot leave the sources of the information out of consideration because of their relevance in giving the additional notion of "strength of belief": the reliability of the source affects the credibility of the information and vice-versa. It is necessary to develop systems that deal with couples . Derived from researches in multi-agent [4] and investigative domains [5], our approach to BR is a novel assembly of known techniques to the treatment of consistency and uncertainty. Let us recapitulate here the main ideas. Defined as a symbolic model-theoretical problem, belief revision has also been approached both as a qualitative syntactic process and as a numerical mathematical issue. Both the previously held knowledge and the incoming information can be represented either as sets of weighted sentences or as sets of weighted possible worlds (the models of the sets of sentences). Weights can be either reals (normally between 0 and 1), representing explicitly the credibility of the sentences/models, or ordinals, representing implicitly the believability of the sentences/models w.r.t. the other ones. Essentially, knowledge revision consists in the redefinition of these weights in the light of the incoming information. According to us, in a multi-agent environment, where information come from a variety of sources with different degrees of reliability, belief revision has to depart considerably from its original framework. Particularly, the principle of "priority of the incoming information" should be abandoned. While it is acceptable when updating the representation of an evolving world, that principle is not generally justified when revising the representation of a static situation. In this case, the chronological sequence of the informative acts has nothing to do with their credibility or importance. Another point is that changes should not be irrevocable. To make practical and useful belief revision in a multi-agent environment, we substitute the priority of the incoming information with the following principle [6]. Recoverability: any previously believed information item must belong to the current cognitive state if it is consistent with it. We achieve recoverability by imposing the maximal consistency of the revised cognitive state. This method is local, i.e., integration/revision of the information is accomplished locally to the intelligent information agent in a centralized way. Under normal operating conditions, we do not expect that the global output emergent from DBR will be better than the local output of BR, neither for the quality nor for the quantity of the information provided. What we expect is that the distributed architecture will be: (1) more efficient: each local BR module should manage less information than in the centralized architecture and this should be very important as BR shows exponential complexity, (2) more "robust" ("fault tolerant"): it should be able to offer an acceptable output even in cases that BR fails due to nodes seriously compromised. On the other hand, nowadays DBR is a viable alternative to BR since the prices of hardware (CPU, RAM and, expecially, mass storage) and the communication costs have been dramatically cut down. In DBR nodes exchange information with each others. Thus we need to equip them with (at least) two modules: 1. a communication module (Comm), which deals with the three fundamental communication policies: a) choice of the recipient of the communication b) choice of the argument of the communication c) choice of the time of the communication 2. a model for belief integration/revision in a multi-source environment (BR) Communication can be either spontaneous (nodes offer information to some others) or on-demand (nodes ask some others for information). Among the various thinkable criteria to select the recipient of the communication, we see that two of them are worth noticing. Being guided by an "esprit de corps", one should offer its best information to the node it retain the least reliable one, with the aim of increasing its reliability. But the same collaborative spirit could lead to the opposite conclusion: one should send its best information item to the most reliable node since, if it will be recognized also by the others as the most reliable one, then that information item will be spreaded over all the group. The latter criterion seems to imply that unreliable nodes will be gradually isolated from the rest of the group. In order to increase the realism of this distributed architecture, we introduced two fundamental assumptions: 1. nodes do not communicate to the others the sources from where they received the data, but they present themselves as completely responsible for the knowledge they are passing onto the others; a receiver considers the sender as the source of the information it is sending 2. nodes do not exchange opinions regarding the reliability of the other nodes with whom they got in touch. By comparing its opinion with the others' ones, each node produces its own local opinion. The effects of the others' opinions depend on the rules adopted by the BR module. Although not necessary, we may want to extract from the network an emergent global opinion regarding the information treated by the group. To preserve the decentralized nature of DBR, this opinion shoud be synthetized not by an external supervisor/decisor, but by the entire group through some form of election: the group elects what it believes the global output to be returned to the external world should be. However, nothing prevents a user to get his/her information directly from a single node's output, since the election does not change the node's personal opinions. If the various cognitive states are quite similar, then the global output cannot differ very much from each node's one. Perhaps, the similarity between the opinions of the various nodes could be taken as a parameter to evaluate the quality of the Comm and BR modules. The election of the group's emergent output could be done in several ways. We have no room here to explore sufficiently this matter, however at the extreme positions we see two distinct kinds of election: 1. "data driven" election: the candidates are information items; only the winners will be part of the global output (direct synthesis of the global output) 2. "node driven" election: the candidates are nodes of the network; only the winners will be charged to make up the global opinion (synthesis "by proxy" of the global output) Many strategies can be conceived by mixing these two kinds of election. We believed that the comparison of the characteristics and performances of DBR could be done only on a simulation basis. We can report some first results. References [1] Dragoni A.F., A Model for Belief Revision in a Multi-Agent Environment, in Werner E. and Demazeau Y. (eds.), Decentralized A. I. 3, North Holland Elsevier Science Publisher, 1992. [2] Dragoni A.F., Belief Revision: from theory to practice, "The Knowledge Engineering Review", vol 12, n*2, Cambridge University Press, 1997. [3] A.F. Dragoni, P. Giorgini and P. Puliti, Distributed Belief Revision vs. Distributed Truth Maintenance, in Proc. 6th IEEE Conf. on Tools with A.I., IEEE Computer Press, 1994. [4] A.F. Dragoni, P. Giorgini, "Belief Revision through the Belief Function Formalism in a Multi-Agent Environment", Intelligent Agents III, LNAI n* 1193, Springer-Verlag, 1997. [5] Dragoni, A.F., Maximal Consistency, Theory of Evidence and Bayesian Conditioning in the Investigative Domain, to appear on the "International Journal on Artificial Intelligence and Law", 1997. [6] Dragoni A.F., Mascaretti F. and Puliti P., A Generalized Approach to Consistency-Based Belief Revision, in Gori, M. and Soda, G. (Eds.), Topics in Artificial Intelligence, LNAI 992, Springer Verlag, 1995.