基于蚁群改进与尖峰平滑的移动机器人路径规划

王娇娇　毛剑琳

摘要：

近年来，移动机器人路径规划作为机器人自主导航领域的一个重要问题而备受关注，针对传统ACA有易陷入局部最优，以及现阶段在很多机器人路径规划中易被忽略的出现过于尖锐拐点的问题，提出一种改进蚁群算法（ACA-ES）应用于移动机器人路径规划。首先，针对ACA易陷入早熟的问题，引入精英策略，目的是给每次循环结束后找出的最优解增加额外信息素，提高算法收敛速度；其次，为了不使机器人在路径尖峰处失去平衡，引入基于中心点的平滑方法，提高路径平滑性。在栅格环境下进行仿真，得到一条平滑路径，且路径长度比原来缩短了5.90%，证明了该改进算法的有效性和可行性。

关键词：

移动机器人；路径规划；蚁群算法；精英策略；尖峰平滑

DOIDOI：10.11907/rjdk.181005

中图分类号：TP303

文献标识码：A文章编号文章编号：16727800（2018）009003604

英文标题Mobile Robot Path Planning Based on Ant Colony Improvement and Spike Smoothing

——副标题

英文作者WANG Jiaojiao， MAO Jianlin

英文作者单位（Institute of Information Engineering and Automation， Kunming University of Science and Technology，Kunming 650000，China）

英文摘要Abstract：In recent years， Mobile robot path planning has drawn much attention as an important issue in robot autonomous navigation. An improved ACA （ACA-ES）is proposed for mobile robot path planning. First of all， in view of the ACA is easy to fall premature， Introducing Elitist Strategyelitist strategy is employed to aim at the fact that ACA is easy to fall premature， The purpose is to add extra pheromones to the optimal solution found at the end of each cycle， amd improve the convergence speed of the algorithm. Secondly， in order not to make the robot lose balance at the peak of the path， a smoothing method based on the center point is introduced to improve the smoothness of the path. Simulation in the grid environment A smooth path is obtained in grid environment， and the path length is reduced by 5.90%. The effectiveness and feasibility of the improved algorithm are proved.

英文关键词Key Words：mobile robot； path planning； ant colony algorithm；elite strategy； spike smoothing

0引言

移动机器人路径规划是移动机器人研究领域的核心技术之一，主要目的是从已知起始点到要求达到的终止点，并且在有障碍物的情况下完成避障和路径规划。

遗传算法的全局搜索能力较强[1]，文献[2]通过设计自适应变异概率，提高了遗传个体评价精度和其应用于路径规划时的求解质量；文献[3]采用染色体变长遗传算法（Messy GA），提高了路径规划的可靠性，但A*算法收敛速度慢，并且在搜索过程中会陷入“死循环”；文献[4]采用头尾双向搜索法提高了A*算法的执行效率和稳定性，但粒子群算法（PSO）缺乏时间的动态调节，使得局部寻优能力相对较差；文献[5]引入一种非线性动态调整惯性权重的改进PSO；文献[6]引入一种更新函数，提高了PSO的局部路径搜索能力，但蚁群算法（Ant Colony Algorithn，ACA）有易陷入局部最优，且会导致收敛速度变慢的缺点[7]；文献[8]分析了ACA主要参数对路径规划的影响，得到了最佳匹配参数；文献[9]通过引入最大、最小蚁群系统对更新的信息素浓度进行限制，解决了ACA因信息素差异过大而陷入“早熟”的问题。

尽管上述算法都在一定程度上解决了路径规划中遇到的问题，但多数算法都忽略了路径规划过程中的实际应用问题，比如得到了一条相对较短的路径，但忽略了实际应用中对路径平滑性的要求，使得机器人实体平衡性差，且会在路径尖峰处产生不必要的能量损耗。本文利用平滑方法增加路径转角的平滑性，消除路径尖峰，以保障机器人实体的平衡性，并且能够减少不必要的能量消耗。该改进后的蚁群算法（ACA-ES）能獲得最短并且适合机器人行进的平滑路径。

1基于蚁群改进与尖峰平滑（ACA-ES）的移动机器人路径规划

1.1问题描述

移动机器人路径规划问题是移动机器人研究中最基本的问题，目的是在起始点和目标点已知的情况下找到一条最优无碰路径。根据机器人对运行环境的掌握程度，可将其分为全局路径规划与局部路径规划[10]。本文研究的基于蚁群改进与尖峰平滑（ACA-ES）的移动机器人路径规划是环境信息已知的全局路径规划，主要包括环境建模、路径规划与路径平滑。采用栅格法对环境进行划分，将环境信息存储于（0，1）矩阵中，矩阵中1表示黑色不可通过的障碍栅格，0表示白色可通过栅格。

1.2基于中心点的平滑方法

平滑方法（Smooth Method）对规划好的路径中出现的尖峰有修正作用，可使路径拐角更为平滑，机器人实体能在拐弯过程中平稳前进，同时减少在路径尖峰处不必要的能量损耗。

文献[11]设计了动态搜索模型，以加快ACA的收敛速度，优化解的质量；文献[12]采用简化A*算法对初始信息素进行优化设置，反馈优化目标以实现自适应调节，提高ACA的全局搜索能力。但文献中的改进方法都忽略了机器人实体对路径平滑性的要求。

本文基于中心点平滑方法改进的蚁群算法（ACA-S）是通过在路径拐点处增加新节点实现的，用新节点代替旧节点完成路径平滑处理[13]。新节点的选择及添加对路径平滑性的改善和整体路径规划效率有着直接影响。图1是基于中心点的平滑方法操作示意图，原路径线段夹角称为α2，选择及添加新节点并去除旧节点，与设置的两条路径拐角的角度期望值α1有关，角度期望值α1定为155°。若两条相邻直线的实际拐角α2≤α1，则在两条线段的可行域之间取中点（x-new1，y-new1）和（x-new2，y-new2），再判断新节点与两边构成的拐角角度是否满足大于角度期望值α。若不满足，继续进行上述变换，寻找新拐点（x-new1，y-new1）和（x-new2，y-new2）；满足角度条件后，删除旧拐点，以新拐点代替。再以此判断路径内的其它拐点是否满足条件，不断重复，使整条路径的拐角都大于角度期望值。

1.3基于精英策略的改进蚁群算法

精英策略（Elitist Strategy）[14]是指当每只蚂蚁经过一次循环后，利用传统ACA即可找出最优解。精英策略是对其信息素给予额外补偿，蚁群之间主要靠信息素传递信息，找出的最优解对应的信息素增强，目的是这次循环中找到的最优解在蚂蚁的下次循环中，经过信息素的增强操作后，对后面经过的蚂蚁吸引力更大，解决了蚁群算法在迭代过程中易陷入局部最优从而使路径中出现不必要尖峰的缺点。信息素更新公式如下：

τij（t+l）=ρ.τij（t）+Δτij+Δτ+*ij（1）

式中：

Δτ+*ij=QL+*，若边（i，j）是所找最优解的一部分0，否则（2）

式中，△τij表示精英蚂蚁在路径（i，j）上信息素的增加，σ表示精英蚂蚁及数量，L*表示循环结束后所找出的最优解对应的路径总长度。

仿真结果表明，精英策略解决了蚁群算法在路径规划时遇到的易陷入“早熟”的缺点，加入精英策略的蚁群算法比传统ACA的迭代次数明显减少，并能获得相对满意的最优路径。

1.4ACA-ES 算法步骤

基于中心点的平滑方法改进后的蚁群算法（ACA-ES）步骤如下：

Step1：初始化参数，对蚂蚁个数M、迭代次数K、栅格、蚂蚁起始点和终止点、表征信息素重要程度的参数α、表征启发式因子重要程度的参数β、信息素挥发系数ρ、信息素增加强度系数Q以及期望偏转角度α1、禁忌表初始化。

Step2：将M只蚂蚁分布到各节点。

Step3：for k=1， 2， …， M

while 下步可行点≥1&&未到达终止点

end

计算各路径长度并保存

K=k+1

end

Step4：根据公式（1）精英策略更新信息素。

Step5：判断是否达到最大迭代次数：

if N=Nmax

Step 6

跳转到Step 2

Step6：利用基于中心点的平滑方法对路径进行平滑操作。

Step7：判断路径上相邻的3个点是否在一条直线上：

if 3个相邻点不在一条直线上

Step 6

else

跳转到下一个点 Step 6

Step8：输出优化后的路径。

2仿真实验及分析

为验证引入精英策略和基于中心点平滑方法的改进后蚁群算法（ACA-ES）应用于移动机器人的路径规划效果，在MATLAB2012a环境下进行仿真实验。利用栅格法对环境进行划分，图中黑色格子表示不能通过的栅格即为障碍物栅格，白色格子表示道路为可通过栅格。分别在障碍物覆盖率为19%的20*20简单栅格和障碍物覆盖率为77%的17*17复杂栅格环境下进行仿真。

2.1简单障碍物栅格环境仿真

为了验证本文提出的基于中心点的平滑方法（ACA-S）應用于移动机器人路径规划的可行性，划分机器人的工作环境为20*20简单障碍物栅格，仿真参数设置为：蚂蚁个数M为50，迭代次数N为200，启发因子α为1，期望启发因子β为7，信息素蒸发系数ρ为0.7，信息素增加强度系数为1，机器人起始点坐标为（0.5，19.5），终止点坐标为（19.5，0.5），期望偏转角度α1为155°。路径规划仿真如图3所示。

由图3可看出，本文提出的路径平滑方法应用于移动机器人路径规划过程中，不仅能够规划出令人满意的避障路径，而且在机器人拐弯处的路线有了明显的平滑改善。路径由原来的30.384 8缩短为29.799 0，迭代次数由32减少到29，证明了该平滑方法可为实体机器人规划出一条更加适合自主移动的平滑路线。

2.2复杂障碍物栅格环境仿真

为验证该改进算法（ACA-ES）应用于移动机器人路径规划时的可行性和有效性，在17*17栅格环境下进行路径规划仿真，参数设置与20*20栅格一致，机器人的起始点坐标为（0.5，16.5），终止点坐标为（16.5，0.5）。

分别采用传统蚁群算法（ACA）、基于精英策略的改进蚁群算法（ACA-E）、在精英策略基础上加入平滑方法的改进蚁群算法（ACA-ES）在17*17的复杂障碍物栅格环境下进行路径规划仿真研究，图4给出了采用各类算法的机器人路径规划仿真结果，表1对其路径长度和仿真耗时进行汇总对比。

由图4（a）可知，传统蚁群算法（ACA）虽然能有效避开障碍物并规划出一条可行路线，但由于蚁群算法本身有易陷入局部最优的缺点，使得规划好的路径中出现了不必要的冗余节点。为了去除路径中的这些节点，达到缩短路径长度的目的，引入精英策略；如图4（b）所示为ACA-E路径规划图，精英策略提高了ACA的全局搜索能力，消除了路径中的多余节点。由表1可知，路径长度由原来的33.899 5缩短为32.727 9，迭代次数由70下降到35，减少了一半。在此基础上引入基于中心点的平滑方法进一步对拐点进行优化，使得路径更加圆滑，符合实体机器人的运动特性，同时路径长度缩短为31.899 5，迭代次数减少为25；如图4（c）所示，与传统ACA路径规划相比，ACA-ES应用于移动机器人路径规划，不仅缩短了得到的最优路径长度，而且相对于传统ACA减少了迭代次数，并结合实体机器人对路径规划的特殊要求，得到一条适合机器人行进的平滑路线。

表1数据显示路径规划在引入精英策略（ACA-E）和基于中心点的平滑方法（ACA-ES）后，所得规划路径长度明显优于传统ACA，分别减少了3.46%和5.90%，说明精英策略和基于中心点的平滑方法有效发挥了作用。但是路径的缩短以消耗时间为代价，改进后的ACA-E和ACA-ES所需的规划时间分别增加了5.48%和4.51%。

3结语

本文提出一种引入精英策略和路径尖峰平滑方法的改进蚁群算法 （ACA-ES）应用于移动机器人路径规划，其中，精英策略的加入解决了传统蚁群算法易陷入局部最优而导致算法搜索停滞的弊端，提高了解的全局性。在引入精英策略的基础上加入基于中心点的平滑方法，该方法使路径中的较小转角更为平滑，降低了机器人在路径转弯处的能量损耗，机器人实体在行进中的稳定性也得到了保障。仿真实验表明，采用ACA-ES算法明显提高了路径平滑度，所获得的路径长度也更短，但这是以消耗计算机的运行时间为代价的，在实际要求较高的情况下需要进一步改进。

参考文献参考文献：

[1]ZHANG X， TANG L. A new hybrid ant colony optimization algorithm for the vehicle routing problem [J]. Pattern Recognition Letters， 2009，30（9）：848855.

[2]王雷，李明，唐敦兵，等.基于改进遗传算法的机器人动态路径规划[J].南京航空航天大学学报，2016，48（6）：841846.

[3]卢瑾，杨东勇.基于双重遗传算法机制的路径规划[J].系统仿真学报，2008，20（8）：20482051.

[4]劉钰，陆建峰，蔡海舟.基于改进A*算法的机器人路径规划方法研究[J].计算机技术与发展，2012（12）：108111.

[5]张万绪，张向兰，李莹.基于改进粒子群算法的智能机器人路径规划[J].计算机应用，2014，34（2）：510513.

[6]颜雪松，胡成玉，姚宏，等.精英粒子群优化算法及其在机器人路径规划中的应用[J].光学精密工程，2013，21（12）：31603168.

[7]XIONG W Q， WEI P. A kind of ant colony algorithm for function optimization[C].International Conference on Machine Learning and Cybernetics， Proceedings， 2002：552555.

[8]史恩秀，陈敏敏，李俊，等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报，2014，45（6）：5357.

[9]赵开新，魏勇，王东署.改进蚁群算法在移动机器人路径规划中的研究[J].计算机测量与控制，2014，22（11）：6770.

[10]GE S S， CUI Y J. New potential functions for mobile robot path planning [J]. IEEE Transactions on Robotics & Automation， 2000，16（5）：615620.

[11]游晓明，刘升，吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策，2017，32（3）：552556.

[12]黄辰，费继友，刘洋，等.基于动态反馈A*蚁群算法的平滑路径规划方法[J].农业机械学报， 2017，48（4）：3440.

[13]王雪松，高阳，程玉虎，等.知识引导遗传算法实现机器人路径规划[J].控制与决策，2009，24（7）：10431049.

[14]张家善，王志宏，陈应显.一种基于精英策略的改进蚁群算法及应用[J].计算机系统应用，2012，21（10）：105108.

责任编辑（责任编辑：黄健）