基于多智能体系统的自动化码头多AGV无冲突路径规划

郭昆仑，朱 瑾

（上海海事大学 物流科学与工程研究院，上海 201306）

0 引言

自动导引车（Automated Guided Vehicle，AGV）是自动化码头运输集装箱的主要运输工具，是码头自动化的重要设备之一。在人工作业难度不断提高、作业大型化、码头智能化的影响下，AGV的数量一直在增加，同时数量增加也导致其作业过程中的设备等待、冲突、死锁等频繁发生，现已成为自动化码头更加关注和急需解决的问题。

针对多AGV的无冲突路径规划问题，很多学者已经做出了研究，例如，王雨等[1]用改进蚁群算法解决AGV无冲突路径规划问题，方华等[2]用A～*算法求解三维的AGV无冲突路径规划模型。张素云等[3]建立了多参数优化控制模型，模型中考虑了路径中AGV数量、AGV的安全距离和速度，同时改进了速度控制策略解决冲突。仲美酥等[4]考虑到AGV的行驶速度、AGV重载率和冲突时间，以最小化AGV在岸桥和堆场之间的行驶距离为目标建立多AGV无冲突路径规划模型，采用速度控制策略解决冲突。曹小华等[5]提出了基于冲突预测的多AGV避碰决策优化方法，将改进粒子群算法应用到避碰策略的优化中，解决冲突问题。Liu等[6]以最小化AGV任务完成时间为目标建模，考虑AGV的行驶速度来进行定位和避免冲突的约束，通过仿真验证了模型和算法能够避免AGV发生冲突和拥堵。现有大量文献对于多AGV无冲突路径的研究规模是在20台～30台，然而目前国内主要自动化码头AGV的数量是18、38、50台，洋山四期的设计规模更是多达130台，因此，解决30台以上AGV的无冲突路径规划更具有实际意义。

目前大量文献主要是将多智能体系统（Multi-Agent System，MAS）应用在车间、物流仓库AGV上，李晓萌等[7]建立了基于Agent的多级决策和协作学习方法的AGV调度系统，同时设计了AGV的分布式动态调度策略。Koen H等[8]引入了智能体概念，提出了一种通过应用协作控制的方式来改善多车辆系统的事故处理，通过与现有自动化码头中多AGV系统进行比较，发现基于MAS的控制方式更能提高系统的运行效率。Fauadi等[9]提出了基于MAS的分布式架构来控制制造业中的AGV操作系统和代理体系结构，旨在实现控制物料搬运活动。Erol Rizvan等[10]提出了基于MAS的实时环境下的AGV和制造系统的协同调度，并采用MAS中投标、中标机制作为多AGV系统的协商策略。经建峰[11]建立了基于Agent的分布式多AGV控制系统，为AGV任务分配后，可以自主进行路径规划，同时AGV发生冲突时可以相互通信协作完成任务。然而，由于自动化码头AGV的运行环境更加复杂、地图规模更大，现有文献将MAS应用到码头AGV上求解多AGV的无冲突路径规划文献更是少之又少。

综上所述，本文针对30台以上的AGV无冲突路径规划问题，以最小化AGV在岸桥和堆场之间的作业堵塞率为目标，考虑AGV的行驶速度、作业时间和冲突距离，建立自动化码头多AGV无冲突路径规划模型，同时设计了基于MAS的多AGV体系结构，改进Dijkstra算法规划多条AGV路径，改进速度控制策略控制AGV到达冲突节点前的速度，解决冲突。设计基于MAS的控制方式和任务优先级的控制方式的对比实验，比较不同数量下AGV的平均堵塞率、平均等待时间和平均完成任务时间。

1 模型建立

1.1 模型假设

1）岸桥和堆场位置固定不变且已知，同时一个岸桥对应所有堆场；

2）在岸桥和堆场处设置缓冲区，使AGV在岸桥作业区和堆场作业区排队等待作业时与路径中其他运行AGV不会形成冲突；

3）不考虑AGV在行驶过程中故障、天气等不可抗因素的影响；

4）AGV在转弯过程中速度保持不变。

1.2 变量设定

在表示自动化码头多AGV的运行路径网时，用G=（N，W）有向加权图表示AGV的路径网。其中N为AGV运行地图中所有节点编号的集合，W为的G边集，Wk（i，j）表示路径k上第i个节点到第j个节点的边的长度。下面引入以下变量，方便进行表示。

L为AGV设备的自身长度；

R为AGV行驶过程中冲突距离传感器的检测范围半径长度；

Ls为行驶过程中AGV间的安全距离；

v为AGV的作业时的平均速度；

α为检测到冲突时AGV的加/减速度；

Dk为第k条路径的长度，k=1，2，…，K，且K为AGV的所有路径的集合；

AGVkm为路径k中第m台AGV的编号；

C（k1，k2）为两台发生冲突的AGV的路径k1和k2，且k1，k2∈K；

w为路径k中第m台AGV发生冲突的次数；

s为路径k中的起点；

e为路径k中的终点；

Akm为路径k中第m台AGV的优先级；

tkms为路径k中第m台AGV的起始时间；

tkmep为路径k中第m台AGV的运行结束时间；

tkmeop为路径k中第m台AGV的预计完成任务时间；

tck为路径k中AGV在冲突节点的等待时间；

t为路径中AGV因冲突延误的时间；

T为AGV从初始位置到达终止位置的总时间消耗。

1.3 分布控制模型

对于AGV路径冲突问题构建模型如下：

在AGV运行过程中，式(1)和式(2)表示同一时间每个节点至多被AGV访问一次，即路径中AGV不重复行驶同一路段，且同一节点只能有一辆AGV通过；式(3)表示任意一台AGV在任意路径中行驶的长度；式(4)表示任意路径中任意一台AGV完成任务的结束运行时间。

为AGV分配任务后，AGV运行过程中行驶速度不变为，且为了避免从同一出发点出发的同一路径中多台AGV之间的冲突，AGV之间需要保持最小的安全距离，即安全检测距离。

若不同路径中两台或多台AGV同时到达两条路径的交叉节点时，则AGV可能在交叉节点处发生冲突，若发生冲突AGVs需经过协商确定其中某台AGV通过冲突节点，解决冲突问题。当发生冲突时，AGVs先提取AGV编号进行协商，首先比较AGV的优先级。式(5)为根据单台AGV的路径规划计算预计完成任务时间；式(6)为根据预计完成任务时间判断AGVs的优先级，完成任务时间长的AGV优先级低，否则，优先级高。

AGVs协商后根据自身优先级做出调整，优先级低的AGV到达冲突节点前开始减速可能直到停止，优先级高的AGV则匀速通过冲突节点。式(7)为k1中AGV与k2中的AGV通过距离传感器检测到对方时，两台AGV的安全距离小于冲突检测范围距离；式(8)为k1中AGV与k2中的AGV通过距离传感器检测到对方时，进行协商和同意k2中的AGV先通过冲突节点，而k1中AGV从v0减速到v1的距离ls；式(9)为k1中AGV从v0减速到v1的时间tc11，同时也是AGV加速恢复到原速的时间tc12；式(10)为k1中AGV解决冲突过程中的最终减速度v1；式(11)k1中第m台AGV发生w次冲突后到达终点的时间为Tk1m；式(12)～式(13)为n台AGV在路径中因冲突延误的等待时间，以及n台AGV完成任务的总时间；式(14)为最小化n台AGV作业过程中的堵塞率，即总等待时间和任务完成时间的比值TJ。

2 MAS在自动化码头AGV的体系结构

2.1 AGV的运行地图建模

MAS在自动化码头AGV上应用时，AGV作为智能体能够通过传感器确定自身位置，然后与已知的坐标值路标进行比较，从而与全局坐标系统进行匹配，得到自身的实时位置。因此，本文在研究基于MAS的自动化码头多AGV的运行路径时，选择拓扑地图，拓扑法将码头中的岸桥、堆场、路径中的交叉点作为拓扑地图中的节点，节点与节点之间的连线表示实际码头中AGV的运行路线。

单车道单向路径网络，就是一条路径上的车道只有一个方向一个车道，不存在双向双车道，并且在每一条路径的垂直方向上只可能有一辆AGV。同时，实际码头中AGV运行线路为正值，所以建立的拓扑地图是一张加权有向图，边的权值均为正值。使用邻接表的方法来建立有向加权图，邻接表方法是将所有与某一个顶点相连接的其他顶点存入到一个链表中，并且将这个链表关联到该顶点。此外，码头中的AGV运行路径大多为直角弯，即在拓扑地图中路径节点的上下左右四个方向上，才可能存在与其他节点相连接的边。

对于邻接表实现拓扑地图的设计代码如下：

2.2 基于黑板模型的交互协议

在基于MAS的自动化码头多AGV的体系结构中，交互协议是AGV与AGV、AGV与控制台的通信。AGV在运行过程中需要发送和接收信息，即AGV给控制台需要发送的小车编号、小车任务、当前所在位置、当前时间、以及下一个节点位置；控制台则需要给所有AGV发送路径表中某台即将AGV占用某个节点，以便AGVs到达冲突节点前做出协商解决问题；AGV与AGV之间的交互信息主要是AGV发生冲突时，进行协商，需要发送各自的当前位置、当前时间和自身优先级。

根据本文需要的交互信息，对共享资源的同步和认知是AGV之间协作的重要前提。在MAS中黑板模型能够较大程度上管理全局资源，所以本文采用黑板模型设计了多AGV交互协议，如图1所示。

图1 基于黑板模型的多AGV交互协议

1）黑板的主要作用是将地图中岸桥到堆场、堆场到岸桥的路径分配给每台AGV，监控每台AGV的位置、速度、时间，并以向量的形式保存，即vector::iterator it，it是可以读写的位置、速度、时间元素，同时，黑板也需将每台AGV的位置、速度、时间以向量的形式发送到每台AGV上。

2）系统中运行的AGV是黑板模型中的知识源。（1）每台AGV都有各自运行特征，如可能发生的冲突以及自身运行的参数（速度、时间、优先级等），都是黑板控制机制需要的信息；（2）AGVs即将发生冲突时，黑板控制机制允许AGV进行协商，从黑板中提取优先级等信息协商处理。

3）系统中的黑板控制单元功能由无线网络完成，并且本文中AGV与AGV交互信息、AGV与黑板的交互信息的间隔时间为0.02s。

2.3 多AGV的冲突协商策略

多AGV的协商策略主要是根据AGV的优先级进行判断，然后进行让步，解决冲突。本文采用基于时间成本的方法确定AGV的优先级，并结合速度控制方式作为AGV的协商策略。

2.3.1 基于时间成本的AGV优先级确定

本文采用了一种基于时间成本的方法确定AGV的优先级，如图2所示，为每台AGV分配任务后，AGV根据起始点和终点，使用最短路径算法得到最短路径，同时计算完成该任务的预计完成任务时间，根据时间的长短确定AGV的预计优先级。当解决冲突过程中，优先级低的AGV通过减速，直到优先级高的AGV通过冲突节点，此时，优先级低的AGV花费更多的时间，并将时间重新计算到预计优先级中，优先级的高低也会随之发生变化。

图2 基于时间成本的AGV优先级流程图

2.3.2 基于改进速度控制的冲突协商策略

AGV冲突情况如图3所示，当两台AGV即将到达同一交叉口，AGV1、AGV2自身的冲突检测传感器设置半径为R1、R2的检测半径，并且R1=R2，R1与R2的长度根据AGV车身长度和路径长度等因素设置，检测临界圆随着AGV移动而移动。在图3(a)中，AGV1和AGV2同时向路径交叉口行驶，此时AGV1、AGV2的检测临界圆没有发生相交，所以两台AGV并没有检测到冲突；当两台AGV继续运行到图3(b)情形时，两个检测临界圆开始相交，表明AGV1和AGV2可能会发生交叉节点处的冲突，此时需要AGV协商让步，解决冲突。

图3 AGV冲突示意图

下面以发生冲突的两台AGV中一台AGV为例解释解决冲突的过程：

1）当AGV的检测临界圆与别的检测临界圆开始相交，AGV根据黑板模型提供的信息确认即将发生冲突。

2）AGV提取对方AGV编号，确定协商对象AGV并与之通信，请求通过前方可能冲突节点。

3）双方根据自身优先级得到结果，确定其中一台AGV锁定冲突节点，并匀速通过。

4）优先级低的AGV减速，等到优先级高的AGV通过该节点，再恢复原速通过该节点，解决冲突问题。

2.4 改进Dijkstra算法

Dijkstra算法可以有效地求解带有权值的有向连接的拓扑地图上的最短路径，在确定起始点和终点后，以起点为中心，采用贪心算法的思想，每次遍历搜索相邻接点中距离始点最近的且从未访问过的节点，直至扩展到目标点出现在搜索范围中。在AGV路径规划中，权值代表的是该边的长度，如果两点不相连，那么它们的权值对应的值为无穷大。但是，Dijkstra算法要遍历计算每个节点，计算时间效率低，浪费运算空间。因此，本文采用堆优化改进Dijkstra算法。

堆优化能够有效减少算法运行时间，其思想就是使用一个优先队列的方法，该方法主要是每次弹出的元素一定是整个队列中最小的元素，最小元素代替每次查找的最短距离的边，即用邻接表代替邻接矩阵，堆优化能够大幅减少计算时间。堆优化方法实现如下：首先，需要定义一个优先队列，优先队列存储并快速寻找距离最近的点，该队列的元素为节点编号和该节点到下个节点的距离；其次，起始点需要初始化，即将起点加入优先队列中，起点的编号就是在优先队列元素的节点编号，此时计算过程中该节点与起始点的距离为0；最后，如果在其他运算过程中，优先队列中的某个节点到起始点的最短距离发生了变化，原本优先队列中的元素无需删除，而是将变化后最短节点元素再次存入作为优先队列作为最小元素弹出。改进Dijkstra算法流程图如图4所示。

图4 改进Dijkstra算法流程图

3 实验分析

3.1 多AGV的实验与分析

建立了如图5所示的单向单通道路径网，以岸桥到堆场、堆场到岸桥的运行方式选择起始点和终点，其中3、8、13为岸桥位置，59、60、63、64、67、68为堆场箱区的位置。岸桥到堆场、堆场到岸桥共有36种组合，对应36台AGV；每台AGV的速度不变，为2m/s；AGV加/减速度为0.5m/s2；AGV的长度为2m；AGV的冲突检测距离为2m；地图顶点数目为69；实验次数为100次；采用c++编写多AGV系统的控制程序，在Inter（R）Core（TM）i7-8750H CPU @ 2.20GHz 2.21 GHz、16GB内存的Windows10计算机上实现。

图5 AGV路径图

为36台AGV随机分配任务，根据起始点和终点用改进Dijkstra生成每台AGV的路径，如表1所示，且同一顶点出发的多台AGV出发时间依次间隔2s，即1号车第0s出发，2号车第2s出发，3号车第4s出发。同时，36台AGV的路径必须包含所有起点的路径，目的是避免36台AGV同时选择一条路径，不会发生冲突。

表1 路径起始点、终点表

36台AGV实验100次的堵塞率分布情况如图6所示，堵塞率为0的情况主要是为AGV随机分配的起始点和终点时，重复选择相同的路径，导致冲突次数为0；而当为AGV随机分配路径重复率低时，AGV的冲突次数增加，堵塞率的平均值为0.48%。

图6 基于MAS控制方式的多AGV堵塞率

3.2 不同控制方式实验对比及分析

基于MAS的控制方式和任务优先级的控制方式的堵塞率分布情况如图7所示。任务优先的控制方式主要是指根据每台AGV优先级确定避碰决策，优先级别低的AGV 在避碰过程中需要为其他AGV等待让行。图中虚线代表任务优先级的控制方式，实线代表本文基于MAS的控制方法。在100次实验中，每种控制方式的实验都对36台AGV进行随机分配起始点和终点，并对同一条件进行模拟，从图7中可知，基于MAS的控制方式堵塞率明显整体低于任务优先级的控制方式。

图7 不同控制方式的多AGV堵塞率

结合表2，基于MAS的控制方式与任务优先级的控制方式相比，平均等待时间减少7.8s和平均堵塞率降低0.22%，该方法明显优于任务优先级的控制方式。

表2 不同控制方式的实验数据表

同时，本文考虑了在不同数量AGV下两种方式的平均堵塞率、平均等待时间和平均完成时间的变化。

从图8中可知，1）AGV数量在20～30台时，任务优先级的控制方式与基于MAS的控制方式平均堵塞率相差为0.08%和0.14%，平均堵塞率曲线近乎平行，这是因为AGV数量相对较少，发生冲突频率低且冲突不会影响系统运行效率；2）AGV数量超过30台时，尤其在36台时，基于MAS的控制方式平均堵塞率下降了0.22%，曲线下降幅度更大，说明基于MAS的控制方式能够减少解决冲突时间和降低冲突AGV对系统运行的影响，更加适合解决30台以上AGV无冲突路径规划问题。

图8 不同数量AGV对应平均堵塞率的变化图

表3中GAP=（任务优先级的平均等待时间-基于MAS的控制方式的平均等待时间）/任务优先级的平均等待时间。当20～30时，GAP在20.3%～23.6%变化，变化幅度较小，说明在30台以下时，速度策略比等待策略解决冲突所用时间短；当超过30台时，GAP在23.6%～30.4%，在基于MAS的控制方式的AGV平均等待时间明显减少，而采用任务优先级的控制方式时，解决冲突过程中AGV等待时间较长，影响系统运行效率。

表3 不同数量AGV对应平均完成运行时间表

由表4纵向来看，两种控制方式的平均完成时间差为1.4s、2.2s、4.3s、6.2s和8.9s，时间差值随着AGV数量的增加而增加，说明基于MAS的控制方式能够大幅度减少30台以上AGV的运行时间，提高了AGV的运行效率。

表4 不同数量下平均等待时间和平均堵塞率表

4 结语

本文以最小化AGV作业堵塞率为目标，考虑AGV的行驶速度、作业时间和冲突距离，建立了多AGV无冲突路径规划模型，同时设计了基于MAS的码头多AGV体系结构，将改进速度控制作为AGV的协商策略。设计了基于MAS的控制方式和任务优先级的控制方式对同一条件下的平均堵塞率、平均等待时间和平均完成任务时间的对比试验。实验结果表明当AGV数目少于30台时，两种控制方式在平均堵塞率上相差0.08%～0.14%，变化幅度较小；超过30台AGV时，基于MAS的控制方式在平均堵塞率上减少了0.14%～0.22%，幅度变化大，同时基于MAS的控制方式比任务优先级的控制方式的AGV平均等待时间减少7.8s，平均完成时间减少8.9s，实验结果验证了本文模型的可行性，以及基于MAS的控制方式更加适合解决30台以上规模的AGV无冲突路径规划问题。