张苏英 赵国花 郭宝樑 于佳兴 刘慧贤

摘 要：针对移动机器人路径规划中的传统蚁群算法收敛精度低、易陷入局部最优等问题，提出一种改进蚁群算法。首先，对算法的转移概率进行改进，加入转向代价，减少不必要的转折，并针对启发函数启发性能不够强，对路径启发信息进行改进;然后，提出一种自适应的参数调整伪随机状态转移策略，动态改变参数值，避免过早陷入搜索停滞，增强搜索的全面性，同时对信息素更新方式进行改进，调整信息素挥发系数，保持蚂蚁发现最优路径的能力;最后，通过Matlab与其他算法进行对比分析。仿真结果表明，改进的蚁群算法收敛速度快，且路径长度和算法迭代次数有明显减少，能得到全局最优路径。改进蚁群算法具有可行性、有效性，在移动机器人路径规划中有一定的应用价值。

关键词：机器人控制;信息素;路径规划;改进的蚁群算法;自适应参数调整

中图分类号：TP242 文献标志码：A

doi： 10.7535/hbgykj.2019yx06004

文章编号：1008-1534（2019）06-0390-06

Abstract：An improved ant colony algorithm is proposed for the traditional ant colony algorithm in mobile robot path planning with low convergence precision and easy to fall into local optimum.Firstly， the transition probability of the algorithm is improved， the steering cost is added， the unnecessary turning is reduced， and the heuristic performance of the heuristic function is not strong enough to improve the path heuristic information.Then an adaptive parameter adjustment pseudo-random state transition strategy is proposed to dynamically change the parameter values to avoid prematurely falling into search stagnation and enhance the comprehensiveness of the search. At the same time， the pheromone update method is improved， the pheromone volatilization coefficient is adjusted， and the ant is found to find the optimal path capability. Finally， through matlab and other algorithms， the simulation results show that the improved ant colony algorithm has a fast convergence speed， the path length and algorithm iteration number are significantly reduced， and the global optimal path can be obtained， Proving the feasibility and effectiveness of the improved ant colony algorithm， which has certain application value in mobile robot path planning.

Keywords：robot control;pheromone; path planning; improved ant colony algorithm; adaptive parameter adjusting

隨着科学技术的迅猛发展，移动机器人被广泛用于货仓物流、农业、工业、医疗等领域[1]。路径规划是移动机器人避障研究的重要技术之一，即在障碍物条件下能够规划出一条从起始点到终止点的最佳无撞击路径[2]。从过去到现在，无论国内还是国外优秀学者都对移动机器人的路径规划问题做了很多探究，不仅包括Dijkstra算法[3]等传统算法，也包括遗传算法[4]等智能优化算法。这些算法在解决最短路径问题上有了很大的提高，但是在复杂状态下对机器人的要求就会增多，不单单要考虑路径最短，因此，寻找一种最优路径算法成为研究重点。

蚁群算法是模仿自然界中蚂蚁觅食过程发展起来的一种优化方法[5]，具有适应性强、易与其他算法相结合等特点。蚁群算法相比于其他算法是一种相对成熟的方法，但也有易于陷入局部最优等缺陷[6]。面对这样的缺陷，文献[7]加入目标点吸引机制和局部、全局相结合的策略进行信息素的更新;文献[8]利用人工势场法构建势场导向权改变状态转移概率，使算法收敛性变强，但是算法存在局限性，会出现停滞现象;文献[9]将蚁群算法与遗传算法进行结合，把每次迭代产生的可以行走的路径作为父代种群，通过选择交叉变异得到本次迭代最优路径。

为了更好地解决机器人的避障问题，本文针对蚁群算法的缺陷，引入转向代价，提高路径的平滑性;采用自适应调整伪随机状态转移策略，在算法的前期，参数q0对搜索干预大，从而减少陷入局部最优的程度，随着迭代的增强，在搜索的后期，参数q0对搜索的干预减小，算法使用轮盘赌法进行路径选择的几率增大;对全局信息素的更新方式进行改进，加强最优路径的选择。

1 路径规划问题的基本算法

1.1 栅格法建模

利用栅格法[10]将外部环境抽象离散化，建立机器人二维运动环境模型，使复杂问题简单化，减少数据的计算量。栅格分为可行和不可行栅格，考虑到机器人自身长度、安全性、所占体积等，对环境中的阻隔物进行膨化处理，不足一个栅格的将其转换为一个栅格，存在障碍物的栅格属于不能够行走的栅格[11]。机器人在能够行走的栅格环境下，一共可以有8个行走方向[12]。以机器人所在栅格位置为中心的8个方向任由机器人选择，如图1所示。

1.2 传统蚁群算法

DORIGO等提出了一种依赖于种群的启发式随机查找算法[13]。蚂蚁在环境中觅食时会倾向于选择信息素高的路径行走，从而形成一种正反馈机制[14]。蚁群算法不可忽略以下2个重要方面：状态转移概率选择以及局部、全局信息素更新[15]。

1.3 概率选择

1.4 信息素更新

在蚂蚁全部结束巡游后，不同轨道上的信息素按式（2）运行：

2 改进的蚁群算法

2.1 转移概率的改进

考虑到在实际环境中，机器人大幅度转弯会消耗时间和能量，在机器人路径规划中应该减少不必要的转折，提高路径的平滑度。本文在计算路径转移概率时引入转角启发信息，转角越小，选择此路径的概率越大。节点转移概率公式为

传统蚁群算法的启发函数启发性能不够强，所以引入下一节点j到目标节点z之间的距离。

改进后的启发函数如式（7）所示。

2.2 自适应参数调整策略

在传统蚁群算法中，采用轮盘赌法进行路径决择。由于在算法早期存在差异不显著的信息素浓度，造成蚁群算法早期收敛速度较慢，而且在环境规模很大的情况下，传统蚁群容易出现停滞现象，减弱了算法对于最优解的搜索，大大减弱了自适应调整的作用。所以，本文添加状态转移规则可调控制参数q0，具体如式（8）、式（9）所示。

考虑到蚁群在迭代过程中搜索特性的需求，在算法的初期q0大概率大于q，使算法在前期路径以伪随机概率选择方式为主，加快算法早期收敛，当到算法的后期，q0选取较小的数，从而使蚂蚁随机性进行寻优。

2.3 全局信息素更新机制

每完成一次迭代后，按照式（10）进行更新。

蚂蚁每次迭代完成后，如果La>Ln，那就意味着本次迭代的路径更短，式（10）就应该加强本次迭代信息素的强度，保存本次迭代的最优路径;反之，要是La

2.4 挥发系数ρ的改进

ρ的设置决定着蚂蚁搜索的效果，也极大地影响着算法实现的性能，所以对挥发系数ρ做相应的改进如式（11）所示。

3 算法详细步骤

运行步骤如下。

步骤1：栅格环境地图构建;

步骤2：对涉及到的参数进行分配，包括机器人初始坐标S，终止坐标Z，蚂蚁数量m，启发因子α，β等参数;

步骤3：蚂蚁路径选择，根据式（4）、式（8）选择下一节点;

步骤4：找出历史迭代最优La，本次迭代最优路径Ln，本次迭代最差路径LA，对蚂蚁应用式（10）进行全局信息素更新;

步骤5：判断是否达到最大迭代次数，条件成立得出最佳路径，否则执行步骤2。

算法实现流程图如图3所示。

4 仿真研究

为了使改进后的算法更具有说服力，在Matlab 2016a仿真平台进行对比，设置算法初始参数，α=4，β=8，ρ=0.7，最大循环次数Nmax=50，蚂蚁数量m=50，Q=1，为了验证改进蚁群算法的优越性，在不同环境下将其与传统蚁群算法及文献[7]算法进行比较。

4.1 20×20栅格地图下仿真结果对比

由图4—图6可以直观地看出，传统蚁群算法陷入局部最优，虽然最终也找到了一条最优路径，但路径质量不如改进后的蚁群算法。改进后的蚁群算法对启发信息进行了改进，为蚁群提供了相对正确的初始启发信息，从而使蚂蚁找到了较好的路径，并且改进的蚁群算法在转弯次数上明显少于传统蚁群算法，对路径进行了平滑处理，从而提高了算法的收敛速度。对比结果如表1所示，在简单环境下，相比于传统蚁群算法，本文算法有较高的收敛速度，运行时间也较短。

4.2 30×30栅格地图下仿真结果对比

为了进一步了解本文算法在复杂环境下的全局

搜索能力，在复杂环境下对传统蚁群、文献[7]算法以及本文算法进行了对比，如图7—图10所示。

由图7—图10可以看出，为了对比明显，在地图尺寸和环境复杂度上进行了增强，故3种算法的迭代次数都有所增长，但是传统蚁群算法依然陷入了局部最优，文献[7]对启发信息进行了修改，引入了局部全局信息素更新机制，算法的收敛性能和全局寻优能力得到了提升，在迭代15次后找到了最优解，而本文引入了自适应参数调整策略，在前期加速收敛，算法在迭代初期就取得了较小的初始值，通过引入转弯角，本文算法转弯次数的优越性非常明显，路径更加平滑，仅用了9次就找到了最优路径。仿真结果对比见表2。

5 结 语

本文针对蚁群算法存在的不足，在栅格地图中对蚁群算法进行了自适应参数调整，在状态转移概率中引入转角启发信息，减少了运动过程中不必要的转弯，实现路径平滑，同时引入邻域栅格和目标点的距离因子构建新的啟发函数，使得算法搜索路径方向性更强;通过自适应参数调整策略，动态地改变了参数值，提高了算法的收敛精度，保证蚂蚁搜索的全局性;采用全局信息素更新方式进行信息素的更新，在规划中对最短路径进行信息素的加强，非最短路径进行信息素的减弱，通过对挥发系数ρ的自适应调整，防止路径信息素轨迹量差异过大。本文改进算法相对于传统蚁群算法和文献[7]算法，寻找最优路径的能力更强，有很好的应用价值。

本文只是在全局静态环境下展开了研究，没有考虑动态障碍物。在接下来的研究中将结合动态避障，进一步提高算法路径规划的能力。

参考文献/References：

[1]欧青立，何克忠.室外智能移动机器人的发展及其关键技术研究[J].机器人，2000， 22（6）：519-526.

OU Qingli， HE Kezhong. Research on key techniques and development of outdoor intelligent autonomous mobile robot[J]. Robot， 2000， 22（6）： 519-526.

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

ZHANG Dianfu， LIU Fu. Research and development trend of path planning based on artificial potential field method[J]. Computer Engineering and Science， 2013， 35（6）： 88-95.

[3]田茹会.基于扇形优化Dijkstra算法的舰船最佳导航路线分析[J].航舰电子工程，2019， 39（5）：41-45.

TIAN Ruhui. Research on shortest route of avoid disaster of mine roadway based on Dijkstra algorithm[J]. Ship Electronic Engineering， 2019， 39（5）： 41-45.

[4]FUKUSHIMA R， WANG H， TAMURA K， et al. Dominance relation-based genetic algorithm for superior solution set search problem[J]. IEEJ Transactions on Electrical and Electronic Engineering， 2019， 14（10）：959-960.

[5]陳晓，戴冉，陈昌源.基于Maklink 图和蚁群算法的航线规划[J].中国航海，2017， 40（3）：9-13.

CHEN Xiao， DAI Ran， CHEN Changyuan. Navigation route planning with Maklink graph and ant colony algorithm[J]. Navigation of China， 2017， 40（3）： 9-13.

[6]董晔，吴丽娟.基于混合人工势场-蚁群算法的机器人避障[J].辽宁科技大学学报，2015， 38（3）：212-216.

DONG Ye， WU Lijuan. Research of robot obstacle avoidance based on hybrid artificial potential field-ant colony algorithm[J]. Journal of University of Science and Technology Liaoning， 2015， 38（3）：212-216.

[7]庄丽阳，陈树林，朱龙彪，等.基于改进蚁群算法的农用喷药机器人路径规划[J].机床与液压，2018， 46（21）：15-19.

ZHUANG Liyang， CHEN Shulin， ZHU Longbiao，et al. Path planning of agricultural spraying robot based on improved ant colony algorithm[J]. Machine Tool and Hydraulics， 2018， 46（21）： 15-19.

[8]王芳，李昆鹏，袁明新.一种人工势场导向的蚁群路径规划算法[J].计算机科学，2014， 41（11A）：47-50.

WANG Fang， LI Kunpeng， YUAN Mingxin. Ant colony algorithm based on optimization of potential field method for path planning [J]. Computer Science， 2014， 41（11A）： 47-50.

[9]吴建，李康，庞宇，等.基于差分阈值与模板匹配的心电R波提取算法[J].重庆邮电大学学报（自然科学版），2015， 27（3）：372-376.

WU Jian， LI Kang， PANG Yu，et al. Algorithm of ECG R-wave extraction based on differential threshold and template matching[J]. Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition）， 2015， 27（3）： 372-376.

[10]周东健，张兴国，马海波，等.基于栅格地图-蚁群算法的机器人最优路径规划[J].制造业自动化，2013， 12（4）：91-94.

ZHOU Dongjian， ZHANG Xingguo， MA Haibo，et al. Optimal path planning for mobile robot based on grid map with ant colony algorithm[J]. Manufacturing Automation， 2013， 12（4）： 91-94.

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

LIANG Jiajun， ZENG Bi， HE Yuanlie. Research on path planning algorithm for cleaning robot based on improved potential field grid method[J]. Journal of Guangdong University of Technology， 2016， 33（4）： 30-36.

[12]李晓静，余东满.改进蚁群算法在果蔬采摘机器人路径规划中的应用[J].江苏农业科学，2018， 46（23）：253-258.

LI Xiaojing， YU Dongman. Application of improved ant colony algorithm in path planning of fruit and vegetable picking robot[J]. Jiangsu Agricultural Science， 2018， 46（23）： 253-258.

[13]LU M， XU B， JIANG Z， et al. Automated tracking approach with ant colonies for different cell population density distribution[J]. Soft Computing， 2017， 21（14）：3977-3992.

[14]郭秀娟，張坤鹏.基于蚁群混合遗传算法的组卷问题研究[J].吉林建筑大学学报，2017， 34（4）：79-83.

GUO Xiujuan， ZHANG Kunpeng. Research on application of ant colony algorithms hybrid genetic algorithms for test paper generation problems[J]. Journal of Jilin Jianzhu University， 2017， 34（4）： 79-83.

[15]李晓静，余东满.煤炭勘探及救援机器人最优路径规划研究[J].工矿自动化，2017， 43（3）：24-29.

LI Xiaojing， YU Dongman. Research on the optimal path planning of coal exploration and rescue robot[J]. Industry and Mine Automation， 2017， 43（3）： 24-29.