面向机器人全局路径规划的改进蚁群算法研究

doi:10.3778/j.issn.1002-8331.2107-0369

摘要/Abstract

摘要： 针对基本蚁群算法在机器人路径规划过程中路径转弯角度过大、易陷入局部极小值、收敛速度慢等问题，对其进行改进。在分析机器人路径规划环境建模方法基础上，将转角启发函数引入至节点选择概率公式，以增强路径选择指向性，提高算法搜索速度；通过引入当前节点与下一节点之间的距离和下一节点与目标节点距离之和的二次方对启发函数进行改进，使得算法搜索过程更有针对性，并降低陷入局部极小值概率；提出信息素挥发因子自适应更新策略，扩大算法搜索范围，提高收敛速度；利用遗传算法的交叉操作对移动路径进行二次优化，以增强算法的寻优能力，进而以Floyd算法为基础引入路径平滑操作，减少移动路径节点。在MATLAB中与其他算法通过求解多个单模测试函数与多模测试函数进行对比，并在栅格法环境建模中进行机器人全局路径规划仿真对比实验，以验证改进算法在路径寻优速度和质量上更具优越性。仿真结果表明，改进后的蚁群算法具有一定的可行性和有效性。

关键词: 路径规划, 改进蚁群算法, 环境建模, 栅格法, 遗传算法

Abstract: The problems of basic ant colony algorithm are solved including too large turning angle, easy to fall into local minimum and slow convergence speed of basic ant colony algorithm in the process of robot path planning. Based on the analysis of robot path planning environment modeling method, firstly, the corner heuristic function is introduced into the node selection probability formula to enhance the directivity of path selection and improve the search speed of the algorithm. Furthermore, the heuristic function is improved by introducing the quadratic sum of the distance between the current node and the next node, the distance between the next node and the target node, which makes the search process more targeted and reduces the probability of falling into local minimum. In addition, the pheromone volatilization factor adaptive update strategy is proposed to expand the search range and improve the convergence speed. Secondly, the crossover operation of genetic algorithm is used to optimize the mobile path twice to enhance the optimization ability of the algorithm. Then the path smoothing operation is introduced based on Floyd algorithm to reduce the number of nodes in the mobile path. Finally, the grid method is used to model the environment. Finally, compared with other algorithms by solving multiple unimodal test functions and multi-modal test functions in MATLAB, and the simulation comparison experiment of robot global path planning in grid environment modeling, so as to verify that the improved algorithm has more advantages in path optimization speed and quality. The simulation results show that the improved ant colony algorithm is feasible and effective.

Key words: path planning, improved ant colony algorithm, environmental modeling, grid method, genetic algorithm

张天瑞, 吴宝库, 周福强. 面向机器人全局路径规划的改进蚁群算法研究[J]. 计算机工程与应用, 2022, 58(1): 282-291.

ZHANG Tianrui, WU Baoku, ZHOU Fuqiang. Research on Improved Ant Colony Algorithm for Robot Global Path Planning[J]. Computer Engineering and Applications, 2022, 58(1): 282-291.

参考文献

[1] 王中玉，曾国辉，黄勃.基于改进双向A~*的移动机器人路径规划算法[J].计算机应用，2019，39（9）：2517-2522.
WANG Z Y，ZENG G H，HUANG B.Global optimal path planning for robots with improved A* algorithm[J].Journal of Computer Applications，2019，39（9）：2517-2522.
[2] 张松灿，普杰信，司彦娜，等.蚁群算法在移动机器人路径规划中的应用综述[J].计算机工程与应用，2020，56（8）：10-19.
ZHANG S C，PU J X，SI Y N，et al.Survey on application of ant colony algorithm in path planning of mobile robot[J].Computer Engineering and Applications，2020，56（8）：10-19.
[3] 王春颖，刘平，秦洪政.移动机器人的智能路径规划算法综述[J].传感器与微系统，2018，37（8）：5-8.
WANG C Y，LIU P，QIN H Z.Review on intelligent path planning algorithm of mobile robots[J].Transducer and Microsystem Technologies，2018，37（8）：5-8.
[4] 曹凯，陈阳泉，高嵩，等.涡流人工势场引导下的RRT~*移动机器人路径规划[J].计算机科学与探索，2021，15（4）：723-732.
CAO K，CHEN Y Q，GAO C，et al.Vortex artificial-potential-field guided RRT* for path planning of mobile robot[J].Journal of Frontiers of Computer Science and Technology，2021，15（4）：723-732.
[5] 王洪斌，尹鹏衡，郑维，等.基于改进的A~*算法与动态窗口法的移动机器人路径规划[J].机器人，2020，42（3）：346-353.
WANG H B，YIN P H，ZHENG W，et al.Mobile robot path planning based on improved A* algorithm and dynamic window method[J].Robot，2020，42（3）：346-353.
[6] ZHANG B，TANG L，DECASTRO J，et al.A recursive receding horizon planning for unmanned vehicles[J].IEEE Transactions on Industrial Electronics，2015，62（5）：2912-2920.
[7] 徐林，范昕炜.基于改进遗传算法的餐厅服务机器人路径规划[J].计算机应用，2017，37（7）：1967-1971.
XU L，FAN X W.Path planning for restaurant service robot based on improved genetic algorithm[J].Journal of Computer Applications，2017，37（7）：1967-1971.
[8] 强宁，高洁，康凤举.基于PSO和三次样条插值的多机器人全局路径规划[J].系统仿真学报，2017，29（7）：1397-1404.
QIANG N，GAO J，KANG F J.Multi-robots global path planning based on PSO algorithm and cubic spline[J].Journal of System Simulation，2017，29（7）：1397-1404.
[9] 马小陆，梅宏.基于改进势场蚁群算法的移动机器人全局路径规划[J].机械工程学报，2021，57（1）：19-27.
MA X L，MEI H.Mobile robot global path planning based on improved ant colony system algorithm with potential field[J].Journal of Mechanical Engineerings，2021，57（1）：19-27.
[10] 陈克斌，鲁云军，韩梦瑶，等.一种基于双编码遗传算法的机动微波接力网组网方法[J].控制与决策，2020，35（12）：2915-2922.
CHEN K B，LU Y J，HAN M Y，et al.Mobile microwave relay network construction method based on double coding genetic algorithm[J].Control and Decision，2020，35（12）：2915-2922.
[11] 张国辉，胡一凡，孙靖贺.改进遗传算法求解多时间约束的柔性作业车间调度问题[J].工业工程，2020，23（2）：19-25.
ZHANG G H，HU Y F，SUN J H.An improved genetic algorithm for flexible job shop scheduling problem with multiple time constraints[J].Industrial Engineering Journal，2020，23（2）：19-25.
[12] 宋启松，李少波，柘龙炫，等.基于改进遗传算法的自动导引小车路径规划[J].组合机床与自动化加工技术，2020（7）：88-92.
SONG Q S，LI S B，ZHE L X，et al.Path planning for automatic guided vehicle based on improved genetic algorithm[J].Modular Machine Tool ＆ Automatic Manufacturing Technique，2020（7）：88-92.
[13] 张进峰，杨涛宁，马伟皓.基于多目标粒子群算法的船舶航速优化[J].系统仿真学报，2019，31（4）：787-794.
ZHANG J F，YANG T N，MA W H.Ship speed optimization based on multi-objective particle swarm algorithm[J].Journal of System Simulation，2019，31（4）：787-794.
[14] 吴永明，戴隆州，李少波，等.基于改进粒子群优化算法的混流装配线演进平[J].计算机集成制造系统，2017，23（4）：781-790.
WU Y M，DAI L Z，LI S B，et al.Mixed assembly line evolution balancing based on improved particle swarm algorithm[J].Computer Integrated Manufacturing Systems，2017，23（4）：781-790.
[15] 罗阳阳，彭晓燕.基于改进PSO的四轮移动机器人全局路径规划[J].计算机仿真，2020，37（7）：373-379.
LUO Y Y，PENG X Y.Global path planning of four-wheel mobile robot based on improved PSO[J].Computer Simulation，2020，37（7）：373-379.
[16] DORIGO M，GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.
[17] 吉珊珊.基于增强蚁群算法的传感网移动sink路径规划[J].系统仿真学报，2019，31（11）：2543-2552.
JI S S.Path Planning for mobile sink based on enhanced ant colony optimization algorithm[J].Journal of System Simulation，2019，31（11）：2543-2552.
[18] 杜玉红，张岩，赵焕峰.基于参数优化蚁群算法的机器人路径规划研究[J].现代制造工程，2020（9）：7-14.
DU Y H，ZHANG Y，ZHAO H F.Research on robot path planning based on parameters optimized ant colony optimization[J].Modern Manufacturing Engineering，2020（9）：7-14.
[19] 徐菱，付文浩，江文辉，等.基于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.
[20] 李志锟，黄宜庆，徐玉琼.改进变步长蚁群算法的移动机器人路径规划[J].电子测量与仪器学报，2020，34（8）：15-21.
LI Z K，HUANG Y Q，XU Y Q.Path planning of mobile robot based on improved variable step size ant colony algorithm[J].Journal of Electronic Measurement and Instrumentation，2020，34（8）：15-21.
[21] 赵春芳，李江昊，张大伟.基于改进免疫遗传优化蚁群算法的移动机器人路径寻优研究[J].计量学报，2019，40（3）：505-510.
ZHAO C F，LI J H，ZHANG D W.Robot path optimization research based on improved immune genetic optimization ant colony algorithm[J].Acta Metrologica Sinica，2019，40（3）：505-510.
[22] 何少佳，史剑清，王海坤.基于改进蚁群粒子群算法的移动机器人路径规划[J].桂林理工大学学报，2014，34（4）：765-770.
HE S J，SHI J Q，WANG H K.Path planning for mobile robot based on improved ant colony and particle swarm optimization[J].Journal of Guilin University of Technology，2014，34（4）：765-770.
[23] 陈思远，林丕源，黄沛杰.指针网络改进遗传算法求解旅行商问题[J].计算机工程与应用，2020，56（19）：231-236.
CHEN S Y，LIN P Y，HUANG P J.Pointer network improved genetic algorithm for solving traveling salesmen problem[J].Computer Engineering and Applications，2020，56（19）：231-236.
[24] 任红格，胡鸿长，史涛.基于改进蚁群算法的移动机器人全局路径规划[J].华北理工大学学报（自然科学版），2021，43（2）：102-109.
REN H G，HU H C，SHI T.Global path planning of mobile robots based on improved ant colony algorithm[J].Journal of North China University of Science and Technology（Natural Science Edition），2021，43（2）：102-109.