一种改进蚁群算法的移动机器人路径规划

颜杰 秦飞舟 翟帅华

摘 要：路径规划是移动机器人运动控制中的关键问题。针对传统蚁群算法在机器人全局路径规划中存在收敛速度慢、易陷入局部最优等缺点，提出一种改进型蚁群路径规划算法。首先，通过栅格法建立机器人运动环境模型，然后在传统蚁群算法基础上引入A*搜索算法的估价函数思想，改进蚁群算法的启发函数，增加目标节点与可选行进节点数对启发函数的影响。其次，在信息素更新公式中，通过引入Logistic增长函数对信息素挥发因子作自适应调整，提高算法速度与精度。最后，通过Matlab仿真实验证明，改进蚁群算法比传统算法在路径搜索速度和精度上都有较大提升。

关键词：移动机器人;路径规划;改进蚁群算法

DOI：10. 11907/rjdk. 182031

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）002-0005-04

Abstract： Path planning is a key problem in motion control of mobile robot. An improved ant colony path planning algorithm is proposed to solve the problems of slow convergence rate and getting stuck in the local optimum easily. First robot movement environment model is established by the grid method， and then on the basis of traditional ant colony algorithm， the evaluation function of A* search algorithm is produced to improve ant colony algorithm function， increase the target node and optional node number's influence on the heuristic function. Secondly， in the update formula of pheromones， the speed and accuracy of the algorithm are improved by introducing logistic growth function to adjust the volatility factor of pheromones. Finally， through the Matlab simulation experiment， it is verified that the improved ant colony algorithm has greatly improved the speed and precision of the path search compared with the traditional algorithm.

Key Words： mobile robot; path planning; improved ant colony algorithm

0 引言

智能机器人是当下研究的热门，其中路径规划是智能机器人研究领域的核心内容之一。机器人路径规划是指在有障碍物的环境下，按照一定评价标准，找出一条从起点到终点的最优无碰路径[1-3]。机器人路径规划方法可以分为全部环境信息已知的全局路径规划和信息未知的局部路径规划[4-5]。常见的局部路径规划方法有模糊控制法[6-8]、人工势场法[9-10]等。常见的全局路径规划方法有蚁群算法[11-13]、拓扑图法[14]、可视图法[15]等。其中，蚁群算法是由学者Marco Dorigo[16]在20世纪90年代首次提出的，因其具有良好的鲁棒性且易与其它算法相结合，被广泛用于机器人全局路径规划中。针对传统蚁群算法存在收敛速度慢、易陷入局部最优等问题，国内外学者通过引入方向角参数[17]、制定蚂蚁回退策略[18]、更改信息素更新策略[19-20]等方法对蚁群算法进行改进并取得了不错效果。本文在已有蚁群算法基础上，利用A*算法的估价函数思想改进蚁群算法的启发函数，同时引入Logistic函数自适应调整信息素挥发因子，进一步提高蚁群算法在全局路径规划中的搜索速度和精度。

1 环境建模

基于蚁群算法的机器人路径规划是一种在已知环境信息下的路径规划方法。因此，首先需要对环境进行建模处理，将环境信息转化为机器人可识别的数学模型。本文采用栅格法[21]建立机器人工作的二维环境模型，直接在机器人工作环境中建立二维直角坐标系，以大小固定的栅格对环境进行割分。每个栅格按序号法表示，取每个栅格中心点坐标为栅格坐标，并将其作为机器人行进点，栅格序号与坐标之间可以相互转化。划分后的栅格分为障碍栅格和可行栅格，考虑到机器人自身尺寸影响，把障碍物的边界按机器人本体在長或宽方向上最大尺度的[12]长度进行扩展，则可将机器人看作质点忽略不计，栅格法建立的环境模型如图1所示。图中黑色栅格为障碍栅格，白色栅格为可行栅格，除边界栅格外，每个栅格与8个栅格相连，除去障碍栅格，其它相连栅格为该栅格的可选行进栅格节点。

2 传统蚁群算法路径规划

蚁群算法是一种通过随机搜索空间寻找目标最优解的算法，主要利用蚁群之间的信息传递，通过正反馈寻求问题的最优解。蚁群算法是一种新型的启发式智能优化算法，蚁群在寻找食物过程中，各蚂蚁可以通过遗留在当前节点路径上的信息素浓度以及启发信息确定当前节点到下一节点的路径转移概率，再根据路径转移概率选择行走路径。路径转移概率的数学模型可以用式（1）描述。

式（1）中，[pkij（t）]为t时刻蚂蚁k从节点i转移到节点j的转移概率;[Sk]为蚂蚁k在当前节点行进到下一个可选节点的集合，其中不包括蚂蚁k已经行进过的节点与障碍节点;[τij（t）]表示t时刻节点i到节点j之间路径的信息素浓度，初始时刻各路径的信息素浓度相同，即[τij（0）]=C，C为某一常数;[ηij（t）]为表示節点i到节点j的启发函数，也叫能见度，其表达式为[ηij（t）=1/dij]，其中[dij]为节点i到节点j的欧式距离;[α]为信息素浓度启发因子，代表信息素浓度的相对重要程度，该因子越大，蚂蚁越倾向于选择其它蚂蚁走过的路程;[β]为能见度启发因子，表示能见度相对重要程度。

按照上述规则，蚂蚁可以确定当前节点到每个可选节点的路径转移概率，再根据转轮赌法确定下一个行进节点。当所有蚂蚁从起点到达终点完成一轮路径搜索后，需要计算每只蚂蚁所经过的路径长度，并保存最小路径长度，然后更新每条路径的信息素浓度，信息素浓度的更新规则为挥发一部分、增加一部分，如式（2）、式（3）所示。

其中，[τij（t+1）]为更新后的节点i到节点j路径上的信息素浓度;[τij（t）]为该路径上当前信息素浓度;[ρ]为信息素挥发因子，其取值为[0，1]，其值越大信息素浓度挥发得越快;[Δτij（t）]为搜索过程中经过该路径的所有蚂蚁留下的信息素浓度之和。

每只经过该路径的蚂蚁遗留的信息浓度计算公式为式（4），其中LK为蚂蚁k完成路径搜索后行走的总路径长度，Q为蚂蚁携带的信息素浓度因子。从式（4）中可以看到，蚂蚁走的总路径越短，遗留在路径上的信息素浓度越高。蚁群正是通过以上路径选择规则和信息素更新规则，使得较优路径上的信息素越来越多，而较差路径上的信息素越来越少，从而寻找出一条最优行进路径。

3 改进蚁群算法路径规划

3.1 启发函数改进

在传统蚁群算法中，启发函数[ηij（t）]仅仅考虑了当前节点到下一节点的距离大小，这样会使得算法初期搜索具有很大的盲目性，降低算法的搜索精度与速度。因此，在传统蚁群算法基础上，引入A*算法的估价函数思想，增加算法搜索的指向性，提高算法的搜索速度与精度。估价函数的表达式如式（5）。

其中，[f（n）]为当前节点的估价函数;[g（n）]为当前节点到可选节点的实际代价，取值为当前节点i到可选节点j之间的欧式距离[dij]，即[g（n）=dij];[h（n）]为下一可选节点j到目标节点g之间的最小路径估计代价。[h（n）]的值主要考虑两点因素：下一可选节点j到目标节点g的欧式距离[djg];下一节点j的可选行走节点数Nj。表达式如式（6）。

其中，Nj为下一节点j的可选行走节点数，其值越大，表明该节点的路径选择越多，算法的搜索多样性越高，因此相应的估计代价值越小;[djg]为下一可选节点j到目标节点g的欧式距离，其值越小，表明下一节点到目标节点的朝向性越好，估计代价值也越小。但考虑到实际环境中由于障碍物的存在，当可选节点离目标节点较远时，实际路径长度远大于估计值，此时估计路径长度应适当扩大，当距离较近时，实际值接近甚至等于估计值。因此对其进行加权处理，引入加权系数[μdjg（μ>1）]，当[djg]较大时，加权系数大，估计路径值也更大。加权系数会随着[djg]的减小而减小，直至减到1，估计值等于实际值。最终得到新启发函数[ηij（t）]式（7）。

3.2 挥发因子自适应调整

在蚁群算法搜索最优解过程中，信息素浓度的更新规则起极其重要作用，信息素浓度更新公式中的挥发因子直接影响蚁群算法的性能。当信息素挥发因子的值过小时，各条路径的信息素浓度差别较小，使得蚁群对每只蚂蚁的引导性降低，从而降低算法搜索速度。当信息素挥发因子过大时，使得蚁群对蚂蚁的引导作用过强，导致蚂蚁搜索更多路径的可能性变小，更易陷入局部最优解。因此，引入Logistic增长函数对挥发因子进行自适应调整。Logistic增长函数是一种常见的S形函数，如图2所示。

由图2可以看到，Logistic增长函数最初因变量Y从某一最小值开始随着X增加而缓慢增长;当X值到达一定量后，Y值随X值的增加速度陡然加快;当X继续增加到一定量时，Y值随X值的增加速度开始急速变慢，且Y值随X值的增加不断趋近于某一极限值。Logistic函数表达式为：

式（8）中，参数Theta1为y值的上边界，Theta2为y值的下边界，Theta3为增长线中心点的x值，Theta4的值可以控制增长线的增长速度。本文将该函数用于挥发系数自适应调整，将迭代次数t作为自变量，挥发因子[ρ]作为因变量。在算法前期，使挥发因子较小，减小蚁群的引导作用，增加蚂蚁的搜索解范围，提高算法精度。随着算法进行，挥发因子快速增加，增大蚁群引导作用，提高蚁群搜索速度，使算法快速收敛。同时针对不同环境，可以通过设定Theta1、Theta2、Theta3、Theta4的值，确定挥发因子最大值、最小值以及挥发因子的增长速度。改进后算法表达式为：

4 算法仿真测试

为了验证改进蚁群算法在机器人路径规划中的有效性与优越性，通过Matlab 2014a软件对算法进行仿真测试。首先搭建两个机器人运动环境栅格模型：较复杂环境模型与简单环境模型。复杂环境模型下设置初始蚁群蚂蚁数量60，最大迭代次数200次;简单环境模型下设置初始蚁群蚂蚁数量50，最大迭代次数150。在简单环境下，改进蚁群算法与传统算法规划路径及收敛速度如图3、图4、图5所示。

从图3可以看到，在较简单环境下，两种算法都能够有效规划最优行驶路径，但对比两种算法的收敛速度，可以看出传统算法经历53次迭代才最终收敛，而改进算法迭代40次后就进入收敛状态，改进算法的搜索速度有明显提升。

复杂环境下的路径规划仿真结果如图6、图7、图8所示。通过对比图6、图7可以看出，在较复杂环境下，改进算法规划的路径更短，转折点更少，路径规划效果更好。图8为两种算法的最优路径长度与收敛速度对比，其中上方曲线为传统算法的收敛曲线，下方曲线为改进算法的收敛曲线。传统算法经过105次迭代后达到最小路径，最小路径长度为38，而改進算法仅经过76次迭代收敛到最小路径，且最小路径长度为35。改进后的算法在搜索精度和速度上都有了很大提升。

5 结语

本文针对传统蚁群路径规划算法在搜索速度和精度上的不足，对蚁群算法进行了改进。通过在启发函数中引入估价函数，加入目标节点和可选行进节点数对路径选择概率的影响，降低了算法前期搜索的盲目性。同时，通过引入Logistic函数自适应调整信息素挥发因子，既保证了算法前期能够大范围搜索，又使得算法后期能够快速收敛，提高了算法搜索的速度和精度。仿真实验结果表明，改进算法相比传统算法在搜索次数、最优路径长度上都有所改进，具有更好的路径规划效果。

参考文献：

[1] 任玉洁，付丽霞，张勇，等. 基于平滑A*人工势场法的机器人动态路径规划[J]. 软件导刊，2018，17（1）：8-10.

[2] 高涵，高柏军. 移动机器人路径规划方法研究[J]. 现代仪器与医疗，2015，21（5）：14-17.

[3] 王殿君. 基于改进A*算法的室内移动机器人路径规划[J]. 清华大学学报：自然科学版，2012，52（8）：1085-1089.

[4] FAKOOR M，KOSARI A，JAFARZADEH M. Humanoid robot path planning with fuzzy Markov decision processes[J]. Journal of Applied Research & Technology，2016，14（5）：300-310.

[5] 周文卷. 复杂环境下自主移动机器人路径规划方法的研究[D]. 长春：吉林大学，2014.

[6] MEHD I，FATEH M，FATEH S. A precise robust fuzzy control of robots using voltage control strategy[J]. International Journal of Automation and Computing，2013，10（1）：64-72.

[7] 施磊磊，施化吉，束长波，等. 改进的模糊控制算法在机器人路径规划中的应用[J]. 软件导刊，2014，13（11）：46-48.

[8] 彭玉青，李木，张媛媛. 基于改进模糊算法的移动机器人避障[J]. 计算机应用，2015，35（8）：2256-2260.

[9] 李奕铭. 基于人工势场法的移动机器人避障研究[D]. 合肥：合肥工业大学，2013.

[10] 张殿富，刘福. 基于人工势场法的路径规划方法研究及展望[J]. 计算机工程与科学，2013，35（6）：88-95.

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

[12] ZHANG K，YUAN C M，GAO X S. A greedy algorithm for feedrate planning of CNC machines along curved tool paths with confined jerk[J].  Robotics and Computer Integrated Manufacturing，2012，28（4）：472-483.

[13] 夏小云，周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报，2016，11（1）：27-36.

[14] 李明磊，赵杰，李戈. 面向方形节点拓扑地图下的移动机器人路径规划算法研究[J]. 机械与电子，2015（10）：67-70.

[15] 陈超，唐坚，靳祖光. 一种基于可视图法导盲机器人路径规划的研究[J]. 机械科学与技术，2014，33（4）：490-495.

[16] 李士勇，陈勇强，李研. 蚁群算法及其应用[M]. 哈尔滨：哈尔滨出版社，2004.

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

[18] 侯欣蕾，于莲芝. 基于改进蚁群算法的移动机器人路径规划[J]. 软件导刊，2017，16（12）：162-164.

[19] MOHAMMAD S M，SAEED D A，FARSHID E，et al.An ant colony algorithm （ACA） for solving the new integrated model of job shop scheduling and conflictfree routing of AGVs[J]. Computers and Industrial Engineering，2015，86（C）： 2-13.

[20] 王沛栋. 改进蚁群算法及在路径规划问题的应用研究[D]. 青岛：中国海洋大学，2012.

[21] 梁嘉俊，曾碧，何元烈. 基于改进势场栅格法的清洁机器人路径规划算法研究[J]. 广东工业大学学报，2016，33（4）：30-36.

（责任编辑：何 丽）