Agent-organized networks for dynamic team formation

ABSTRACT

Many multi-agent systems consist of a complex network of autonomous yet interdependent agents. Examples of such networked multi-agent systems include supply chains and sensor networks. In these systems, agents have a select set of other agents with whom they interact based on environmental knowledge, cognitive capabilities, resource limitations, and communications constraints. Previous findings have demonstrated that the structure of the artificial social network governing the agent interactions is strongly correlated with organizational performance. As multi-agent systems are typically embedded in dynamic environments, we wish to develop distributed, on-line network adaptation mechanisms for discovering effective network structures. Therefore, within the context of dynamic team formation, we propose several strategies for agent-organized networks (AONs) and evaluate their effectiveness for increasing organizational performance.

REFERENCES

• 1: Sherief Abdallah , Victor Lesser, Organization-Based Cooperative Coalition Formation, Proceedings of the Intelligent Agent Technology, IEEE/WIC/ACM International Conference on (IAT'04), p.162-168, September 20-24, 2004 [doi>10.1109/IAT.2004.87]
• 2: G. Abramson and M. Kuperman. Social games in a social network. Phys. Rev. E, 63(030901), 2001.
• 3: R. Albert and A. Barabási. Statistical mechanics of complex networks. Review of Modern Physics, 99(3):7314--7316, May 2002.
• 4: M. Anghel, Z. Toroczkai, K. Bassler, and G. Korniss. Competition-driven network dynamics: Emergence of a scale-free leadership structure and collective efficiency. Physical Review Letters, 92(5), 2004.
• 5: R. C. Arkin and J. Diaz. Line-of-sight constrained exploration for reactive multiagent robotic teams. In Proceedings of the Seventh International Workshop on Advanced Motion Control (AMC'02), 2002.
• 6: R. Arunachalam, N. Sadeh, J. Eriksson, N. Finne, and S. Janson. The supply chain management game for the Trading Agent Competition 2004. Technical Report CMU-CS-04-107, Carnegie Mellon University School of Computer Science, July 2004.
• 7: Robert Axtell, Effects of interaction topology and activation regime in several mutli-agent systems, Proceedings of the second international workshop on Multi-agent based simulation, p.33-48, January 2001, Boston, Massachusetts
• 8: David Culler , Deborah Estrin , Mani Srivastava, Guest Editors' Introduction: Overview of Sensor Networks, Computer, v.37 n.8, p.41-49, August 2004 [doi>10.1109/MC.2004.93]
• 9: J. Dall and M. Christensen. Random geometric graphs. Phys. Rev. E., 66(016121), 2002.
• 10: Jordi Delgado, Emergence of social conventions in complex networks, Artificial Intelligence, v.141 n.1, p.171-185, October 2002 [doi>10.1016/S0004-3702(02)00262-X]
• 11: Holger Ebel , Jörn Davidsen , Stefan Bornholdt, Dynamics of social networks, Complexity, v.8 n.2, p.24-27, November 2002 [doi>10.1002/cplx.10066]
• 12: M. Fox, M. Barbuceanu, and R. Teigen. Agent-oriented supply-chain management. International Journal of Flexible Manufacturing Systems, 12(2/3):165--188, 2000.
• 13: M. Gaston and M. desJardins. Team formation in complex networks. In Proceedings of the 1st NAACSOS Conference, June 2003.
• 14: M. Gaston, J. Simmons, and M. desJardins. Adapting network structures for efficient team formation. In Proceedings of AAMAS-04 Workshop on Learning and Evolution in Agent-based Systems, July 2004.
• 15: P. Holme, A. Trusina, B. J. Kim, and P. Minnhagen. Prisoners' dilemma in real-world acquaintance networks: Spikes and quasi-equilibria induced by the interplay between structure and dynamics. Phys. Rev. E, 68(030901), 2003.
• 16: Bryan Horling , Brett Benyo , Victor Lesser, Using self-diagnosis to adapt organizational structures, Proceedings of the fifth international conference on Autonomous agents, p.529-536, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376436]
• 17: A Combinatorial Auction for Collaborative Planning, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.151, July 10-12, 2000
• 18: B. Kim, A. Trusina, P. Holme, P. Minnhagen, J. Chung, and M. Choi. Dynamics instabilities induced by asymmetric influence: Prisoners' dilemma game in small-world networks. Phys. Rev. E, 66(021907), 2002.
• 19: Sarit Kraus , Onn Shehory , Gilad Taase, Coalition formation with uncertain heterogeneous information, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860577]
• 20: Pragnesh J. Modi , Hyuckchul Jung , Milind Tambe , Wei-Min Shen , Shriniwas Kulkarni, A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.685-700, November 26-December 01, 2001
• 21: R. Nair, M. Tambe, and S. Marsella. Team formation for reformation. In Proceedings of the AAAI Spring Symposium on Intelligent Distributed and Embedded Systems, 2002.
• 22: Ranjit Nair , Milind Tambe , Stacy Marsella, Role allocation and reallocation in multiagent teams: towards a practical analysis, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860664]
• 23: M. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 24: David V. Pynadath , Milind Tambe, Multiagent teamwork: analyzing the optimality and complexity of key theories and models, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544946]
• 25: F. Schweitzer and B. Tilch. Self-assembling of networks in an agent-based model. Physical Review E, 66:1--9, 2002.
• 26: B. Skyrms and R. Pemantle. A dynamic model of social network formation. Proceedings of the National Academy of Sciences USA, 97:9340--9346, 2000.
• 27: A. Szolnoki and G. Szabo. Phase transitions for rock-scissors-paper game on different networks. To appear in Phys. Rev. E, 2004.
• 28: M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research, 7:83--124, 1997.
• 29: Hari Prasad Thadakamalla , Usha Nandini Raghavan , Soundar Kumara , Albert Albert, Survivability of Multiagent-Based Supply Networks: A Topological Perspective, IEEE Intelligent Systems, v.19 n.5, p.24-31, September 2004 [doi>10.1109/MIS.2004.49]
• 30: D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 31: Pinar Yolum , Munindar P. Singh, Dynamic communities in referral networks, Web Intelligence and Agent System, v.1 n.2, p.105-116, December 2003
• 32: P. Yolum and M. P. Singh. Emergent personalized communities in referral networks. In Proceedings of the IJCAI Workshop on Intelligent Techniques for Web Personalization (ITWP), August 2003.
• 33: Bin Yu , Munindar P. Singh, Searching social networks, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860587]
• 34: B. Yu, M. Venkatraman, and M. P. Singh. An adaptive social network for information access: Architecture and experimental results. Applied Artificial Intelligence, 17(1):21--38, January 2003.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms

Keywords:
multi-agent systems, organizational learning, team formation