基于改进蚁群算法的电动叉车路径规划技术研究

刘显贵, 赵率棚

(厦门理工学院 机械与汽车工程学院, 福建 厦门 361021)

0 引 言

电动叉车由于其无排放、低噪音、高效率等优点,在港口、仓储及烟草、食品、纺织等行业应用逐渐广泛[1]。路径的选择及优化极大地影响电动叉车的运输效率。优秀的路径规划能力是移动机器人的一个重要指标[2],而路径规划的好坏,关键在于路径搜索算法的选取[3]。目前,常用的路径规划算法主要包括蚁群算法、遗传算法、人工势场法、A*算法等[4-7]。

蚁群算法有很多优点,如正反馈、并行计算、鲁棒性强等,受到研究者的广泛关注[8]。但蚁群算法在计算过程中容易求得局部最优解且收敛性能差,所以很多学者对蚁群算法进行了改进。文献[9]引入精英蚂蚁策略和最大最小蚂蚁机制,通过改进信息素更新方式,更好地平衡了寻优能力和收敛速度。文献[10]采用伪随机状态规则进行路径选择,通过提出一种奖惩机制更新信息素增量,定义一种信息素自适应挥发因子,限制信息素浓度上下限等改进措施,提高了算法收敛速度。文献[11]基于蚁群算法的信息素提出自适应的信息素挥发系数,对启发函数进行相应的变化,提高了算法的搜索效率和准确性。文献[12]结合人工势场法,对启发函数通过距离改进,避免了算法早期由于盲目搜索导致路径交叉及收敛速度慢等问题。文献[13]赋予不同栅格位置不同的初始信息素,设定迭代阈值,自适应调节信息素挥发系数,降低蚁群搜索的盲目性,提高全局搜索能力。

基于蚁群算法的诸多优点,结合电动叉车工作情况,对传统蚁群算法进行改进。为了改变其前期盲目搜索导致收敛速度慢的问题,文中融合人工势场法算法,加入人工势场引力,构建人工势场启发函数中的启发信息函数,指导蚂蚁进行初始搜索,避免了传统蚁群算法搜索过于随机;改进信息素更新规则,根据最优最差蚂蚁策略使得信息素在更小的区间内变化,提高算法的全局搜索能力;提出三角剪枝算法,实现了更优的路径平滑规划,为提高电动叉车工作效率打下良好基础。

1 基于栅格法的环境建模

环境建模是建立电动叉车仿真环境,也是路径规划的载体。栅格法具有简单易实现等特点,因此,文中选取栅格法搭建仿真环境。

2 基本算法

2.1 传统蚁群算法

蚁群算法是受蚂蚁觅食过程启发而设计出来的群智能算法。蚂蚁在觅食过程中会留下信息素,同时会感知信息素,其浓度大小引导向前移动。蚂蚁自身携带的信息素是定量的,所以信息素浓度较高的路径距离是较短的,后续迭代过程中蚂蚁选择此路径的概率就较大。由此形成的正反馈使蚂蚁不断逼近最优路径,找到最优解。蚁群算法的两个重要步骤是概率选择和信息素的更新。

概率选择就是蚂蚁从当前节点选择到下一节点的概率。蚁群算法采用伪随机比例原则进行计算,规则如下:

(1)

其中,蚂蚁k从当前节点i移动到下一节点j的概率为q0,j是使概率值取得最大的节点:

(2)

(3)

τij(t)----t时刻蚂蚁从当前节点i移动到下一节点j的信息素浓度;

τis(t)----t时刻蚂蚁从当前节点i移动到下一节点s的信息素浓度;

ηij(t)----t时刻蚂蚁从当前节点i移动到下一节点j的启发函数;

ηis(t)----t时刻蚂蚁从当前节点i移动到下一节点s的启发函数;

α----信息素重要程度因子;

β----启发函数重要程度因子;

J----除节点j外其他某节点由式(2)产生的随机变量;

ak----可能到达节点的集合;

djg----节点j到目标节点g的欧氏距离。

信息素的更新是指从本次迭代到下次迭代过程,路径中信息素经过累积和挥发所剩余的浓度。各节点浓度不同,从而引导蚁群进行后续的路径选择。所以完成一次迭代后要对信息素进行更新,传统蚁群算法信息素全局更新规则如下:

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

(4)

(5)

(6)

式中:ρ----全局信息素挥发系数;

Δτij(t)----路径(i,j)上释放的信息素之和;

Q----信息素强度系数。

2.2 人工势场法

人工势场法的基本思想是在障碍物周围和目标点构建斥力势场和引力势场,两种力的共同作用使机器人到达目的地。在人工势场中,机器人距离障碍物越近,斥力越大;机器人距离目标点越远,引力越大,到达目标点时引力为零。

设移动的当前位置为

X=(x,y),

目标点的位置为

Xg=(xg,yg),

定义引力势场函数为

(7)

式中:kgra----引力场的增益系数;

|X-Xg|----机器人与目标点的欧氏距离。

定义斥力势场函数为

(8)

式中:krep----斥力势场增益系数;

ρ(x,x0)----机器人与障碍物之间的欧式距离;

ρ0----斥力的有效作用范围。

机器人受到势场中的引力和斥力向目标点移动,并完成向一条无碰撞路径搜索。

3 改进的势场蚁群算法

3.1 改进启发信息函数

传统蚁群算法在最初搜索时,每段路径的起始信息素浓度一致,此时主要差异在启发信息上。由于传统公式路径选择节点启发性不强,导致路径搜索具有盲目性,搜索后的初始路径欠佳,而蚁群算法具有正反馈性,这造成了传统蚁群算法前期搜索较慢,且最终路径易陷入局部最优等问题。

对于传统蚁群算法启发性不强的缺点,文中在启发信息函数中加入人工势场引力,增强启发函数在搜索过程中的目标性,改善算法搜索效率,改进的启发信息为:

(9)

(10)

(11)

将式(9)～式(11)代入改进启发信息ηij(t)*中得到

(12)

式中:δ----加入人工势场引力的因子;

α----当前节点j到目标点的人工势场引力;

φ----常数,取值范围(0, 1);

π----正比例系数;

d(j,H)----当前节点j到目标点H的距离,距离越大,机器人受到人工势场的引力就越大,距离越小,机器人受到的引力值则越小。

3.2 改进信息素更新规则

在传统蚁群算法中,随着地图上蚂蚁迭代数量的增加,保存信息素的数量逐渐积累,使得蚂蚁越来越多地走上信息素浓度高的路径,这在一定程度上是可行的,但容易导致蚁群行走路径陷入局部最优。为了防止局部最优解的产生,采用自适应性的信息素调节模式τij(t)*,根据更新后信息素的传统添加,将前一代所有蚂蚁在最佳路线上携带的信息素常数与所有蚂蚁在较差路线上携带的信息素常数之间做减法运算,使得信息素在更小的区间内变化,

τij(t+1)*=(1-p)·Δτij(t)+Δτij(t)*,

(13)

(14)

(15)

式中:Δτij(t)*----最优路径上蚂蚁所携带信息素总和与最差路径上蚂蚁所携带信息素总和的差值,是额外的信息素增量;

v----本次循环最优路径上的蚂蚁数量;

w----本次循环最差路径上的蚂蚁数量;

Lmin----本次迭代最优路径长度;

Lmax----本次迭代最差路径长度。

3.3 路径优化与更新

生成的路径可能有大量的冗余线和转弯点,这不仅会增加路径的长度,而且会导致电动叉车在移动过程中需要反复改变运动方向,不利于电动叉车的快速移动。

图 1 三角剪枝算法原理

如图1中实线 A-B-D-C为传统蚁群算法搜索的最短路径,而通过剪枝算法优化后,实线 A-B-C为最短搜索路径。可以看出,剪枝算法优化路径与原路径相比长度明显减少,搜索时间也相应减少。可知三角剪枝法可以有效地消除转弯点所产生的多余路径。

三角剪枝算法原理是将转弯节点相连,如果连接后的路径不经过障碍物,则去除该两点间冗余的转弯点和折线,对路径进行更新。

定义传统路径节点集合为H,H={h1,h2,…,hn},剪枝优化后节点集合为P,P={p1,p2,…,pn},两节点m1,m2的连线m1m2经过的元素集合为Nm1m2,Nm1m2={n1,n2,…,nn},障碍物元素集合为O,O={o1,o2,…,on}。在传统路径节点集合H中顺次拿出3个节点,如h1,h2,h3,将h1与h3相连得到h1h3,若

Nh1h3∪O=∅。

(16)

则把h1h3定义为剪枝优化线路,将h1,h3纳入剪枝优化后的集合P中,将这两个节点重新定义为p1,p2,以此类推,直至判断完集合H中所有节点,把剪枝优化线路用实线表示。

3.4 算法流程

1)建立环境模型。利用栅格法建立机器人工作环境,设置可移动栅格为0,障碍物栅格为1。设置起点位置为S和目标点位置为E。

2)初始化基本参数。

3)选择路径节点。蚂蚁k按照转移概率公式选择下一可行节点,由于加入人工势场的引力函数,蚂蚁在初始阶段就可以感知目标点所在的位置,从而大大减少了随机搜索方向的可能性,对此将传统禁忌表TABUK去除。

4)记录各路径长度及其蚂蚁数量。每次迭代完成后,对每只蚂蚁的路径曲线和路径长度进行记录,并对本次迭代从起点到达目标点的蚂蚁数量记录,写入储存结构CELL。

5)信息素更新。根据CLEE中的数据,找出本次迭代的最优路径和最差路径上蚂蚁数量,根据式(14)～式(16)进行信息素浓度更新。

6)结束迭代。判断算法是否达到最大迭代次数,若达到,则输出最优路径;若没有达到,则返回3)进行再次迭代。

7)进行优化。对于得到的最优路线,按照三角剪枝算法进行优化,得到最优路径线路。

4 实验与仿真分析

为了验证文中改进势场蚁群算法的性能,在Matlab 2021a仿真平台进行测试,设置两种平面栅格仿真环境。设置仿真参数,改进蚁群算法中迭代次数为100次,蚂蚁数量为50。单位栅格长度为1,总长为20,机器人起点为(0.5,19.5),终点为(19.5,0.5)。信息素浓度α为1,距离启发因子β为2,信息素增强系数Q为10,信息素挥发系数ρ为0.8。传统蚁群算法中距离启发因子β为7,信息素增强系数Q为1,信息素挥发系数ρ为0.3,其余参数相同。通过传统蚁群算法和改进势场蚁群算法进行对比,验证了改进势场蚁群算法的性能。

4.1 环境1

凹形障碍物可以导致路径搜索长度增加[8],故在搭建20*20的栅格环境1时,充分考虑凹形障碍物的影响,两种算法的最优路径和收敛曲线分别如图2和图3所示。

(a) 最优路径

(a) 最优路径

图3(a)中曲线1代表改进蚁群算法直接生成的原始路径;曲线2代表原始路径经过三角剪枝算法计算修建后生成的改进路径。

由图2(a)和图3(a)可知,两种算法都能规划出一条可行进路径,改进势场蚁群路径和传统蚁群算法路径差别较小,去除多余转折点路径相对于传统蚁群算法路径打破了八自由度移动的限制,转弯次数明显减少,轨迹更加平滑。

从图2(b)和图3(b)可知,改进蚁群算法和传统蚁群算法经过一定的迭代次数后均达到较短路径,但传统蚁群算法收敛速度较慢,收敛性能较不稳定,搜索效率较低。改进蚁群算法明显提高了收敛速度,收敛性能更加稳定,搜索效率较高。

对两种算法各运行10次,从最优路径长度、最差路径长度、平均路径长度和平均收敛代数上进行比较,见表1。

表1 20*20环境算法性能

由表1可知,在路径长度方面,去除多余转折点后,最终路径比传统蚁群算法路径在最优路径长度、最差路径长度及平均路径长度分别减少4.31%、2.84%、3.23%。在平均收敛代数方面,改进蚁群算法比传统蚁群算法减少96.97%。结果表明,文中算法具有路径搜索能力强和收敛性快的特点。

4.2 环境2

为了进一步验证文中算法的路径寻优能力,将栅格环境改为30*30,增加其复杂程度。调整传统蚁群算法迭代次数为300,使其收敛。得到两种算法的最优路径和收敛曲线分别如图4和图5所示。

(a) 最优路径

(a) 最优路径

图4(a)中曲线1代表改进蚁群算法直接生成的原始路径;曲线2代表原始路径经过三角剪枝算法计算修建后生成的改进路径。

由图4(a)和图5(a)可知,在复杂环境下,改进蚁群算法和传统蚁群算法经过一定的迭代次数均能规划出一条无障碍通行路径,改进蚁群算法去除多余转折点后生成的路径转弯次数减少,且轨迹更加平滑。

由图4(b)和图5(b)可知,在复杂环境下,传统蚁群算法收敛速度慢,收敛性能不稳定,搜索效率低;改进蚁群算法仍能保持较快的收敛速度、较稳定的收敛性能和较高的搜索效率。

对两种算法各运行10次,从最优路径长度、最差路径长度、平均路径长度和平均收敛代数上进行比较,见表2。

表 2 30*30环境算法性能

由表2可知,在路径长度方面,去除多余转折点后,最终路径比传统蚁群算法路径在最优路径长度、最差路径长度及平均路径长度分别减少3.05%、6.31%,5.45%。在平均收敛代数方面,改进势场最优最差蚁群算法比传统蚁群算法减少93.40%。结果表明,在复杂环境下,文中算法仍具有路径搜索能力强和收敛性快的特点。

5 结 语

基于栅格法对移动机器人工作空间进行环境建模,针对传统蚁群算法在路径规划中存在的不足,提出一种改进的蚁群算法。

1)通过人工势场引力函数对启发信息进行改进,减少路径搜索初期的盲目性,且该方法在首轮迭代生成的路径对后续迭代过程产生正反馈作用,加快了算法的收敛速度,有效提高了算法的搜索效率。

2)改进了信息素更新规则,通过引入最优最差蚂蚁策略,削弱信息素累计效果,有效避免了蚁群行走路径陷入局部最优。

3)构建三角剪枝算法去除冗余线和转弯点,打破了传统蚁群算法搜索规则,使路径长度变短且更加光滑,符合电动叉车的实际运动情况。

4)仿真结果表明,相对于传统蚁群算法,改进的蚁群算法可以更高效地规划出一条更优、更平滑的路径。