基于多邻域蚁群算法的机器人路径规划  

Robot path planning based on multi-neighborhood ant colony algorithm

作　　者：唐宏伟[1] 罗佳强 TANG Hongwei;LUO Jiaqiang(Hunan Provincial Key Laboratory of Grids Operation and Control on Multi-Power Source Area,Shaoyang University,Shaoyang 422000,China)

机构地区：[1]邵阳学院多电源地区电网运行与控制湖南省重点实验室,湖南邵阳422000

出　　处：《邵阳学院学报（自然科学版）》2024年第3期1-10,共10页Journal of Shaoyang University：Natural Science Edition

基　　金：湖南省自科基金(2022JJ50205);湖南省教育厅科研项目(21B0682,21B0676,21C0599);湖南省科技计划项目(2016TP1023);邵阳学院研究生科研创新项目(CX2023SY083)。

摘　　要：针对传统蚁群算法在机器人路径规划中路径不是最短距离、运行时间长以及收敛速度慢等问题,提出多邻域蚁群算法(multi-neighborhood ant colony algorithm,ACO-MN)。为了解决路径不是最短距离的问题,引入多邻域搜索,使得搜索邻域扩大,机器人的路径距离减小;为了解决运行时间长的问题,在快速判断的基础上运用象限概率和象限概率控制参数,使得算法运行加快;为了解决收敛速度慢的问题,结合步长和邻域夹角改进启发函数,使得算法在后期的收敛速度加快。最后,在不同大小、不同复杂程度的栅格地图下,将ACO-MN与传统蚁群算法和其他改进算法进行仿真对比实验。实验表明,在小规模简单环境下ACO-MN的收敛速度相比于传统蚁群算法加快了76.19%,在大规模复杂环境下ACO-MN的运行时间相比于其他改进算法缩短了49.84%,最短路径缩短了5.6%,验证了该算法的有效性和优越性。Aiming at the problems of traditional ant colony algorithm in robot path planning,such as the path was not the shortest distance,long running time,and slow convergence speed,a multi-neighborhood ant colony algorithm(ACO-MN)was proposed.In order to solve the problem that the path was not the shortest distance,multi-neighborhood search was introduced to expand the search field and reduce the path distance of the robot;in order to solve the problem of long running time,quadrant probability and quadrant probability control parameters were used on the basis of rapid judgment,which made the algorithm run faster;in order to solve the problem of slow convergence speed,the heuristic function was improved by combining the step size and the angle between fields,so that the convergence speed of the algorithm was accelerated in the later stage.Finally,the multi-neighborhood ant colony algorithm was simulated and compared with the traditional ant colony algorithm and other improved algorithms under different size and complexity grid maps.The experiments show that the convergence speed of this algorithm is 76.19%faster higher than the traditional ant colony algorithm in small-scale simple environment,and the running time of the algorithm is 49.84%less than other improved algorithms in large-scale complex environment,and the shortest path is 5.6%shorter,which verifies the effectiveness and superiority of the algorithm.

关 键 词：蚁群算法 路径规划 多邻域 启发函数 象限概率控制参数 机器人 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]