多策略蚁群算法在机器人路径规划中的应用

doi:10.3778/j.issn.1002-8331.2109-0106

摘要/Abstract

摘要： 在二维环境中，蚁群算法规划路径时易出现收敛慢，搜索得到的路径是次优路径等问题。针对这些问题，提出一种新式多策略改进的蚁群算法以提高路径寻优性能和搜索效率。根据当前栅格相对于起始点的位置采用非均匀信息素的分布方式，使得优势栅格的初始信息素浓度较高，避免蚂蚁盲目搜索；采用定向邻域扩展策略重新定义蚂蚁移动规则，进一步缩短路径并提高搜索效率；利用角度引导因子增加终点的指导作用，增加障碍物影响因子避免路径陷入死锁以及降低曲折路径的出现率；采用双层精英蚁策略加大最佳路径的信息素含量，防止算法陷入局部最优，提升算法收敛性。实验结果表明，经过改进后，算法的寻优性和收敛能力都得到了极大的提升。

关键词: 路径规划, 蚁群算法, 非均匀信息素, 角度引导因子, 障碍物影响因子, 精英蚂蚁

Abstract: In a two-dimensional environment, the ant colony algorithm is prone to slow convergence when planning paths, and the paths obtained from the search are sub-optimal paths. To address these problems, a new multi-strategy improved ant colony algorithm is proposed to improve the path finding performance and search efficiency. A non-uniform pheromone distribution is used according to the position of the current grid relative to the starting point, so that the initial pheromone concentration of the dominant grid is higher to avoid blind search by ants. The angle guidance factor is used to increase the guiding effect of the endpoint, the obstacle influence factor is increased to avoid the paths from deadlock as well as to reduce the occurrence rate of zigzag paths. The double-layer elite ant strategy is used to increase the pheromone content of the best path to prevent the algorithm from falling into local optimum and improve the convergence of the algorithm. The experimental results show that, the optimization and convergence ability of the improved algorithm have been greatly improved.

Key words: path planning, ant colony algorithm, non-uniform pheromone, angle guide factor, obstacle influence factor, elite ants

刘双双, 黄宜庆. 多策略蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2022, 58(6): 278-286.

LIU Shuangshuang, HUANG Yiqing. Application of Multi-strategy Ant Colony Algorithm in Robot Path Planning[J]. Computer Engineering and Applications, 2022, 58(6): 278-286.

参考文献

[1] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，25（7）：961-967.
ZHU D Q，YAN M Z.Survey on technology of mobile robot path planning[J].Control and Decision，2010，25（7）：961-967.
[2] HART P E，NILSSON N J，RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics，1968，4（2）：100-107.
[3] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[C]//IEEE International Conference on Robotics and Automation.St.Louis：IEEE，1985：500-505.
[4] 康玉祥，姜春英，秦运海，等.基于改进PSO算法的机器人路径规划及实验[J].机器人，2020，42（1）：71-78.
KANG Y X，JIANG C Y，QIN Y H，et al.Robot path planning and experiment with an improved PSO algorithm[J].Robot，2020，42（1）：71-78.
[5] 魏彤，龙琛.基于改进遗传算法的移动机器人路径规划[J].北京航空航天大学学报，2020，46（4）：703-711.
WEI T，LONG C.Path planning for mobile robot based on improved genetic algorithm[J].Journal of Beijing University of Aeronautics and Astronautics，2020，46（4）：703-711.
[6] ZHANG W，GONG X，HAN G，et al.An improved ant colony algorithm for path planning in one scenic area with many spots[J].IEEE Access，2017，5：13260-13269.
[7] LEI T，MING L.A robot exploration strategy based on Q-learning network[C]//2016 IEEE International Conference on Real-Time Computing and Robotics（RCAR），Angkor Wat，Cambodia，America，2016：57-62.
[8] 成怡，郝密密.改进深度强化学习的室内移动机器人路径规划[J].计算机工程与应用，2021，57（21）：256-262.
CHENG Y，HAO M M.Path planning for indoor mobile robot with improved deep reinforcement learning[J].Computer Engineering and Applications，2021，57（21）：256-262.
[9] 陈晖，周德强.改进蚁群优化算法的移动机器人路径规划[J].电子测量技术，2020，43（23）：17-22.
CHEN H，ZHOU D Q.Mobile robot path planning based on improved ant colony algorithm[J].Electronic Measurement Technology，2020，43（23）：17-22.
[10] 刘智飞，刘冬冬.栅格环境下基于开阔视野蚁群的机器人路径规划[J].重庆理工大学学报（自然科学），2022，36（1）：159-164.
LIU Z F，LIU D D.Robot path planning based on wide-field ant colony in grid environment[J].Journal of Chongqing University of Technology（Natural Science），2022，36（1）：159-164.
[11] 许凯波，鲁海燕，黄洋，等.基于双层蚁群算法和动态环境的机器人路径规划方法[J].电子学报，2019，47（10）：2166-2176.
XU K B，LU H Y，HUANG Y，et al.Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment[J].Acta Electronica Sinica，2019，47（10）：2166-2176.
[12] 徐菱，付文浩，江文辉，等.基于16方向24邻域改进蚁群算法的移动机器人路径规划[J].控制与决策，2021，36（5）：1137-1146.
XU L，FU W H，JIANG W H，et al.Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm[J].Control and Decision，2021，36（5）：1137-1146.
[13] 何雅颖，范昕炜.改进蚁群算法在机器人路径规划中的应用[J].计算机工程与应用，2021，57（16）：276-282.
HE Y Y，FAN X W.Application of improved ant colony optimization in robot path planning[J].Computer Engineering and Applications，2021，57（16）：276-282.
[14] 邓向阳，张立民，方伟，等.基于双向汇聚引导蚁群算法的机器人路径规划[J/OL].系统仿真学报：1-8[2021-09-06].http：//kns.cnki.net/kcms/detail/11.3092.v.20210420.1808.
002.html.
DENG X Y，ZHANG L M，FANG W，et al.Robot path planning based on two-way convergent guided ant colony algorithm[J/OL].Journal of System Simulation：1-8[2021-09-06].http：//kns.cnki.net/kcms/detail/11.3092.v.20210420.
1808.002.html.
[15] ZHAO Y，WANG J，XIE X.Continuous ant colony algorithm based on entity and its convergence[C]//2008 Second International Symposium on Intelligent Information Technology Application，Shanghai，China，20-22 Dec 2008：80-84.
[16] 张恒，何丽，袁亮，等.基于改进双层蚁群算法的移动机器人路径规划[J].控制与决策，2022，37（2）：303-313.
ZHANG H，HE L，YUAN L，et al.Mobile robot path planning using improved double-layer ant colony algorithm[J].Control and Decision，2022，37（2）：303-313.