Hypotheses Refinement under Topological Communication Constraints ∗ Gauvain Bourgne, Gael Hette, Nicolas Maudet, and Suzanne Pinson LAMSADE, Univ. Paris-Dauphine, France {bourgne,hette,maudet,pinson}@lamsade.dauphine.fr ABSTRACT We investigate the properties of a multiagent system where each (distributed) agent locally perceives its environment. Upon perception of an unexpected event, each agent locally computes its favoured hypothesis and tries to propagate it to other agents, by exchanging hypotheses and supporting arguments (observations). However, we further assume that communication opportunities are severely constrained and change dynamically. In this paper, we mostly investigate the convergence of such systems towards global consistency. We first show that (for a wide class of protocols that we shall define), the communication constraints induced by the topology will not prevent the convergence of the system, at the condition that the system dynamics guarantees that no agent will ever be isolated forever, and that agents have unlimited time for computation and arguments exchange. As this assumption cannot be made in most situations though, we then set up an experimental framework aiming at comparing the relative efficiency and effectiveness of different interaction protocols for hypotheses exchange. We study a critical situation involving a number of agents aiming at escaping from a burning building. The results reported here provide some insights regarding the design of optimal protocol for hypotheses refinement in this context. Categories and Subject Descriptors I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence-Multiagent systems General Terms Theory, Experimentation 1. INTRODUCTION We consider a multiagent system where each (distributed) agent locally perceives its environment, and we assume that some unexpected event occurs in that system. If each agent computes only locally its favoured hypothesis, it is only natural to assume that agents will seek to coordinate and refine their hypotheses by confronting their observations with other agents. If, in addition, the communication opportunities are severely constrained (for instance, agents can only communicate when they are close enough to some other agent), and dynamically changing (for instance, agents may change their locations), it becomes crucial to carefully design protocols that will allow agents to converge to some desired state of global consistency. In this paper we exhibit some sufficient conditions on the system dynamics and on the protocol/strategy structures that allow to guarantee that property, and we experimentally study some contexts where (some of) these assumptions are relaxed. While problems of diagnosis are among the venerable classics in the AI tradition, their multiagent counterparts have much more recently attracted some attention. Roos and colleagues [8, 9] in particular study a situation where a number of distributed entities try to come up with a satisfying global diagnosis of the whole system. They show in particular that the number of messages required to establish this global diagnosis is bound to be prohibitive, unless the communication is enhanced with some suitable protocol. However, they do not put any restrictions on agents" communication options, and do not assume either that the system is dynamic. The benefits of enhancing communication with supporting information to make convergence to a desired global state of a system more efficient has often been put forward in the literature. This is for instance one of the main idea underlying the argumentation-based negotiation approach [7], where the desired state is a compromise between agents with conflicting preferences. Many of these works however make the assumption that this approach is beneficial to start with, and study the technical facets of the problem (or instead emphasize other advantages of using argumentation). Notable exceptions are the works of [3, 4, 2, 5], which studied in contexts different from ours the efficiency of argumentation. The rest of the paper is as follows. Section 2 specifies the basic elements of our model, and Section 3 goes on to presenting the different protocols and strategies used by the agents to exchange hypotheses and observations. We put special attention at clearly emphasizing the conditions on the system dynamics and protocols/strategies that will be exploited in the rest of the paper. Section 4 details one of 998 978-81-904262-7-5 (RPS) c 2007 IFAAMAS the main results of the paper, namely the fact that under the aforementioned conditions, the constraints that we put on the topology will not prevent the convergence of the system towards global consistency, at the condition that no agent ever gets completely lost forever in the system, and that unlimited time is allowed for computation and argument exchange. While the conditions on protocols and strategies are fairly mild, it is also clear that these system requirements look much more problematic, even frankly unrealistic in critical situations where distributed approaches are precisely advocated. To get a clearer picture of the situation induced when time is a critical factor, we have set up an experimental framework that we introduce and discuss in Section 5. The critical situation involves a number of agents aiming at escaping from a burning building. The results reported here show that the effectiveness of argument exchange crucially depends upon the nature of the building, and provide some insights regarding the design of optimal protocol for hypotheses refinement in this context. 2. BASIC NOTIONS We start by defining the basic elements of our system. Environment Let O be the (potentially infinite) set of possible observations. We assume the sensors of our agents to be perfect, hence the observations to be certain. Let H be the set of hypotheses, uncertain and revisable. Let Cons(h, O) be the consistency relation, a binary relation between a hypothesis h ∈ H and a set of observations O ⊆ O. In most cases, Cons will refer to classical consistency relation, however, we may overload its meaning and add some additional properties to that relation (in which case we will mention it). The environment may include some dynamics, and change over the course of time. We define below sequences of time points to deal with it: Definition 1 (Sequence of time points). A sequence of time points t1, t2, . . . , tn from t is an ordered set of time points t1, t2, . . . , tn such that t1 ≥ t and ∀i ∈ [1, n − 1], ti+1 ≥ ti. Agent We take a system populated by n agents a1, . . . , an. Each agent is defined as a tuple F, Oi, hi , where: • F, the set of facts, common knowledge to all agents. • Oi ∈ 2O , the set of observations made by the agent so far. We assume a perfect memory, hence this set grows monotonically. • hi ∈ H, the favourite hypothesis of the agent. A key notion governing the formation of hypotheses is that of consistency, defined below: Definition 2 (Consistency). We say that: • An agent is consistent (Cons(ai)) iff Cons(hi, Oi) (that is, its hypothesis is consistent with its observation set). • An agent ai consistent with a partner agent aj iff Cons(ai) and Cons(hi, Oj) (that is, this agent is consistent and its hypothesis can explain the observation set of the other agent). • Two agents ai and aj are mutually consistent (MCons(ai, aj)) iff Cons(ai, aj) and Cons(aj, ai). • A system is consistent iff ∀(i, j)∈[1, n]2 it is the case that MCons(ai, aj). To ensure its consistency, each agent is equipped with an abstract reasoning machinery that we shall call the explanation function Eh. This (deterministic) function takes a set of observation and returns a single prefered hypothesis (2O → H). We assume h = Eh(O) to be consistent with O by definition of Eh, so using this function on its observation set to determine its favourite hypothesis is a sure way for the agent to achieve consistency. Note however that an hypothesis does not need to be generated by Eh to be consistent with an observation set. As a concrete example of such a function, and one of the main inspiration of this work, one can cite the Theorist reasoning system [6] -as long as it is coupled with a filter selecting a single prefered theory among the ones initially selected by Theorist. Note also that hi may only be modified as a consequence of the application Eh. We refer to this as the autonomy of the agent: no other agent can directly impose a given hypothesis to an agent. As a consequence, only a new observation (being it a new perception, or an observation communicated by a fellow agent) can result in a modification of its prefered hypothesis hi (but not necessarily of course). We finally define a property of the system that we shall use in the rest of the paper: Definition 3 (Bounded Perceptions). A system involves a bounded perception for agents iff ∃n0 s.t. ∀t| ∪N i=1 Oi| ≤ n0. (That is, the number of observations to be made by the agents in the system is not infinite.) Agent Cycle Now we need to see how these agents will evolve and interact in their environment. In our context, agents evolve in a dynamic environment, and we classicaly assume the following system cycle: 1. Environment dynamics: the environment evolves according to the defined rules of the system dynamics. 2. Perception step : agents get perceptions from the environment. These perceptions are typically partial (e.g. the agent can only see a portion of a map). 3. Reasoning step: agents compare perception with predictions, seek explanations for (potential) difference(s), refine their hypothesis, draw new conclusions. 4. Communication step: agents can communicate hypotheses and observations with other agents through a defined protocol. Any agent can only be involved in one communication with another agent by step. 5. Action step: agents do some practical reasoning using the models obtained from the previous steps and select an action. They can then modify the environment by executing it. The communication of the agents will be further constrained by topological consideration. At a given time, an agent will only be able to communicate with a number of neighbours. Its connexions with these others agents may The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 999 evolve with its situation in the environment. Typically, an agent can only communicate with agents that it can sense, but one could imagine evolving topological constraints on communication based on a network of communications between agents where the links are not always active. Communication In our system, agents will be able to communicate with each other. However, due to the aforementionned topological constraints, they will not be able to communicate with any agents at anytime. Who an agent can communicate with will be defined dynamically (for instance, this can be a consequence of the agents being close enough to get in touch). We will abstractly denote by C(ai, aj, t) the communication property, in other words, the fact that agents ai and aj can communicate at time t (note that this relation is assumed to be symetric, but of course not transitive). We are now in a position to define two essential properties of our system. Definition 4 (Temporal Path). There exists a temporal communication path at horizon tf (noted Ltf (aI , aJ )) between ai and aj iff there exists a sequence of time points t1, t2, . . . , tn from tf and a sequence of agents k1, k2, . . . , kn s.t. (i) C(aI , ak1 , t1), (ii) C(akn , aJ , tn+1), (iii) ∀i ∈ [1, n], C(aki , aki+1 , ti) Intuitively, what this property says is that it is possible to find a temporal path in the future that would allow to link agent ai and aj via a sequence of intermediary agents. Note that the time points are not necessarily successive, and that the sequence of agents may involve the same agents several times. Definition 5 (Temporal Connexity). A system is temporaly connex iff ∀t ∀(i, j)∈[1, n]2 Lt(ai, aj) In short, a temporaly connex system guarantees that any agent will be able to communicate with any other agents, no matter how long it might take to do so, at any time. To put it another way, it is never the case that an agent will be isolated for ever from another agent of the system. We will next discuss the detail of how communication concretely takes place in our system. Remember that in this paper, we only consider the case of bilateral exchanges (an agent can only speak to a single other agent), and that we also assume that any agent can only engage in a single exchange in a given round. 3. PROTOCOLS AND STRATEGIES In this section, we discuss the requirements of the interaction protocols that govern the exchange of messages between agents, and provide some example instantiation of such protocols. To clarify the presentation, we distinguish two levels: the local level, which is concerned with the regulation of bilateral exchanges; and the global level,which essentially regulates the way agents can actually engage into a conversation. At each level, we separate what is specified by the protocol, and what is left to agents" strategies. Local Protocol and Strategies We start by inspecting local protocols and strategies that will regulate the communication between the agents of the system. As we limit ourselves to bilateral communication, these protocols will simply involve two agents. Such protocol will have to meet one basic requirement to be satisfying. • consistency (CONS)- a local protocol has to guarantee the mutual consistency of agents upon termination (which implies termination of course). Figure 1: A Hypotheses Exchange Protocol [1] One example such protocol is the protocol described in [1] that is pictured in Fig. 1. To further illustrate how such protocol can be used by agents, we give some details on a possible strategy: upon receiving a hypothesis h1 (propose(h1) or counterpropose(h1)) from a1, agent a2 is in state 2 and has the following possible replies: counterexample (if the agent knows an example contradicting the hypothesis, or not explained by this hypothesis), challenge (if the agents lacks evidence to accept this hypothesis), counterpropose (if the agent agrees with the hypothesis but prefers another one), or accept (if it is indeed as good as its favourite hypothesis). This strategy guarantees, among other properties, the eventual mutual logical consistency of the involved agents [1]. Global Protocol The global protocol regulates the way bilateral exchanges will be initiated between agents. At each turn, agents will concurrently send one weighted request to communicate to other agents. This weight is a value measuring the agent"s willingness to converse with the targeted agent (in practice, this can be based on different heuristics, but we shall make some assumptions on agents" strategies, see below). Sending such a request is a kind of conditional commitment for the agent. An agent sending a weighted request commits to engage in conversation with the target if he does not receive and accept himself another request. Once all request have been received, each agent replies with either an acccept or a reject. By answering with an accept, an agent makes a full commitment to engage in conversation with the sender. Therefore, it can only send one accept in a given round, as an agent can only participate in one conversation per time step. When all response have been received, each agent receiving an accept can either initiate a conversation using the local protocol or send a cancel if it has accepted another request. At the end of all the bilateral exchanges, the agents engaged in conversation are discarded from the protocol. Then each of the remaining agents resends a request and the process iterates until no more requests are sent. Global Strategy We now define four requirements for the strategies used by agents, depending on their role in the protocol: two are concerned with the requestee role (how to decide who the 1000 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) agent wishes to communicate with?), the other two with the responder role (how to decide which communication request to accept or not?). • Willingness to solve inconsistancies (SOLVE)-agents want to communicate with any other agents unless they know they are mutually consistent. • Focus on solving inconsistencies (FOCUS)-agents do not request communication with an agent with whom they know they are mutually consistent. • Willingness to communicate (COMM)-agents cannot refuse a weighted communication request, unless they have just received or send a request with a greater weight. • Commitment to communication request (REQU)agents cannot accept a weighted communication request if they have themselves sent a communication request with a greater weight. Therefore, they will not cancel their request unless they have received a communicational request with greater weight. Now the protocol structure, together with the properties COMM+REQU, ensure that a request can only be rejected if its target agent engages in communication with another agent. Suppose indeed that agent ai wants to communicate with aj by sending a request with weight w. COMM guarantees that an agent receiving a weighted request will either accept this communication, accept a communication with a greater weight or wait for the answer to a request with a greater weight. This ensures that the request with maximal weight will be accepted and not cancelled (as REQU ensures that an agent sending a request can only cancel it if he accepts another request with greater weight). Therefore at least two agents will engage in conversation per round of the global protocol. As the protocol ensures that ai can resend its request while aj is not engaged in a conversation, there will be a turn in which aj must engage in a conversation, either with ai or another agent. These requirements concern request sending and acceptation, but agents also need some strategy of weight attribution. We describe below an altruist strategy, used in our experiments. Being cooperative, an agent may want to know more of the communication wishes of other agents in order to improve the overall allocation of exchanges to agents. A context request step is then added to the global protocol. Before sending their chosen weighted request, agents attribute a weight to all agents they are prepared to communicate with, according to some internal factors. In the simplest case, this weight will be 1 for all agent with whom the agent is not sure of being mutually consistent (ensuring SOLVE), other agent being not considered for communication (ensuring FOCUS). The agent then sends a context request to all agents with whom communication is considered. This request also provides information about the sender (list of considered communications along with their weight). After reception of all the context requests, agents will either reply with a deny, iff they are already engaged in a conversation (in which case, the requesting agent will not consider communication with them anymore in this turn), or an inform giving the requester information about the requests it has sent and received. When all replies have been received, each agent can calculate the weight of all requests concerning it. It does so by substracting from the weight of its request the weight of all requests concerning either it or its target (that is, the final weight of the request from ai to aj is Wi,j = wi,j +wj,i − ( P k∈R(i)−{j} wi,k + P k∈S(i)−{j} wk,i + P k∈R(j)−{i} wj,k + P k∈S(j)−{i} wk,j) where wi,j is the weight of the request of ai to aj, R(i) is the set of indice of agents having received a request from ai and S(i) is the set of indice of agents having send a request to ai). It then finally sends a weighted request to the agents who maximise this weight (or wait for a request) as described in the global protocol. 4. (CONDITIONAL) CONVERGENCE TO GLOBAL CONSISTENCY In this section we will show that the requirements regarding protocols and strategies just discussed will be sufficient to ensure that the system will eventually converge towards global consistency, under some conditions. We first show that, if two agents are not mutually consistent at some time, then there will be necessarily a time in the future such that an agent will learn a new observation, being it because it is new for the system, or by learning it from another agent. Lemma 1. Let S be a system populated by n agents a1, a2, ..., an, temporaly connex, and involving bounded perceptions for these agents. Let n1 be the sum of cardinalities of the intersection of pairwise observation sets. (n1 = P (i,j)∈[1,n]2 |Oi ∩ Oj|) Let n2 be the cardinality of the union of all agents" observations sets. (n2 = | ∪N i=1 Oi|). If ¬MCons(ai, aj) at time t0, there is necessarily a time t > t0 s.t. either n1 or n2 will increase. Proof. Suppose that there exist a time t0 and indices (i, j) s.t. ¬MCons(ai, aj). We will use mt0 = P (k,l)∈[1,n]2 εComm(ak, al, t0) where εComm(ak, al, t0) = 1 if ak and al have communicated at least once since t0, and 0 otherwise. Temporal connexity guarantees that there exist t1, ..., tm+1 and k1, ..., km s.t. C(ai, ak1 , t1), C(akm , aj, tm+1), and ∀p ∈ [1, m], C(akp , akp+1 , tp). Clearly, if MCons(ai, ak1 ), MCons(akm , aj) and ∀p, MCons(akp , akp+1 ), we have MCons(ai, aj) which contradicts our hypothesis (MCons being transitive, MCons(ai, ak1 )∧MCons(ak1 , ak2 ) implies that MCons(ai, ak2 ) and so on till MCons(ai, akm )∧ MCons(akm , aj) which implies MCons(ai, aj) ). At least two agents are then necessarily inconsistent (¬MCons(ai, ak1 ), or ¬MCons(akm , aj), or ∃p0 t.q. ¬MCons(akp0 , akp0+1 )). Let ak and al be these two neighbours at a time t > t0 1 . The SOLVE property ensures that either ak or al will send a communication request to the other agent at time t . As shown before, this in turn ensures that at least one of these agents will be involved in a communication. Then there are two possibilities: (case i) ak and al communicate at time t . In this case, we know that ¬MCons(ak, al). This and the CONS property ensures that at least one of the agents must change its 1 Strictly speaking, the transitivity of MCons only ensure that ak and al are inconsistent at a time t ≥ t0 that can be different from the time t at which they can communicate. But if they become consistent between t and t (or inconsistent between t and t ), it means that at least one of them have changed its hypothesis between t and t , that is, after t0. We can then apply the reasoning of case iib. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1001 hypothesis, which in turn, since agents are autonomous, implies at least one exchange of observation. But then |Ok ∩Ol| is bound to increase: n1(t ) > n1(t0). (case ii) ak communicates with ap at time t . We then have again two possibilities: (case iia) ak and ap did not communicate since t0. But then εComm(ak, ap, t0) had value 0 and takes value 1. Hence mt0 increases. (case iib) ak and ap did communicate at some time t0 > t0. The CONS property of the protocol ensures that MCons(ak, ap) at that time. Now the fact that they communicate and FOCUS implies that at least one of them did change its hypothesis in the meantime. The fact that agents are autonomous implies in turn that a new observation (perceived or received from another agent) necessarily provoked this change. The latter case would ensure the existence of a time t > t0 and an agent aq s.t. either |Op ∩Oq| or |Ok ∩Oq| increases of 1 at that time (implying n1(t ) > n1(t0)). The former case means that the agent gets a new perception o at time t . If that observation was unknown in the system before, then n2(t ) > n2(t0). If some agent aq already knew this observation before, then either Op ∩ Oq or Ok ∩ Oq increases of 1 at time t (which implies that n1(t ) > n1(t0)). Hence, ¬MCons(ai, aj) at time t0 guarantees that, either: −∃t > t0 t.q. n1(t ) > n1(t0); or −∃t > t0 t.q. n2(t ) > n2(t0); or −∃t > t0 t.q. mt0 increases of 1 at time t . By iterating the reasoning with t (but keeping t0 as the time reference for mt0 ), we can eliminate the third case (mt0 is integer and bounded by n2 , which means that after a maximum of n2 iterations, we necessarily will be in one of two other cases.) As a result, we have proven that if ¬MCons(ai, aj) at time t0, there is necessarily a time t s.t. either n1 or n2 will increase. Theorem 1 (Global consistency). Let S be a system populated by n agents a1, a2, ..., an, temporaly connex, and involving bounded perceptions for these agents. Let Cons(ai, aj) be a transitive consistency property. Then any protocol and strategies satisfying properties CONS, SOLVE, FOCUS, COMM and REQU guarantees that the system will converge towards global consistency. Proof. For the sake of contradiction, let us assume ∃I, J ∈ [1, N] s.t. ∀t, ∃t0 > t, t.q. ¬Cons(aI , aJ , t0). Using the lemma, this implies that ∃t > t0 s.t. either n1(t ) > n1(t0) or n2(t ) > n2(t0). But we can apply the same reasoning taking t = t , which would give us t1 > t > t0 s.t. ¬Cons(aI , aJ , t1), which gives us t > t1 s.t. either n1(t ) > n1(t1) or n2(t ) > n2(t1). By successive iterations we can then construct a sequence t0, t1, ..., tn, which can be divided in two sub-sequences t0, t1, ...tn and t0 , t1 , ..., tn s.t. n1(t0) < n1(t1) < ... < n1(tn) and n2(t0 ) < n2(t1 ) < ... < n2(tn). One of these sub-sequences has to be infinite. However, n1(ti) and n2(ti ) are strictly growing, integer, and bounded, which implies that both are finite. Contradiction. What the previous result essentially shows is that, in a system where no agent will be isolated from the rest of the agents for ever, only very mild assumptions on the protocols and strategies used by agents suffice to guarantee convergence towards system consistency in a finite amount of time (although it might take very long). Unfortunately, in many critical situations, it will not be possible to assume this temporal connexity. As distributed approaches as the one advocated in this paper are precisely often presented as a good way to tackle problems of reliability or problems of dependence to a center that are of utmost importance in these critical applications, it is certainly interesting to further explore how such a system would behave when we relax this assumption. 5. EXPERIMENTAL STUDY This experiment involves agents trying to escape from a burning building. The environment is described as a spatial grid with a set of walls and (thankfully) some exits. Time and space are considered discrete. Time is divided in rounds. Agents are localised by their position on the spatial grid. These agents can move and communicate with other agents. In a round, an agent can move of one cell in any of the four cardinal directions, provided it is not blocked by a wall. In this application, agents communicate with any other agent (but, recall, a single one) given that this agent is in view, and that they have not yet exchanged their current favoured hypothesis. Suddenly, a fire erupts in these premises. From this moment, the fire propagates. Each round, for each cases where there is fire, the fire propagates in the four directions. However, the fire cannot propagate through a wall. If the fire propagates in a case where an agent is positioned, that agent burns and is considered dead. It can of course no longer move nor communicate. If an agent gets to an exit, it is considered saved, and can no longer be burned. Agents know the environment and the rules governing the dynamics of this environment, that is, they know the map as well as the rules of fire propagation previously described. They also locally perceive this environment, but cannot see further than 3 cases away, in any direction. Walls also block the line of view, preventing agents from seeing behind them. Within their sight, they can see other agents and whether or not the cases they see are on fire. All these perceptions are memorised. We now show how this instantiates the abstract framework presented the paper. • O = {Fire(x, y, t), NoFire(x, y, t), Agent(ai, x, y, t)} Observations can then be positive (o ∈ P(O) iff ∃h ∈ H s.t. h |= o) or negative (o ∈ N(O) iff ∃h ∈ H s.t. h |= ¬o). • H={FireOrigin(x1, y1, t1)∧...∧FireOrigin(xl, yl, tl)} Hypotheses are conjunctions of FireOrigins. • Cons(h, O) consistency relation satisfies: - coherence : ∀o ∈ N(O), h |= ¬o. - completeness : ∀o ∈ P(O), h |= o. - minimality : For all h ∈ H, if h is coherent and complete for O, then h is prefered to h according to the preference relation (h ≤p h ).2 2 Selects first the minimal number of origins, then the most recent (least preemptive strategy [6]), then uses some arbitrary fixed ranking to discriminate ex-aequo. The resulting relation is a total order, hence minimality implies that there will be a single h s.t.Cons(O, h) for a given O. This in turn means that MCons(ai, aj) iff Cons(ai), Cons(aj), and hi = hj. This relation is then transitive and symmetric. 1002 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) • Eh takes O as argument and returns min≤p of the coherent and complete hypothesis for O 5.1 Experimental Evaluation We will classically (see e.g. [3, 4]) assess the effectiveness and efficiency of different interaction protocols. Effectiveness of a protocol The proportion of agents surviving the fire over the initial number of agents involved in the experiment will determine the effectiveness of a given protocol. If this value is high, the protocol has been effective to propagate the information and/or for the agents to refine their hypotheses and determine the best way to the exit. Efficiency of a protocol Typically, the use of supporting information will involve a communication overhead. We will assume here that the efficiency of a given protocol is characterised by the data flow induced by this protocol. In this paper we will only discuss this aspect wrt. local protocols. The main measure that we shall then use here is the mean total size of messages that are exchanged by agents per exchange (hence taking into account both the number of messages and the actual size of the messages, because it could be that messages happen to be very big, containing e.g. a large number of observations, which could counter-balance a low number of messages). 5.2 Experimental Settings The chosen experimental settings are the following: • Environmental topology- Performances of information propagation are highly constrained by the environment topology. The perception skills of the agents depend on the openness of the environment. With a large number of walls the perceptions of agents are limited, and also the number of possible inter-agent communications, whereas an open environment will provide optimal possibilities of perception and information propagation. Thus, we propose a topological index (see below) as a common basis to charaterize the environments (maps) used during experimentations. The topological index (TI) is the ratio of the number of cells that can be perceived by agents summed up from all possible positions, divided by the number of cells that would be perceived from the same positions but without any walls. (The closer to 1, the more open the environment). We shall also use two additional, more classical [10], measures: the characteristic path length3 (CPL) and the clustering coefficient4 (CC). • Number of agents- The propagation of information also depends on the initial number of agents involved during an experimentation. For instance, the more agents, the more potential communications there is. This means that there will be more potential for propagation, but also that the bilateral exchange restriction will be more crucial. 3 The CPL is the median of the means of the shortest path lengths connecting each node to all other nodes. 4 characterising the isolation degree of a region of an environment in terms of acessibility (number of roads still usable to reach this region). Map T.I. (%) C.P.L. C.C. 69-1 69,23 4,5 0,69 69-2 68,88 4,38 0,65 69-3 69,80 4,25 0,67 53-1 53,19 5,6 0,59 53-2 53,53 6,38 0,54 53-3 53,92 6,08 0,61 38-1 38,56 8,19 0,50 38-2 38,56 7,3 0,50 38-3 38,23 8,13 0,50 Table 1: Topological Characteristics of the Maps • Initial positions of the agents- Initial positions of the agents have a significant influence on the overall behavior of an instance of our system: being close from an exit will (in general) ease the escape. 5.3 Experimental environments We choose to realize experiments on three very different topological indexes (69% for open environments, 53% for mixed environments, and 38% for labyrinth-like environments). Figure 2: Two maps (left: TI=69%, right TI=38%) We designed three different maps for each index (Fig. 2 shows two of them), containing the same maximum number of agents (36 agents max.) with a maximum density of one agent per cell, the same number of exits and a similar fire origin (e.g. starting time and position). The three differents maps of a given index are designed as follows. The first map is a model of an existing building floor. The second map has the same enclosure, exits and fire origin as the first one, but the number and location of walls are different (wall locations are designed by an heuristic which randomly creates walls on the spatial grid such that no fully closed rooms are created and that no exit is closed). The third map is characterised by geometrical enclosure in wich walls location is also designed with the aforementioned heuristic. Table 1 summarizes the different topological measures characterizing these different maps. It is worth pointing out that the values confirm the relevance of TI (maps with a high TI have a low CPL and a high CC. However the CPL and CC allows to further refine the difference between the maps, e.g. between 53-1 and 53-2). 5.4 Experimental Results For each triple of maps defined as above we conduct the same experiments. In each experiment, the society differs in terms of its initial proportion of involved agents, from 1% to 100%. This initial proportion represents the percentage of involved agents with regards to the possible maximum number of agents. For each map and each initial proportion, The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1003 we select randomly 100 different initial agents" locations. For each of those different locations we execute the system one time for each different interaction protocol. Effectiveness of Communication and Argumentation The first experiment that we set up aims at testing how effective is hypotheses exchange (HE), and in particular how the topological aspects will affect this effectiveness. In order to do so, we have computed the ratio of improvement offered by that protocol over a situation where agents could simply not communicate (no comm). To get further insights as to what extent the hypotheses exchange was really crucial, we also tested a much less elaborated protocol consisting of mere observation exchanges (OE). More precisely, this protocol requires that each agent stores any unexpected observation that it perceives, and agents simply exchange their respective lists of observations when they discuss. In this case, the local protocol is different (note in particular that it does not guarantee mutual consistency), but the global protocol remains the same (at the only exception that agents" motivation to communicate is to synchronise their list of observations, not their hypothesis). If this protocol is at best as effective as HE, it has the advantage of being more efficient (this is obvious wrt the number of messages which will be limited to 2, less straightforward as far as the size of messages is concerned, but the rough observation that the exchange of observations can be viewed as a flat version of the challenge is helpful to see this). The results of these experiments are reported in Fig. 3. Figure 3: Comparative effectiveness ratio gain of protocols when the proportion of agents augments The first observation that needs to be made is that communication improves the effectiveness of the process, and this ratio increases as the number of agents grows in the system. The second lesson that we learn here is that closeness relatively makes communication more effective over non communication. Maps exhibiting a T.I. of 38% are constantly above the two others, and 53% are still slightly but significantly better than 69%. However, these curves also suggest, perhaps surprisingly, that HE outperforms OE in precisely those situations where the ratio gain is less important (the only noticeable difference occurs for rather open maps where T.I. is 69%). This may be explained as follows: when a map is open, agents have many potential explanation candidates, and argumentation becomes useful to discriminate between those. When a map is labyrinth-like, there are fewer possible explanations to an unexpected event. Importance of the Global Protocol The second set of experiments seeks to evaluate the importance of the design of the global protocol. We tested our protocol against a local broadcast (LB) protocol. Local broadcast means that all the neighbours agents perceived by an agent will be involved in a communication with that agent in a given round -we alleviate the constraint of a single communication by agent. This gives us a rough upper bound upon the possible ratio gain in the system (for a given local protocol). Again, we evaluated the ratio gain induced by that LB over our classical HE, for the three different classes of maps. The results are reported in Fig. 4. Figure 4: Ratio gain of local broadcast over hypotheses exchange Note to begin with that the ratio gain is 0 when the proportion of agents is 5%, which is easily explained by the fact that it corresponds to situations involving only two agents. We first observe that all classes of maps witness a ratio gain increasing when the proportion of agents augments: the gain reaches 10 to 20%, depending on the class of maps considered. If one compares this with the improvement reported in the previous experiment, it appears to be of the same magnitude. This illustrates that the design of the global protocol cannot be ignored, especially when the proportion of agents is high. However, we also note that the effectiveness ratio gain curves have very different shapes in both cases: the gain induced by the accuracy of the local protocol increases very quickly with the proportion of agents, while the curve is really smooth for the global one. Now let us observe more carefully the results reported here: the curve corresponding to a TI of 53% is above that corresponding to 38%. This is so because the more open a map, the more opportunities to communicate with more than one agent (and hence benefits from broadcast). However, we also observe that curve for 69% is below that for 53%. This is explained as follows: in the case of 69%, the potential gain to be made in terms of surviving agents is much lower, because our protocols already give rather efficient outcomes anyway (quickly reaching 90%, see Fig. 3). A simple rule of thumb could be that when the number of agents is small, special attention should be put on the local 1004 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) protocol, whereas when that number is large, one should carefully design the global one (unless the map is so open that the protocol is already almost optimally efficient). Efficiency of the Protocols The final experiment reported here is concerned with the analysis of the efficiency of the protocols. We analysis here the mean size of the totality of the messages that are exchanged by agents (mean size of exchanges, for short) using the following protocols: HE, OE, and two variant protocols. The first one is an intermediary restricted hypotheses exchange protocol (RHE). RHE is as follows: it does not involve any challenge nor counter-propose, which means that agents cannot switch their role during the protocol (this differs from RE in that respect). In short, RHE allows an agent to exhaust its partner"s criticism, and eventually this partner will come to adopt the agent"s hypothesis. Note that this means that the autonomy of the agent is not preserved here (as an agent will essentially accept any hypothesis it cannot undermine), with the hope that the gain in efficiency will be significant enough to compensate a loss in effectiveness. The second variant protocol is a complete observation exchange protocol (COE). COE uses the same principles as OE, but includes in addition all critical negative examples (nofire) in the exchange (thus giving all examples used as arguments by the hypotheses exchanges protocol), hence improving effectiveness. Results for map 69-1 are shown on Fig. 5. Figure 5: Mean size of exchanges First we can observe the fact that the ordering of the protocols, from the least efficient to the most efficient, is COE, HE, RHE and then OE. HE being more efficient than COE proves that the argumentation process gains efficiency by selecting when it is needed to provide negative example, which have less impact that positive ones in our specific testbed. However, by communicating hypotheses before eventually giving observation to support it (HE) instead of directly giving the most crucial observations (OE), the argumentation process doubles the size of data exchanges. It is the cost for ensuring consistency at the end of the exchange (a property that OE does not support). Also significant is the fact the the mean size of exchanges is slightly higher when the number of agents is small. This is explained by the fact that in these cases only a very few agents have relevant informations in their possession, and that they will need to communicate a lot in order to come up with a common view of the situation. When the number of agents increases, this knowledge is distributed over more agents which need shorter discussions to get to mutual consistency. As a consequence, the relative gain in efficiency of using RHE appears to be better when the number of agents is small: when it is high, they will hardly argue anyway. Finally, it is worth noticing that the standard deviation for these experiments is rather high, which means that the conversation do not converge to any stereotypic pattern. 6. CONCLUSION This paper has investigated the properties of a multiagent system where each (distributed) agent locally perceives its environment, and tries to reach consistency with other agents despite severe communication restrictions. In particular we have exhibited conditions allowing convergence, and experimentally investigated a typical situation where those conditions cannot hold. There are many possible extensions to this work, the first being to further investigate the properties of different global protocols belonging to the class we identified, and their influence on the outcome. There are in particular many heuristics, highly dependent on the context of the study, that could intuitively yield interesting results (in our study, selecting the recipient on the basis of what can be inferred from his observed actions could be such a heuristic). One obvious candidate for longer term issues concern the relaxation of the assumption of perfect sensing. 7. REFERENCES [1] G. Bourgne, N. Maudet, and S. Pinson. When agents communicate hypotheses in critical situations. In Proceedings of DALT-2006, May 2006. [2] P. Harvey, C. F. Chang, and A. Ghose. Support-based distributed search: a new approach for multiagent constraint processing. In Proceedings of AAMAS06, 2006. [3] H. Jung and M. Tambe. Argumentation as distributed constraint satisfaction: Applications and results. In Proceedings of AGENTS01, 2001. [4] N. C. Karunatillake and N. R. Jennings. Is it worth arguing? In Proceedings of ArgMAS 2004, 2004. [5] S. Onta˜n´on and E. Plaza. Arguments and counterexamples in case-based joint deliberation. In Proceedings of ArgMAS-2006, May 2006. [6] D. Poole. Explanation and prediction: An architecture for default and abductive reasoning. Computational Intelligence, 5(2):97-110, 1989. [7] I. Rahwan, S. D. Ramchurn, N. R. Jennings, P. McBurney, S. Parsons, and L. Sonenberg. Argumention-based negotiation. The Knowledge Engineering Review, 4(18):345-375, 2003. [8] N. Roos, A. ten Tije, and C. Witteveen. A protocol for multi-agent diagnosis with spatially distributed knowledge. In Proceedings of AAMAS03, 2003. [9] N. Roos, A. ten Tije, and C. Witteveen. Reaching diagnostic agreement in multiagent diagnosis. In Proceedings of AAMAS04, 2004. [10] T. Takahashi, Y. Kaneda, and N. Ito. Preliminary study - using robocuprescue simulations for disasters prevention. In Proceedings of SRMED2004, 2004. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1005
multiagent system favoured hypothesis global consistency consistency observation set bounded perception temporal path bilateral exchange context request step
sequence of time point time point sequence topological constraint hypothesis exchange protocol mutual consistency inter-agent communication negotiation and argumentation agent communication language and protocol