面向机器人全局路径规划的改进蚁群算法研究

2022-01-22张天瑞吴宝库周福强

计算机工程与应用 2022年1期

张天瑞，吴宝库，周福强

沈阳大学机械工程学院，沈阳 110044

近几年，国内外科学技术水平与自动化程度逐渐提升，移动机器人的应用日益广泛。例如在仓储车间中机器人可以替代人工搬运货物，既能提升搬运效率，又可以降低危险事故的发生，同时为企业节省大量人工成本。在智慧医疗领域，移动机器人也有着巨大的应用价值，例如可以代替人工将食物从厨房运送到病房、运输一些被污染的医疗废品、运输清洁手推车等，可大幅度提升医院的运行效率[1-2]。而优秀的路径规划能力是移动机器人的重要指标。路径规划是指移动机器人从起点开始规划出一条到终点的最佳移动路径，且有能力避开环境中存在的障碍物，不与其发生碰撞，防止危险的发生[3]，该路径的质量直接影响到移动机器人系统的工作稳定性与运行效率[3-5]。全局路径规划作为机器人领域的一个重要研究对象[6]，专家学者已进行了大量科研工作，例如遗传算法[7]、粒子群算法[8]、蚁群算法等优化算法[9]等。遗传算法是借鉴生物界的进化规律所设计的算法，在求解很多复杂优化问题方面，具有出色的性能，例如组合优化[10]、车间调度[11]等领域，同时在机器人移动路径规划方面也有着广泛的应用[12]。粒子群算法受鸟类寻找食物的过程启发，具有收敛速度快的特点，可应用于复杂的多目标优化[13]、装配线平衡[14]、机器人路径规划[15]等方面。

Dorigo[16]模拟自然界中蚁群觅食过程中搜寻可行路径的方式提出蚁群算法，其全局优化能力较强，因此非常适合用于优化sink移动距离[17]、机器人全局路径规划[18]等问题，然而在实际应用中，基本蚁群算法易出现局部极小值、收敛速度慢等问题，因而国内外众多学者以不同的方式对其进行了优化。文献[19]提出一种16方向24邻域的路径搜索方式，并对启发函数进行改进，使得蚂蚁有更多的移动路径可供选择，在简单的栅格地图可有效缩短路径长度，但是在相对复杂的环境中，此方法效果并不明显。文献[20]在概率转移函数中引入了权重因子，同时改进了信息的更新方式，其仿真结果表明改进后的算法收敛速度有所提高，最优路径更短，但是其搜索结果并不稳定。文献[21]提出了改进改进免疫遗传优化蚁群算法，可依照具体情况来调整变异概率与方式，并且可自适应更新个体免疫位长度，然后将改进后的变异算子与免疫算法引入到蚁群算法，提升了算法寻优能力，但使得算法步骤过多，延长运行时间。文献[22]将粒子群算法与蚁群算法相结合，用粒子群算法得到初始的信息素，降低前期蚂蚁搜索路径的时间，但在路径寻优能力上还有待改进，且算法运行后期容易陷入局部极小值。

针对上述改进蚁群算法的缺陷，提出新的改进蚁群算法，引入转角启发函数以提升路径选择指向性；对启发函数进行改进，提高搜索速度；提出信息素挥发因子自适应更新策略，提升算法搜索性能，加快收敛速度；引入遗传算法的染色体交叉操作，提升寻优能力；最后通过路径平滑操作得到最优的机器人移动路径。

1 环境建模

为精准表述机器人路径规划过程，需对其二维环境地图进行建模，常规的环境建模法有栅格法、几何信息法、视图法等。而栅格法具有建图简单、数据结构清晰易于实现等优点。因此选取栅格法对机器人工作环境进行建模。栅格法可将平面地图分解为一系列的栅格，便于分析地图信息。白色栅格表示机器人可自由移动的区域，黑色栅格表示障碍物区域，示例如图1 所示。对障碍物进行膨化处理，如图2 所示，障碍物扩展的尺寸是移动机器人半径与安全预留距离之和，因此移动机器人可视为一个没有体积的质点，图中r为机器人半径。若不规则障碍物没有占满一个栅格时，仍视为占满一个栅格。

图1 环境建模示例Fig.1 Environment modeling example

图2 障碍物膨化Fig.2 Obstacle puffing

机器人将按照如下规则进行移动：

（1）机器人只可以出现在白色栅格内，不能穿越或经过黑色栅格移动，但机器人可在黑色栅格的四角通过。

（2）优秀的机器人路径规划要以尽可能短的移动路径使得机器人从起点运动到目标点，因此若机器人重复经过同一栅格，则证明该路径必定浪费更多不必要的能量且并非是最短路径，因此定义机器人不可重复经过同一栅格。

（3）在单位时间里，机器人只能在两个相邻的栅格间移动，因此在一个单位的下一时刻，机器人只能出现在所处当前栅格附近的8 个栅格里。利用欧氏距离来度量移动路径的长度，若机器人向上下左右4个方向移动，则路径长度为1 个单位，若机器人向栅格的4 角移动，则路径长度为1.4个单位。

2 基本蚁群算法

蚁群算法受蚂蚁种群觅食行为的启发，在此过程，种群中每只蚂蚁都会在其移动路径中留下信息素以向种群传达信息。移动路径越短，则信息素浓度较高，该路径被蚂蚁选中的概率较大，这就形成了蚂蚁寻找最短路径的正反馈机制。基本蚁群算法原理如下。

蚂蚁移动时，依照信息素浓度与距离启发函数来选择路径，蚂蚁k从栅格i运动至栅格j的概率可表示为：α为信息素启发因子，β为距离期望函数因子，二者分别影响着信息素与距离启发函数的重要程度；Ak表示蚂蚁下一步可到达目的地集合；τij(t)为t时刻移动路线上的信息素浓度；ηij(t)表示距离启发函数。

每只蚂蚁在移动时均会遗留一定量的信息素，因此算法不断迭代时，路径中信息素含量逐渐累积，同时也在不断的挥发，当全体种群均完成第一次迭代后，将依照式（4）～（6）刷新路径上信息素含量：

ρ为信息素挥发系数；Δτij表示两节点上释放信息素的和；表示两节点上信息素增量；Lk表示蚂蚁k经过路径长度，Q为信息素增强系数。

3 改进蚁群算法

利用基本蚁群算法对机器人路径进行规划时，其算法的启发函数仅仅考虑了局部的最短路径，若以全局路径的角度分析，并非是最优的选择。此外，基本蚁群算法的信息素挥发因子数值从始至终是一成不变的，并没有任何动态的调整，因而算法极其容易陷入局部最优解，导致无法找到全局最优解，并消耗了大量的时间与能源。针对上述问题，提出合理的优化策略与改善方案：包括引入转角启发函数达到提升路径选择指向性，并缩短转弯时间的效果；其次改进启发函数，可快速找到较优路径；此外提出信息素挥发因子自适应更新策略，以降低算法前期搜索的盲目性，并提高搜索后期的收敛速度；最后引入遗传算法的染色体交叉操作，找到全局最优解，并通过路径平滑操作得到最优的机器人移动路径。

3.1 设计转角启发函数

当蚂蚁在栅格移动时，爬行的角度只能是0°、45°、90°、135°四种情形，为应尽可能减少路径转折点，并提升路径指向性，设计转角启发函数：

3.2 改进启发函数

在基本蚁群算法运行的初始阶段，蚂蚁经过的移动路径并不存在信息素，导致后续的蚂蚁不能依照路径中信息素的浓度高低来判定其较优移动方向，无法快速搜寻到可行路径。针对这一问题，对基本蚁群算法的距离启发函数进行优化，利用当前节点与下一节点之间的距离和下一节点与目标节点距离之和的二次方来改进启发函数，可达到在算法运行初期获得朝向目标点引导方向搜索的目的，优化后启发函数：

其中djD含义为节点j与目标点的欧几里得距离，改进后的启发函数可提高算法搜索路径的目的性，并降低陷入局部极小值的概率。

3.3 信息素挥发因子自适应更新

基本蚁群算法信息素挥发因子通常是不变的，这就导致蚂蚁在探索路径时信息素分配不合理。早期路径中信息素含量过低，因此，增加了蚂蚁搜索路径的盲目性，而后期由于信息素积累过多，又缩小了路径的可选择范围，导致算法陷入局部最优。故不变的挥发因子对搜索最优路径并非是最具优势的。本文提出信息素挥发因子自适应更新策略如下：

其中T表示算法总迭代次数，t表示当前迭代次数。

为尽可能搜索到更多的移动路径，在算法寻优的初始阶段，应将信息素含量控制在较低水平，因此初始挥发因子ρ1的取值不应过小，此时信息素浓度对蚂蚁探索路径的过程干预较小，蚂蚁可搜索到更多的移动路径。随着算法逐步迭代，挥发因子ρ数值逐渐降低，负反馈效果削弱，移动路径上信息素含量提高，信息素浓度对蚁群的导向作用增强，当迭代次数提升到一定次数时，蚁群将向信息素含量较高的路径汇集。因此，改进后的算法可以扩大蚁群搜索范围，且提高收敛速度，信息素挥发因子变化曲线如图3所示，其中初始挥发因子ρ1设置为0.9。

图3 信息素挥发因子变化曲线Fig.3 Change curve of pheromone volatilization factor

算法改进后，蚂蚁从节点i运动到节点j概率为：

3.4 路径交叉

当蚁群算法在迭代过程中，随着移动路径上信息素的挥发与积累，最终收敛至最优路径，若算法多次迭代后，始终无法寻得更优路径，则算法陷入局部最优。因此，本文将利用标准遗传算法中染色体交叉操作，对蚁群算法在每次迭代后得到的移动路径进行二次优化，进而使得蚁群算法跳出局部最优解，以找到全局最优，遗传算法染色体交叉操作如下。

（1）从目前算法迭代得到的全部移动路径中，选择当前最优路径并复制全部路径的1n个，作为种群的一部分，同时利用轮盘赌[23]方法，生成剩余()n-1 /n个初始种群。

（2）在初始种群中，随机挑选两条路径作为染色体交叉操作的亲代。

（3）找出亲代路径中全部相同的节点，随机选取一组进行路径片段交叉操作，生成两个子代路径。

（4）在全部子代路径中找出最优路径，若路径长度比当前迭代最优路径或全局最优路径更短，则用其代替当前迭代最优路径和全局最优路径。

3.5 路径平滑

当机器人移动过程中，能源消耗与运行时间也应予以考虑，移动路径的节点越多，机器人的移动时间就越长，导致能源浪费。利用基本蚁群算法规划的移动路径存在一些冗余节点，因此需要对该路径进行路径平滑操作，减少多余的节点，缩短移动路径长度，提高路径平滑度。所以本文基于Floyd 算法的思想设计路径平滑方法，以减少路径中不必要的转弯节点，缩短移动距离进而节约工作时间，降低能耗。

具体操作步骤为，从起点开始，往后依次选择相邻的3个路径中的节点连接，将节点1与节点3连线，若之间没有障碍物且第3个节点的位置处于第1个节点可移动的范围内，则删除节点1与节点3之间的节点2，所以机器人将直接从节点1移动至节点2，缩短移动距离，遍历后续全部节点，继续依照此方法，进行路径平滑操作，直至选取的节点为目标点为止。

如图4 所示，以该路径平滑为例，若利用基本蚁群算法规划的移动路径为(S,1,2,3,4,5,6,7,8,9,10,11,T)，显而易见该移动路径中存在一些冗余的节点，则利用上述路径平滑的方法对移动路径进行优化后，移动路径缩短为(S,1,2,3,4,6,8,10,T)，有效地减少了移动路径中的冗余节点，移动路径更加平滑。

图4 路径平滑优化前后对比Fig.4 Comparison of path smooth before and after optimization

3.6 算法步骤

改进后蚁群算法流程如图5所示，步骤如下：

图5 改进蚁群算法流程Fig.5 Flow chart of improved ant colony algorithm

步骤1 利用栅格法构建机器人工作的地图模型。

步骤2 调试算法参数，设置起点与终点位置。

步骤3 蚂蚁从起始点出发，搜寻最优移动路径。

步骤4 依照引入转角启发函数的概率公式，得到蚂蚁下一次运动节点。

步骤5 判断每只蚂蚁是否全部移动至终点，若到达则算法运行下一步操作；否则回到步骤4。

步骤6 依照优化的后的信息素自适应更新策略更新路径中蚂蚁留下的信息素含量。

步骤7 记录每只蚂蚁的路径长度，选出当前迭代中最优路径，更新全局最优路径。

步骤8 选择当前迭代中对应的路径进行路径交叉操作，所得结果更新当前最优解与全局最优解。

步骤9 判断是否达到终止迭代条件，若达到则输出全局最优解并执行路径平滑操作；否则返回步骤3。

3.7 运算复杂度

4 实验仿真与分析

为验证本文改进蚁群算法的可行性、稳定性、优越性，通过仿真软件MATLAB2018a，在2.20 GHz PC，8 GB RAM，Windows10，64位操作系统上运行。

4.1 优化引入参数

在实验中依照经验，蚁群算法参数初始化为：M=100，T=400，α=1.5，β=10，Q=1，ρ1=0.9。对引入的参数n、ε进行组合优化，设定参数范围为：n∈{4，5，6，7，8}，ε∈{1，2，3，4，5}，参数默认为n=6，ε=2。每次实验仅改变一个参数，其他参数设为默认值，实验在40×40复杂环境中，进行如图6所示数仿真实验20次取均值，实验结果如表1所示，n=5时路径最优，ε=3路径最优。故本文引入参数n、ε取值分别为5、3。

图6 40×40复杂环境地图Fig.6 40×40 complex environment map

表1 引入参数优化结果Table 1 Optimization results of introduced parameters

4.2 算法性能测试

为验证本文改进蚁群算法的寻优能力，利用7个不同特质的测试函数进行函数寻优对比测试，其中f1、f2、f3、f4是单模态函数，f5、f6、f7是多模态函数，如表2所示。与本文改进蚁群算法（IACO）对比的是基本蚁群算法（ACO）与基于改进搜索策略的蚁群算法[24]（UACO）。种群数量设为100，问题维度设为30，最大迭代次数设为400，算法共有参数保持一致。上述3 种算法在各个测试函数上独立运行30 次的结果，如表3所示。

表2 测试函数Table 2 Test functions

由表3 的测试实验结果可知，本文提出的IACO 算法针对单模测试函数与多模测试函数的寻优效果在3个算法的对比中都是最优的，并且对于函数f1、f2、f5都可以搜索得到理论的全局最优值0，寻优效果可达到100%，此外IACO在这3个函数寻优过程中的标准差始终都为0，则证明IACO 算法具有良好的稳定性与鲁棒性。在测试函数f3中，ACO 算法与UACO 算法的寻优表现均相对较差，而利用IACO算法对测试函数f3进行寻优时，其平均值比其他两个算法高出了5 个数量级，说明IACO算法的寻优能力更强。对于函数f4、f6、f7而言，IACO算法在实验结果的4项指标中，均优于ACO算法与UACO 算法，表明IACO 算法的寻优精度更高，寻优能力更强。

表3 测试函数实验结果Table 3 Test results

为更好地体现出IACO算法较强的寻优能力，部分测试函数的收敛曲线如图7所示。

图7 函数的收敛曲线Fig.7 Convergence curves of functions

本文选取的测试函数中f1～f4是单峰函数，可用来检测算法的收敛精度和收敛速度，而f5～f7是多峰函数，可用来检测算法跳出局部极小值与全局搜索能力，同时也能测试算法的收敛精度和收敛速度。由7 图可知，IACO 算法的适应度值收敛曲线下降速度相比较于ACO 与UACO 更快，而且达到稳定时的状态所用迭代次数更少，并且稳定时函数适应度值更低，证明IACO算法具有更高的收敛精度与收敛速度。此外，在多峰函数f6与f7的收敛曲线中，IACO算法在迭代过程中出现多个拐点，并且其收敛精度也是3 个算法中最高的，因此IACO算法可以跳出局部极小值，具有良好的局部搜索能力同时也具有优秀的全局搜索能力。

4.3 算法仿真与对比分析

为验证IACO算法在机器人路径规划中的有效性，将ACO 与UACO 作为对比算法，在3 种不同环境地图中进行仿真对比实验，3种算法参数设置如表4所示。

表4 算法参数设置Table 4 Algorithm parameters setting

4.3.1 20×20仿真环境

在20×20 的栅格地图中进行仿真实验，分别利用ACO、UACO算法和本文提出的IACO算法对机器人移动路径进行规划，3种算法路径规划图与算法迭代收敛曲线图如图8、9所示。实验结果如表5所示。

图8 20×20栅格地图中基于3种蚁群算法最优规划路径Fig.8 Optimal plan path based on three ant colony algorithms in 20×20 grid map

由表5 可知，应用本文提出的IACO 算法得到的最短路径长度比应用ACO算法和UACO算法得到的最短路径长度分别缩短了14.5%和9.8%。且应用IACO算法的搜索效率相比于ACO 和UACO 分别提高了47.2%和41.7%。此外应用IACO得到的最优路径拐点数量相比于ACO和UACO算法分别减少了58.8%和30%。因此，本文提出的IACO 算法在机器人路径规划中具有更强的寻优能力。

表5 20×20栅格地图中3种蚁群算法仿真结果对比Table 5 Comparison of simulation results of three ant colony algorithms in 20×20 grid map

4.3.2 30×30仿真环境

为验证复杂情况下本文提出的IACO 算法的机器人移动路径规划能力，在30×30 的栅格地图中，分别利用ACO、UACO算法和IACO算法进行机器人路径规划仿真。由于地形相比较于20×20的地图中更为复杂，为保持算法的可靠性，将蚂蚁数量设置为100 只，算法最大迭代次数设置为150，其他参数不变。3 种算法路径规划图与算法迭代收敛曲线如图10与图11所示。

图9 20×20栅格地图中3种蚁群算法迭代曲线Fig.9 Iteration curves of three ant colony algorithms in 20×20 grid map

图10 30×30栅格地图中基于3种蚁群算法最优规划路径Fig.10 Optimal plan path based on three ant colony algorithms in 30×30 grid map

图11 30×30栅格地图中3种蚁群算法迭代曲线Fig.11 Iteration curves of three ant colony algorithms in 30×30 grid map

由图10 与图11 可知，ACO 算法搜索速度较慢，搜索最优路径较长，并难以得到最优解。UACO算法搜索前期具有一定的盲目性，且算法收敛较慢。而本文提出的IACO算法可在搜索前期较快的收敛，并且找到最短路径。如表6 所示，应用IACO 算法得到的最短路径比ACO 算法和UACO 算法分别缩短了16.1%和2.6%，拐点数量减少了38.1%和23.5%。因此，IACO算法有着较高的搜索效率，路径拐点数量较少，路径更为平滑，有着强劲路径规划性能。

表6 30×30栅格地图中3种蚁群算法仿真结果对比Table 6 Comparison of simulation results of three ant colony algorithms in 30×30 grid map

4.3.3 40×40仿真环境

为验证在环境空间较大且障碍物分布较为复杂情况下，ICAO算法的机器人路径规划能力，创建40×40栅格地图，分别利用ACO、UACO 算法和IACO 算法进行机器人路径规划仿真。由于40×40 地图较大且障碍物分布情况更加复杂，为保持算法可靠性与稳定性，将蚂蚁数量设置为100只，算法最大迭代次数设置为400，其他参数不变。3种算法路径规划图与算法迭代收敛曲线如图12和图13所示。

图12 40×40栅格地图中基于3种蚁群算法最优规划路径图Fig.12 Optimal plan path based on three ant colony algorithms in 40×40 grid map

图13 40×40栅格地图中3种蚁群算法迭代曲线Fig.13 Iteration curves of three ant colony algorithms in 40×40 grid map

由图12 和图13 可知，当机器人工作环境较大且障碍物分布较为密集时，应用ACO 算法与UACO 算法进行机器人路径规划时均无法有效收敛至最短路径，规划的机器人移动路径较长，而应用IACO算法得到的机器人移动路径更短，且算法可以有效收敛。如表7 所示，应用IACO 算法得到的最短路径比ACO 算法和UACO算法分别缩短了23.2%和10.2%，拐点数量减少51.9%和31.6%，系统运行时间分别减少了52.0%与40.1%。因此，IACO算法可在更短的时间内找到最短的移动路径，且路径更加平滑。