一种基于P学习的分布式并行多任务分配算法

苏兆品; 蒋建国; 梁昌勇; 张国富

doi:10.3724/SP.J.1004.2011.00865

一种基于P学习的分布式并行多任务分配算法

doi: 10.3724/SP.J.1004.2011.00865

计量
- 文章访问数: 2490
- HTML全文浏览量: 103
- PDF下载量: 1061
- 被引次数: 0
出版历程
- 收稿日期: 2010-03-05
- 修回日期: 2011-03-02
- 刊出日期: 2011-07-20

A Distributed Algorithm for Parallel Multi-task Allocation Based on Profit Sharing Learning

摘要

摘要: 并行多任务分配是多agent系统中极具挑战性的课题, 主要面向资源分配、灾害应急管理等应用需求, 研究如何把一组待求解任务分配给相应的agent联盟去执行. 本文提出了一种基于自组织、自学习agent的分布式并行多任务分配算法, 该算法引入P学习设计了单agent寻找任务的学习模型, 并给出了agent之间通信和协商策略. 对比实验说明该算法不仅能快速寻找到每个任务的求解联盟, 而且能明确给出联盟中各agent成员的实际资源承担量, 从而可以为实际的控制和决策任务提供有价值的参考依据.
- 多Agent系统(MAS) /
- 并发多任务分配 /
- 联盟形成 /
- P学习 /
- 协商
Abstract: Task allocation via coalition formation is a fundamental research challenge in several application domains of multi-agent systems (MAS), such as resource allocation, disaster response management, and so on. It mainly deals with how to allocate many unresolved tasks to groups of agents in a distributed manner. In this paper, we propose a distributed parallel multi-task allocation algorithm among self-organizing and self-learning agents. To tackle the situation, we disperse agents and tasks geographically in two-dimensional cells, and then introduce profit sharing learning (PSL) for a single agent to search its tasks by continual self-learning. We also present strategies for communication and negotiation among agents to allocate real workload to every tasked agent. Finally, to evaluate the effectiveness of the proposed algorithm, we compare it with Shehory and Kraus' distributed task allocation algorithm which were discussed by many researchers in recent years. Experimental results show that the proposed algorithm can quickly form a solving coalition for every task. Moreover, the proposed algorithm can specifically tell us the real workload of every tasked agent, and thus can provide a specific and significant reference for practical control tasks.
- Multi-agent systems (MAS) /
- parallel multi-task allocation /
- coalition formation /
- profit sharing learning (PSL) /
- negotiation

HTML全文

参考文献(1)

[1]

Seow K T, Sim K M, Kwek S Y. Coalition formation for resource coallocation using BDI assignment agents. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2007, 37(4): 682-693[2] Li J D, Yahyapour R. Negotiation model supporting co-allocation for grid scheduling. In: Proceedings of the 7th IEEE/ACM International Conference on Grid Computing. Barcelona, Spain, IEEE, 2006. 254-261[3] Gunawan L T. Collaboration-oriented design of disaster response system. In: Proceedings of the 26th Annual SIGCHI Conference on Human Factors in Computing Systems. Florence, Italy: ACM, 2008. 2613-2616[4] Boloni L, Khan M A, Turgut D. Agent-based coalition formation in disaster response applications. In: Proceedings of the IEEE Workshop on Distributed Intelligent Systems: Collective Intelligence and Its Applications. Prague, Czech Republic: IEEE, 2006. 259-264[5] Bachrach Y, Rosenschein J S. Coalitional skill games. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. Richland, USA: International Foundation for Autonomous Agents and Multiagent Systems, 2008. 1023-1030[6] Chen Y M, Huan P N. Agent-based bilateral multi-issue negotiation scheme for e-market transactions. Applied Soft Computing, 2009, 9(3): 1057-1067[7] Kulkarni A J, Tai K. Probability collectives: a multi-agent approach for solving combinatorial optimization problems. Applied Soft Computing, 2010, 10(3): 759-771[8] Vig L, Adams J A. Multi-robot coalition formation. IEEE Transactions on Robotics, 2006, 22(4): 637-649[9] Rahwan T, Ramchurn S D, Jennings N R, Giovannucci A. An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research, 2009, 34(1): 521-567[10] Agotnes T, Hoek W V D, Wooldridge M. Reasoning about coalitional games. Artificial Intelligence, 2009, 173(1): 45-79 [11] Sen S, Dutta P S. Searching for optimal coalition structures. In: Proceedings of the 4th International Conference on MultiAgent Systems. Boston, USA: IEEE, 2000. 287-292[12] Yang J A, Luo Z H. Coalition formation mechanism in multi-agent systems based on genetic algorithms. Applied Soft Computing, 2007, 7(2): 561-568[13] Zhang G F, Jiang J G, Su Z P, Qi M B, Fang H. Searching for overlapping coalitions in multiple virtual organizations. Information Sciences, 2010, 180(17): 3140-3156[14] Shehory O, Kraus S. Methods for task allocation via agent coalition formation. Artificial Intelligence, 1998, 101(1-2): 165-200 [15] Mataric M J, Sukhatme G S, Ostergaard E H. Multi-robot task allocation in uncertain environments. Autonomous Robots, 2003, 14(2-3): 255-263[16] Thomas L, Rachid A, Simon L. A distributed tasks allocation scheme in multi-UAV context. In: Proceedings of the IEEE International Conference on Robotics and Automation. Washington D. C., USA: IEEE, 2004. 3622-3627[17] Rahwan T, Jennings N R. An algorithm for distributing coalitional value calculations among cooperating agents. Artificial Intelligence, 2007, 171(8-9): 535-567[18] Dash R K, Vytelingum P, Rogers A, David E, Jennings N R. Market-based task allocation mechanisms for limited-capacity suppliers. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2007, 37(3): 391-405[19] Sander P V, Peleshchuk D, Grosz B J. A scalable, distributed algorithm for efficient task allocation. In: Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems. New York, USA: ACM, 2002. 1191-1198[20] Viguria A, Howard A. Upper-bound cost analysis of a market-based algorithm applied to the initial formation problem. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. San Diego, USA: IEEE, 2007. 2326-2331[21] Kitakoshia D, Shioyab H, Nakanoa R. Empirical analysis of an on-line adaptive system using a mixture of Bayesian networks. Information Sciences: an International Journal, 2010, 180(15): 2856-2874[22] Ken S, Shiro M. Profit sharing introducing the judgement of incomplete perception. Transactions of the Japanese Society for Artificial Intelligence, 2004, 19(5): 379-388[23] Hasegawa Y, Takada S, Nakano H, Arai S, Miyauchi A. A reinforcement learning method using a dynamic reinforcement function based on action selection probability. Systems and Computers in Japan, 2007, 38(7): 1-11[24] Fujishiro T, Nakano H, Miyauchi A. Parallel distributed profit sharing for PC cluster. In: Proceedings of the 16th International Conference on Artificial Neural Networks. Athens, Greece: Springer, 2006. 811-819

施引文献

资源附件(0)

访问统计