Hypotheses refinement under topological communication constraints

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.

REFERENCES

• 1: G. Bourgne, N. Maudet, and S. Pinson. When agents communicate hypotheses in critical situations. In Proceedings of DALT-2006, May 2006.
• 2: Peter Harvey , Chee Fon Chang , Aditya Ghose, Support-based distributed search: a new approach for multiagent constraint processing, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160700]
• 3: Hyuckchul Jung , Milind Tambe , Shriniwas Kulkarni, Argumentation as distributed constraint satisfaction: applications and results, Proceedings of the fifth international conference on Autonomous agents, p.324-331, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376322]
• 4: N. C. Karunatillake and N. R. Jennings. Is it worth arguing? In Proceedings of ArgMAS 2004, 2004.
• 5: S. Ontañón 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, v.5 n.2, p.97-110, May 1989 [doi>10.1111/j.1467-8640.1989.tb00319.x]
• 7: Iyad Rahwan , Sarvapali D. Ramchurn , Nicholas R. Jennings , Peter Mcburney , Simon Parsons , Liz Sonenberg, Argumentation-based negotiation, The Knowledge Engineering Review, v.18 n.4, p.343-375, December 2003 [doi>DOI:10.1017/S0269888904000098]
• 8: Nico Roos , Annette ten Teije , Cees Witteveen, A protocol for multi-agent diagnosis with spatially distributed knowledge, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860681]
• 9: Nico Roos , Annette ten Teije , Cees Witteveen, Reaching Diagnostic Agreement in Multi-Agent Diagnosis, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1256-1257, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.222]
• 10: T. Takahashi, Y. Kaneda, and N. Ito. Preliminary study - using robocuprescue simulations for disasters prevention. In Proceedings of SRMED2004, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Experimentation, Theory

Keywords:
agent communication languages and protocols, negotiation and argumentation