基于转角约束的改进蚁群优化算法路径规划

2021-09-18 06:21李开荣胡倩倩唐亦媛
计算机应用 2021年9期
关键词:移动机器人栅格次数

李开荣,刘 爽,胡倩倩,唐亦媛

(扬州大学信息工程学院,江苏扬州 225127)

(*通信作者电子邮箱973279727@qq.com)

0 引言

随着智能化时代的到来,移动机器人越来越普及,其中一项重要的研究工作即移动机器人的路径规划问题。移动机器人的工作环境中往往存在着一定数量的障碍物,需要从初始点准确且快速地寻找一条能够避开所有障碍物到达目标点的最优路径[1]。传统的路径规划算法有栅格法、人工势场法等[2]。栅格法属于全局路径规划算法,用于构建移动环境,将机器人的路径转换为网格之间的连接,算法简单易实现;但是当移动环境变大时,网格数量急剧增加,数据存储空间大,计算速度慢。人工势场法是一种局部路径规划算法,实时性强、计算量小,对硬件平台的要求低;但是其存在的局部最小点问题很容易引起路径规划的失败。因此,随着移动环境复杂度和任务难度的增加,传统的路径规划算法无法达到预期的效果。随着人工智能的发展,例如遗传算法[3]、蚁群优化(Ant Colony Optimization,ACO)算法[4]、烟花算法[5]、粒子群算法[6]等智能算法也被应用到路径规划领域中,并且取得了丰富的成果。

在上述路径规划方法中,蚁群优化算法[7]具有较强的鲁棒性和搜索能力,作为一种启发式算法,对蚂蚁群体的觅食过程进行学习模拟,得出蚂蚁们共同规划的解路径,具有正反馈、并行计算以及易融合等特点,但也存在迭代次数多和易忽略全局最优解等问题。针对这些问题,许多国内外学者进行了探索与改进,文献[8]针对传统蚁群优化算法易陷入局部最优、初期搜索能力差等问题,采用改进的头尾搜索机制,引入奖惩因子与信息素最大最小阈值,添加遗传算法变异因子,使规划出来的路径得到了进一步的优化。文献[9]为避免初期寻优的盲目性,在栅格地图中划定优选区域,设置新的初始信息素浓度模型,提高了算法的收敛速度。文献[10]使用伪随机状态转移规则选择路径,根据当前最优解和迭代次数计算状态转移概率,自适应地调整确定选择和随机选择的比例,引入最优解和最差解改进全局信息素更新方法,仿真实验结果表明,改进后的蚁群优化算法收敛速度更快、全局搜索能力更强。文献[11]在蚁群优化算法中融合免疫算法,大大缓解了抗体种群的“早熟”问题。文献[12]将蚁群优化算法生成的路径进行平滑操作,减少了转弯次数。

以上改进蚁群优化算法大多致力于优化路径长度以及提高寻路效率,很少有学者在寻找下一步移动节点时就考虑到转弯角度次数过多导致机器人运行时间增长、能耗增加的问题,部分学者在路径规划出来后对其进行平滑操作,但这种方式增加了算法的复杂性,且最终路径未必就是全局最优路径。鉴于此,本文提出了一种基于转角约束的改进蚁群优化算法,用于移动机器人路径规划。为降低搜索初期的盲目性,该算法首先增加起始点与终止点之间的初始信息素浓度;并且在启发函数中加入A*算法的估价函数和转弯角度因子,使搜索到的路径是综合路径长度和累计转角最小的最优路径,有利于减少移动机器人损失的能耗,防止出现局部最优的情况;在信息素更新公式中,引进狼群算法的猎物分配原则,同时借鉴最大最小蚁群(Max and Min Ant System,MMAS)算法给路径上的信息素规定上限和下限,进一步提高收敛速度,便于快速搜索到一条综合指标最优的路径。

1 基本蚁群优化算法

蚁群优化算法即蚂蚁种群从起始点出发,至目标位置获取食物的过程,蚂蚁的信息素会被留在其走过的路径上,它们利用信息素相互通信,当某一条路径上通过的蚂蚁越来越多时,该路径的信息素浓度就会越高,其他蚂蚁就有更大的概率选择这条路径,起到正反馈作用,然而也容易导致局部最优或死锁情况的出现[13]。

通过对信息素浓度、启发因子、路径方向等因素进行综合判断选择下一步移动的栅格,并利用轮盘赌法计算当前节点到下一节点的概率[14],如式(1)~(3)所示。

其中:τij是网格i到网格j的信息素值;ηij是网格i到网格j的启发式信息;α为信息素激励因子,代表信息素值对路径选择的影响程度,α越大则信息素对于路径选择的影响越大,大多数蚂蚁走过的路径将有更大几率被选中;β是期望启发式因子,代表启发信息对蚂蚁选择路径的影响程度,β与影响程度之间是正相关关系;dij代表节点i与节点j之间的欧几里得距离。(xi,y)i和(xj,y)j是网格i与网格j的坐标;allowedk中存放网格i中蚂蚁此时能够选择的网格集合。

经过t时刻,当每只蚂蚁都进行了一次路径规划后,计算所有顺利到达目标点的蚂蚁走过的路径长度,从中筛选出最短路径,并且将每条路径上的信息素浓度都进行更新,一段时间后,将挥发一部分信息素,如式(4)所示:

其中:ρ是信息素挥发系数。

同时蚂蚁也将在路径上留下一些信息素,如式(5)所示:

式(6)为蚁群模型的信息素更新策略,其中:Q为信息素的强度,若蚂蚁搜索到的路径长度dij越小,依据公式,则将会有更多的信息素被加到路径上,之后其他蚂蚁选中该路径的可能性也将更大[15]。

2 环境建模

常用的环境建模方法有栅格图法、可视图空间法、自由空间法、几何信息法[16]等。本文选择栅格图法对移动机器人二维运动空间进行建模,假设每个栅格的边长为1,其中:白色栅格为自由栅格,表示可通行区域;黑色栅格为障碍物区域,移动机器人不可通行。如式(7)所示:

移动机器人平行行驶在障碍物边缘的位置关系如图1所示。

图1 机器人与障碍物的位置关系Fig.1 Position relationship between robot and obstacle

假设移动机器人的直径为W,从图1 可以看出,当机器人的中心占据栅格距离障碍物边缘的最小距离小于W/2 时,就会发生碰撞[17],此时的碰撞概率为100%,即

其中:P(x,y)为栅格(x,y)的碰撞概率;N(x,y)为移动机器人中心所占据的栅格;{O}为障碍物所有边缘栅格的集合;min({O},N(x,y))表示移动机器人中心占据栅格到障碍物所有边缘栅格距离集的最小值。

为确保移动机器人在运动中不与障碍物边缘发生碰撞,且保证每次转弯的顺利进行,本文将障碍物尺寸进行适当膨化后再预留出一定的安全距离,其中安全距离为移动机器人的半径,进而可将机器人简化为一个质点来处理,障碍物处理过程如图2所示。

图2 障碍物处理图Fig.2 Obstacle processing diagram

网格模型被放置在二维坐标系中,x为横轴,y为纵轴,采用序列号的方法标记每个网格。在N*N的网格图中,起始节点以“起始”命名,目标节点以“目标”命名,其余栅格分别用编号i表示,每个栅格的中心点坐标为(xi,y)i,栅格编号与其坐标的对应关系如式(9)所示:

3 改进蚁群优化算法

基本的蚁群优化算法有以下缺点:每个栅格的初始信息素值相同且启发式值之间也不存在明显差异,因此往往搜索时间较长,难以寻找到全局最优解[18];同时在栅格地图中,使用基本蚁群优化算法规划出来的路径可能会有更多的转弯次数和较大的累计转弯角度。为了解决上述问题,本文进行了以下改进。

3.1 初始信息素不均匀分布

在基本蚁群优化算法的初始阶段,每个栅格的初始信息素值相同,这就使得蚂蚁在初期搜索时存在不小的盲目性,算法运行时间增加。因此本文将初始信息素的分布进行适当调整,使其不均匀分布,并且不会增加算法的复杂性。通过参考其他众多文献中的路径,本文发现最优路径大部分情况下都存在于起点与终点连线的附近[19],因此此处取栅格地图各边的中点,连接相邻边的中点,得到与起点终点连线平行的两条直线,直线AB与直线CD之间的区域如图3 所示,增强该区域的初始信息素值,如式(10)所示。

图3 初始信息素增强区域Fig.3 Initial pheromone enhancement area

其中:τ0为信息素初始值,C为大于τ0的常数。

3.2 改进启发式信息

基本蚁群优化算法的启发函数中,相邻网格之间启发式值的大小相差无几,所以往往需要较长的搜寻时间且不易搜索到全局最优路径。为此,本文将A*算法加入到蚁群优化算法的启发式信息中,以提高算法的收敛速度并获得更优的全局路径[20]。

A*算法有较快的寻路速度,其启发式成本由估价函数(fn)表示,通过(fn)来指导节点的扩展与搜索,每一次都是搜索从起始点到目标点之间使得(fn)最小的路径,估价函数方程为:

其中:g(n)为从起始节点到当前节点的最小路径成本值;h(n)为从当前节点到目标节点的最小路径成本估计值;nx和ny是当前节点n的坐标;gx和gy是目标节点g的坐标;sx和sy是初始节点s的坐标。

机器人在经过障碍物群时,若只是把路径最短作为主要因素,则会造成机器人转弯次数过多,时间和能耗大大增加,也会导致机器人寿命的减少。因此,本文将转弯角度因子也加入到蚁群优化算法的启发信息中,使移动机器人尽可能选择一条转弯角度更小的路径,若一条路径中节点之间的转弯角度过大,则启发函数值将降低,路径中节点之间的转弯角度示意图如图4所示。

图4 转弯角度示意图Fig.4 Schematic diagram of turning angle

图4中统一按照顺时针的方向进行角度测量,(A,B)节点之间的路径相对于(O,A)节点之间转弯角度是45°,而(C,D)节点之间的路径相对于(B,C)节点之间的转弯角度是90°,转弯角度值的计算公式如下:

其中:R是转弯角度因子;γ是转弯角度(单位:rad);c是转弯角度权重系数。

综上,在蚁群优化算法中,将A*算法的估计函数用作启发式信息,以便于搜索全局最优路径、提高收敛速度;同时,将转弯角度因子也添加到蚁群优化算法的启发式值中,以减少转弯次数和累计转向角度,促使机器人按照路径长度和转弯角度双重因素进行最优选择。改进后的启发函数公式如下:

其中:Q1是大于1的常数。

3.3 改进信息素更新

蚁群算法模拟自然界中的蚁群觅食机制,采用分布式正反馈并行计算机制,传统蚁群算法是各个蚂蚁单独行动且每只蚂蚁都执行相同的操作,蚂蚁之间的协作不足,可能会导致滞后、算法陷入局部最优、收敛速度慢等问题。在搜索路径时,存在一部分蚂蚁找到的路径是最差路径,它们所释放的信息素将对之后的蚂蚁寻路造成负面影响,从而容易使搜索陷入局部最优,还可能出现死锁情况导致有效蚂蚁数量损失;而另一些蚂蚁寻得最优路径,它们所释放的信息素将对其余蚂蚁寻找最优路径起到促进作用。为了提升收敛速度、获得最优路径,此处融合狼群算法,在蚁群算法的信息素更新公式中加入猎物分配原则[21]。

狼群算法是一种智能优化算法,模拟狼群的社会分工和捕食行为,其分配规则为“强者生存”的狼群更新机制,狼群中存在贡献能力弱的狼,即身体瘦弱的狼,它们猎得食物的数量和可能性都远小于身体强壮的狼,就如蚁群中存在寻得路径差的蚂蚁,这些蚂蚁寻得的路径要差于寻路能力强的蚂蚁。

因此,狼群算法中按照狼“由强到弱”的顺序进行猎物分配,身体强壮且善于捕猎的狼会优先获得食物,反之身体瘦弱的狼则只能分得很少的食物。随着每次分配的进行,部分身体弱小的狼将越来越难以生存下去,直至饿死;而先前本就强壮的狼将越发强壮,在下一次捕猎时猎得食物的可能性将进一步增大,经过迭代,狼群的生存能力被逐渐提高。

在蚁群算法中融合狼群算法中猎物分配原则的动机是借鉴该分配原则来解决传统蚁群算法在信息素更新时存在的问题,即寻得最差路径的蚂蚁释放的信息素将会对随后的蚂蚁寻路造成一定的误导作用,容易使路径陷入局部最优,并且寻得最优路径的蚂蚁释放的信息素不能很好地传递给之后的蚂蚁。这一融合过程可以理解为,加强蚁群算法中优质路径上的信息素浓度,较弱个体的经验由于参考价值少,不应被着重考虑,便于更多的蚂蚁吸收优质个体的经验,提高收敛速度。

采用狼群算法中“强者生存”的更新机制有效传承了整个蚂蚁种群在搜索路径时形成的“智慧”、提高全局搜索能力、避免陷入局部最优解,符合自然界种群繁衍进化的特点,不断更新的信息素代表着蚁群在整个路径搜索过程中形成的寻路智慧,有利于该智能优化算法对解空间进行更好的学习。

借鉴这种思想,本文算法在每次迭代中,计算各个蚂蚁的运动轨迹长度,将到达目标点路径最短的蚂蚁所留下的信息素增强,路径最长的蚂蚁所留下的信息素减弱,突出不同路径之间信息素的差别化。对信息素更新公式作如下改进:

其中:Δ*τij和Δ**τij分别代表每次迭代中最优和最差路径经过节点i、j的信息素大小;L*和L**分别代表每次蚁群到达目标点的最短运动轨迹和最长运动轨迹;δ和ω分别表示每次搜索时找到最短路径和最长路径的蚂蚁数量;Q2为增强因子,此处将其设为1;R1为减弱因子,将其值设为0.5。

经过多次迭代后,某条路径上的信息素值可能远大于或远小于其他路径,使得搜索不能继续进行下去、过早收敛,为防止这种极端情况产生,借鉴MMAS算法[22],将信息素的取值范围限定在τmin到τmax,如式(19)所示:

4 改进算法的步骤

综上所述,本文对基本蚁群算法改进后,移动机器人路径规划的步骤如下:

步骤1 通过栅格法对工作环境进行建模,为移动机器人设定好运动的起始点和目标点。

步骤2 初始化参数:蚂蚁数量m,信息素重要程度因子α,启发函数重要程度因子β,信息素挥发系数ρ,信息素强度系数Q、迭代次数N等,其中初始信息素浓度按式(10)设置。

步骤3 更新禁忌表。将蚂蚁k(k=1,2,…,n)放在当前节点上,将当前节点添加到禁忌表中。

步骤4 选择下一步的网格。根据式(15)计算加入A*估价函数和转角约束的启发式函数值,然后依据式(1)~(3)求出状态转移概率值。再借鉴轮盘赌法选出下一步将要到达的栅格,若蚂蚁抵达目标位置,则转到步骤5;反之转到步骤3。

步骤5 如果蚂蚁到达目标位置,重复步骤3,直到每个蚂蚁在其迭代过程中完成整个搜索过程,之后转到步骤6。

步骤6 更新信息素。每次迭代完成,如果此时迭代次数小于最大迭代次数,将按照狼群算法的猎物分配原则即式(16)~(18)计算路径上的信息素浓度,同时要保证其满足式(19),若满足收敛条件,则退出;若不满足,转到步骤3。反之迭代次数大于最大迭代次数时,则停止计数,输出最终结果。

本文算法整体流程如图5所示。

图5 本文算法流程Fig.5 Flowchart of proposed algorithm

5 仿真分析

为了验证本文改进蚁群算法的可靠性,使用Matlab 软件进行仿真。分别使用4 种不同规模的栅格地图,每次在同样大小的栅格地图中,采用相同的实验条件对8 种不同的算法进行对比分析。

5.1 参数取值

关于蚁群算法主要参数值的确定,目前没有特别详尽的理论方法,因此本文根据经验反复实验而定,设置不同的参数组合进行仿真,分析实验结果,选择最佳参数组合。

对每一个参数设置一组值,以图3 的栅格地图为本次实验环境,起始点和目标点分别用点S和点T在图中表示,在每次测试中仅改变一个参数的取值,其他参数为常量,分别计算最佳路径长度和迭代次数。由于对规划结果影响较大的参数是蚂蚁数量m、信息素启发因子α和期望启发式因子β,因此本文仅介绍这三个参数的取值过程。其余参数根据经验及实验仿真对比,初始化参数值如表1所示。

表1 初始化参数值Tab.1 Initialized parameter values

5.1.1 蚂蚁数量m

在蚁群算法中,当蚂蚁数目过多时,信息素的作用将被削弱,导致蚁群算法的收敛速度变慢;当蚂蚁数目过少时,可能存在路径未被选择的情况,无法有效搜索到全局最优解。因此,选择合适的蚂蚁数量至关重要,本文对除蚂蚁数目m之外的其他参数取值分别为:α=1,β=7,ρ=0.3,取蚂蚁数量m=10,20,30,40,50,60,70,80,90,100。为防止偶然因素,对每组数据运行10次,得到蚂蚁数量m对计算结果的影响如图6所示。

图6 蚂蚁数量m对ACO算法的影响Fig.6 Influence of the number of ants m on ACO algorithm

由图6 可知,随着蚂蚁数量从10 变化到40,最短路径的长度急剧下降,之后变化幅度减小至不再变化;迭代次数呈现升降升的趋势,在蚂蚁数量为50 时,迭代次数达到最小。总结发现,当蚂蚁数量约为自由栅格数的1/6 时,算法的收敛速度和路径长度达到最优。

5.1.2 信息素启发因子α和期望启发式因子β

α表示当前蚂蚁受前代蚁群搜索结果的启发程度,β反映的是当前环境相关信息对蚂蚁的影响程度。α越大,β越小,则蚂蚁越依赖信息素的指导,倾向于选择之前走过的路径;反之,α越小,β越大,则蚂蚁更倾向依据当下的环境选择较短的路径抵达目标点。两者是相互关联的,因此此处选择将β/α设为自变量,路径长度和迭代次数作为因变量。设α=1,β/α取1~10,m=50,ρ=0.3,其余参数取值如表1。对计算结果的影响如图7所示。

图7 β/α对ACO算法的影响Fig.7 Influence of β/α on ACO algorithm

由图7 可知,随着β/α值的递增,最短路径长度逐渐减小直至稳定,迭代次数先减小后增加,在β/α=7 时取最小值。因此,当α=1,β=7时,蚁群算法各方面具有较优的性能。

5.2 小规模栅格环境

首先将基本蚁群算法、文献[12]、文献[23]、文献[24]改进的蚁群算法及本文算法在20×20、30×30规模的栅格地图上进行对比实验。此处实验各相关参数取值为:m=50,α=1,β=7,其余按表1取值。

5.2.1 20×20栅格环境

在20×20 规模的栅格环境中,5 种算法仿真结果如图8 所示。由图8可知,基本蚁群算法规划出的路径长度为31.4,文献[23]算法的路径长度为31.4,文献[24]算法的路径规划长度为29.8,文献[12]规划出的路径长度为28.82,本文算法的最优路径长度为28.63。

图8 在20×20地图上5种算法规划的路径Fig.8 Paths planned by five algorithms on 20×20 map

五种算法的路径长度和迭代次数如图9 所示。由图9 可知,本文算法和文献[23]算法的迭代稳定次数相差不大,比基本蚁群算法和文献[12]算法减少50%的迭代稳定次数,比文献[24]的迭代稳定次数也更优,具体指标比较如表2 所示。由表2 可知,在路径长度上,本文改进之后的算法运行出的最优路径长度为28.63,较基本蚁群算法和文献[23]算法缩短8.8%,较文献[24]算法也缩短了3.9%;在转弯次数上,本文算法转弯次数为4,分别较基本蚁群算法和文献[23]算法减少了75%和50%,大幅减少了转弯次数;在累计转弯角度上,较基本蚁群算法、文献[23]和文献[24]算法分别减少了720°、270°和180°,规划出的路径更加平滑,避免了移动机器人过多的能耗损失,延长了寿命,缩短了转弯时间。

图9 在20×20地图上的路径长度迭代图Fig.9 Path length iteration graph on 20×20 map

文献[12]算法的主要思想是将蚁群算法生成的全局最优路径再进行平滑处理,将路径中两个不在同一直线上的节点连线,若连线中间不穿过障碍物则此连线就是新的路径,以此法来进行路径平滑处理。由表2 中可以看出,文献[12]算法能够有效缩短路径长度和累计转弯角度,但是该算法仍存在明显不足:在迭代次数上,该算法需要26 次迭代才能达到稳定,而本文算法仅需4 次即可;在程序运行时间上,文献[12]算法需要10.632 s,本文算法在6.921 s 内即可完成。综合多种指标来看,在此处栅格环境下本文算法都要优于文献[12]算法。

表2 在20×20地图上的仿真结果Tab.2 Simulation results on 20×20 map

综上,本文算法生成的路径综合指标最优,改进之后的算法优势明显。

5.2.2 30×30栅格环境

为了进一步验证本文算法的可靠性,将栅格地图扩大为30×30,障碍物增多,再次进行仿真。基本蚁群算法、文献[12]算法、文献[23]算法、文献[24]算法以及本文算法的路径规划如图10所示。

图10 在30×30地图上五种算法规划的路径Fig.10 Paths planned by five algorithms on 30×30 map

由图10 可以看出,当栅格地图规模扩大并且障碍物增多时,基本蚁群算法、文献[12]算法、文献[23]算法、文献[24]算法无法很好地适应该类较为复杂环境的全局路径规划,其规划出的最优路径长度分别为50.2、45.8、47.2和47.5,而本文算法仍然可以很好地执行,寻得的最优路径长度为43.3,较其他算法有效缩短了路径长度,路径长度与迭代次数的关系如图11所示。

图11 在30×30地图上的路径长度迭代图Fig.11 Path length iteration graph on 30×30 map

图11为五种算法在30×30栅格规模下的收敛曲线变化趋势,可以看出当环境复杂化后,本文算法及文献[23]算法在迭代稳定次数上比其余三种算法更优,文献[23]算法的收敛速度比文本算法稍快一些,具体指标比较如表3所示。

表3 在30×30地图上的仿真结果Tab.3 Simulation results on 30×30 map

由表3 可知,本文的改进蚁群算法在路径长度、转弯次数以及累计转弯角度等指标上都明显优于基本蚁群算法、文献[23]及文献[24]的算法,这三种算法在障碍物增多的环境中都无法很好地适应,其中本文算法在路径长度上较基本蚁群算法缩短了13.7%、较文献[23]算法和文献[24]算法缩短了8.3%和8.8%;转弯次数也是其中最少的,尤其是较基本蚁群算法减少了64.3%;在累计转弯角度指标上,本文算法占明显优势,较迭代稳定次数表现较优的文献[23]算法减少了41.2%。另外,可以看出文献[12]算法、文献[23]算法和文献[24]算法在复杂环境下出现多次直角转弯,而移动机器人面临直角转弯时比45°转弯会消耗更多的能量,本文算法规划的路径中不存在直角转弯的情况。同时在实际运动中,直角转弯所需要的时间也更多,将大大增加机器人从起始点到目标点的运行时间,而本文算法不仅累计转弯角度最小,也有效避免了直角转弯的出现。

目前针对移动机器人转角减小的研究中,文献[12]中的平滑方法较为普遍,但该方法存在一定的局限性。由表3 可以看出,在路径长度上,文献[12]算法较其他三种算法更优,但本文算法规划出的路径长度是43.3,比其更短;在转弯次数上,两者相同;但在累计转弯角度上,本文算法比文献[12]算法减少了20.4%;除此之外,本文算法在迭代稳定次数和程序运行时间上分别比文献[12]算法减少了50.0%和21.1%。综合来看,本文算法在30×30 的栅格地图中具有更好的计算结果,各方面性能更优,克服了传统路径平滑方法的不足。

由两次不同规模的栅格实验可以看出,环境变复杂时,本文算法仍有良好的适应性并且优势更加明显,可以寻得一条综合性能更优的路径。

5.3 大规模栅格环境

5.3.1 100×100栅格环境

为了进一步验证本文改进算法在规模较大的栅格地图中的适应性,首先建立100×100 规模的栅格地图,将文献[25]的改进A*算法、文献[26]的改进RRT(Rapidly-exploring Random Tree)算法以及本文算法在该规模的地图中进行仿真,此处实验各相关参数取值为:m=100,α=1,β=7,其余按表1 取值。三种算法的路径规划如图12所示。

图12 在100×100地图上三种算法规划的路径Fig.12 Paths planned by three algorithms on 100×100 map

由图12可以直观地看出,相较于改进的A*算法以及RRT算法,本文算法生成的路径拥有更少的转弯次数,三种算法的具体仿真结果如表4所示

表4 在100×100地图上的仿真结果Tab.4 Simulation results on 100×100 map

由表4 可以看出,改进A*算法和改进RRT 算法在路径长度上相差很小,本文算法规划的路径长度上更优;同时,在转弯次数上,本文算法表现更好,规划出的路径最为平滑;本文规划路径的累计转弯角度较前两种算法分别减少了19.9%和37.6%;但在程序运行时间上,表现得不如改进A*算法优异。综合来看,本文算法在100×100 规模的栅格地图中仍具有良好的适应性,规划路径的长度和转角次数是最优的。

5.3.2 200×200栅格环境

将栅格规模再次扩大为200×200,此处将文献[27]的改进蚁群算法作为本文算法的对比算法。将两者在栅格地图中进行仿真分析,两种算法的路径规划如图13所示。

图13 在200×200地图上两种算法规划的路径Fig.13 Paths planned by two algorithms on 200×200 map

由图13 可知,两种算法在大规模的复杂环境中均能从起点顺利抵达终点,与文献[27]算法相比,本文算法规划出的路径更加平滑,转弯次数更少,具体实验结果如表5所示。

表5 在200×200地图上的仿真结果Tab.5 Simulation results on 200×200 map

由表5 可知,本文算法在运行时间上稍逊于文献[27]算法,但在路径长度、转弯次数以及累计转弯角度上都更占优势,分别较文献[27]算法降低了6.7%、55.6%和65.8%。

由以上实验结果,验证了本文改进蚁群算法在复杂地形环境中进行路径规划的可行性和有效性。

6 结语

本文针对基本蚁群算法在移动机器人路径规划应用上存在的缺陷,提出了基于转弯角度约束的改进蚁群算法。规划不同栅格的初始信息素值,在启发函数中有效融合了A*算法的寻路能力,以路径长度和转弯角度两因素为下一步栅格的选择指标,使路径更加平滑,并且在信息素更新中引入了狼群算法的分配原则,同时限制最大最小信息素的值。本文改进之后的算法使蚂蚁能在更短的时间内寻得一条综合路径长度和转角次数的最优路径,降低了移动机器人的能耗损失,延长寿命,使其能高效、安全地移动到目标点,验证了本文算法在复杂环境中的有效性和适应性。

在今后的研究中,将进一步研究蚁群算法参数的取值问题,利用神经网络计算出使路径更优的参数取值,将大大节约调试时间,使算法更加智能化。

猜你喜欢
移动机器人栅格次数
移动机器人自主动态避障方法
栅格环境下基于开阔视野蚁群的机器人路径规划
基于粒子滤波的欠驱动移动机器人多目标点跟踪控制
2020年,我国汽车召回次数同比减少10.8%,召回数量同比增长3.9%
移动机器人路径规划算法综述
超声速栅格舵/弹身干扰特性数值模拟与试验研究
最后才吃梨
一种面向潜艇管系自动布局的环境建模方法
俄罗斯是全球阅兵次数最多的国家吗?
反恐防暴机器人运动控制系统设计