Analyzing the performance of randomized information sharing

ABSTRACT

In large, collaborative, heterogeneous teams, team members often collect information that is useful to other members of the team. Recognizing the utility of such information and delivering it efficiently across a team has been the focus of much research, with proposed approaches ranging from flooding to complex filters and matchmakers. Interestingly, random forwarding of information has been found to be a surprisingly effective information sharing approach in some domains. In this paper, we investigate this phenomenon in detail and show that in certain systems, random forwarding of information performs almost half as well as a globally optimal approach. We present analytic and empirical results comparing random methods with theoretically optimal sharing in small-worlds, scale-free, and random networks. In addition, we demonstrate a method for modeling real domains that allows our results to be applied toward estimating information sharing performance.

REFERENCES

• 1: N. Balakrishnan and A. C. Cohen. Order statistics and inference. Statistical Modeling and Decision Science, Boston: Academic Press, 1991.
• 2: F. Bourgault and H. Durrant-Whyte. Communication in general decentralized filter and the coordinated search strategy. In Proc. of FUSION'04, 2004.
• 3: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. In Proc. of IEEE/ACM Trans. Netw., 2006.
• 4: L. Chaimowicz and V. Kumar. Aerial shepherds: Coordination among uavs and swarms of robots. In Proc. of DARS'04, 2004.
• 5: J. L. Drury, J. Richer, N. Rackliffe, and M. A. Goodrich. Comparing situation awareness for two unmanned aerial vehicle human interface approaches. In Proc. of IEEE Int. Workshop on Safety, Security and Rescue Robotics, 2006.
• 6: Claudia V. Goldman , Shlomo Zilberstein, Optimizing information exchange in cooperative multi-agent systems, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860598]
• 7: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 8: Sven Koenig , Maxim Likhachev, D*lite, Eighteenth national conference on Artificial intelligence, p.476-483, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 9: Daniel Kuokka , Larry Harada, Matchmaking for information services, Readings in agents, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: C. C. Leary, M. Schwehm, M. Eichner, and H. P. Duerr. Tuning degree distributions of scale-free networks. Arxiv preprint physics/0602152, 2006.
• 11: Ranjit Nair , Maayan Roth , Makoto Yohoo, Communication for Improving Policy Computation in Distributed POMDPs, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1098-1105, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.88]
• 12: M. Rosencrantz, G. Gordon, and S. Thrun. Decentralized sensor fusion with distributed particle filters. In Proc. of UAI'03, 2003.
• 13: Maayan Roth , Reid Simmons , Manuela Veloso, Execution-time communication decisions for coordination of multi-agent teams, Carnegie Mellon University, Pittsburgh, PA, 2007
• 14: J. P. Royston. Algorithm as 177: Expected normal order statistics (exact and approximate). Applied Statistics, 31(2):161--165, 1982.
• 15: N. Schurr, J. Marecki, M. Tambe, P. Scerri, J. Levis, and N. Kasinadhuni. The future of disaster response: Humans working with multiagent teams using DEFACTO. In AAAI Spring Symposium on Homeland Security, 2005.
• 16: M. Tambe. Agent architectures for flexible, practical teamwork. In Proc. of AAAI'97, 1997.
• 17: P. Velagapudi, O. Prokopyev, K. Sycara, and P. Scerri. Maintaining shared belief in a large multiagent team. In Proc. of FUSION'07, 2007.
• 18: Yang Xu , Paul Scerri , Bin Yu , Steven Okamoto , Michael Lewis , Katia Sycara, An integrated token-based algorithm for scalable coordination, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082536]
• 19: Ping Xuan , Victor Lesser , Shlomo Zilberstein, Communication decisions in multi-agent cooperation: model and experiments, Proceedings of the fifth international conference on Autonomous agents, p.616-623, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376469]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Value of information

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

General Terms:
Algorithms, Performance

Keywords:
information dissemination, random walk, tokens, utility