基于冲突预测的多自动导引小车避碰决策优化

曹小华，朱 孟

(武汉理工大学 物流工程学院，湖北 武汉 430063)

0 引言

在“中国制造2025”大背景下，我国的工业水平不断发展，智能制造进程不断推进，柔性装配流水线和自动化立体仓库全面进入高速发展阶段。由于在成本、效率、灵活性、可靠性等指标上具有优势，自动导引小车(Automated Guided Vehicle，AGV)在工业中的作用日益突出。

然而，AGV在工业上的应用也面临着一些问题，其中一个关键问题就是多AGV的路径冲突[1-2]。路径冲突指同一时段多台AGV的行驶路线出现交叉或重叠，主要分为路口冲突、追赶冲突和相向冲突[3]。路径冲突一旦处理不当，就会出现AGV碰撞或死锁问题，严重影响多AGV系统的工作效率。近年来，多AGV系统的路径冲突已经成为AGV研究的重点[4]。面对多AGV系统可能出现的路径冲突情况，一般做法是应用数学规划方法为AGV在地图中提前规划好无冲突路径[4-7]，这种路径规划方法是非实时的静态路径规划，AGV在行驶过程中并不总能在规划的时间到达指定位置，而且随着AGV数量的增加，多台AGV之间的运行路线必将出现交叉和重叠。为了避免AGV路径冲突，前人根据路网的实时状态动态调整AGV的路径[8-14]，然而动态路径规划不但增加了运算量，而且当多台AGV聚集在某一区域执行任务时，部分AGV必须绕开这片区域来避免路径冲突，从而增加AGV的额外运行时间，除此之外，在高密集型多AGV系统中可能会出现无法搜索到无冲突路径的情况。

针对上述现状，为了减少路径规划的计算量，本文采用非实时的静态路径规划算法，并通过冲突预测和避碰决策加以改进，AGV的最优路径在任务发布时就规划完毕且不再更改，面对路径冲突时将会采用停车或绕道的避碰策略来解除路径冲突。本文运用图论知识构建多AGV系统的工作地图，并基于顶点属性预测路径冲突。考虑到执行避碰决策对系统全局状态的影响，采用粒子群优化(Particle Swarm Optimization，PSO)算法优化避碰决策，并对PSO算法进行改进来改善优化效果。最后在VS2012平台上搭建上位机系统进行实验验证，结果表明改进的PSO算法具有较优的性能。

1 路径冲突分析与预测

在路径冲突问题上，相比于传统的重规划无冲突路径，文本所提方法注重已知路径下的避碰决策优化，即在路径冲突时不进行二次路径规划。在多路径类型的工作环境下，本文提出结合顶点属性和AGV位姿信息的冲突预测方法，通过预测多AGV系统未来的路径冲突状态来实现避碰决策的全局优化。

在本文研究的港口、物流仓储等环境下的多AGV系统中，AGV沿固定车道行驶，将车道的交叉点和卸货点作为图的顶点，车道作为连接两相邻顶点的边。AGV行驶的车道分为单向单车道、双向单车道、双向双车道3类。因为单向单车道和双向双车道可以看作为双向单车道的一种特殊情况，所以在处理路径冲突情况时只需要制定AGV在双向单车道上的行驶规则和避碰规则，即可解决多AGV系统中的路径冲突。

针对上述情况，本文提出一种基于图论的冲突预测方法，预测过程包括基于顶点属性快速搜索阶段、结合AGV位姿预测冲突阶段两个阶段。首先，基于图论的基本原理将某一时刻向某个顶点行驶的总AGV数量作为顶点的一个属性。显然，若某一时刻朝向某顶点的AGV数量大于等于2，则在该顶点处可能发生冲突，根据这一特点可以快速搜索到可能发生冲突的顶点，避免预测过程中的重复计算。然后，根据各个AGV的位姿信息进一步确定可能发生冲突的AGV。

(1)基于顶点属性的快速搜索阶段

建立二维数组M[A][B]表示顶点与AGV的关系。其中A为AGV的总数量，B为地图中顶点的总数量，M[i][j]=k表示当前时刻下j号顶点是i号AGV的第k个目标顶点。在冲突顶点的搜索过程中需要遍历数组M，将当前时刻具有相同目标顶点的AGV存储到一个一维数组中，表示可能存在冲突的顶点集合。搜索算法的伪代码如下：

算法1路径冲突顶点搜索算法伪代码。

1 /* 采用顶点属性法搜索冲突顶点*/

2 建立顶点属性矩阵M[A][B]

3 建立顶点冲突数组Conflict[B]

3 for b=0, b

4 Conflict[b]=0;

5 for a=0, a

6 If M[a][b]=1 then

7 Conflict[b]++;

8 End

9 If Conflict[b]>1 then

10 b号节点可能发生冲突

11 End

(2)结合AGV位姿的预测冲突阶段

通过搜索算法快速得出可能发生路径冲突的顶点后，需要接收AGV内置传感器的数据，根据AGV的实际位姿预测路径冲突区域的中心顶点。

如图1所示，当前时刻AGV1和AGV2均以中心顶点作为目标，两AGV的行驶路线存在交叉，为了预测AGV是否会发生碰撞，需要结合AGV位姿信息进行分析。

首先记录一台AGV从进入到离开一个顶点所需的时间，记为t0，根据该时间估算AGV的安全距离D，D=Vmaxt0+K。对于可能发生路径冲突的AGV，采用安全距离法判断是否会发生碰撞。首先调用通过顶点属性法初步确定的路径冲突的顶点和以其为目标顶点的AGV，然后计算各个AGV与顶点之间的距离S1，S2，…，Sk。对于任意两台AGV顶点的距离Si和Sj，若|Si-Sj| ≤D，则预测i号AGV和j号AGV会在该顶点处发生碰撞；若|Si-Sj|>D，则判定不发生碰撞。

预测出发生碰撞的AGV和顶点后，一般采取停车或绕道让行的方式解决冲突。

2 避碰决策的优化方法

2.1 多AGV系统的全局优化目标

在多AGV系统中，AGV在避碰过程中的通行次序将影响未来时刻的系统路径冲突状态，因此如何规划多AGV的避碰决策非常重要。在第2章路径冲突预测方法的基础上，提出一种基于冲突预测的多AGV系统避碰决策优化方法。

对于一个冲突时刻ti，对发生路径冲突的AGV做出避碰规划γi。对于每台AGV-Ak，用Lk表示其等待时长。对于目标规划γ={γ1,γ2,γ3,…,γi}，K号AGV产生的总等待时长记为Lk(γ)∈[0,∞)。由此得出，同时执行任务的m辆AGV的总等待时长

(1)

设定每台AGV在执行一次任务所需的时间为

nk0+nk1+nk2=nk。

(2)

式中：Tk为k号AGV经过的总时间；v为AGV的平均速度；eij为顶点ij的距离(i,j

Lk(γ)=nk1·t1+nk2·t2为路径冲突造成堵塞的总等待时间，其中t1为AGV在路口等待的时间，t2包括顶点转弯时间、最小安全距离移动时间和等待时间。除去因避碰决策造成的额外时间t1t2，一台AGV执行任务所必要的时间为

(3)

由式(3)可得m辆AGV执行任务所需的必要时间总和为

(4)

定义系统堵塞率J为m辆AGV总等待时间与任务执行总耗时的比值，即

(5)

则多AGV路径冲突的避碰决策优化目标为min(J)。

2.2 多AGV避碰决策优化算法

在多AGV系统运行过程中，每一次的避碰决策都会对系统运行产生影响，而多AGV的避碰决策的组合优化是一个NP难问题，难以采用传统数学规划方法进行求解，因此结合第2章的冲突预测方法，采用PSO算法优化AGV系统避碰决策。

PSO算法是受自然界鸟群觅食行为的启发而总结出的群体智能优化算法[15-17]，本文通过调整PSO算法模型，将其应用在避碰决策的优化中。实验发现，该算法存在提前收敛、全局搜索能力弱的问题，为解决这一问题，本文对PSO算法进行了改进。

在D维解空间中设置m个粒子，粒子群表示为G={p1,p2,p3,…,pi,…,pm},i=1,2,3,…,m。每个粒子有速度V和位置X两个属性，速度V用于更新解的变换，可表示为V={v1,v2,v3,…,vi,…,vD},vi=-1,0,1；位置X即对应的避碰决策方案，决策方案的数量为D，表示一个决策周期T内的避碰决策集合，表示为X={x1,x2,x3,…,xi,…,xD},xi=0,1。由于避碰决策是离散型变量，用0和1表示两种不同的避碰决策，0表示在避碰过程中小编号的AGV让行，1表示在避碰过程中大编号的AGV让行。每个粒子在决策空间中单独地搜寻最优解，并将其记为当前个体最优解Pbest，最优的个体极值记为整个粒子群的当前全局最优解Gbest，粒子群中的所有粒子根据当前个体最优解和全局最优解来调整自己的速度和位置。

PSO算法步骤主要分为：①初始化粒子群；②计算粒子适应值；③寻找个体最优解；④寻找全局最优解；⑤修改粒子的速度和位置。

PSO算法的核心是粒子速度V与位置X的更新，粒子速度V根据个体最优解Pbest和群体最优解Gbest来更新调整。粒子的个体最优解通过计算适应度函数来确定，适应度f=1-J，J采用式(5)计算，将计算出的适应度与粒子的当前个体最优解比较，较大适应度的成为新的个体最优解,拥有最大适应度的个体最优解作为群体最优解Gbest。

图2所示为粒子适应度值的计算过程。由于当前路径冲突的避碰决策会影响AGV系统的运行状态，要获得合理的适应度值，就要考虑AGV后续的路径冲突。设置决策周期为T，即每一次路径冲突都会考虑避碰决策对未来T时段内AGV系统状态的影响。采用第1章的路径冲突预测方法预测未来的路径冲突并执行决策集X对应的避碰决策，直到对T时间内的所有路径冲突做出避碰决策后，再估算系统等待时间并返回粒子的适应度值。

对于本文研究的多AGV避碰决策优化问题，由于解空间是离散的，需要对粒子运动速度V的更新方式进行改进。引入速度离散函数H(K)，将计算出的连续速度转为离散速度，使粒子能在离散解空间中移动。

K=ωVi(t)+c1r1(Pbest-Xi(t))+

c2r2(Gbest-Xi(t))；

(6)

Vi(t+1)=H(K)。

(7)

式中K为计算速度；H(K)为速度离散函数。K可分解为D个维度方向的分速度，即

K={k1,k2,k3,…,ki,…,kD}。

(8)

(9)

式中：ki为第i维方向上的计算速度；h(ki)为第i维方向速度的离散函数；KN为速度的下界；KP为速度的上界。

通过比较计算出的连续速度值K与设定的速度上下界限定值KN，KP，确定AGV在解空间各个维度方向上的速度。

位置X更新公式为

Xi(t+1)=Xi(t)+Vi(t+1)。

(10)

通过不断迭代，调整粒子速度V和位置X，使个体位置不断接近群体最优解Gbest。

为了能够优化粒子在解空间的移动速度和方向，引入速度接纳概率Pv。Pv表示接受通过计算得到的速度K的概率，Pv越大，该维上的速度更新概率越大，反之粒子速度更新概率越小。每一维上的Pv可用下式调节：

(11)

通过式(11)可以调节粒子在每一维上的速度变化概率，使高维度决策位的速度调节概率降低，即时间上靠后的决策不易被改变，从而限制粒子在解空间的运动方向，使粒子按照决策的时间顺序逐步移动到最优解附近的解空间，以找寻到更优解。

为了提高粒子的全局搜索能力，避免优化算法早熟，本文融合遗传算法的变异思想引入粒子变异操作，让粒子有一定概率跳出局部最优位置而收敛到更优位置。为了使算法最终能够收敛，设置变异概率随迭代次数的增加不断降低，通过调整变异概率的大小，使改进PSO算法在合适的迭代次数后收敛。变异概率为

n=1,2,3,…,D,i=1,2,3,…,gmax。

(12)

式中：n为解空间的维度；i为算法迭代次数；gmax为最大迭代次数。

3 实验结果及分析

为了验证本文所提多AGV系统避碰决策优化算法的有效性，采用C++编写了多AGV系统的控制程序和算法，并用Visual studio 2012搭建了Winform上位机控制系统平台，多AGV通过CAN总线与上位机建立通信。图3所示为上位机控制系统界面。

实验参数如表1所示，多AGV系统工作环境被重构成包括100个顶点的图，每次实验投放的AGV数量为1～40台，标准数量为30台。每台AGV的平均运行速度设置为1 m/s，实验次数为200次。

表1 实验参数表

为了优化PSO算法的搜索能力，提出优化粒子运动方向和速度及变异操作来改进PSO算法。图4所示的实验结果清晰地表明了改进PSO算法与传统PSO算法在粒子速度更新上的差异。虚线为传统PSO算法在500次迭代过程中粒子平均速度的变化曲线，可见传统PSO算法的粒子速度收敛过快，难以充分搜索解空间。实线为改进PSO算法的速度曲线，粒子在整个迭代过程中移动速度较快，收敛速度平缓，具备较好的搜索能力。

在一次实验中，为30台AGV随机分配任务起始点，并采用Dijkstra算法为各AGV规划行驶路径，在AGV的任务全部执行完毕后，计算堵塞率J，实验次数为200次。图5所示为 PSO算法和改进PSO算法的系统堵塞率拟合趋势线，可见采用改进粒子群避碰决策优化算法后，在同样的任务下，堵塞率明显下降，平均堵塞率从6.41%下降到5.96%，减少了7.1%的堵塞时间。

图6所示为基于任务优先级避碰方式、基于贪心算法避碰方式和基于冲突预测的避碰方式(使用改进PSO算法优化)的系统堵塞率分布情况。其中对照组基于任务优先级避碰方式是根据每台AGV优先级确定避碰决策，优先级别低的AGV在避碰过程中需要为其他AGV让行。

基于贪心算法避碰方式在求解过程中采用贪心算法思想，该算法在一次决策中分别计算不同决策对当前路网造成的拥堵情况，然后实施对路网状态负面影响最小的决策。相比本文方法，这种启发式搜索避碰方法只关注决策对当前系统状态的影响，不考虑对系统的后续影响，因此是短视的。

在200次实验中，每次实验都会为AGV随机生成任务和运行路径，并依次采用3种避碰方式对同一初始条件进行决策。结合表2可见，与传统的优先级避碰方式和基于贪心算法的避碰方式相比，基于冲突预测的避碰方式的系统堵塞率和等待时长较低。

表2 不同避碰方式下的实验数据

图7所示为堵塞率下降百分比图，其以优先级避碰方式为对照，可见基于贪心算法避碰相对优先级避碰的提升并不很大，而且有可能出现堵塞率负增长，而采用改进PSO算法的冲突预测避碰方式能提升20%以上。

图8所示为随着同时运行AGV数量的增加，不同算法的优化效果。可见，AGV的数量越多，采用改进PSO算法冲突预测避碰方式的优化效果越明显。

4 结束语

AGV数量的增加增大了解决多AGV系统路径冲突的困难。本文根据图论知识和AGV位姿信息预测冲突点，实现了多AGV系统中路径冲突的快速和准确预测。为了有效地解决AGV的冲突问题，本文将改进PSO算法应用到避碰策略优化中，经过实验分析验证了该算法可以有效缓解路线拥堵状况，显著提升多AGV系统的运行效率。未来将研究融合多AGV系统的动态路径规划算法，以进一步缓解路网的阻塞状况，提高系统的生产效率。