State Key Laboratory of Robotics and System,Harbin Institute of Technology,Harbin 150080 Key Laboratory of Computer Network and Information Integration of State Education Ministry,School of Computer Science and Engineering,Southeast University,Nanjing 211189
Abstract：Large scale multiagent systems are always organized in networked structures where each agent interacts only with its immediate neighbors. Moreover, the networked multiagent systems always run on certain underlying physical networks. Obviously, the traditional task allocation methods based on agent self-owned resources are not fit for the networked multiagent systems. Aiming at this problem, three task allocation methods are reviewed for networked multiagent systems: the task allocation method based on underlying networks and agent resources, the task allocation method based on multiagent interaction networks and agent resources and the task allocation method based on contextual resource distribution. It considers both the underlying networks and multiagent interaction networks. Besides, the related works on centralized and distributed task allocations are reviewed, and the related works are compared to the proposed task allocation methods. Finally, the difficulties and the further work on the task allocation of networked multiagent systems are discussed.
[1] Jennings N R.An Agent-Based Approach for Building Complex Software Systems.Communications of the ACM,2001,44(4): 35-41 [2] Liu Jiming,Jin Xiaolong,Ching T K.Autonomy Oriented Computing (AOC): From Problem Solving to Complex Systems Modeling.Boston,USA: Kluwer Academic Publisher,2005 [3] Cao Longbing,Zhang Chengqi,Zhou Mengchu.Engineering Open Complex Agent Systems: A Case Study.IEEE Trans on Systems,Man and Cybernetics,2008,38(4): 483-496 [4] Jiang Yichuan,Jiang Jiuchuan.Contextual Resource Negotiation-Based Task Allocation and Load Balancing in Complex Software Systems.IEEE Trans on Parallel and Distributed Systems,2009,20(5): 641-653 [5] Lü Jian,Tao Xianping,Ma Xiaoxing,et al.The Research on Interware Model Based on Agents.Science China: Series E,2005,35(12): 1233-1253 (in Chinese) (吕 建,陶先平,马晓星,等.基于Agent的网构软件模型研究.中国科学.E辑,2005,35(12): 1233-1253) [6] Jiang Yichuan,Hu Jing,Lin Donghui.Decision Making of Networked Multiagent Systems for Interaction Structures.IEEE Trans on Systems,Man and Cybernetics,2011,99(3): 1-15 [7] Abdallah S,Lesser V.Multiagent Reinforcement Learning and Self-Organization in a Network of Agents // Proc of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems.Honolulu,USA,2007: 172-179 [8] Shehory O,Kraus S.Methods for Task Allocation via Agent Coalition Formation.Artificial Intelligence,1998,101(1/2): 165-200 [9] Jiang Yichuan,Jiang Jiuchuan.A Multi-Agent Coordination Model for the Variation of Underlying Network Topology.Expert Systems with Applications: An International Journal,2005,29(2): 372-382 [10] Kraus S,Plotkin T.Algorithms of Distributed Task Allocation for Cooperative Agents.Theoretical Computer Science,2000,242(1/2): 1-27 [11] Liu Jiming,Jin Xiaolong,Wang Yuanshi.Agent-Based Load Balancing on Homogeneous Minigrids: Macroscopic Modeling and Characterization.IEEE Trans on Parallel and Distributed Systems,2005,16(7): 586-598 [12] Chow K P,Kwok Y K.On Load Balancing for Distributed Multiagent Computing.IEEE Trans on Parallel and Distributed Systems,2002,13(8): 787-801 [13] Palmer D,Kirschenbaum M,Murton J,et al.Decentralized Cooperative Auction for Multiple Agent Task Allocation Using Synchronized Random Number Generators // Proc of the IEEE International Conference on Intelligent Robots and Systems.Las Vegas,USA,2003: 1963-1968 [14] Sims M,Phelps J,Mostafa H,et al.Lateral and Hierarchical Partial Centralization for Distributed Coordination and Scheduling of Complex Hierarchical Task Networks // Proc of the AAAI Spring Symposium on Distributed Plan and Schedule Management.Stanford,USA,2006: 113-120 [15] Fjuita S,Lesser V R.Centralized Task Distribution in the Presence of Uncertainty and Time Deadlines // Proc of the 2nd International Conference on Multiagent Systems.Kyoto,Japan,1996: 87-94 [16] Jiang Yichuan,Li Zhaofeng.Locality-Sensitive Task Allocation and Load Balancing in Networked Multiagent Systems: Talent versus Centrality.Journal of Parallel and Distributed Computing,2011,71(6): 822-836 [17] Findler N V.Multiagent Coordination and Cooperation in a Distributed Dynamic Environment with Limited Resources.Artificial Intelligence in Engineering,1995,9(3): 229-238 [18] Borgatti S P.Centrality and Network Flow.Social Networks,2005,27(1): 55-71 [19] Freeman L C.Centrality in Social Networks Conceptual Clarification.Social Networks,1979,1(3): 215-239 [20] Zhang Xiaoqin,Lesser V,Wagner T.Integrative Negotiation among Agents Situated in Organizations.IEEE Trans on Systems,Man and Cybernetics,2006,36(11): 19-30 [21] Haken H.Information and Self-Organization: A Macroscopic Approach to Complex Systems.2nd Edition.Berlin,Germany: Springer,2000 [22] Erdmann M,Lozano-Perez T.On Multiple Moving Robots.Algorithmica,1987,2(4): 477-521 [23] Walsh W E,Wellman M P.A Market Protocol for Decentralized Task Allocation // Proc of the 3rd International Conference on Multi-Agent Systems.Paris,France,1998: 325-332 [24] Krainin M,An Bo,Lesser V.An Application of Automated Negotiation to Distributed Task Allocation // Proc of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology.Silicon Valley,USA,2007: 138-145 [25] Zhang Xiaoqin,Lesser V,Podorozhny R.Multi-Dimensional,Multistep Negotiation for Task Allocation in a Cooperative System.Autonomous Agents and Multi-Agent Systems,2005,10(1): 5-40 [26] Abdallah S,Lesser V.Learning the Task Allocation Game // Proc of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems.Hakodate,Japan,2006: 850-857 [27] Smith R G.The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver.IEEE Trans on Computers,1980,29(12): 1104-1113
2012, Vol. 25 
