Multi-Agent path planning algorithm based on ant colony algorithm and game theory
ZHENG Yanbin1,2, WANG Linlin1, XI Pengxue1, FAN Wenxin1, HAN Mengyun1
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
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.
郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多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. Journal of Computer Applications, 2019, 39(3): 681-687.
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.)
2019, Vol. 39 
