基于改进蚁群算法的自动落布车路径规划

沈丹峰,王 博,李许锋,白鹏飞

(西安工程大学 机电工程学院,陕西 西安 710048)

0 引 言

自动落布车是纺织企业实现智慧车间的重要组成部分。落布车的自主运动主要是指根据预定的目标轨迹及落布车的状态和纺织车间里的环境信息,自动控制落布车到达指定的目标点[1]。由于自动落布车在纺织车间运行的工作环境较为复杂,为保证自动落布车在车间能够正常工作,有必要对自动落布车进行路径规划。

路径规划问题实质是如何利用已知的地图信息,找到一条从起始点到终止点的无障碍且长度最短的路径。目前常用的路径规划算法包括蚁群算法[2-3]、遗传算法[4-5]、粒子群算法[6-7],以及A*算法[8-9]等。蚁群算法具有正反馈高、鲁棒性强、分布式计算等优点,但是蚁群算法在算法初期搜索过于随机而使得算法搜索效率低,以至于算法整体收敛速度缓慢,信息素浓度在算法中后期过于集中会导致算法搜索停滞和易陷入局部最优解[10]。因此,很多学者都对蚁群算法进行了优化。徐菱等针对蚁群算法效率低的问题提出一种16个搜索方向24个邻域的改进方式,针对启发信息引入向量夹角的思想,并在转移概率部分添加转移概率控制参数,提高了蚁群算法全局搜索能力[11];赵增旭等在转移概率中引入向量夹角,同时融合了插点策略使算法收敛速度提高,路径拐点减少,更加平滑[12];CHEN等在蚁群算法中引入人工势场法进行改进,提出一种可通过调整动态预警步长进行避障的改进蚁群算法[13];WANG等在改进蚁群算法中引入方向偏心扩展法,提出一种可用于解决静态未知环境与动态已知环境下路径规划问题的改进蚁群算法[14];王玉等将跳点搜索算法与蚁群算法相融合,并引入双向蚁群的思想缩短了寻优路径[15];叶轩等通过添加动态随机机制的转移概率公式提高了算法的全局搜索能力,同时提出一种非必要转折点优化算法对路径进行二次优化,减少了路径长度[16];何心等通过引入目标方向启发因子提高了算法收敛速度,在采用有效拐点的路径优化策略的基础上引入三次B样条曲线使得规划的路径更加平滑[17];钱平等通过融合蚁群算法与遗传算法加快了算法收敛速度并解决了算法陷入局部最优的问题,同时使用平滑机制使得路径更加平滑同时提升了算法的避障性能[18]。

以上的方法在一定程度上改进了传统蚁群算法的搜索效率与规划的最优路径。本文针对自动落布车工作环境复杂,传统蚁群算法存在的收敛速度慢且容易陷入局部最优的问题,提出改进蚁群算法(IACA)。该算法引入细菌觅食算法的趋化操作对信息素更新公式进行改进,同时自适应调整信息素挥发因子ρ,减少搜索时间,提高全局搜索能力。

1 环境建模

规划路径前,需要建立一个二维地图,常见的二维地图建模方法有拓扑图法、单元数法以及栅格图法,因为栅格图法相比其他2种地图建模方法更容易实现且更直观地看出障碍物和可行区域,所以选择栅格图法对地图建模[19]。矩阵中的0和1分别表示通行节点(白色栅格)和障碍物节点(黑色栅格)[20]。

规定每个栅格的边长是1。坐标原点O在栅格地图左下角,原点向上和向右为y轴、x轴正方向。蚂蚁算法采用八邻域搜索法。

直角坐标系与栅格地图转换公式为

(1)

式中：Mx代表栅格序号;n代表每行或每列的栅格数目;mod(Mx,n)为Mx/n的取余函数;ceil(Mx/n)为求大于等于Mx/n的最小整数函数。

通过式(1)可以获取自动落布车在栅格地图中的坐标位置。

2 传统蚁群算法的原理

蚁群算法是一种通过模拟蚂蚁群体与环境之间的信息交互,实现最优路径选择的元启发式算法,具有自组织、分布式与正反馈等特点[21]。

蚂蚁在构建行走路径时,会按照一个随机概率选择下一步所走节点,通常是通过轮盘赌法计算状态转移概率。计算状态转移概率公式为

(2)

启发信息值计算公式为

ηij(t)=1/dij

(3)

(4)

式中：dij是节点i到节点j的欧氏路径距离。

蚂蚁路径信息素更新为

(5)

3 IACA算法

传统的蚁群算法在应用于路径规划问题中时容易出现以下问题：1)传统的蚁群算法在早期进行搜索时,搜索空间较大,加上蚂蚁在路径留下的信息素较为均匀,使得蚂蚁容易进行盲目搜索,产生大量的无用路径,造成算法收敛速度慢;2)传统蚁群算法后期容易出现某条路径信息素浓度较高,使得算法陷入局部最优的情况。为改善传统蚁群算法,本文提出一种改进蚁群算法IACA。

3.1 引入细菌觅食算法BFO

BFO算法就是模拟大肠杆菌在觅食行为过程中所体现出来的生理行为,是进行建模迭代产生最优解的一种仿生搜索算法[22]。该算法具有全局最优、易跳出局部最优、并行搜索和鲁棒性强等优点[23]。

趋化操作是对细菌寻找适合自身生存环境的觅食行为的模拟,包括旋转和游动。细菌向任意方向移动单位步长定义为旋转[24]。旋转后计算适应度值,若得到的路径适应度值更小则继续沿着该方向游动,直到达到最大步长或者适应度值不发生改变,此过程称为游动[24]。趋化操作位置更新公式为

P(e,f+1,g,h)=P(e,f,g,h)+

(6)

(7)

将进行信息素更新公式改进的蚁群算法与传统蚁群算法在文献[19]的20×20地图中的a类地图进行仿真对比,结果如图1所示。

图 1 不同算法收敛曲线对比Fig.1 Convergence curve comparison of the different algorithms

从图1可以看出：相比传统蚁群算法,改进后的算法在迭代次数方面减少7次,在最小路径长度方面降低3.2 m。因此,改进后的算法相比传统蚁群算法有了很大的改善。

3.2 自适应调整信息素挥发因子ρ

一般蚁群算法的信息素挥发系数为常数[25]。信息素挥发因子ρ对于算法整体的效果有显著的影响。ρ越大,信息素挥发速度越快,从而影响算法收敛速度;ρ越小,信息素挥发速度越慢,影响全局搜索能力,容易陷入局部搜索[26]。针对以上情况,提出一种假设：如果可以使信息素挥发因子ρ实现自适应变化,迭代开始数值较大,随着迭代的进行逐渐减小,就可以在提高算法全局搜索能力的前提下降低收敛时间,又可以避免算法陷入局部最优,从而提高算法效率。为实现假设,对信息素挥发因子ρ作自适应调整,构造如下

ρ=exp[-(s/p)r],0

(8)

式中：s为当前的迭代次数;p为最大迭代次数,取p=100。

对r取值进行讨论。图2(a)是r取值从1～6对ρ数值影响结果,图2(b)是在文献[19]的a类20×20地图中,算法对r取值从1～6的仿真结果。

(a) ρ值变化

由图2(a)看出,构造式(8)中,信息素挥发因子与迭代次数的变化趋势是迭代前期数值较大,后期数值较小,满足假设。由图2(b)看出,当r=2时,算法的结果最好,取r=2。

将只进行自适应调整信息素挥发因子改进的蚁群算法与传统蚁群算法在文献[19]的20×20地图中的a类地图进行仿真对比,结果如图3所示。

图 3 自适应调节ρ与传统蚁群算法收敛曲线对比Fig.3 Convergence curve comparison ofthe adaptive adjustment ρ and traditional ant colony algorithm

由图3可以看出：相比传统蚁群算法,改进后的算法在迭代次数方面减少39次,在最小路径长度方面减少3.3 m。因此,改进后的算法相比传统蚁群算法有了很大的改善。

3.3 IACA算法流程

本文改进的蚁群算法IACA是在传统蚁群算法的基础上,对信息素挥发因子ρ进行自适应调整,并引入细菌觅食算法的趋化操作对信息素更新公式进行改进。具体流程图如图4所示。

4 IACA算法仿真分析

为验证IACA应用于自动落布车路径规划方面的效果,利用MATLAB对IACA、ACA和文献[19]中的改进算法进行仿真对比。仿真环境：Windows 10(64位)操作系统、Intel(R) Core(TM)i5-8250U处理器、1.60 GHzCPU。

4.1 参数初始化

首先对3种算法的参数进行赋值,具体如表1所示。

表 1 相关参数数值

为验证IACA的有效性,引入文献[19]的20×20地图中的a、b类地图与30×30地图,分别对IACA、传统蚁群算法和文献[19]的改进蚁群算法进行仿真对比。

4.2 20×20地图环境

4.2.1 20×20的a类地图

将IACA与传统蚁群算法以及文献[19]的算法放入20×20中的a类地图中进行仿真验证。其中IACA算法寻优结果如图5(a)所示,传统蚁群算法与文献[19]寻优结果如图5(b)、(c)所示,3种算法迭代次数与最小路径长度如图5(d)所示。

(a) IACA

3种算法在a类20×20地图进行仿真实验得到的各实验数据如表2所示。

表 2 a类20×20地图各类实验数值

从表2可以看出,IACA算法在最小路径长度方面比传统蚁群算法减少了9.3%,比文献[19]算法减少了0.8%;在迭代次数方面,IACA比传统蚁群算法减少了80.4%,比文献[19]算法减少了52.6%;在迭代时间方面,IACA比传统蚁群算法减少了28%,比文献[19]算法减少了18.9%。

4.2.2 20×20的b类地图

将IACA与传统蚁群算法以及文献[19]的算法放入20×20中的b类地图中进行仿真验证。其中IACA算法寻优结果如图6(a)所示,传统蚁群算法与文献[19]寻优结果如图6(b)和图6(c)所示,3种算法迭代次数与最小路径长度如图6(d)所示。

(a) IACA

3种算法在b类20×20地图进行仿真实验得到的各实验数据如表3。

表 3 b类20×20地图各类实验数值

通过表3可以看出,在b类地图中,IACA在最小路径长度方面比传统蚁群算法减少了3.1%,比文献[19]算法减少了0.5%;在迭代次数方面,IACA比传统蚁群算法减少了81.6%,比文献[19]算法减少了64%;在迭代时间上,IACA比传统蚁群算法减少了13.4%,比文献[19]算法减少了10.4%。

4.2.3 30×30地图环境

为验证IACA在复杂环境下的有效性与优越性,将IACA算法、传统蚁群算法与文献[19]算法在30×30地图中进行仿真对比验证。其中IACA仿真结果如图7(a)所示,传统蚁群算法与文献[19]算法在地图中的仿真结果如图7(b)、(c)所示。图7(d)是这3种算法收敛时的收敛次数与最小路径长度。

(a) IACA

从图7(a)与图7(b)中可以看出,IACA算法相比传统蚁群算法路径上更加平滑,拐点数量更少。

3种算法在30×30地图进行仿真实验得到的各实验数据如表4所示。

表 4 30×30地图各类实验数值

在最小路径长度方面,IACA算法比传统蚁群算法减少了17.6%,比文献[19]算法减少了2.3%;在迭代次数方面,IACA算法比传统蚁群算法减少了79.7%,比文献[19]算法减少了55.9%;在迭代时间方面,IACA比传统蚁群算法减少了16.9%,比文献[19]算法增加了1.6%。

在20×20地图中,IACA算法比传统蚁群算法在最小路径长度方面平均减少了6.3%,迭代次数方面平均减少81.1%,迭代时间上平均减少20.7%;相比文献[19]算法,IACA算法在最小路径方面平均减少0.7%,迭代次数方面平均减少59.1%,迭代时间上平均减少14.5%。从以上数据可以看出,IACA算法相比传统蚁群算法无论是在最小路径长度还是在迭代次数上都具有明显优势;相比文献[19]算法,虽然在最小路径距离方面差异不大,但在迭代次数上,IACA算法更有优势。

综上所述,IACA算法在最小路径距离、迭代次数与迭代时间方面比传统蚁群算法都有很大提升,在实际中可以提高自动落布车的运行效率。

5 实验分析验证

为进一步验证IACA算法在织布车间环境中的运行效果,设计了基于ROS系统的机器小车实验。实验使用的ROS小车搭载支持Ubuntu系统的树莓派4B板,通过SSH与PC计算机进行远程连接,并通过其搭载的思岚AI单线激光雷达对室内封闭环境中的类似织机的箱型障碍物进行扫描建立地图,再利用Rviz三维可视化平台将地图进行可视化处理。应用的建图算法为Gmapping算法。

实验步骤：首先利用ROS系统与Gmapping算法构建模拟的织布车间实验环境地图。ROS小车与构建的织布车间实验环境地图如图8(a)、(b)所示。

(a) 实验用ROS小车

在实验中,为保护小车避免发生碰撞,对实验用的障碍物织机进行膨胀处理,通过设置膨胀半径R(R=0.2 m),扩大障碍物占地面积,从而降低了小车与织机进行碰撞的风险。

其次,在建立了织布车间的模拟环境地图之后,分别采用IACA算法与ACA算法进行路径规划步骤。实验全过程通过电脑PC端的Rviz三维可视化平台将小车运动过程呈现出来,如图9(a)、(b)、(c)所示。实验小车分别用传统蚁群算法与IACA进行路径规划的路线图如图9(d)所示,其中黑色路径是传统蚁群算法,红色路径是IACA算法。

(a) 小车在起点位置

实验采用的ROS小车的运动速度为0.5 m/s,图中传统蚁群算法与IACA规划的路径长度相同,但IACA总运行时间是30.65 s,传统蚁群算法总运行时间为33.52 s,相比传统蚁群算法,IACA在运行时间上减少了8.6%。

由此可以得出：IACA能够寻找到一条不亚于传统蚁群算法的路径,同时耗时更短。该结论与仿真结果基本吻合。

6 结 语

本文针对自动落布车使用传统蚁群算法进行路径规划过程中出现的收敛次数多、时间长,收敛速度慢,容易陷入局部最优的问题,提出一种改进蚁群算法IACA。算法首先对信息素挥发系数ρ进行自适应调整,然后引入细菌觅食算法的趋化操作对信息素更新公式进行改进,从而使改进后的算法能够避免出现陷入局部最优的情况,同时降低了收敛时间,提高了收敛速度。实验结果表明,IACA相比传统蚁群算法寻优时间更短,收敛速度更快。在实际生产中,可以有效提高自动落布车路径规划效率。但从实验中可看出,改进算法在最小路径长度方面提升不大,还有改进空间。