|
|
基于市场权值的二阶段多agent任务分配算法
|
Abstract:
当前对于多Agent系统中比较热点问题是多agent的资源分配和多agent的任务分配，即如何将合适的任务分配给合适的agent，以优化整体任务分配结果。但是考虑到其中的agent具有自利性问题的研究却很少。为了有效的解决自利agent任务分配的问题，构造出一个包含最优竞争和市场协作的两阶段任务分配模型，在最优竞争的基础上，市场协作阶段进一步协调和优化最优任务的分配。考虑到候选人之间的关系可能最终影响市场的总体收益，提出“市场权值”的概念来描述更精确的合作关系。基于市场权值的两阶段分配模型，不仅能让任务候选人充分发挥自身优势参与竞争，保护任务候选人利益，而且能优化市场的总体收益。最后，通过仿真结果验证本文提出算法的有效性。
At present, the hot issues in multi-agent system are multi-agent resource allocation and multi-agent task allocation, that is, how to allocate appropriate tasks to appropriate agents to optimize the overall task allocation results. However, considering the self-interest of the agent, there is little re-search on the problem. In order to effectively solve the problem of task allocation of self-interest agent, a two-stage task allocation model including optimal competition and market cooperation is constructed. On the basis of optimal competition, the market cooperation stage further coordinates and optimizes the optimal task allocation. Considering that the relationship between candidates may ultimately affect the overall income of the market, the concept of “market weight” is proposed to describe a more accurate cooperative relationship. The two-stage allocation model based on market weight can not only enable task candidates to give full play to their own advantages, participate in competition and protect the interests of task candidates, but also optimize the overall in-come of the market. Finally, the simulation results verify the effectiveness of the proposed algorithm.
| [1] | Sycara, P.K. (1998) Muti-Agent Systems. AI Magazine, 19, 79-92. |
| [2] | Jennings, N.R. (1995) Controlling Cooperative Problem Solving in Industrial Multi-Agent Systems Using Joint Intentions. Artificial Intelligence, 75, 195-240. https://doi.org/10.1016/0004-3702(94)00020-2 |
| [3] | Kraus, S. and Arkin, R.C. (2001) Strategic Negotiation in Multiagent Environments. MIT Press, Cambrigde. |
| [4] | 陈琦. 2020年9月新能源车销售三强:上汽通用五菱、比亚迪、特斯拉[J]. 汽车与配件, 2020(20): 43. |
| [5] | Bachrach, Y., Parkes, D.C. and Rosenschein, J.S. (2013) Computing Co-operative Solution Concepts in Coalitional Skill Games. Artificial Intelligence, 204, 1-21. https://doi.org/10.1016/j.artint.2013.07.005 |
| [6] | 蒋建国, 苏兆品, 张国富, 夏娜. 多任务联盟形成中的Agent行为策略研究[J]. 控制理论与应用, 2008, 25(5): 853-856. |
| [7] | Cisneros-Cabrera, S., Sampaio, P. and Mehandjiev, N. (2018) A B2B Team Formation Microservice for Collaborative Manufacturing in Industry 4.0. 2018 IEEE World Congress on Services (SERVICES), San Francisco, 2-7 July 2018, 37-38. https://doi.org/10.1109/SERVICES.2018.00032 |
| [8] | Hayano, M., Hamada, D. and Sugawara, T. (2014) Role and Member Selection in Team Formation Using Resource Estimation for Large-Scale Multi-Agent Systems. Neurocompu-ting, 146, 164-172.
https://doi.org/10.1016/j.neucom.2014.04.059 |
| [9] | Juárez, J. and Brizuela, C.A. (2018) A Multi-Objective For-mulation of the Team Formation Problem in Social Networks: Preliminary Results. Proceedings of the Genetic and Evo-lutionary Computation Conference, Kyoto, 15-19 July 2018, 261-268. https://doi.org/10.1145/3205455.3205634 |
| [10] | Zzkarian, A. and Kusiak, A. (1999) Forming Teams: An Analytical Approach. IIE Transactions, 31, 85-97.
https://doi.org/10.1080/07408179908969808 |
| [11] | Kara, I. and Bektas, T. (2006) Integer Linear Programming Formulations of Multiple Salesman Problems and Its Variations. European Journal of Operational Research, 174, 1449-1458. https://doi.org/10.1016/j.ejor.2005.03.008 |
| [12] | Wooldridge, M. and Dunne, P.E. (2004) On the Com-putational Complexity of Qualitative Coalitional Games. Artificial Intelligence, 158, 27-73. https://doi.org/10.1016/j.artint.2004.04.002 |
| [13] | Wooldridge, M. and Dunne, P.E. (2006) On the Computational Complexity of Coalitional Resource Games. Journal of Artificial Intelligence, 170, 835-871. https://doi.org/10.1016/j.artint.2006.03.003 |
| [14] | 张国富, 蒋建国, 夏娜, 苏兆品. 基于离散粒子群算法求解复杂联盟生成问题[J]. 电子学报, 2007, 35(2): 323-327. |
| [15] | Larson, K.S. and Sandholm, T.W. (2000) Anytime Coali-tion Structure Generation: An Average Case Study. Journal of Experimental & Theoretical Artificial Intelligence, 12, 23-42. https://doi.org/10.1080/095281300146290 |
| [16] | 苏射雄, 胡山立, 郑盛福, 林超峰, 骆剑彬. 基于势结构的任一时间联盟结构生成算法[J]. 计算机研究与发展, 2008, 45(10): 1756-1762. |
| [17] | 梁军, 程显毅. 基于混合蚁群遗传算法的agent联盟求解[J]. 计算机科学, 2009, 36(5): 227-231. |
| [18] | 桂海霞, 张国富, 苏兆品, 蒋建国. 一种基于差分进化和编码修正的重叠联盟结构生成算法[J]. 控制理论与应用, 2018, 35(2): 215-223. |
| [19] | 许波, 余建平. 基于QPSO的单任务Agent联盟形成[J]. 计算机工程, 2010, 36(19): 168-170. |
| [20] | 尹蕾. 分布式智能系统中多任务协作机制研究[D]: [博士学位论文]. 合肥: 合肥工业大学, 2019. |
| [21] | Vig, L. and Adams, J.A. (2006) Multi-Robot Coalition Formation. IEEE Transactions on Robotics, 22, 637-649.
https://doi.org/10.1109/TRO.2006.878948 |
| [22] | Service T.C. and Adams J.A. (2011) Coalition Formation for Task Allocation: Theory and Algorithms. Autonomous Agents and Multi-Agent Systems, 22, 225-248. https://doi.org/10.1007/s10458-010-9123-8 |
| [23] | Lin, L. and Zheng, Z. (2005) Combinatorial Bids Based Mul-ti-Robot Task Allocation Method. Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, 18-22 April 2005, 1145-1150.
https://doi.org/10.1109/ROBOT.2005.1570270 |
| [24] | Sisikoglu, E., Epelman, M.A. and Smith, R.L. (2011) A Sampled Fictitious Play Based Learning Algorithm for Infinite Horizon Markov Decision Processes. Proceedings of the 2011 Winter Simulation Conference, Phoenix, 11-14 December 2011, 4086-4097. https://doi.org/10.1109/WSC.2011.6148098 |
| [25] | Myszkowski, P.B., Skowroński, M.E. and Sikora, K. (2015) A New Benchmark Dataset for Multi-Skill Resource- Constrained Project Scheduling Problem. Proceedings of the 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), ？ód？, 13-16 September 2015, 129-138. https://doi.org/10.15439/2015F273 |
| [26] | Myszkowski, P.B., Skowroński, M.E., Olech, ？.P., et al. (2015) Hybrid Ant Colony Optimization in Solving Multi-Skill Resource-Constrained Project Scheduling Problem. Soft Computing, 19, 3599-3619.
https://doi.org/10.1007/s00500-014-1455-x |
