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

doi:10.11772/j.issn.1001-9081.2018071601

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 681-687.DOI: 10.11772/j.issn.1001-9081.2018071601

Previous Articles Next Articles

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-10 Published:2019-03-11
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).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP24

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.

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

References

[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.)

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CHAI Jie, GUO Liuxiao, SHEN Wanqiang, CHEN Jing. Consensus of time-varying multi-agent systems based on event-triggered impulsive control [J]. Journal of Computer Applications, 2021, 41(9): 2748-2753.
[2]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[3]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[4]	WANG Yunyan, HU Aihua. Consensus of two-layer multi-agent systems subjected to cyber-attack [J]. Journal of Computer Applications, 2021, 41(5): 1399-1405.
[5]	WANG Yijie, FAN Jiafei, WANG Chenyu. Two-stage task offloading strategy based on game theory in cloud-edge environment [J]. Journal of Computer Applications, 2021, 41(5): 1392-1398.
[6]	ZHANG Kang, CHEN Jianping. Path planning algorithm in complex environment using self-adjusting sampling space [J]. Journal of Computer Applications, 2021, 41(4): 1207-1213.
[7]	MAO Yingchi, XU Xuesong, LIU Pengfei. Multi-user task offloading strategy based on stable allocation [J]. Journal of Computer Applications, 2021, 41(3): 786-793.
[8]	ZHANG Shuyao, LI Yonghua, FAN Jiajia. Bulk storage assignment algorithm in bulk port based on game theory [J]. Journal of Computer Applications, 2021, 41(3): 867-874.
[9]	WEI Bo, YANG Rong, SHU Sihao, WAN Yong, MIAO Jianguo. Path planning of mobile robots based on ion motion-artificial bee colony algorithm [J]. Journal of Computer Applications, 2021, 41(2): 379-383.
[10]	HUANG Shuzhao, TIAN Junwei, QIAO Lu, WANG Qin, SU Yu. Unmanned aerial vehicle path planning based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(2): 390-397.
[11]	WANG Jialiang, LI Shuhua, ZHANG Haitao. Obstacle avoidance path planning algorithm of quad-rotor helicopter based on Bayesian estimation and region division traversal [J]. Journal of Computer Applications, 2021, 41(2): 384-389.
[12]	Ying LEI, Wanbo ZHENG, Wei WEI, Yunni XIA, Xiaobo LI, Chengwu LIU, Hong XIE. Task offloading method based on probabilistic performance awareness and evolutionary game strategy in “cloud + edge” hybrid environment [J]. Journal of Computer Applications, 2021, 41(11): 3302-3308.
[13]	LI Wei, JIN Shijun. Optimal path convergence method based on artificial potential field method and informed sampling [J]. Journal of Computer Applications, 2021, 41(10): 2912-2918.
[14]	LIU Sijia, TONG Xiangrong. Urban transportation path planning based on reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 185-190.
[15]	YAO Xinghu, TAN Xiaoyang. Reward highway network based global credit assignment algorithm in multi-agent reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 1-7.