基于改进蚁群算法的移动机器人平滑路径规划

孙 瑞，张文胜

基于改进蚁群算法的移动机器人平滑路径规划

孙 瑞，张文胜

(石家庄铁道大学交通运输学院，河北 石家庄 050043)

针对移动机器人提出了基于改进蚁群算法的平滑路径规划方法。为了克服蚁群算法解决路径规划问题时存在的收敛速度慢的缺点，对启发因子的矩阵初始值及更新方式进行了改进，启发因子改进后的结果与之前相比，平均路径长度减少了17.6%，平均收敛代数减少了93.1%；对于栅格环境下存在障碍物时机器人累计转弯角度大的问题，提出了控制点转移策略，在上一步改进的基础上，通过对控制路径走向的栅格中心点向栅格角顶点的转移，实现了路径规划的平滑改进。路径规划仿真结果表明，与平滑改进前相比，平滑改进后机器人的平均路径长度减少了4.28%，累计转弯角度减少了52.58%。

蚁群算法；移动机器人；路径规划；控制点转移策略

随着人工智能的发展，机器人在人类社会发挥着越来越重要的作用[1]。移动机器人的路径规划是机器人执行任务的首要条件[2]，可要求机器人在躲避障碍物的前提下，找到从出发点到目的地的最优路径。

蚁群算法是模仿自然界中蚂蚁觅食过程发展起来的一种优化方法[3-4]，具有较强的鲁棒性，在解决优化问题方面显示出巨大优势和发展潜力[5-7]，广泛应用于移动机器人路径规划问题。目前众多学者对其进行研究，徐胜华等[8]在解决机器人路径规划问题时对蚁群算法进行改进，使其能根据环境特征进行优化；张文强和张彦[9]提出一种改进蚁群算法，将引力系数和避障系数引入启发因子中，提高了解的质量和搜索效率；朱艳等[10]将方向信息加到启发因子中，且动态调整权重系数使算法搜索效率更高；王辉等[11]通过更改启发因子及信息素更新规则，使改进后的算法收敛更快；王志中[12]提出了蚂蚁相遇策略及蚂蚁回退策略，设置了信息素感应阈值，对信息素残留方法进行了改进，使改进后的蚁群算法具有更快的收敛速度以及更优的规划结果；张玮等[13]采用改进烟花-蚁群混合算法进行最优路径的求解，将改进烟花算法得到的最短路径作为参照路径，将其换算成蚁群算法的初始信息素分布，结果表明该算法具有良好的性能；王红君等[14]提出了一种平滑蚁群算法，将路径上当前节点与其他不在同一条直线上的节点依次连线，如果新的连接线不穿越障碍物，则将当前连接线作为新路径代替原来路径，降低了路径长度。

以上研究大多是对蚁群算法进行改进，对于改进后的路径进行平滑的方法较少。本文不但通过改进启发因子实现了对蚁群算法的改进，而且提出了控制点转移策略，通过对控制路径走向的栅格中心点向栅格角顶点的转移，实现了对蚁群算法改进后的路径平滑操作，为蚁群算法的改进及路径平滑操作提供了一种新思路。

1 环境建模

栅格法可使机器人感知的栅格信息与环境相对应，且栅格法地图易于创建和维护，因此采用栅格法建立移动机器人二维空间环境模型。栅格法模型如图1所示，划分栅格区域的指标为机器人单位运动步长。左上角栅格为起始栅格，栅格序号按自左向右，从上至下的顺序依次增大，右下角栅格为终点栅格。障碍物栅格表现为黑色，自由栅格为白色[15]。设为栅格序号；为栅格的边长。栅格序号与栅格中心点坐标对应关系如下

2 基本蚁群算法

在觅食过程中，蚂蚁根据信息素浓度选择新的路径，并赋予路径一定概率。信息素具有挥发性，随着时间的推移，挥发留下的信息素能引导蚂蚁找到最优路径[16-17]。

在寻找新的食物源时，蚂蚁没有信息素指引，因此进行完全随机搜索，此时所有路径均被赋予相同的概率。蚂蚁将更多的信息素留在较短的路径上，较长的路径逐渐被放弃[18]。之后会有更多的蚂蚁选择信息素较多的路径，这就形成了正反馈机制，通过该机制，蚁群中蚂蚁能沿着最佳路径找到食物。该过程如图2所示。

图2 蚂蚁觅食示意图

设为食物来源；为蚁巢所在地；为时间；和为单位距离；和为0.5单位距离。设和中有30只蚂蚁，当＝1时，上没有信息素，因此蚂蚁以相同的概率选择路径。经过1单位时间后，路径上信息素量是的2倍；当＝2时，和中的30只蚂蚁根据先前迭代中不同路径上的信息素浓度再次选择路径：从点出发的蚂蚁有20只选择，10只选择；从点出发的蚂蚁有20只选择，10只选择，因此，较短路径上积累了更多的信息素。随着时间的推移，会有更多蚂蚁选择()路径，直到最后一组蚂蚁均找到蚁巢和食物之间的最短路径。蚂蚁觅食是一个正反馈过程。某刻，蚂蚁从节点转向节点的概率为[19]

3 改进蚁群算法

3.1 启发因子的改进

对于启发因子的改进分为启发因子矩阵初始值和启发因子更新方式2部分。

3.1.1 启发因子矩阵初始值的改进

在基本蚁群算法中，启发因子矩阵初始值为该节点与下一节点距离的倒数。经验证其收敛性能较弱、全局搜索能力较差。为加强蚁群算法收敛性能，减少收敛代数，提高全局搜索能力，对启发因子矩阵初始值进行改进，即

(x,y)为该节点处坐标值，(x,y)为下一节点处坐标值，引入常数a、b，使启发因子矩阵初始值为任意两节点距离进行初等变换后的倒数。在第4节中进行路径规划统计结果分析，找到移动机器人路径规划最短且收敛代数最少的a、b值。

3.1.2 启发因子更新方式的改进

在基本蚁群算法中，启发因子为该节点与下一节点距离的倒数，使蚂蚁具有一定的盲目性，易陷入局部最优而错失全局最优路径[20]。为减少这种情况的发生，提高蚁群算法全局搜索能力，引入下一节点到目标节点之间的距离，对启发因子更新方式进行改进，即

其中，为下一节点；为目标节点；d为节点到目标节点之间的距离。

将改进后启发因子带入状态转移公式，得到改进后的状态转移公式为

分析可知，当下一节点到目标节点之间的距离越大时，启发因子越小，蚂蚁选择该节点的概率随之越小。也就是说，当搜索到的距离越短时，蚂蚁选择的概率越大，因此移动机器人路径规划更优。

3.2 路径规划的平滑改进

在栅格环境下，移动机器人的路径规划是该路径上各个栅格中心点连成的直线段，将这些栅格中心点称为控制点，其控制着移动机器人的路径规划。由于移动机器人的路径是从中心点到中心点的直线段，从一定程度上增加了路径长度，且增大了移动机器人累计转弯角度。对路径规划进行平滑改进，不仅能减少移动机器人运行距离，还能降低其由于转弯带来的能耗[21]。

图3实线为基于蚁群算法搜索到的路径，从点到点的路径由3段折线组成。若将路径上的点与点相连，能减小移动机器人路径规划累计转弯角度，且根据三角形两边之和大于第三边的定理，线段的长度小于原路径长度。

图3 从A到B的路径规划改进

因此引入控制点转移策略，将图3中第35个栅格的控制点由栅格中心点转移到该栅格上离起点最近的点，将第55个栅格的控制点由栅格中心点转移到该栅格上离终点最近的点，删除原路径上第45个栅格的中心点，并将点与点连接成一条直线段。因此，缩短了路径规划的距离，减少了路径规划的累计转弯角度，实现了路径的平滑操作。

3.3 基于改进蚁群算法的移动机器人平滑路径规划

步骤1.运用经过启发因子改进后的蚁群算法生成一条机器人最优路径。

步骤2. 引入控制点转移策略，即通过对控制路径走向的栅格中心点向栅格角顶点的转移，进行路径简化与平滑操作。

设置路径起点为，终点为。控制点转移策略主要针对除起点与终点之外的路径上的其他栅格中心点。当路径上存在竖直线段时，将最上方栅格中心点记为(X,Y)，分别判断所在栅格的4个角顶点：U(X–0.5,Y+0.5)，U(X+0.5,Y+0.5)，U(X+0.5,Y–0.5)，U(X–0.5,Y–0.5)与起点的距离，选择与起点的距离最小的点作为转移的目标角顶点(记为U)，将转移至U。将最下方栅格中心点记为(X,Y)，分别判断所在栅格的4个角顶点：D，D，D，D与终点的距离，选择与终点距离最小的点作为转移的目标角顶点(记为D)，将转移至D。删除与之间的中心栅格点，并将点U与点D相连。

判断当路径上存在水平线段时，将最左侧栅格中心点记为，分别判断所在栅格的4个角顶点：，L，L，L与起点的距离，将转移到该栅格距起点最近的角顶点(记为L)上。将最右侧栅格中心点记为，分别判断所在栅格的4个角顶点：R，R，R，R与终点的距离，将转移到该栅格距终点最近的角顶点(记为R)上。删除与之间的中心栅格点，并将点L与点R相连。

步骤3.生成新路径取代原有路径。判断路径上是否仍存在水平线段或竖直线段，若仍存在则重新执行步骤2和步骤3，否则输出机器人最终路径。

路径规划的平滑改进能有效减小移动机器人的路径长度及累计转弯角度，使得机器人的能量消耗得以降低，更符合移动机器人的路径规划要求。路径规划平滑改进流程图如图4所示。

图4 路径规划平滑改进流程图

4 改进蚁群算法及路径平滑操作的仿真验证

4.1 仿真1

为验证经过启发因子改进的蚁群算法在移动机器人路径规划的正确性与有效性，对算法进行仿真。仿真环境为MATLAB R2016a，采用栅格法建模，栅格边长为10。蚂蚁个数=30，信息素重要程度参数=1，启发因子重要程度参数=6，信息素蒸发系数=0.1，信息素增加强度系数=14。

在和均为默认值1的情况下，对基本蚁群算法及经过启发因子更新方式、状态转移公式改进的蚁群算法进行仿真，路径规划仿真结果如图5所示。

蚁群算法在搜索过程中进行下一节点选择时存在着随机性因素，仅根据一次实验结果难以准确判断两种算法的优劣，因此需进行多次实验来得到更准确的结果。为此，分别用MATLAB运行20次和50次，并对两者的运行结果进行对比。

用MATLAB运行20次得到的路径规划统计结果见表1。

用MATLAB运行50次得到的路径规划统计结果见表2。

图5 启发因子更新方式、状态转移公式改进前后路径规划仿真结果

表1 a和b均为1时，运行20次的路径规划统计结果

表2 a和b均为1时，运行50次的路径规划统计结果

由表1和表2比较分析可知，运行50次时，基本蚁群算法的平均路径长度、平均收敛代数、最小收敛代数均发生变化。运行50次比20次包含更多的路径搜索情况，以最小收敛代数为例，运行50次时为147，而运行20次时未出现此情况。因此，选择用MATLAB进行50次独立实验，分析时采用MATLAB运行50次得到的路径规划统计数据。

由表2可知，启发因子更新方式改进后的蚁群算法仿真出的平均路径长度比基本蚁群算法减少了17.6%，最短路径长度减少了16.8%。在平均收敛代数方面，改进蚁群算法比基本蚁群算法减少了87.3%。在最小收敛代数方面，改进蚁群算法比基本蚁群算法减少了91.8%。因此，在路径长度及收敛速度上，经过启发因子更新方式改进后的算法优于基本蚁群算法。

当和取不同值时，在10×10栅格环境下，对经过启发因子更新方式改进的蚁群算法执行50次，路径规划统计结果见表3。

表3 当a和b取不同值时，改进蚁群算法路径规划统计结果

由表3分析可知，当=1；=1，2，3时，对经过启发因子更新方式改进的蚁群算法执行50次得到的平均路径长度均为最短，在保证具有最短路径的前提下，当=3，=1时平均收敛代数及最小收敛代数最小，此时蚁群算法具有较好的收敛性能。与基本蚁群算法路径统计结果相比，=3且=1时平均路径长度减少了17.6%，平均收敛代数减少了93.1%。

4.2 仿真2

运用控制点转移策略，对路径规划进行平滑改进，仿真结果如图6和图7所示。由图6分析可知，在10×10栅格环境下，路径规划平滑改进后最优路径长度为13.677 3，比原有路径长度14.485 3减少了5.58%。改进前累计转弯角度为315.000 0°，改进后累计转弯角度为169.695 2°，减少了46.13%。

图7在20×20栅格环境下，经过路径规划平滑改进后的路径长度为27.329 0，比原有路径长度28.041 6减少了2.54%。改进前转弯角度为360.000 0°，改进后转弯角度为147.479 3°，减少了59.03%。

采用控制点转移策略后，平均路径长度减少量为4.28%，平均转弯角度减少量为52.58%。平滑改进前后数据对比见表4。

图7 20×20栅格环境下平滑改进前后的路径规划

表4 路径平滑前后对比

5 结束语

针对蚁群算法解决路径规划问题时存在的收敛速度慢的缺点，对启发因子矩阵初始值及更新方式进行了改进，与基本蚁群算法相比，改进后平均路径长度减少了17.6%，平均收敛代数减少了93.1%；对于在栅格环境下机器人累计转弯角度大的问题，提出了控制点转移策略，通过对控制路径走向的栅格中心点向栅格角顶点的转移，进一步缩短了路径长度，实现了路径规划的平滑改进，平滑改进后机器人的平均路径长度减少了4.28%，累计转弯角度减少了52.58%。

[1] 栗红生, 刘莹. 复杂路径下机器人路径规划优化方法仿真[J]. 计算机仿真, 2014, 31(1): 407-411.

[2] 赵开新, 孙新领, 王东署, 等. 基于改进蚁群算法的移动机器人路径规划研究[J]. 科技通报, 2017, 33(9): 76-79.

[3] GONG Y J, CHEN E, ZHANG X L, et al. AntMapper: An ant colony-based map matching approach for trajectory-based applications [J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(2): 390-401.

[4] 陈晓, 戴冉, 陈昌源. 基于Maklink图和蚁群算法的航线规划[J]. 中国航海, 2017, 40(3): 9-13.

[5] 张琦. 移动机器人的路径规划与定位技术研究[D]. 哈尔滨: 哈尔滨工业大学, 2014.

[6] DENG X Y, ZHANG L, LUO L. An improved ant colony optimization applied in robot path planning problem [J]. Journal of Computers, 2013, 8(3): 585-593.

[7] TANG B W, ZHU Z X, FANG Q, et al. Path planning and replanning for intelligent robot based on improved ant colony algorithm [J]. Applied Mechanics and Materials, 2013, 390: 495-499.

[8] 徐胜华, 宋树祥, 佘果. 一种扫地机器人路径规划的改进算法[J]. 测控技术, 2017, 36(2): 120-123, 127.

[9] 张文强, 张彦. 基于改进蚁群算法的机器人三维空间路径规划[J]. 组合机床与自动化加工技术, 2018(4): 73-75.

[10] 朱艳, 游晓明, 刘升, 等. 基于改进蚁群算法的机器人路径规划问题研究[J/OL].计算机工程与应用. [2018-05-22]. http://kns.cnki.net/kcms/detail/11.2127.TP. 20180313.0951.014.html.

[11] 王辉, 王景良, 朱龙彪, 等. 基于改进蚁群算法的泊车系统路径规划[J]. 控制工程, 2018, 25(2): 253-258.

[12] 王志中. 基于改进蚁群算法的移动机器人路径规划研究[J]. 机械设计与制造, 2018(1): 242-244.

[13] 张玮, 马焱, 赵捍东, 等. 基于改进烟花-蚁群混合算法的智能移动体避障路径规划[J/OL]. 控制与决策. [2018-07-03]. https://doi.org/10.13195/j.kzyjc.2017.0870.

[14] 王红君, 徐军, 赵辉, 等. 基于平滑蚁群算法的机器人路径规划[J]. 燕山大学学报, 2017, 41(3): 278-282.

[15] 史恩秀, 陈敏敏, 李俊, 等. 基于蚁群算法的移动机器人全局路径规划方法研究[J]. 农业机械学报, 2014, 45(6): 53-57.

[16] 龚星宇, 常心坦, 贾澎涛, 等. 基于蚁群算法的井下救援路径优化方法[J]. 工矿自动化, 2018, 44(3): 76-81.

[17] 顾军华, 孟慧婕, 夏红梅, 等. 基于改进蚁群算法的多机器人路径规划研究[J]. 河北工业大学学报, 2016, 45(5): 28-34.

[18] SHU J, WU L, HAN B, et al. Enhanced multi‐dimensional power network planning based on ant colony optimization [J]. International Transactions on Electrical Energy Systems, 2015, 25(7): 1204-1222.

[19] ZHANG W B, GONG X P, HAN G J, et al. An improved ant colony algorithm for path planning in one scenic area with many spots [J]. IEEE Access, 2017, 5: 13260-13269.

[20] 万晓凤, 胡伟, 方武义, 等. 基于改进蚁群算法的机器人路径规划研究[J]. 计算机工程与应用, 2014, 50(18): 63-66.

[21] 黄辰, 费继友, 刘洋, 等. 基于动态反馈A*蚁群算法的平滑路径规划方法[J]. 农业机械学报, 2017, 48(4): 34-40.

Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm

SUN Rui, ZHANG Wen-sheng

(School of Traffic and Transportation, Shijiazhuang Tiedao University, Shijiazhuang Hebei 050043, China)

A smooth path planning method based on improved ant colony algorithm is proposed for mobile robot in this paper.In order to overcome the disadvantage of slow convergence rate of ant colony algorithm in solving path planning problem,the initial value and updating method of the matrix of heuristic factors are improved. Compared with the results that the heuristic factor has not been improved, the average path length is reduced by 17.6%, and the average convergence algebra is decreased by 93.1%.The control point transfer strategy is proposed to solve the problem of large cumulative turning angle of the robot when obstacles exist in the grid environment.Based on the previous improvement,a smooth improvement of path planning is achieved by transferring the central point of grid to the vertex of grid. The path planning simulation results show that the average path length of the robot is decreased by 4.28% and the cumulative turning angle is reduced by 52.58%, compared with the non-smooth improvement.

ant colony algorithm; mobile robot; path planning; control point transfer strategy

TP 391

10.11996/JG.j.2095-302X.2019020344

A

2095-302X(2019)02-0344-07

2018-07-07；

2018-09-19

河北省重点研发计划项目(18390324D)；石家庄市科学技术研究与发展计划项目(181130034A，191260411A)；石家庄铁道大学研究生创新项目(YC2019044)

孙 瑞(1995-)，女，河北衡水人，硕士研究生。主要研究方向为智能优化算法。E-mail：sunr3617@163.com

张文胜(1971-)，男，宁夏隆德人，教授，博士。主要研究方向为交通信息。E-mail：zws@stdu.edu.cn