在静态栅格地图环境下,针对传统蚁群算法在机器人全局路径规划中存在无法找到最短路径、路径搜索盲目性大、拐点多等问题,提出一种改进蚁群算法。在传统正向搜索的基础上,增加反向路径搜索,即双向路径搜索,每个方向采用不同的启发函数,增加路径搜索的目的性以及提高解的构造效率。对每代路径进行路径交叉,有助于产生新解,避免陷入局部最优。更新上述得到的有效路径的信息素,避免无效路径的干扰。采用改进的挥发系数公式,实现动态调整挥发系数,并设置信息素浓度范围,能够避免陷入早熟。采用改进的贝塞尔曲线优化上述得到的最优路径,能够根据需求调节曲线优化程度。通过与其他算法进行仿真对比,验证了改进算法的可行性、有效性和优越性。
In the static grid map environment, aiming at the problems of traditional ant colony algorithm in robot global path planning, such as failing to find the shortest path, blind path search and many inflection points, an improved ant colony algorithm was proposed. On the basis of traditional forward search, reverse path search was added, that was, bidirectional path search. Different heuristic functions were used in each direction. The combination of the two increased the purpose of path search and the construction efficiency of solution.Path crossing for each generation of paths was helpful to generate new solutions and avoid falling into local optimization.The pheromone of the obtained effective path was updated to avoid the interference of the invalid path.The improved volatilization coefficient formula was adopted to dynamically adjust the volatilization coefficient and set the pheromone concentration range, which could avoid falling into premature maturity.The improved Bessel curve was used to optimize the above optimal path, and the degree of curve optimization could be adjusted according to the demand.Compared with other algorithms, the feasibility, effectiveness and superiority of the improved algorithm are verified.
[1] 辜勇,段晶晶,苏宇霞,等.基于改进蚁群算法的仓储物流机器人路径规划[J].武汉理工大学学报(交通科学与工程版),2020,44(4):688-693,697.
GU Y,DUAN J J,SU Y X,et al.Path planning of warehouse logistics robot based on improved ant colony algorithm[J].Journal of Wuhan University of Technology (Transportation Science & Engineering),2020,44(4):688-693,697.
[2] 王迪,李彩虹,郭娜,等.基于人工势场法的移动机器人局部路径规划[J].山东理工大学学报(自然科学版),2021,35(1):21-26,32.
WANG D,LI C H,GUO N,et al.Local path planning of mobile robot based on artificial potential field method[J].Journal of Shandong University of Technology (Natural Science Edition),2021,35(1):21-26,32.
[3] 王维.基于改进A*算法的移动机器人路径规划的研究[D].兰州:西北师范大学,2019.
WANG W.Research on path planning for mobile robot based on improved A* algorithm[D].Lanzhou:Northwest Normal University,2019.
[4] 朱艳,游晓明,刘升.基于启发式机制的改进蚁群算法[J].信息与控制,2019,48(3):265-271.
ZHU Y,YOU X M,LIU S.Improved ant colony algorithm based on heuristic mechanism[J].Information and Control,2019,48(3):265-271.
[5] BU Q M,WANG Z J,TONG X.An improved genetic algorithm for searching for pollution sources[J].Water Science and Engineering,2013,6(4):392-401.
[6] 陈亮,陈君若.基于改进遗传算法的移动机器人路径规划[J].软件导刊,2019,18(4):24-27.
CHEN L,CHEN J R.Mobile robot path planning based on improved genetic algorithms[J].Software Guide,2019,18(4):24-27.
[7] 刘泽,金世俊,王庆.基于改进蚁群算法的移动机器人二维路径规划[J].传感器与微系统,2020,39(10):149-152.
LIU Z,JIN S J,WANG Q.2D path planning of mobile robots based on improved ant colony algorithm[J].Transducer and Microsystem Technologies,2020,39(10):149-152.
[8] 任彦,赵海波,肖永健.改进势场蚁群法的机器人避障及路径规划[J].电光与控制,2019,26(11):75-79.
REN Y,ZHAO H B,XIAO Y J.Robot obstacle avoidance and path planning based on improved potential field ant colony method[J].Electronics Optics & Control,2019,26(11):75-79.
[9] 王晓燕,杨乐,张宇,等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策,2018,33(10):1775-1781.
WANG X Y,YANG L,ZHANG Y,et al.Robot path planning based on improved ant colony algorithm with potential field heuristic[J].Control and Decision,2018,33(10):1775-1781.
[10] 陈志,韩兴国.改进蚁群算法在移动机器人路径规划上的应用[J].计算机工程与设计,2020,41(8):2388-2395.
CHEN Z,HAN X G.Application of improved ant colony algorithm in mobile robot path planning[J].Computer Engineering and Design,2020,41(8):2388-2395.
[11] 王娇娇,毛剑琳.基于蚁群改进与尖峰平滑的移动机器人路径规划[J].软件导刊,2018,17(9):36-39.
WANG J J,MAO J L.Mobile robot path planning based on ant colony improvement and spike smoothing[J].Software Guide,2018,17(9):36-39.
[12] 王红君,徐军,赵辉,等.基于平滑蚁群算法的机器人路径规划[J].燕山大学学报,2017,41(3):278-282.
WANG H J,XU J,ZHAO H,et al.Mobile robot path planning based on smoothing ant colony algorithm[J].Journal of Yanshan University,2017,41(3):278-282.
[13] 徐梁,高宏力,宋兴国.贝塞尔曲线融合ACO的移动机器人路径规划[J].机械设计与制造,2020(1):263-266.
XU L,GAO H L,SONG X G.Path planning of mobile robot based on fusion of bezier curve and ACO[J].Machinery Design & Manufacture,2020(1):263-266.
[14] 赵开新,王东署,徐立新.蚁群遗传算法在移动机器人路径规划中的综合应用研究[J].制造业自动化,2014,36(17):70-72,84.
ZHAO K X,WANG D S,XU L X.Comprehensive application research of ant colony genetic algorithm in mobile robot path planning[J].Manufacturing Automation,2014,36(17):70-72,84.
[15] 曹新亮,王智文,冯晶,等.基于改进蚁群算法的机器人全局路径规划研究[J].计算机工程与科学,2020,42(3):564-570.
CAO X L,WANG Z W,FENG J,et al.Global path planning of robots based on improved ant colony algorithm[J].Computer Engineering & Science,2020,42(3):564-570.
[16] LUO Q,WANG H B,ZHENG Y,et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications,2020,32(6):1555-1566.
