基于蚁群算法及博弈论的多Agent路径规划算法

doi:10.11772/j.issn.1001-9081.2018071601

计算机应用 ›› 2019, Vol. 39 ›› Issue (3): 681-687.DOI: 10.11772/j.issn.1001-9081.2018071601

基于蚁群算法及博弈论的多Agent路径规划算法

郑延斌^1,2, 王林林¹, 席鹏雪¹, 樊文鑫¹, 韩梦云¹

1. 河南师范大学计算机与信息工程学院, 河南新乡 453007;
2. 智慧商务与物联网技术河南省工程实验室(河南师范大学), 河南新乡 453007

收稿日期:2018-08-02 修回日期:2018-09-12 发布日期:2019-03-11 出版日期:2019-03-10
作者简介:郑延斌(1964-),男,河南内乡人,教授,博士,CCF会员,主要研究方向:虚拟现实、多智能体系统、对策论;王林林(1993-),女,河南周口人,硕士研究生,主要研究方向:虚拟现实、多智能体系统;席鹏雪(1993-),女,河南新乡人,硕士研究生,主要研究方向:虚拟现实、多智能体系统;樊文鑫(1994-),男,河南郑州人,硕士研究生,主要研究方向:虚拟现实、多智能体系统;韩梦云(1993-),女,河南安阳人,硕士研究生,主要研究方向:虚拟现实、汉字识别。
基金资助:
河南省科技攻关项目（142300410349，132102210538）；河南省软科学项目（142400411001）；河南师范大学青年基金资助项目（2017QK20）。

Multi-Agent path planning algorithm based on ant colony algorithm and game theory

ZHENG Yanbin^1,2, WANG Linlin¹, XI Pengxue¹, FAN Wenxin¹, HAN Mengyun¹

1. College of Computer and Information Engineering, Henan Normal University, Xinxiang Henan 453007, China;
2. Henan Engineering Laboratory of Intellectual Business and Internet of Things Technologies(Henan Normal University), Xinxiang Henan 453007, China

Received:2018-08-02 Revised:2018-09-12 Online:2019-03-11 Published:2019-03-10
Contact: 王林林
Supported by:
This work is partially supported by the Science and Technology Research Project of Henan Province (142300410349, 132102210538), the Soft Science Project of Henan Province (142400411001), the Youth Fund of Henan Normal University (2017QK20).

摘要/Abstract

摘要： 针对多Agent路径规划问题，提出了一个两阶段的路径规划算法。首先，利用改进的蚁群算法来为每个Agent规划出一条从起始点到目标点，不与环境中静态障碍物碰撞的最优路径。在蚁群算法的改进中引入反向学习方法来对蚂蚁位置进行初始化分布，提高了算法的全局搜索能力；利用粒子群算法中的自适应惯性权重因子来调节信息素强度Q值，使其自适应地变化，避免陷入局部最优；对信息素挥发因子ρ进行调节，提高算法的迭代速度。其次，若多Agent之间存在动态碰撞，利用博弈论构建多Agent之间的动态避障模型，并利用虚拟行动法来解决博弈的求解问题及多Nash均衡的选择问题，确保每个Agent能够快速学习到最优Nash均衡。仿真实验结果表明改进蚁群算法与传统蚁群算法相比在搜索精度与搜索速度上有明显的提高，与Mylvaganam的多Agent动态避障算法相比，所提算法减小了路径总长度并提高了收敛速度。

关键词: 多Agent, 路径规划, 反向学习, 蚁群算法, 博弈论

Abstract: A two-stage path planning algorithm was proposed for multi-Agent path planning. Firstly, an improved ant colony algorithm was used to plan an optimal path for each Agent from the starting point to the target point without colliding with the static obstacles in the environment. The reverse learning method was introduced to an improved ant colony algorithm to initialize the ant positions and increase the global search ability of the algorithm. The adaptive inertia weighted factor in the particle swarm optimization algorithm was used to adjust the pheromone intensity Q value to make it adaptively change to avoid falling into local optimum. The pheromone volatilization factor ρ was adjusted to speed up the iteration of the algorithm. Then, if there were dynamic collisions between multiple Agents, the game theory was used to construct a dynamic obstacle avoidance model between them, and the virtual action method was used to solve the game and select multiple Nash equilibria, making each Agent quickly learn the optimal Nash equilibrium. The simulation results show that the improved ant colony algorithm has a significant improvement in search accuracy and search speed compared with the traditional ant colony algorithm. And compared with Mylvaganam's multi-Agent dynamic obstacle avoidance algorithm, the proposed algorithm reduces the total path length and improves the convergence speed.

Key words: multi-Agent, path planning, reverse learning, ant colony algorithm, game theory

中图分类号:

TP24

郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.

ZHENG Yanbin, WANG Linlin, XI Pengxue, FAN Wenxin, HAN Mengyun. Multi-Agent path planning algorithm based on ant colony algorithm and game theory[J]. Journal of Computer Applications, 2019, 39(3): 681-687.

参考文献

[1] BENNET D J, MCINNES C R. Distributed control of multi-robot systems using bifurcating potential fields[J]. Robotics and Autonomous Systems, 2010, 58(3):256-264.
[2] DORIGO M, MANIEZZO V, COLORNI A. Ant system:optimization by a colony of cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 1996, 26(1):29-41.
[3] KOVACS B, SZAYER G, TAJTI F, et al. A novel potential field method for path planning of mobile robots by adapting animal motion attributes[J]. Robotics and Autonomous Systems, 2016, 82(C):24-34.
[4] QIAN W J, ZHOU L F,YANG L, et al. An improved ant colony algorithm of three dimensional path planning[C]//Proceedings of the 201710th International Symposium on Computational Intelligence and Design. Piscataway, NJ:IEEE, 2017,1:119-122.
[5] DARWISH A H, JOUKHADAR A, KASHKASH M. Using the bees algorithm for wheeled mobile robot path planning in an indoor dynamic environment[J]. Cogent Engineering, 2018, 5(1):1-23.
[6] 裴振兵,陈雪波.改进蚁群算法及其在机器人避障中的应用[J].智能系统学报,2015,10(1):90-96.(PEI Z B, CHEN X B. Improved ant colony algorithm and its application in obstacle avoidance for robot[J]. CAAI Transactions on Intelligent Systems, 2015, 10(1):90-96.)
[7] 柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.(LIU C A, YAN X H, LIU C Y, et al. Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J]. Acta Electronica Sinica, 2011, 39(5):1220-1224.)
[8] YUAN Z, YU H, HUANG M. Improved ant colony optimization algorithm for intelligent vehicle path planning[C]//Proceedings of the 2017 International Conference on Industrial Informatics-Computing Technology, Intelligent Technology, Industrial Information Integration. Piscataway, NJ:IEEE, 2017:1-4.
[9] ZOUARI W, ALAYA I, TAGINA M. A hybrid ant colony algorithm with a local search for the strongly correlated knapsack problem[C]//Proceedings of the 2017 IEEE/ACS 14th International Conference on Computer Systems and Applications. Piscataway, NJ:IEEE, 2017:527-533.
[10] 屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44(2):260-265.(QU H, HUANG L W, KE X. Research of improved ant colony based robot path planning under dynamic environment[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(2):260-265.)
[11] MYLVAGANAM T, SASSANO M, ASTOLFI A. A constructive differential game approach to collision avoidance in multi-Agent systems[C]//Proceedings of the 2014 American Control Conference on Portland. Piscataway, NJ:IEEE, 2014:311-316.
[12] MYLVAGANAM T, SASSANO M, ASTOLFI A. A differential game approach to multi-Agent collision avoidance[J]. IEEE Transactions on Automatic Control, 2017, 62(8):4229-4235.
[13] TIZHOOSH H R. Opposition-based learning:a new scheme for machine intelligence[C]//CIMCA'05:Proceedings of the 2005 International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Washington, DC:IEEE Computer Society, 2005,1:695-701.
[14] 杜继永,张凤鸣,李建文,等.一种具有初始化功能的自适应惯性权重粒子群算法[J].信息与控制,2012,41(2):165-169.(DU J Y, ZHANG F M, LI J W, et al. A particle swarm optimization algorithm with initialized adaptive inertia weights[J]. Information and Control, 2012, 41(2):165-169.)
[15] 施锡全.博弈论[M].上海:上海财经大学出版社,2000:29-80.(SHI X Q. Game Theory[M]. Shanghai:Shanghai University of Finance and Economics Press, 2000:29-80.)
[16] FUDENBERG D, LEVINE D K. The Theory of Learning in Games[M]. Cambridge:MIT Press, 1996:177-198.
[17] 丁占文,蔡超英,杨宏林,等.不完全博弈学习过程的虚拟行动规则[J].运筹学学报,2010,14(3):91-100.(DING Z W,CAI C Y, YANG H L, et al. Rule of fictitious play in the learning process with incomplete learning times[J]. Operations Research Transactions, 2010, 14(3):91-100.)

基于蚁群算法及博弈论的多Agent路径规划算法

Multi-Agent path planning algorithm based on ant colony algorithm and game theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[2]	杨乐, 张达敏, 何庆, 邓佳欣, 左锋琴. 改进猎人猎物优化算法在WSN覆盖中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2506-2513.
[3]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[4]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[5]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[6]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[7]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[8]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[9]	邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860.
[10]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[11]	王波, 王浩, 杜晓昕, 郑晓东, 周薇. 基于亚群和差分进化的混合蜻蜓算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2868-2876.
[12]	王思蕊, 程世娟, 袁非梦. 基于改进证据融合的高可靠产品可靠性评估方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2140-2146.
[13]	邱仲睿, 苗虹, 曾成碧. 多策略融合的改进黏菌算法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 812-819.
[14]	向君幸, 吴永红. 基于邻域重心反向学习的混合樽海鞘群蝴蝶优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 820-826.
[15]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.