基于靠近目标粒子群算法的AGV路径规划

屈新怀, 单 笛, 孟冠军

(合肥工业大学 机械工程学院,安徽 合肥 230009)

移动机器人(automated guided vehicle, AGV)导航运输车也被称作移动机器人,是一种装有导航定位及安全保护装置的、能够按照规划路径行驶且具有移载功能的运输小车。AGV最显著的特点是无人驾驶、柔性较好、自动化与智能化水平高。随着社会进步以及工业技术的快速发展,AGV已经成为当今生产以及自动化仓储系统的重要工具之一,对AGV及其关键技术的研究,可以有效降低成本,提高生产率,而AGV路径规划是众多研究中的关键一环[1-3]。

路径规划问题通常分为环境建模、路径搜索、路径平滑3个步骤。其中环境建模是将实际的物理空间抽象成算法能够计算的抽象空间,现阶段常采用栅格法、可视图法、拓扑法、自由空间法等方法[4-5],传统的路径规划方法有A-star算法[6]、Dijkstra算法[7]、RRT算法[8]等,但这些算法常存在鲁棒性差、精度低的问题。后期学者多应用群体智能算法，如遗传算法[9]、蚁群算法[10]等,并对群智能算法进行改进与优化,大大提高了路径规划的精度和效率[11]。

本文对障碍物进行多边化及膨胀处理,建立多目标适应度函数并提出统一化权重系数,在传统粒子群算法中引入Metropolis准则,加速算法跳出停滞搜索状态,引入自适应引力系数,从而提出靠近目标的粒子群算法,并将其应用到AGV路径规划中。该算法所求得的路径长度更短,同时在路径平滑度、算法稳定性上表现更优。

1 环境建模

1.1 问题描述及障碍物处理

静态环境下的路径规划是在障碍物已知的情况下,寻找一条最优的从起点至终点的无碰撞路径。本文旨在求得路径最短且AGV转弯最平滑的路径,即进行多目标优化。

在研究机器人运行路径时不考虑AGV体积大小,故需对AGV工作空间中的障碍物进行多边形转换及膨胀处理,以保证AGV行驶的安全性,避免其与障碍物边界发生擦碰。如图1所示,先将不同形状的障碍物按AGV体积的最大半径进行膨胀,再转换成凸多边形,转化原则为凸圆弧或不规则部分取水平或垂直的最高点切线,凹陷部分用直线填充,直线部分不进行操作。

图1 障碍物“多边化”及“膨胀”处理

1.2 环境建模

AGV运行环境及建模示意图如图2所示。图2a中采用自由空间法为AGV工作环境建立坐标系Oxy,黑色实心多边形为经多边化及膨胀处理的障碍物,记起点坐标为O(x0,y0),终点坐标为G(xn,yn),从起点到终点不穿过障碍物的连线为一条有效路径。

为确定各位置坐标点,按障碍物顶点划分区域,保证AGV在每个区段内只需对一条障碍物边界进行避障处理,从而简化避障过程。如图2b所示,从所有障碍物多边形的顶点引出一条平行于y轴的虚线贯穿坐标系,算法取初始解时在每条虚线上随机获取一个不在障碍物内部的位置坐标点Pij(xij,yij),且保证相邻坐标点之间的连线不穿越所有障碍物,则所有位置坐标点的连线所构成的由起点至终点的一条无碰路径即可表示为Pi=(Pi0,Pi1,Pi2,…,Pij,…,Pi(n-1),Pin),其中j=0,1,…,n。若Pi中各点之间的连线不穿过障碍物,则视该条路径为有效路径。

图2 AGV运行环境及建模示意

2 靠近目标粒子群算法

2.1 传统粒子群算法

粒子群算法是一种生物进化算法,最初是受到鸟群觅食过程的启发[12]。在优化问题的解空间内随机初始化一群粒子,每个粒子代表目标函数的一个可行解,其位置由粒子运动速度决定,而粒子运动速度受粒子历史最优解和群体历史最优解影响。

假设粒子群中包含n个粒子,其搜索区域的维数为D维。xi=(xi1,xi2,…,xiD)为粒子i在D维空间中的位置,vi=(vi1,vi2,…,viD)为粒子i的飞行速度,Pbest为粒子的个体极值,即粒子i在寻优过程中所找到的历史最优解,则该粒子在D维空间中的位置可以表示为Pi=(Pi1,Pi2,…,PiD),整个群体在搜索过程中寻找到的历史最优解为gbest,其在D维搜索空间的位置表示为Pg=(Pg1,Pg2,…,PgD),对于第k+1次迭代,每个粒子的每一维度的移动速度和位置都按照下列迭代公式进行更新迭代:

(1)

(2)

2.2 靠近目标粒子群算法

针对传统粒子群算法的缺陷,本文对算法进行了改进,在算法迭代过程中引入Metropolis准则,并提出自适应引力系数的概念,以提高粒子群算法的搜索效率及精度。

(1) 在算法迭代后期,粒子种群多样性急剧下降,使算法陷入局部最优值而出现“早熟”现象。针对该问题,引入Metropolis准则,并将该准则应用到群体最优值更新部分,以增加迭代后期解的更多可能性,避免陷入局部最优解。

本文以最大迭代次数k来表示Metropolis准则中温度的概率,改进公式为:

(3)

更新群体最优值时，按(3)式概率接受非最优解的新解作为当前群体最优,(3)式中迭代次数k逐一增加,概率P随k的增加而变小,即算法迭代后期接受该新解的概率逐渐变小,搜索效率提高。群体最优值更新部分改进后程序代码如下:

输入:y(i);F(i)

//y(i)为粒子;F(i)为粒子适应度值

输出:gbest;F(gbest)

//gbest为群体最优粒子;F(gbest)为群体最优粒子适应度值

ifF(i)

gbest=y(i);

F(gbest)=F(i);

elseif exp((1-k2)/k)≥srand

gbest=y(i);

F(gbest)=F(i)

end.

(2) 因为算法只利用个体最优和群体最优进行迭代,所以最终解无法达到一定的精度,当粒子被困于较差搜索区域难以自动跳出时,就会导致搜索效率降低,算法收敛变慢的问题。本文为了解决上述路径规划问题提出自适应引力系数的概念,使粒子在搜索后期趋近于个体最优及群体最优值迭代的同时,受目标点引力影响,加速靠近并搜索到最优解。

设求解当前坐标点(xi,yi),利用路径规划目标终点(xn,yn)以及当前坐标点的前一个坐标点(xi-1,yi-1)之间的最短线段,即两点连线来控制当前点迭代范围,已知两点所在的直线方程为:

(4)

则当前点(xi,yi)的横坐标值xi在该直线上对应的纵坐标值yi为:

(5)

求得的(xi,yi)点即为理想点。为保证各坐标点在迭代过程中能够趋于该理想点,在传统粒子群算法的位置迭代公式中,增加自适应引力系数a,改进后的迭代公式为:

(6)

其中,a为自适应引力系数,其取值如下:

(7)

由于该算法逐点优化迭代,当前点与终点连接的线段即为最短路线。为保证下一点靠近当前点与终点连线进行搜索,在障碍物环境中增加引力因子,在避开障碍物的情况下快速向最优解靠近,提高搜索效率的同时提高求解精度。

3 基于改进算法的AGV路径规划

3.1 粒子编码

粒子编码指粒子位置的表达方式,是粒子群算法设计应用的关键问题,本文对AGV路径规划问题中的粒子进行编码。设粒子数为m,粒子中除起点外的坐标点数为n,算法开始时随机生成的每条可行路径为待优化的一个粒子,包含构成该路径的各个坐标点,粒子集M可表示为:

M={(x0,yi0),(x1,yi1),…,(xj,yij),…,

(xn,yin)}

(8)

其中:i=1,2,…,m;j=0,1,…,n。

环境建模阶段,按障碍物顶点对坐标系进行划分,故粒子中的各坐标点x值为定值,算法求解过程则是搜索最优y值解集的过程.

3.2 适应度函数建立

在移动机器人路径规划问题中,最终目标是要规划出一条最优的可行路径,其约束条件是路径不与障碍物相交,且要求与障碍物保持一定的安全距离。适应度值是评估路径优劣程度的标准,因此需将规划路径时所涉及的一些要求包含进去并用数值的形式体现,以便比较与衡量。本文适应度函数包含路径长度和路径平滑度。

(1) 路径长度评价函数F1。路径长度评价函数F1为各分段路径长度之和，即

(9)

其中,n为环境坐标系中的区域划分线数量。

(2) 路径平滑度评价函数F2。路径平滑度通常取决于AGV移动时的转角大小,故用相邻2条路段之间的夹角之和作为判断路径平滑度优劣的指标。夹角越接近180°,路径越平滑。

(10)

其中:θ(PiPi+1,Pi+1Pi+2)为2条相邻路段PiPi+1与Pi+1Pi+2之间的夹角。相邻路段夹角与180°差值总和越小,则路径越平滑,AGV转弯消耗越小。

对于多目标优化函数,需要对多目标进行归一化处理。本文参考了标准归一化处理方法,同时结合多目标权重分配,以路径长度权重取1为基础对多目标进行统一化。统一化权重系数β为:

(11)

因此,AGV路径规划适应度函数为:

F=F1+βF2

(12)

3.3 算法步骤

本文将求解AGV最优路径问题简化为求解构成最优路径的坐标集,划分环境坐标系得到虚线集lj={l0,l1,…,ln},具体划分方法见第1节。虚线上部分范围被障碍物覆盖,则其对应障碍物为Dj=(0,D1,…,Dn-1,Dn)。在各虚线上取一个坐标点,所有坐标点连线最终构成一条可行路径,虚线集对应坐标点的横坐标xj=(x0,x1,…,xj,…,xn)为定值,则算法所寻优的解即为各坐标点的纵坐标集yij=(y0,yi1,…,yij,…,yn)。其中:l0为坐标系y轴;y0、yn分别为起点和终点纵坐标。

基于靠近目标粒子群算法的AGV路径规划步骤如下:

(1) 以AGV运行起点为原点建立平面直角坐标系,对障碍物进行多边化处理和膨胀处理后,过障碍物各顶点绘制垂直于x轴的虚线,得到虚线集lj={l0,l1,…,ln}。

(2) 参数初始化。确定迭代公式参数c、ω、种群数量m、粒子中包含的坐标点个数n、最大迭代次数maxgen;确定坐标取值范围,y=max(xn,yDmax),其中,xn为终点横坐标,yDmax为障碍物顶点纵坐标最大值;确定最大迭代速度vmax∈(0.1lDmin,0.2lDmin),其中,lDmin为与虚线集重叠的障碍物边界的最小长度。

(3) 初始化粒子。随机生成各坐标的初始迭代速度v=vmaxrands(n,m),v≤|vmax|;随机生成各坐标点位置构成初始粒子(xj,yij),yij∈Ml,其中Ml为虚线l上未被障碍物覆盖的纵坐标集合。

(4) 计算各粒子适应度F(j),并记录个体最优值Pbest(j)及群体最优值gbest。

(5) 按改进后的迭代公式(6)更新粒子的速度与位置,并计算更新后粒子的适应度函数值。

(7) 若搜索结果满足终止条件或迭代次数达到上限,则算法结束;否则转至步骤(5)继续迭代。

4 实验仿真与结果分析

使用仿真实验对本文提出的靠近目标粒子群算法进行验证。AGV普通工作环境为7 m×6 m,粒子种群数为80,算法最大迭代更新次数为60次,最大迭代速度vmax=0.18,粒子维数与构成最终路径的坐标点个数一致，即D=8。对于复杂环境,AGV工作环境为10 m×7.5 m,粒子种群为180,算法最大迭代更新次数为100次,最大迭代速度为vmax=0.1,粒子维数取D=13。2种环境中均取c1=149 445,c2=149 445,ws=0.9,we=0.4,AGV起始坐标均为(0,0),目标点坐标分别为(7,6)和(10,6),算法最大循环次数均为20次。

实验分为2组,分别验证传统粒子群算法和靠近目标粒子群算法在普通和复杂环境下的算法有效性和路径规划能力。该实验对传统粒子群算法及靠近目标粒子群算法分别在普通环境下运行1 000次,在复杂环境下运行1 800次。普通环境和复杂环境运行数次后平均值的规划结果如图3、图4所示,普通环境和复杂环境下算法运行数次的路径规划统计数据见表1、表2所列。

图3 普通环境下算法路径规划及求解迭代示意图

由图3和表1可知,普通环境下2种算法均可规划出一条可行路径,但靠近目标粒子群算法相较于传统算法路径更短且更平滑,迭代时间更短,收敛速度更快。对比2种算法的求解方差可知,靠近目标粒子群算法求解更稳定,而传统算法所求解的波动较大。

表1 普通环境下2种算法数据统计

由图4可知,复杂环境下，传统粒子群算法更容易陷入局部最优解,而靠近目标粒子群算法则在数次运算中均避开了局部最优解。

由表2可知,靠近目标粒子群算法在路径长度、迭代稳定性、收敛速度及算法稳定性方面均优于传统算法。

图4 复杂环境下算法路径规划及求解迭代示意图

表2 复杂环境下2种算法数据统计

为了更直观地验证改进算法的稳定性,在普通工作环境中,对传统粒子群算法和靠近目标粒子群算法各在其迭代60次的基础上循环计算20次,得到2种算法的20次计算结果并绘制求解结果变化折线，如图5所示。

从图5可以看出，相较于传统算法,靠近目标粒子群算法求解结果十分稳定,没有大幅度波动，且更接近最优解。

靠近目标粒子群算法在路径长度、收敛速度等方面的优势主要在于Metropolis准则能使算法避开局部最优解,及时跳出较差区域,相较于传统算法能更易搜索到最优解;自适应引力系数的提出则让算法运行时受目标引力作用,加快收敛速度,相较于传统算法能更快找到最优解。仿真实验结果充分说明了靠近目标粒子群算法的有效性及稳定性。

图5 2种算法求解结果变化折线图

5 结 论

在AGV路径规划研究中,本文针对传统粒子群算法易陷入局部最优解等问题,提出靠近目标粒子群算法以优化算法性能,提高算法效率,引入Metropolis准则并应用到算法中,避免了算法陷入局部最优解的问题,并有效加快了算法跳出停滞状态的速度;在传统算法中引入自适应引力系数,并将其应用到迭代公式中,使算法靠近目标进行快速迭代,明显加快了收敛速度,提高了搜索效率。仿真结果表明,本文提出的靠近目标粒子群算法在收敛速度、精度、稳定性等方面均具有明显优势,具备一定的实际应用价值。