基于改进蚁群算法的机器人全局路径规划研究*

2020-03-26曹新亮王智文王宇航

计算机工程与科学 2020年3期

曹新亮，王智文，冯晶，查敏，王宇航

(1.广西科技大学电气与信息工程学院，广西柳州 545006； 2.广西科技大学计算机科学与通信工程学院,广西柳州 545006； 3.广西师范大学多源信息挖掘与安全重点实验室，广西桂林 541004； 4.广西师范大学计算机科学与信息工程学院，广西桂林 541004 )

1 引言

随着科技的快速发展以及机器人的大量应用，人们对机器人的要求也越来越高，尤其表现在对机器人的智能化方面的要求，而机器人自主路径规划是实现机器人智能化的重要步骤，路径规划是指规划机器人从起点位置出发，无碰撞、安全到达指定目标位置的最优路径。迄今为止，国内外很多学者围绕机器人路径规划开展了大量研究，如传统算法有迪杰斯特拉算法[1]、A*算法[2,3]、人工势场法[4]等。随着研究的深入，传统算法已经无法很好地解决问题，对此许多学者提出了一系列的智能算法，如遗传算法、花朵授粉算法[5]、粒子群算法[6]、萤火虫算法[7]、蚁群算法[8]等，不同的算法在不同的限定条件下有着其特有的优势，但是也存在不足之处。

蚁群算法是由意大利学者Maro Dorigo首次提出的，是一种分布式仿生算法，本身具有较强的鲁棒性，但也存在着收敛速度慢、容易陷入局部最优的问题。为了解决这些问题，国内外许多学者对传统的蚁群算法进行了相应的改进。Lee[9]改进蚁群算法转移概率函数和信息素更新规则，提高了算法的寻优能力；Mouhcine等人[10]通过获取动态数据，代理协作获取最优路径，优化蚁群算法，提高了算法全局寻优性能，避免了陷入局部最优；Jiao等人[11]在多态蚁群算法中引入了自适应策略和自适应信息更新策略，避免了死锁问题，提高其全局搜索能力；Wang等人[12]通过应用禁忌表和网络权重表，缩小了算法的搜索范围，提高了搜索效率；Luo等人[13]使用伪随机状态转移规则选择路径，提高了算法的全局搜索能力和收敛速度；王志中[14]提出了蚂蚁相遇策略，提高了算法的搜索效率，改进后的算法具有更快的收敛速度；赵峰等人[15]提出了一种自适应搜索半径蚁群算法规划路径，提高了环境适应能力和收敛速度；黄于欣等人[16]改进路径启发函数，并引入动态参数调整机制，优化蚁群搜索和开发机制，有效避免算法陷入局部最优，同时提高了算法收敛速度；郑延斌等人[17]通过引入反向学习方法对蚂蚁位置进行初化分布来改进蚁群算法，提高了算法的全局搜索能力，同时利用粒子群算法中的自适应惯性权重因子调节信息素浓度Q值，使其自适应变化，避免陷入局部最优。

本文针对传统蚁群算法收敛速度慢进行改进，建立新的数学模型，使初始信息素浓度不均匀分布，并通过仿真实验与传统的蚁群算法比较，以验证改进前后算法的效果。实验结果表明，本文改进的算法能够有效地提高蚁群算法的收敛速度。

2 传统蚁群算法

2.1 蚁群算法基本原理

蚁群算法是根据蚁群觅食行为提出的一种仿生智能算法，蚂蚁在寻找食物的过程中会在经过的路径上留下信息素，而遗留下来的信息素能够被其他蚂蚁感知到，蚂蚁根据信息素浓度选择路径，优先选择信息素浓度较高的路径，这样逐渐形成一种正反馈现象。蚂蚁趋向选择较短的路径，经过的蚂蚁越多，表明信息素浓度越高，该路径上的信息素浓度就越大，其它蚂蚁选择这条路径的几率就越大，蚂蚁就是通过这种信息传递的方式选择1条较优路径进行觅食。蚁群算法中的路径选择概率和信息素浓度的更新是2个至关重要的因素，决定着算法的寻优效果。

2.2 蚁群算法模型

(1)

信息素会在蚂蚁完成1次循环后进行更新，根据式(2)～式(4)来调整信息素。

τij(t+1)=(1-ρ)τij(t)+Δτij

(2)

(3)

(4)

3 改进的蚁群算法

针对传统蚁群算法存在收敛速度慢的问题，本文提出对初始信息素进行差异化设置，防止非最优路径上的信息素对蚂蚁产生误导，从而实现快速收敛的效果。

3.1 蚁群算法的具体改进

传统蚁群算法初始信息素浓度是均匀分配的，这样算法初期搜索具有较强的盲目性，进而导致收敛速度慢等问题。蚂蚁通常根据路径上信息素浓度的差异来寻找最优路径，在信息素的引导下选择1条从起始点到目标点的完整路径，由于初始信息素浓度是相同的，而且初期搜索具有很强的盲目性，这样就会出现误导，无法选择最优路径，容易使算法陷入局部最优，影响算法寻优能力。为了避免因信息素导致算法陷入局部最优，减少错误的启发信息对蚂蚁的误导，提高其寻优能力，考虑机器人移动过程中的实际工作环境，本文构造新的数学模型，对初始信息素浓度进行预先的差异化设置，以达到快速寻优的效果。如图1所示，由于最优路径多集中在起始点S和目标点E的连线L附近区域，同时受环境中障碍物的影响。首先根据起始点和目标点在栅格地图上选取出优选区域，预设优选区域外的初始信息素的值τ0，同时在优选区域内预设初始信息素值C，并为优选区域内的点设定不同的增量，具体设置方法如图2所示：在优选区域内，节点j是蚂蚁下一步移动的节点，根据起始点与目标点的直线距离X与节点j到起始点和目标点的距离和的比值设置节点j的信息素浓度增量，对该区域的初始信息素进行差异化增加，使得对初始信息素浓度的差异化设置更符合实际求解问题的要求。

Figure 1 Mathematical model diagram of initial pheromone setting 图1 初始信息素设置数学模型图

Figure 2 Initial pheromone differentiation setting图2 初始信息素差异化设置

假设蚁群算法寻找选择节点j时，节点j到起始点S的距离为X1,到目标点E的距离为X2，X1+X2的值越小，则认为该点越优。在该点设定的初始信息素浓度越高，越能满足实际需求。如图1和图2所示，优选区域内各位置的初始信息素浓度增量是根据建立的数学模型进行设置的，以起始点S和目标点E为焦点可以得到无数个椭圆，这样就可以将优选区域划分成多个部分，每个部分分别具有不同的信息素浓度增量，但在优选区域中会存在一系列信息素相同的节点。考虑存在障碍物的因素，为了避免算法在寻优时选择跨越性较大，应尽量靠近上一个节点。所以，选择节点j时，先判断上一节点在椭圆中的位置，再对比X1、X2的值的大小。若上一个节点靠近起始点S的位置，即当X1X2时，选择节点j,这样避免了优化不稳定性。

节点j的初始信息素浓度值计算如式(5)所示：

(5)

其中，τ0为优选区域以外栅格地图节点的信息素值，C为优选区域内节点信息素值，R为优选区域内节点集合，λ[X/(X1+X2)]为优选区域内栅格地图位置的信息素增量，λ为信息素增量系数，X为理想最优路径SE的长度，X1为节点j到起始点S的距离长度，X2为节点j到目标点E的距离长度。

3.2 改进算法步骤

本文提出的改进蚁群算法的实施步骤分为5个阶段:

(1) 设置蚁群算法基本参数：蚂蚁总量M、信息启发系数α、期望启发系数β、信息素挥发系数ρ、调整系数δ、最大迭代次数Nmax。

(2) 利用栅格法对环境地图进行建模，根据起始点和目标点选出优选区域，增加其信息素初始值，并根据节点与起始点和目标点的距离之和和起始点与目标点之间距离的比例对信息素进行差异化增量设置。

(3) 寻找路径，对禁忌表进行初始化并将起点加入其中，根据状态转移概率(如式(1)所示) 寻找下一可达节点，直到蚂蚁选取的节点为目标点时，停止搜索。

(4) 判断循环迭代次数是否达到设定值，如果达到，则保存信息，否则继续进行路径搜索。

(5) 得到最优路径，算法终止。

4 仿真实验与结果分析

4.1 实验环境建模

在实际工作环境中，移动机器人工作环境是复杂多变的，且为三维空间。为了便于研究，本文对环境进行简化建模。栅格法是一种常用的环境表示方法，因其简单方便(二维环境)，环境建模的复杂性小，因而本文环境建模采用栅格法[18]。在栅格地图中，工作环境被划分为很多栅格，其中包括有障碍物和无障碍的栅格，在仿真程序中用 0 表示此栅格无障碍物，机器人可以通过此栅格，用1表示栅格有障碍物，机器人无法通过，需选择其他栅格。栅格的尺寸大小可根据工作环境中的障碍物尺寸以及安全距离进行设置。为了实现程序仿真，需要对栅格进行标识，如图 3 所示，以10×10的栅格环境为例来说明。

Figure 3 Relationship between raster map and number图3 栅格地图与编号的关系

如图3所示，白色栅格表示无障碍物的栅格，黑色栅格则表示有障碍物的栅格，在地图中对每个栅格编号，不同序号的栅格在坐标系中的坐标可用式(6)来表示。

(6)

其中，mod为取余运算，ceil表示向后取整，Ni是对应栅格的标号，N表示每一列的栅格数量，取栅格中心位置作为栅格在坐标系中的坐标。

这样机器人全局路径规划的问题就转变成了利用算法在栅格地图上寻找由起始点S到目标点E的有序的栅格子集，这些栅格子集的中心连线便是算法寻找的路径。

4.2 实验结果及分析

蚁群算法是一种概率型算法，具有一定随机性，算法的性能可以依据算法运行一次得到最优解的可能性大小来判断。在20×20的地图环境中将传统蚁群算法和本文改进的蚁群算法各运行 20 次进行分析，其中蚂蚁的规模M设置为50，迭代次数为100，信息启发式因子α为1，期望启发式因子β为7，信息素挥发系数ρ为0.3，参数Q为1，C为0.5。对于蚁群算法的参数选取，是基于大量的实验仿真得到的，C设置为0.5，效果更优。

Table 1 Algorithm simulation results in 20×20 environment 表1 20×20环境中算法仿真结果

由图4～图6及表1可知，在20×20环境下，改进后的蚁群算法收敛速度较快，主要原因是传统蚁群算法的初始信息素浓度设置的值是相同的，导致算法在迭代初期具有很大的搜索盲目性，进而会收敛较慢，而改进后的算法在初期就划定全局最优区域，并赋予一个较小的初值，同时在优选区域中，根据新的初始信息素浓度设置模型，对栅格地图中各点初始信息素浓度进行差异化设置，避免了前期搜索的盲目性，能更快地寻找最优路径，提高了算法的收敛速度。本文改进的蚁群算法收敛速度要快于传统蚁群算法。

5 结束语

传统蚁群算法存在着收敛速度慢的不足，寻优效果差，本文提出了一种改进蚁群算法，通过不均匀设置初始信息浓度，使得算法在开始寻优时，能避免寻优盲目性，优选区域的存在，使得寻优初期就在一个较好的范围内，大大提高算法的收敛速度和寻优效果。考虑到研究机器人全局路径问题时，障碍物多是静态的，为了降低空间复杂度，将三维空间降维为二维空间，本文采用栅格地图对环境建模，并建立了新的模型，通过Matlab仿真实验，验证了本文改进蚁群算法对解决机器人路径规划问题的有效性和可行性。本文只是针对蚁群算法其中一点不足做出改进，后期将对算法的其他性能做进一步研究，希望本文做出的改进能为后续工作提供帮助，同时为其他研究者提供一些参考。