Towards Efficient Multi-Agent Abduction Protocols Gauvain Bourgne Katsumi Inoue Nicolas Maudet National Institute of Informatics National Institute of Informatics LAMSADE, Tokyo, Japan Tokyo, Japan Paris Dauphine University, France Email: bourgne@nii.ac.jp Email: ki@nii.ac.jp Email: nicolas.maudet@lamsade.dauphine.fr Abstract—What happens when distributed sources of informa- Distributed abduction has been considered in recent years tion (agents) hold and acquire information locally, and have to in the ALIAS system [3]. They distribute the abductive pro- communicate with neighbouring agents in order to refine their gramming algorithm of [4], using abductive logic program hypothesis regarding the actual global state of this environment? This question occurs when it is not be possible (e. g. for practical to represent each agent’s theory. More recently, DARE [5] or privacy concerns) to collect observations and knowledge, addressed a similar problem, but consider possible dynamicity and centrally compute the resulting theory. In this paper, we of the system by allowing agents to enter or exit some assume that agents are equipped with full clausal theories proof cluster. In none of these works however is the issue of and individually face abductive tasks, in a globally consistent communication constraints explicitely raised. Another related environment. We adopt a learner/critic approach. We present the Multi-agent Abductive Reasoning System (MARS), a protocol work is the peer-to-peer consequence finding algorithm DeCA guaranteeing convergence to a situation “sufficiently” satisfying [6]. Based on a different method (splitting clauses), it is to as far as consistency of the system is concerned. Abduction in our knowledge the only other work in this domain taking a full clausal theory has however already a high computational into account restrictions of communication between peers. It cost in centralized settings, which can become much worse with is however restricted to propositional theories. The work on arbitrary distributions. We thus discuss ways to use knowledge about each agent’s theory language to improve efficiency. We partition-based logical reasoning presented [7] is of particular then present some first experimental results to assess the impact interest for our present study as it investigates efficient theorem of those refinements. proving in partitioned theories. It relies on communication languages describing the common symbol in the individual I. I NTRODUCTION languages of pairs of agents. However, this approach and the previous one explore all the consequences of the distributed In multi-agent systems, the inherent distribution of au- theories, whereas when we are only concerned with some new tonomous entities, perceiving and acting locally, is the source consequences of the theories with respect to some knowledge of many challenging questions. To overcome the limitation (namely the negated observations when computing a hypoth- of their own knowledge, usually local and incomplete, agents esis through inverse entailment, or the hypothesis itself when are driven to form some hypotheses and share information ensuring its consistency). As a result, while inspirational, they with other agents. Especially, abductive reasoning is a form of cannot be directly applied to our approach. hypothetical reasoning deriving the possible causes of an ob- The rest of this paper is as follows. Section II gives the servation. It can be used to complete an agent’s understanding necessary background on abduction and consequence finding. of its environment by explaining its observations, or, more pro- Then, Section III describe formally a multi-agent abduction actively, for planning, as one can try to find the possible actions problem, and present the MARS protocol, giving details about that might cause the completion of a goal. However reasoning the communications exchanged over its execution. Efficiency in a sound manner with distributed knowledge rises interesting is then discussed, and we describe two improvement on the problems, as one cannot ensure locally the consistency of an previous protocol. These variants are then experimentally information. Moreover, the system often comes with severe tested in Section IV, and we conclude in Section V. communication restrictions, due to physical (e. g. the limited II. A BDUCTIVE REASONING scope of a communication device) or reasoning (e. g. the mere impossibility to consider all the potential communications) A. Preliminaries limitations of agents populating it. For such situations, we First, we review some notions and terminology to rep- presented in [1] a sound mechanism that is guaranteed to find resent our problem in a logical setting. A literal is an an abductive hypotheses with respect to distributed full clausal atom or the negation of an atom. A clause is a disjunction theories whenever one exists. This Multi-agent Abductive of literals, and is often denoted by the set of literals. A Reasoning System, MARS, is based on a consequence finding clause {A1 , . . . , Am , ¬B1 , . . . , ¬Bn }, where Ai and ¬Bj are tools named SOLAR [2], that serves as a main reasoning respectively positive and negative atoms is also written as engine. We are concerned in this paper with the efficiency A1 ∨ . . . ∨ Am ← B1 ∧ . . . ∧ Bn . Any variable in a clause of this mechanism, and thus want to evaluate and improve its is assumed to be universally quantified at the front. A clausal average computational and communicational cost. theory is a finite set of clauses which can be identified with the 34 conjunction of the clauses. Let S and T be clausal theories. which converts the accountability W condition (i)Wto T ∪{¬O} |= S logically implies T , denoted as S |= T , if and only if for ¬H, where ¬O = L∈O ¬L and ¬H = L∈H ¬L. Note every interpretation I such that S is true under I, T is also that both ¬O and ¬H are clauses since O and H are sets of true under I. |= is called the entailment relation. For a clausal literals. Similarly, consistency condition (ii) is equivalent to theory T , a consequence of T is a clause entailed by T . We T 6|= ¬H. Hence, for any hypothesis H, its negated form ¬H denote by T h(T ) the set of all consequences of T . Let C and is deductively obtained as a “new” theorem of T ∪ {¬O} that D be two clauses. C subsumes D, denoted C  D, if there is not an “old” theorem of T alone. Moreover, to respect the is a substitution θ such that Cθ ⊆ D. C properly subsumes bias condition (iii), every literal of ¬H has to be an instance of D if C  D but D 6 C. For a clausal theory T , µT denotes a literal in Ā = {¬L|L ∈ A}. Then the negation of minimal the set of clauses in T not properly subsumed by any clause hypotheses are the new characteristic clauses of O with respect in T . to T and Ā, that is, N ewcarc(T , {¬O}, Ā). We can now introduce the notion of characteristic clauses, SOLAR [2] is a sophisticated deductive reasoning system which represents “interesting” consequences of a given prob- based on SOL-resolution [8], which is sound and complete for lem [8]. Each characteristic clause is constructed over a sub- finding minimal consequences belonging to a given language vocabulary of the representation language called a production bias (a production field). Consequence-finding by SOLAR is field, and represented as hLi, where L is a set of literal performed by skipping literals belonging to a production field closed under instantiation. A clause C belongs to P = hLi P instead of resolving them. Those skipped literals are then if every literal in C belongs to L. For a clausal theory T , collected at the end of a proof, which constitute a clause as a the set of consequences of T belonging to P is denoted logical consequence of the axiom set. Using SOLAR, we can T hP (T ). Then, the characteristic clauses of T wrt to P are implement an abductive system that is complete for finding defined as Carc(T , P) = µT hP (T ), where µ is subsumption minimal explanations due to the completeness of consequence- minimality1 . When a set of new clauses S is added to a finding. SOLAR is designed for full clausal theories contain- clausal theory, some consequences are newly derived with this ing non-Horn clauses, and is based on a connection tableau additional information. The set of such clauses that belong to format [10]. In this format, many redundant deductions are the production field are called new characteristic clauses of avoided using various state-of-the-art pruning techniques [2], S wrt T and P; they are defined as N ewcarc(T , S, P) = thereby hypothesis-finding is efficiently realized. Carc(T ∪ S, P) \ Carc(T , P). Once possible hypotheses have been computed, a ranking process can be applied to select a preferred hypothesis (e.g. B. Abductive hypothesis hypothesis ranking such as in [11]). We will not dwell on this The logical framework of hypothesis generation in abduc- part here, and instead assumed that a preference relation ≥p tion for the centralized case can be expressed as follows. Let over the hypothesis is given as a total order between sets of T be a clausal theory, which represents the background theory, grounded literals. and O be a set of literals, which represents observations. Also let A be a set of literals representing the set of abducibles, III. D ISTRIBUTED A BDUCTION which are candidate assumptions to be added to T for explain- A. Problem setting ing O. Given T , O and A, the abduction problem is to find a We propose here a new formalization of our problem as hypothesis H such that: a multi-agent abductive system, which is defined as a tuple (i) T ∪ H |= O (accountability), hS, {Γt }, A, ≥p i, where: (ii) T ∪ H 6|= ⊥ (consistency), and (iii) H is a set of instances of literals from A (bias). S = {a0 , . . . , an−1 } is a set of agents. Each agent ai has • In this case, H is also called an explanation of O (with respects its own individual theory Ti and its own observations Oi . to T and A). A hypothesis is minimal if no proposer subset It will also form its own preferred hypothesis Hi , though of H satisfies the above three conditions (which is equivalent it can also adopt it from other agents. In fact, in the end to subsumption minimality for ground clauses). A hypothesis of the process, all agents will share the same hypothesis. is ground if it is a set of ground literals (literals containing no • Γt = hS, Et i is the communicational constraint graph variable). This restriction is often employed in applications at time t, an undirected unlabeled graph whose nodes whose observations are also given as ground literals. In are the agents in S and whose edges Et represent the the following, we shall indeed assume that observations are communicational links between the agent. An agent ai grounded, and that we are only searching for minimal ground can only communicate with another agent aj at time t if hypotheses. (ai , aj ) ∈ Et . • A is the common set of abducibles that represents the C. Computation through hypothesis finding langage bias of the abductive process. Given the observations O, each hypothesis H of O can • ≥p is the common preference relation, a total order over be computed by the principle of inverse intailment [8], [9], hypotheses. 1 meaning that µX represents the clauses of X that are not properly Theories and observations are considered to be certain subsumed by any other clause of X. knowledge. As such, they are assumed to be consistent, 35 S S meaning that i