基于WebGL的多AGV物流调度仿真系统的研究与应用

荣 燕，李 栋，曹先庆

(1.沈阳化工大学 信息工程学院，沈阳 110142；2.中国科学院 网络化控制系统重点实验室，沈阳 110016；3.中国科学院 沈阳自动化所，沈阳 110016；4.中国科学院 机器人与智能制造创新研究院，沈阳 110169)

0 引言

目前生产型企业的数量众多，每天都需要重复性搬运物料和产品，耗时又耗力，尤其是当比较忙碌时，还容易出现送料错误的情况，这些问题导致了工厂工作效率低下，而且浪费了大量的人力成本。AGV(automated guided vehicle)小车的出现，可以轻松解决这个问题。AGV不仅加速了生产进度和效率，还可以节省大量的人力成本，有效地减少了送错料混料的情况。针对多AGV任务调度的仿真研究，很多研究考虑了多AGV执行任务时影响任务效率的因素。如AGV的电池电量、AGV执行任务时的路径规划、AGV数量配置等。文献[1]考虑了AGV的充电策略，设计出4种充电方式，得出合理的充电方式可以提高AGV的工作效率。文献[2]在集装箱码头作业过程中将电池电量的问题考虑在内，并基于Q学习算法建立出多AGV动态调度模型：AGV在集装箱码头作业时，执行完一个任务时，可以动态选择下一个任务。文献[3]针对AGV路径优化，阐述了一种新的方法-改进人工势场法，解决了传统人工势场法中存在的局部极小值问题。文献[4]提出了用时间窗模型解决AGV路径问题，能够有效提高系统效率并且有良好的适应性。文献[5]以AGV完成任务的时间最短为目标，建立了同步和异步两种挑选模式下AGV的任务调度模型，最终验证了能够有效将解决AGV调度问题。文献[6]提出了路径优化速度较快的混合蚁群粒子群方法，提高了AGV运行效率。文献[7]研究了具有电池约束的AGV任务调度，以运输请求的延迟成本和AGV旅行成本的加权和最小为目标，将充电和运输请求分配给AGV。文献[8]主要研究了一种新型的多品种小批量生产的矩阵式制造车间中的自动引导车辆调度问题。该问题的目的是确定一种解决方案，使客户满意度最大化，同时使分销成本最小化。为此，建设一个多目标混合整数线性规划的模型。此外也有很多研究路径冲突的文献，文献[9]针对传统时间窗法的局限性，提出了更好的多AGV路径冲突检测方法-基因测序算法。文献[10]针对AGV的冲突问题，提出模糊控制方法来优化AGV路径，证明了此方法可以有效提高运输效率。文献[11]提出的基于冲突搜索的多AGV路径算法最终验证能够有效解决路径冲突问题。文献[12]针对自动化码头动态作业环境中多自动引导车的路径规划问题，建立了AGV完成任务时间最小和路径无冲突的两阶段模型，可以有效解决多AGV动态冲突的规避。由上可见，大多数文献研究了AGV任务调度系统的算法、路径规划的算法和AGV充电策略，在任务调度系统中，很少有在研究的同时把AGV充电问题和执行任务时的路径规划问题考虑在内，因此将AGV电池电量和路径规划问题同时作为约束条件，研究适配K公司汽车总装生产线的实际场景需求是很有必要的，并利用webgl技术实现了三维AVG虚拟仿真[13-15]。

1 需求分析

AGV是目前最受欢迎的自动化搬运设备，是实现智能物流的关键环节，从我国的AGV需求分析得知，AGV的应用比较集中，主要分布在汽车工业和家电制造行业。AGV越来越受欢迎的原因有很多，首先AGV小车不需要人工驾驶，只需要在AGV的中央控制系统的控制下即可自动接收和执行搬运任务，将需要搬运的东西自动搬运到指定的地点，真正意义上实现了整个生产过程中无人化、自动化地运送产品，大大提高了企业生产线的物流效率。其次，如今很多的企业都存在招工难的现象，人工成本在不断上升，因此很多企业都在向自动化模式转变，而AGV正好是可以代替普通工人的一种自动化搬运设备，降低成本，实现物流自动化，灵活性和准确性也都挺好，因而备受自动化制造业的欢迎。此外，智能制造时代的3C大批量定制，生产的周期也明显缩短，那么对于物流的速度也要求更高，因此企业对AGV小车的需求也会更加迫切[16-17]。

在AGV实际应用中，还存在着很多需要解决的问题：

1)为了提高多AGV调度系统的效率，很多研究提出改进算法来解决路径优化问题，却很少有学者研究小车充电对调度系统的影响，AGV和电动汽车相似，充电所需时间都比较长，因此根据AGV电量安排任务就尤为重要。将AGV充电需求考虑到调度系统中是比较复杂的，AGV每完成一次运输任务，都需要计算出小车此时剩余的电量，那么就需要知道小车行驶距离和所剩电量二者之间的关系，根据行驶距离计算出所剩电量，然后根据电量合理划分AGV充电区间，从而判断此AGV下一步是执行新的任务还是行驶到充点电充电[18-19]。

2)当越来越多的AGV被同时安排到仓库里工作时，避免AGV之间相互碰撞也成了研究的重点，目前大多数文献研究路径冲突检测的方法是时间窗法，但是时间窗法有一定的局限性，当AGV行驶的距离远，经过的路径节点多，那存储节点的时间窗就需要占据更大的内存，那么冲突检测的效率会降低，所以为了提高路径冲突检测的效率，本次研究利用基因测序算法来预测多AGV之间的路径冲突问题，但是由于基因比对和AGV路径问题的环境是不一样的，因此在环境建立方面有难度，不能完全复制到路径冲突检测当中[20-21]。

3)将充电需求和路径规划分别考虑到调度系统之后，最重要的是还需要将二者结合起来同时考虑到调度系统中，以最小路径为目标，建立多AGV模型也是一大难点。综上分析，本次研究以AGV充电需求算法、路径规划算法、调度系统模型为重点，分析了多AGV调度系统中问题的解决方法[22]。

2 AGV充电需求算法分析

在物流运输行业，安全可靠的无人AGV广泛应用于工厂加工系统，具有低噪音、低污染、智能程控、高效搬运等诸多优点。驱动结构是AGV的重要组成部分，目前大多采用电池供电作为运行动力源。那么多AGV调度系统中电池的供电、放电和充电就显得尤为重要。本文主要研究调度系统中AGV的充电问题，以K公司汽车生产总装生产线为背景，共有十一辆AGV小车。小车负责把不同的汽车零件运送到终点进行组装，执行完任务后回到原点。当AGV一直处于工作状态，不停的在运输物料，AGV的电量就会处于直线下降的状态，当AGV的电量不能够完成系统分配的运输物料任务时，此时AGV就要进入设定的充点电进行充电。等小车电量足够时，就停止充电，以保证运输任务的正常进行，从而减少任务等待的时间，提高AGV任务调度的效率。当AGV在完成运输任务时，存在两种状态，一种是空载，另一种是重载，AGV同样的速度下，重载时的输出功率是要大于空载时的，相同的距离重载和空载的耗电量也有所不同，傅正堂等人提出了AGV电量消耗和距离的关系[23]。

根据图1得出，AGV消耗的电量和路程的关系可以用一元二次函数描述，AGV的电量记为x，AGV行驶的距离记为R，二者关系记为：R(x)=Ax2 +Bx+C，因此根据AGV行驶的距离就可以知道小车所剩的电量。然后将AGV的电量分为3个区间：x1设为AGV从起点到终点最短距离所对应的电量，x2设为AGV能够从起点到达终点，再从终点到起点所行驶的总路程所对应的电量。

图1 AGV电量消耗图

1)低电量区间：[0 ～x1)，当AGV电量在这个区间时，说明AGV已经不能从起点到达终点了，此时AGV必须驶入充电点进行充电。

2)中电量区间：[x1 ～x2)，当AGV电量处于此区间时，AGV可以执行任务，但是在执行任务之前，需要考虑任务距离的远近，执行太远的任务中途可能会电量不足，从而导致小车停在半路，造成拥堵。所以在此区间的AGV尽量执行距离较近的任务。

3)高电量区间：[x2 ～ 1)，当AGV电量处于高电量区间时，可以执行任何一个任务。

通过划分AGV的电量区间，可以更加合理的给小车安排任务，提高系统调度的效率。小车执行任务的流程如图2所示。

图2 AGV充电需求分析

3 AGV路径规划

3.1 AGV最短路径算法

在AGV路径规划的研究中，都以AGV路径最短为目标，完成这个目标一般使用的是A*算法。A*算法的公式表示为：

f(n)=g(n)+h(n)

在研究AGV路径规划问题时，f(n)表示AGV从初始节点经过节点n再到目标节点的最小行驶距离，g(n)表示从初始节点到节点n的最小距离，h(n)表示从节点n到目标节点的路径的最小行驶距离，也称为A*算法的启发函数。如果启发函数h(n)一直为零的话，此时就由g(n)决定路径节点的优先级。如果h(n)始终小于等于节点n到终点的距离，那么A*算法一定能够为AGV找到最短路径，但是当h(n)的值越小，算法将遍历更多的路径节点，从而导致A*算法速度变慢。如果h(n)完全等于路径节点n到终点的距离，则A*算法将找到最佳路径，并且速度很快。如果h(n)的值比节点n到终点的距离要大，那么A*算法就不能保证可以为小车找到最短路径。由此可以得出，A*算法找到最短路径的条件是：h(n)≤h(n)具实距离。A*算法(F=G+H)的具体步骤如下：

1)首先创建两个集合openList和closeList(openList用于存放可以走的路，closeList存放已经走过的路(即不能走的路，包含障碍物))。

2)将起点加入openList中，使用一个workCell变量用于开拓道路。首先取出openList中的第一个元素存放到workCell中。此时进行判断，若workCell等于终点，流程结束。否则进行3)。

3)将openList中的第一个元素即workCell从openList中删除，并加入到closeList中，表示这是走过的路。

4)找到workCell的所有邻点，用一个临时变量neighboursList存放，对neighboursList[i]进行判断，若该邻点在closeList集合中，表示该邻点是走过的，直接跳过，否则进行5)。

5)若neighboursList[i]不在openList中，表示没有计算过F，计算F，并将neighboursList[i]的父节点设置为workCell，然后将该邻居加入到openList中，加入的时候进行判断，当F最小时放在openList首位(保证最短路径)；否则，neighboursList[i]在openList中(表示曾经计算过F)，执行6)。

6)重新计算F，若重新计算的值比之前计算的值小，则更新F和G以及父节点。

7)重复执行2)～6)，直到openList中没有元素(表示没有通路)。

8)若成功找到通路，则用终点来回溯寻找父节点，将每个父节点存到pathList集合中，最终该集合就是通路。

通过A*寻路算法可以算出AGV小车行驶的路径距离，下一步通过距离计算出小车到达节点的时间。AGV在小车运动过程中，不会一直处于匀速状态，所以不能直接利用小车行驶的距离除以速度得出时间，需要考虑小车速度的变化从而求出时间。时间的计算方式主要如下：规定AGV的加速度为a，最大速度为Vmax，匀加速运动和匀减速运动距离如式(1)和(2)所示：

(1)

(2)

当AGV小车从起点开始运动时，初始速度为0，即V0为0，然后进行匀加速运动，加速到最大速度Vmax，此时能够求出从起点到达最大速度这段路程所需要的时间t1为：

(3)

将式(3)代入式(1)，可得出从初始速度0加速至最大速度Vmax时所行驶的距离Smax：

(4)

AGV到达节点时间的求解主要分为4种情况：

2)AGV到达节点时处于匀速状态。如果AGV到达节点时处于匀速的话，说明AGV从起点开始行驶，先开始匀加速，然后加速到了最大速度Vmax之后，AGV就保持Vmax进行匀速运动，所以这种情况下，AGV到达节点的时间就是匀加速运动和匀速运动时间的总和，首先当AGV小车从起点开始运动时，初始速度为0，即V0为0，然后进行匀加速运动，由于AGV到达下一节点时不需要转弯，行驶距离大于Smax′所以能够加速到最大速度Vmax，此时根据式3)就能求出AGV从起点到达最大速度时这一段路程的时间t1为Vmax/a，下一步当AGV进行匀速运动时，一直以Vmax的速度行驶，这一段匀速行驶的距离记为S2，那么这一段路程所需要的时间为t2=S2/Vmax。最后得出AGV到达节点处于匀速状态时的时间为t1+t2。

3)AGV到达节点之前没有加速至最大速度，到达节点时处于匀减速状态。当AGV从起点开始运动，然后进行匀加速运动，由于AGV到达下一节点的距离较短，距离小于Smax时就需要转弯，所以无法加速至最大速度就需要进行匀减速运动。当AGV从起点开始匀加速时，起始速度为0，最终达到的速度Vg

4)AGV到达节点之前加速至最大速度，到达节点时处于匀减速状态。当AGV小车从起点开始运动时，初始速度为0，即V0为0，然后进行匀加速运动，由于AGV到达下一节点时不需要转弯，行驶距离大于Smax′所以能够加速到最大速度Vmax，此时根据式(3)就能求出AGV从起点到达最大速度时这一段路程的时间t1。到达最大速度以后，AGV就进行匀速运动，一直以Vmax的速度行驶，这一段匀速行驶的距离记为S2，那么这一段路程所需要的时间为t2=S2/Vmax，最后当AGV在下一节点需要转弯时，那么AGV的状态就会从最大速度开始减速进行匀减速运动，直到速度减为0，这一段匀减速的路程记为S3，初始速度为Vmax′那么这一段的时间t3=Vmax/a。最终到达节点的时间t即为t1+t2+t3。

3.2 多AGV路径冲突检测算法

在AGV小车实际应用中，往往不是只有一台 AGV在工作，而是同时有多台AGV在共同工作，并且物流运输系统中的各个任务都是交叉同时进行的。为了使多AGV系统能够高效有序的运行，需要为每个AGV规划出无冲突的路径，以免出现AGV之间发生碰撞或出现时间冲突。多AGV系统就是不但是一辆AGV，而是很多辆同时工作，需要在保证AGV之间不发生碰撞的情况下完成系统分配好的任务。针对多AGV系统调度，我们首先要解决的问题是各个AGV之间碰撞问题和时间冲突问题，主要的冲突有3种类型，路口冲突、追赶冲突和相向冲突，分别如图3～5所示。

图3 路口冲突

图4 相向冲突

图5 追赶冲突

图6 地图编号

由于时间窗法(就是使冲突路段和行驶时间窗口化，通常使用坐标轴进行表示。也就是说时间窗描述了每一辆 AGV在地图模型中每个路段的驶入和驶出时间。)无法根据AGV冲突的类型调整预检测的精度，所以利用基因测序冲突检测方法[9]来解决路径冲突问题，能够有效弥补时间窗法的不足。算法的具体步骤如下：

1)对地图中的每一个节点和节点之间的路段进行编号。地图构成记为m×n，第一步对地图中的节点进行编号，表示为0，1，2，…，m×n-1；水平路段编号：左节点为i，右节点为j，那么该路径的编号即为(i+j)/2；垂直路径编号的方法和水平编号类似，路径上节点为a，下节点为b，则此路径的编号为(a+b)/2+ 0.01。不同是垂直路径需要在后面加上0.01，由于工厂仓库的规模一般都很大，水平垂直两个方向的路径编号很有可能会重复，因此垂直路径编号时多加0.01的数值，以便区分水平和垂直两个路段。

2)建立AGV的路径和时间得分矩阵。

路径得分矩阵：路径得分矩阵记为Mr，矩阵Mr的行是一台AGV的路径，列是另一台AGV的路径，在基因序列比对中，相似性是指两个序列在同一位置具有相同的基因片段。和基因比对方法不同的是，AGV行驶的路径是有方向的，所以就需要将两台AGV中的一台AGV的路径进行逆转。如果AGV1经过的节点为[a1，…，ai，aj，…，an]；AGV2经过的节点为[b1，…，bk，bl，…，bm]；那么可得出AGV之间的冲突发生在[ai，aj]或者[bk，bl]段。具体如图7所示：由于AGV1和AGV2的行驶的方向相反，所以AGV1路线从左往右为a1 ～an，而AGV2的路线从右往左为b1～bm。

假设AGV1的路径信息为R1，路径节点为P1，路径长度为L1；AGV2的路径信息为R2，路径节点为则P2T，路径长度为L2。Mr表示以(0，P2T)为行，以(0，P1)为列的(L1+1)(L2+1)的矩阵。

时间得分矩阵：时间得分矩阵记为Mt。由于时间没有方向性，所以不需要像路径那样做逆转处理。其余过程和Mr矩阵类似。假设AGV1的路径信息为R1，时间序列为T1，长度为L1；AGV2的路径信息为R2，时间序列则为T2，长度为L2。Mt为以(0，T2)为行，以(0，T1)为列的矩阵。

3)回溯上面路径和时间得分矩阵，得到冲突发生的区域。

在基因里面，回溯是要找到相似性最高的片段，那么在AGV中，就是找到矩阵中的最大值。如图8所示，因此首先计算此元素上面、对角线方向、左面3个方向的得分，得分的数值为该方向上的得分+移动过程得分；然后计算出的3个方向的得分与0的最大值。根据式(5)计算矩阵中每个元素的得分以此填充整个矩阵。

(5)

其中：(1 ≤i≤L1，1 ≤j≤L2)

Mi，j为第i行第j列元素得分，Mi-1，j-1为对角线方向元素得分，Mi-1，j为上面元素得分，Mi，j-1为左边元素得分。s(a，b)和W为移动过程得分，L1和L2表示AGV1和AGV2路径长度。

回溯的步骤：首先根据上面的计算方法得到矩阵中的最大值。下一步得到路径对比数组MAH_r[]和时间对比数组MAH_t[]，路径最大值数组MAX_r[]和时间最大值数组MAX_t[]。最后通过比对4个数组，得到路径比对结果和时间比对结果。

由于AGV小车一般不会出发点发生冲突，所以可以去除MAX_r[]和MAX_t[]第一个位置的元素，然后得到数组MAX_r’[]和MAX_t’[]，下一步计算出平均值，记MAX_r_a和MAX_t_a。由于AGV行驶时会有延迟，所以设置了一个检测裕度ε，然后在MAX_r’[]和MAX_t’[]中选择符合式(6)和(7)的元素并且存到mah_r[]和mah_t[]里面，具体如式(8)和(9)：

MAX_r_a-ε≤MAX_r′[]≤MAX_r_a+ε

(6)

MAX_t_a-ε≤MAX_t[]≤MAX_t_a+ε

(7)

mah_r[i]←MAX_r′[i]，1≤i≤min(L1，L2)

(8)

mah_t[i]←MAX_t′[i]，1≤i≤min(L1，L2)

(9)

然后取mah_r[]和mah_t[]的交集，就是两台AGV发生冲突的位置，如式(10)所示：

mah_r[j]∩mah_t[k]

(10)

其中：j和k的取值范围都为[1，min(L1，L2)]。

多AGV冲突检测的伪代码如下所示：

冲突预检测:

定义:空列表存储有潜在路径冲突的AGV的数量:number[ ].

1:For i in range [1,n-1]

2: For j in range [i+1,n]

3:If Si ?Sj≠ Ф

4: number[ ] ←(i,j)

5:End For

6:End

冲突预检测之后确定路径冲突路段：如果不同的AGV行驶路径中包含相同的节点，比较AGV到达相同节点的时间，判断AGV是否在这路径中发生冲突。冲突路段的伪代码如下所示：冲突关键段:

定义:空列表存储存在路径冲突的AGV编号:section[ ]

空列表存储路径冲突关键段的长度:length[ ]

1: For i in range [ 1,k-1]

3: [T] ←[Ti]

4: For j in range [ 1,2×(n-1)]

5:For k in range [ j+1,2×n]

6: If [Ti] ∩[Tk] ≠ Φ

7: section[ ] ←arg( [Ti]或 [Tk] )

8: length[ ] ←length[ ]( section[ ])

9: End For

10: End For

11: End For

12: End

3.3 AGV最终路径规划

上面两节介绍了A*算法求解最短路径，然后根据规划的路径进行冲突检测，检测完冲突以后再利用A*算法为冲突的AGV重新规划路径或者原地等待。具体实现过程如图9所示：图中有三辆AGV，三辆AGV的路径具体经过哪些节点如表3所示。

表3 AGV路径节点

图9 AGV运行路径

AGV小车时间节点如表4所示。

表4 AGV时间节点

由表4可知，AGV1和AGV2在节点7处的冲突属于相向冲突，此时就为AGV2用A*算法重新规划一条路径，重新规划的路线为8→9→10→11→30→29→28→27→26。由表3可知，AGV1和AGV3在节点14处的冲突属于路口冲突，那么就让AGV3等待AGV1走完节点14再继续前行，从而避免冲突。

4 实验结果与分析

4.1 仿真原型系统搭建步骤

实现AGV三维模型利用3 ds MAX建立模型，3 ds MAX(3D Studio Max)是3D建模渲染和制作软件。首先建立三维工厂AGV模型。第二步是材质的设置，材质是指物体表面的特性，反应物体表面的质感。下一步是贴图的制作，贴图是材质的一种图像属性，为材质提供可视化的图像信息。然后是灯光的设置，灯光来源于观察和对画面的整体把握。全部设置好之后将建立好的模型以gltf格式导出。导出以后，再利用WebGL(Web Graphics Library)将三维模型加载出来，WebGL技术是可以在网页上绘制和渲染三维图形以及允许用户与之进行交互。渲染出来的效果如图10所示。

图10 三维模型图

最终得到的多AGV模型如下：目标函数有两个条件，任务路径最短为r1，当存在充电需求的AGV的时候，目标函数r为任务路径最短r1和有充电需求的AGV路径最短r2之和。目标函数如下：

r=r1 +r2

(11)

(12)

(13)

约束条件如下：

任务调度车约束：

(14)

一辆AGV一个时间只能完成一个任务：

(15)

如果第m辆AGV有充电需求，可以表现为当前电量处于低电量区间：

ei≤x1

(16)

一辆AGV只能在一个充电桩内充电：

(17)

式中，i表示AGV需要完成的运输任务，i= 1，2，3，…，I。j表示AGV小车，j=1，2，3，…，J。表示任务i由第j辆小车执行，那么Xij=1，否则为0。dij表示第j辆AGV小车在完成运输任务i过程中行驶的距离。

AGV物流调度系统仿真实现如下所示：图11为调度系统的首页，记录了AGV的数量以及离线和在线的情况。图12为公司订单的一些信息统计，可以对订单信息进行增删改的操作。

图11 系统首页

图12 订单信息

4.2 结果分析

对于多AGV物流调度仿真系统的研究，都是为了提高系统中AGV的利用率、AGV负载率等。但是不能单用上面一种指标来评价系统整体效率，不同的系统对于AGV的要求也是不一样的，所以评价多AGV调度系统的效率需要对系统进行全面的分析。

本文设计的系统以一天的工作时间进行仿真，在初始状态，所以AGV都在原点处，处于空闲状态。根据仿真时间，计算出AGV的利用率、负载率、平均电量等信息，原有调度系统和本文设计的系统数据对比如表5所示。

表5 仿真结果对比 %

其中，一天中AGV的电量变化如图13所示。

图13 AGV电量变化

通过表5可以得出，本文设计的调度系统由于考虑了AGV电量和AGV路径冲突，调度系统的任务分配更加合理，从而提高了AGV的利用率和负载率，提高了系统的总体效率。

5 结束语

本文主要以K公司汽车总装生产线为应用背景进行了研究，为了解决多AGV调度系统中电量分配不均、路径冲突等问题，利用WebGL技术建立了整个生产线场景的三维模型，并且建立了三维AGV模型，使得汽车生产线的场景和AGV小车更加可视化。此外，设计出了多AGV物流调度的仿真系统，系统可以自动给AGV分配任务，然后AGV按照系统里面派发的任务去完成。在AGV执行任务过程中，为了提高系统效率，设定了AGV电池电量的阈值，能够合理分配电量，并利用A*算法为AGV寻找最短路径，然后再利用基因序列比对算法找到存在路径冲突的AGV，并为它们重新规划路径。最终经过调度系统仿真验证，综合考虑电池电量和路径规划问题提高了多AGV物流调度系统的效率。