×

Locality-sensitive task allocation and load balancing in networked multiagent systems: talent versus centrality. (English) Zbl 1219.68153

Summary: With the development of large scale multiagent systems, agents are always organized in network structures where each agent interacts only with its immediate neighbors in the network. Coordination among networked agents is a critical issue which mainly includes two aspects: task allocation and load balancing; in traditional approach, the resources of agents are crucial to their abilities to get tasks, which is called talent-based allocation. However, in networked multiagent systems, the tasks may spend so much communication costs among agents that are sensitive to the agent localities; thus this paper presents a novel idea for task allocation and load balancing in networked multiagent systems, which takes into account both the talents and centralities of agents. This paper first investigates the comparison between talent-based task allocation and centrality-based one; then, it explores the load balancing of such two approaches in task allocation. The experiment results show that the centrality-based method can reduce the communication costs for single task more effectively than the talent-based one, but the talent-based method can generally obtain better load balancing performance for parallel tasks than the centrality-based one.

MSC:

68T42 Agent technology and artificial intelligence
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Sherief Abdallah, Victor Lesser, Multiagent reinforcement learning and self-organization in a network of agents, in: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS07), Honolulu, Hawaii, May, 2007, pp. 172–179.
[2] Baruch Awerbuch, David Peleg, Locality-sensitive resource allocation. Technical Report CS90-27, Weizmann Institute, November 1990.
[3] Borgatti, Stephen P.: Centrality and network flow, Social networks 27, No. 1, 55-71 (2005)
[4] Chow, Ka-Po; Kwok, Yu-Kwong: On load balancing for distributed multiagent computing, IEEE transactions on parallel and distributed systems 13, No. 8, 787-801 (2002)
[5] Ka-Po Chow, Yu-Kwong Kwok, Design and evaluation of a novel communication-based approach to multi-agent load balancing, in: Proceedings of the IASTED International Conference Parallel and Distributed Computing and Systems 2000, PDCS 2000, vol. 1, Las Vegas, Nevada, USA, November 2000, pp. 329–334.
[6] Dhakal, Sagar; Hayat, Majeed M.; Pezoa, Jorge E.; Yang, Cundong; Bader, David A.: Dynamic load balancing in distributed systems in the presence of delays: a regeneration-theory approach, IEEE transactions on parallel and distributed systems 18, No. 4, 485-497 (2007)
[7] Dodds, Peter Sheridan; Watts, Duncan J.; Sabel, Charles F.: Information exchange and the robustness of organizational networks, Proceedings of the national Academy of sciences 100, No. 21, 12516-12521 (2003)
[8] Jiang, Yichuan: Extracting social laws from unilateral binary constraint relation topologies in multiagent systems, Expert systems with applications 35, No. 4, 2004-2012 (2008)
[9] Jiang, Yichuan: Concurrent collective strategy diffusion of multiagents: the spatial model and case study, IEEE transactions on systems, man and cybernetics-part C: Applications and reviews 39, No. 4, 448-458 (2009)
[10] Jiang, Yichuan; Jiang, Jiuchuan: Contextual resource negotiation-based task allocation and load balancing in complex software systems, IEEE transactions on parallel and distributed systems 20, No. 5, 641-653 (2009)
[11] Jiang, Yi-Chuan; Jiang, J. C.: A multi-agent coordination model for the variation of underlying network topology, Expert systems with applications 29, No. 2, 372-382 (2005)
[12] Jiang, Yichuan; Jiang, Jiuchuan; Ishida, Toru: Compatibility between the local and social performances of multi-agent societies, Expert systems with applications 36, No. 3-Part 1, 4443-4450 (2009)
[13] Jiani, Guo; Bhuyan, L. N.: Load balancing in a cluster-based web server for multimedia applications, IEEE transactions on parallel and distributed systems 17, No. 11, 1321-1334 (2006)
[14] Kong, Joseph S.; Sarshar, Nima; Roychowdhury, Vwani P.: Experience versus talent shapes the structure of the web, Proceedings of the national Academy of sciences 105, No. 37, 13724-13729 (2008)
[15] Lee, Jin-Shyan; Hsu, Pau-Lo: Implementation of remote hierarchical supervision system using Petri nets and agent technology, IEEE transactions on system, man and cybernetics, part C; applications and reviews 37, No. 1, 77-85 (2007)
[16] Le Quéré, Yann; Sevaux, Marc; Tahon, Christian; Trentesaux, Damien: Reactive scheduling of complex system maintenance in a cooperative environment with communication times, IEEE transactions on systems, man, and cybernetics-part C: Applications and reviews 33, No. 2, 225-234 (2003)
[17] Lin, Donghui; Sheng, Huanye; Ishida, Toru: Interorganizational workflow execution based on process agents and ECA rules, IEICE transactions on information and systems 90-D, No. 9, 1335-1342 (2007)
[18] Liu, Jiming; Jin, Xiaolong; Wang, Yuanshi: Agent-based load balancing on homogeneous minigrids: macroscopic modeling and characterization, IEEE transactions on parallel and distributed systems 16, No. 7, 586-598 (2005)
[19] Low, Kian Hsiang; Leow, Wee Kheng; Jr., Marcelo H. Ang: Autonomic mobile sensor network with self-coordinated task allocation and execution, IEEE transactions on system, man, and cybernetics-part C: Applications and reviews 36, No. 3, 315-327 (2006)
[20] Preiss, B. R.: Data structures and algorithms with object-oriented design patterns in C++, (1999)
[21] Rao, Weixiong; Chen, Lei; Fu, Ada Wai-Chee; Wang, Guoren: Optimal resource placement in structured peer-to-peer networks, IEEE transactions on parallel and distributed systems 21, No. 7, 1011-1026 (2010)
[22] Kraus, Sarit; Plotkin, Tatjana: Algorithms of distributed task allocation for cooperative agents, Theoretical computer science 242, No. 1–2, 1-27 (2000) · Zbl 0944.68005 · doi:10.1016/S0304-3975(98)00175-3
[23] Schaerf, Andrea; Shoham, Yoav; Tennenholtz, Moshe: Adaptive load balancing: a study in multi-agent learning, Journal of artificial intelligence research 2, 475-500 (1995) · Zbl 0900.68355
[24] Seow, Kiam Tian; Sim, Kwang Mong; Kwek, S. Y. C.: Coalition formation for resource coallocation using BDI assignment agents, IEEE transactions on systems, man and cybernetics-part C: Applications and reviews 37, No. 4, 682-693 (2007)
[25] Shehory, Onn; Kraus, Sarit: Methods for task allocation via agent coalition formation, Artificial intelligence 101, No. 1–2, 165-200 (1998) · Zbl 0908.68032 · doi:10.1016/S0004-3702(98)00045-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.