基于改进CBS算法的自动化码头多AGV无冲突路径规划

周欣慈 朱瑾

摘 要：针对自动化集装箱码头上自动引导车（automated guided vehicle，AGV）数量增加导致冲突更频繁。提出一种改进的基于冲突的搜索（conflict based search，CBS）算法。底层采用基于曼哈顿距离的 A*算法，上层结合二叉树原理建立冲突树对AGV之间的冲突进行规避。以最小化AGV在岸桥和堆场之间的总路径长度为目标，使用栅格法建立AGV路网模型。考虑AGV之间的点冲突与边冲突，将自动化码头多AGV无冲突路径规划问题规约为多智能体寻径问题。实验结果表明，所提出的算法在保证堵塞率为0%的前提下，缩短总路径长度并提高运算速度，验证算法的有效性。

关键词：自动化码头； 多AGV； 多智能体路径规划（MAPF）； 基于冲突的搜索算法（CBS）

中图分类号：TP242   文献标志码：A

文章编号：1001-3695（2023）09-010-0000-00

doi：10.19734/j.issn.1001-3695.2023.02.0036

Conflict-free path planning for multi-AGVs in automated terminals

based on improved CBS algorithm

Zhou Xinci， Zhu Jin

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：Increased number of automated guided vehicles（AGV） on automated container terminals leads to more frequent conflicts. This paper proposed an improved conflict based search（CBS） algorithm. The bottom layer used the A* algorithm based on Manhattan distance， and the top layer combined the binary tree principle to build conflict trees to avoid conflicts between AGV. With the objective of minimizing the total path length of AGV between the shore bridge and the yard， the grid method used to developed the AGV road network mode. Considering the point conflict and edge conflict among AGV， the multi-AGV conflict-free path planning problem in automated terminals statuted as a multi-agent pathplanning problem. The experimental results show that the proposed algorithm shortens the total path length and increases the computational speed with a guaranteed blockage rate of 0%， which verifies the effectiveness of the algorithm.

Key words：automated terminals; multi-AGV; multi-intelligent path planning（MAPF）; conflict-based search algorithm（CBS）

0 引言

AGV是自动化码头水平运输作业的重要设备，是集装箱运输的主要工具。在人工操作、大规模操作和智能码头难度不断增加的影响下，AGV的数量不断增加，同时数量增加也导致设备在运行中出现等待、冲突、死锁等问题。影响AGV运输的效率，提高AGV运行速度成为自动化码头现阶段急需解决的问题。

针对自动化码头多AGV路径规划问题，众多学者进行了研究。例如，丁一等人［1］建立两阶段模型，使用最短路径算法规划路径；张其娇等人［2］提出结合冲突规避的加权实时A*算法；牛雅倩等人［3］提出基于动态平衡策略的控制方式，改进Dijkstra算法规划AGV路径；郭昆仑等［4］以最小化AGV在岸桥和堆场的作业堵塞率为目标，设计基于多智能体系统的體系结构；兰培真等人［5］提出基于ant-agent的AGV控制算法，将AGV视为蚂蚁智能体，解决AGV道路死锁与路径冲突问题；曾庆成等人［6］考虑AGV的拥堵因素建立动态模型，使用蚁群算法求解，有效提高运输作业的效率；Zhong等人［7］建立混合整数规划模型，验证带有模糊控制器的混合遗传算法—粒子群优化算法的有效性；Yue等人［8］提出一种两阶段混合整数优化模型，使用改进的基于规则的启发式算法，Dijkstra算法和Q-learning算法集成，设计基于图论的路径冲突避免策略有效减少冲突。现有的文献对于自动化码头上多AGV路径规划的研究规模在30台左右，而目前国内主要自动化码头AGV的数量是18，38，60，甚至136台，解决大规模的AGV路径规划问题更具实际意义。

多智能体路径规划（multi-agent path find-ing，MAPF）问题是一类寻找多个智能体从起始位置到目标位置且无冲突的最优路径集合的问题，在柔性制造系统中如物流中心，智能车间，智能仓储的AGV上有实际应用。考虑最优解法器Goldenberg等人［9］提出增强部分扩展改进A*搜索（EPEA*）算法，只扩展最优节点，修改当前节点的启发函数值并重新加入open-list来求解中的MAPF问题，改进了分支因子的缺陷；Sharon等人［10］提出基于代价增长树搜索（increaing cost tree search，ICTS）算法求解中的MAPF问题，阐述ICTS算法在智能体密度较高和冲突代价较大的局限性；Surynek［11］将MAPF问题规约为SAT问题，将问题中地图的结构、智能体的位置和约束编码为布尔变量，然后用这些布尔变量生成标准的 SAT 问题来验证是否存在全局代价为C的可行解，遍历所有可能的全局代价C就能够生成全局最优解；Sharon等人［12］提出基于CBS算法解决MAPF问题，并与ICTS进行对比实验，验证CBS在求解速度和求解质量的有效性；Hnig等人［13］将MAPF应用在仓储上，缩短理论与现实的局限性；黄鼎勇等人［14］使用CBS算法求解多无人机路径规划，考虑转弯成本，防止安全区域无人机的相互碰撞；郭超等人［15］采用基于时空A*算法求解物流中心的MAPF问题，引入冲突规避以避免与其他路径发生冲突；刘恒麟［16］使用CBS算法应用在智能仓储的多AGV路径规划问题上，与传统的A*算法进行对比实验，验证CBS算法在减少运算时间的有效性；由于自动化码头AGV运行环境更复杂，地图规模更大，现有文献使用MAPF模型及CBS算法应用在自动化码头上，求解大规模AGV无冲突路径规划较少。

本文提出基于冲突规避策略的自动化大规模AGV无冲突路径规划算法，采用改进的CBS算法求解该MF问题，针对小规模算例，设计基于ICTS和基于CBS算法的对比实验，比较算法在不同数量下AGV的平均运算时间和平均总路径长度；针对大规模算例，采用基于CBS算法求解自动化码头上60台AGV的多智能体路径规划问题并分析平均运算时间和平均总路径长度。

1 模型建立

1.1 模型假设

a）岸桥和堆场位置固定不变且已知，一个岸桥对应所有堆场箱区；b）每台AGV型号规格相同；c）AGV运行速度恒定（包括在转弯时）；d）不考虑AGV在行驶过程中故障、天气、电量等因素的影响；e）在岸桥与堆场之间设置缓冲区，其中空闲AGV停车区设置为静态障碍物，AGV在执行水平运输作业时不可通行；f）AGV在岸桥与堆场装卸集装箱的时间忽略不计；g）所有AGV栅格路线可双向行驶；h）每个时间点每个栅格只允许一台AGV占用，岸桥处的栅格可以允许多AGV占用。

1.2 变量设定

在表示自动化码头AGV水平运输区的路径网时，用G=（V，E，ob）有向加权图表示AGV的路网。其中V表示自动化码头上AGV栅格图的所有节点编号的集合，V=［（x1，y1），（x2，y2），…，（xn，yn）］，其中n×n 表示栅格的数量，而E为V的边集，表示每个V对应的长度，ob表示障碍物坐标的集合。其他变ob=［（xm，y1），（xm，y2），…，（xm，yn）］量设置如表1所示。

1.3 数学模型

目标函数：

min∑Ni=1Coni（1）

约束条件：

Xij=1 AGV访问节点i后访问节点j0 否则（2）

∑Ni=1∑Nj=1Xij=1（3）

T=Cov（4）

f（i）=g（i）+h（i）（5）

h（i）=|Pi[t][0]-gi[0]|+|Pi[t][1]-gi[1]|（6）

Td=∑ki=1tdi（7）

mov=1 表示AGV在原地等待0 否则（8）

Co=∑ki=1Pi-1（8）

其中：式（1）表示本模型的目标函数是总代价最小，式（2）（3）表示同一时间每个节点至多被AGV访问一次，式（4）表示所有AGV完成任务的时间，式（5）表示底层使用的A*算法，其中f（i）是估算函数，g（i）是从起始节点到节点i的实际成本，h（i）是节点i到目标节点的估计成本，式（6）表示启发函数采用基于曼哈顿距离的A*算法，式（7）表示总的等待时间，式（8）表示AGV的移动方式选择，包括在原地等待或向相邻节点移动一个时间步长，式（9）表示所有AGV完成任务的总代价。

2 模型求解

2.1 AGV路网模型建立

本模型采用堆场垂直于码头岸线的布局，水平运输设备不进入箱区，在箱区的两端与堆场进行作业交接，设立4台岸桥3个堆场对自动化码头布局进行模拟仿真，如图1所示，本文选择双向单车道路径，AGV的移动方式包括在原地等待或者向相邻可通行的四节点移动。其中灰色障碍物表示堆场缓冲区，在AGV进行水平运输作业时，将其视为障碍物。

自动化码头中AGV路径规划系统是由岸桥，堆场，缓冲区和磁钉等各个设备组成的复杂系统，针对AGV水平运输区，使用栅格法对地图进行建模，用单元格将障碍信息表示出来，单元格的权值是布尔变量，其中可通行的节点用0表示，不可通行的节点用1表示，AGV不可以和障碍物单元格重叠。

2.2 AGV冲突类型

随着AGV数量的增加和码头任务规模的扩大，AGV在岸桥和堆场的水平运输区主要产生的冲突类型如下：

a）交叉口冲突。

如图2（a）所示，当AGVi，AGVj從垂直方向向交叉栅格Vm行驶，并且在时间点t同时到达同一栅格点Vm，产生交叉点冲突。考虑其为点冲突（AGVi，AGVj，Vm，t），并且在该冲突二叉树节点上分别为AGVi添加约束（AGVi，Vm，t），AGVj添加约束（AGVj，Vm，t）。

b）相向冲突。

如图2（b）所示，当AGVi，AGVj从相反的方向向同一栅格节点Vn行驶，并且在时间点t同时到达同一栅格点Vn，产生相向冲突。与交叉口冲突类似，将其考虑为点冲突（AGVi，AGVj，Vn，t），并且在冲突二叉树节点上分别为AGVi添加约束（AGVi，Vn，t），AGVj添加约束（AGVj，Vn，t）。

c）交换冲突。

如图2（c）所示，当AGVi，AGVj从相反的方向行驶，并且在时间点t打算交换栅格点Vm，Vn的位置，产生交换冲突。考虑其为边冲突（AGVi，AGVj，Vm，Vn，t），并且在冲突二叉树节点上分别为AGVi添加约束（AGVi，Vm，Vn，t），AGVj添加约束（AGVj，Vm，Vn，t）。

d）AGV故障。

如图2（d）所示，AGVi发生故障停在栅格点Vm，而AGVj所规划路径与故障点产生重叠，造成设备等待，本模型不考虑AGV因故障导致冲突的情况。

2.3 通信交互协议

针对环境多变的码头水平运输作业，在本模型中忽略通信延迟问题，采用集中式控制方式，使用一个中央处理器为所有AGV找到解决方案。AGV在水平运输任务中不断运动并且范围较广，因此需要采用无线通信系统来实现AGV之间的通信。考虑通信成本和任务运行的便捷，本文选择UDP无线网络通信协议，将AGV和控制台的网络IP地址设置在同一IP网段内，使用无线Wi-Fi信号连接到路由器，实现它们AGV与AGV之间，AGV与控制台之间的通信。AGV在接收到任务后将任务起点，任务终点，AGV小车编号发送给控制台；控制台将计算后的每个小车的无冲突路径发送给各个小车。

2.4 多AGV冲突规避策略

自动化码头上存在点冲突与边冲突，使用底层基于曼哈顿距离的A*算法为每一台AGV搜索出最短路径后，在上层冲突二叉树上执行搜索，冲突树上每个节点表示一组AGV运动的约束，包括三部分组成，即一组约束N.constraints、一个解N.solution和总成本N.cost。

图3是码头AGV冲突实例，S1，S2表示两个岸桥，G1，G2表示两个堆区，每台AGV必须计划其从岸桥到堆场的完整路径。AGV1必须从岸桥S1到堆区G1，AGV2必须从岸桥S2到堆区G2。两台AGV都有各自长度为3的路径：AGV1：S1，A1，D，G1;AGV2：S2，B1，D，G2。在时间步长t2时他们同时到达栅格点D产生冲突，选择总路径长度最短的AGV添加约束，选择AGV1等待一个时间点。因此，在本例中，最优解N.solution=7。

对应的冲突二叉树如图4所示，冲突树的根节点对应的约束集是空的，表示为：N.constraints={}；使用底层的A*算法分别计算出AGV1和AGV2从岸桥到堆场的初始路径为：N.solution={（AGV1：S1，A1，D，G1），（AGV2：S2，B1，D，G2）}；由式（9）可知N.cost=6。这些信息都保存在根节点中。在验证给出的解时，当两台AGV在时间t2时都到达栅格点D时，会产生一个冲突conflict=（AGV1，AGV2，D，t2）。因此根节点不是目标节点。

生成两个子节点以解决冲突。左子节点添加约束N.constraints={（AGV1，D，t2）}，而右子节点添加约束N.constraints={（AGV2，D，t2）}。调用左子节点的底层A*搜索，查找在满足新约束下的最优路径。为此，AGV1必须在A1或S1处等待一个时间点，则AGV1新路径为：{S1，A1，A1，D，G1}，AGV2的路径在左子节点中保持不变。左子节点的总代价N.cost是7。

类似生成右子节点，代价N.cost也是7。两个子节点都被插入到OPEN。在while循环的下一次迭代中，选择cost最低的节点展开，即选择左子节点进行展开，并验证底层路径。因为不存在冲突，所以左子节点被声明为目标节点，它的解决方案N.solution就是这个码头冲突实例最优解决方案。

2.5 改进CBS算法

CBS算法为简化问题通常只考虑点冲突，而码头实际运行时AGV之间存在点冲突与边冲突，本文采取改进的CBS算法在考虑点冲突的同时，判断二叉树中是否存在边冲突，并对存在边冲突节点的子节点增加约束，实现多AGV的无冲突路径规划。流程图如图5所示，具体搜索步骤如下：

a）初始化二叉树根节点，root.constraints=，root.solution=使用底层A*搜索规划的路径集，root.cost=SIC（root.solution）;

b）把根节点插入Q列表中;

c）如果Q列表不是空，取出Q中cost最少的節点设为当前节点;

d）判断当前节点的N.solution是否存在点冲突与边冲突;

e）如果没有冲突，N.solution就是解;

f）如果存在冲突，将当前节点从Q中取出，把当前节点的两个子节点分别添加约束加入Q列表中，循环c）d）直到求出无冲突的路径集。

3 算例分析

参照自动化码头实际，采用如图6所示的双向栅格路网图［2］，路网布局中Q1～Q10为岸桥位置，D1～D30为堆场箱区的位置，其中白色栅格为可通行的点，灰色栅格为静态障碍物不可通行。采用Python语言编程，在IntelAMD5-2500U CPU @ 2.00 GHz、8 GB内存的Windows 10计算机上实现。在本算例中，参数设置如下：设置栅格的长度为2 m，栅格大小为40×40，每台AGV的速度不变为2 m/s，AGV的长度为2 m。以岸桥到堆场，堆场到岸桥的运作方式选择起点和终点。

3.1 不同算法在30台AGV下的实验对比及分析

实验设置AGV的起点和终点如表2所示，AGV需要在相应的岸桥作业起点避开缓冲区到达指定的堆场作业终点，AGV的起点为10个岸桥，终点为30个堆场，实验设置多台AGV可以同时占据岸桥，因此不考虑在岸桥处的点冲突与边冲突。

本实例设置有效时间为60 s，超出时间无法求出解视为无效，其中终点不可重复选择，在AGV数量相同时，为改进CBS算法和代价增长树算法随机分配任务，设置相同的起点和终点，在AGV数量为30台时，必须包含所有起点和所有终点，目的是避免空闲，提高岸桥和堆场的利用率。

基于ICTS算法主要是上层在代价增长树上搜索总路径长度最小的节点后，在上层成本约束下，下层搜索出有效解决方案。文献［10］采用基于ICTS算法，在减少运算时间取得明显效果，但是因为ICTS是耦合的方法，在密集环境中或解决冲突的成本非常高的情况，ICTS是低效的。因此，提出基于改进CBS算法，是一种混合方式求解大规模AGV路径规划问题，能够生成最优方案。

设置AGV的数量分别为2～30台时，使用改进CBS算法和ICTS算法规划多台AGV从起点到终点的路径，分别进行10次实验，为AGV随机分配起点终点，分配后的起点终点固定。基于ICTS和改进CBS算法在不同AGV数量下的平均总代价和平均运算时间如图7所示。

如图7（a）所示，比较平均总路径长度，当AGV数量为2～5时，AGV数量较为稀疏，AGV之间冲突较少，ICTS解决冲突的成本较低，求解效果较好，因此两种算法的总路径长度相近；而当AGV数量为6～30时，随着AGV数量增加，改进CBS算法在二叉树上选择总路径长度最短的节点，拉大与ICTS算法的差距，两种算法之间的差距维持恒定。如图7（b）所示，比较平均运算时间，当AGV数量为2～26台时，两种算法之间的差距较为平稳；当AGV数量为26～30台时，AGV密度增大，ICTS算法采用耦合方式，效率较低，运算时间明显陡峭上升，而改进CBS算法维持较为平稳。

由于两种算法的平均运算时间和总路径长度曲线呈单调递增的趋势，选择AGV数量为10，20，30台时，比较ICTS与改进CBS的运算时间，如图8所示。选择AGV数量为5，10，15，20，25，30台时，比较两种算法的差距，如图9和表2所示，其中reduce time=（ICTS算法运算时间-改进CBS算法运算时间）/ICTS算法运算时间；reduce cost=（ICTS算法总路径长度-改进CBS算法总路径长度）/ICTS算法总路径长度。

如图8所示，在AGV数量为10，20，30时，改进CBS算法运算时间明显低于ICTS。如图9和表3所示，考虑路径总长度：a）在AGV=5时，两种算法之间的总路径长度差距为1.951%；b）随着AGV数量增加，在AGV=10，15，20，25，30时，总路径长度差距增大在9%～22%。符合图7的分析，而改进CBS算法能在冲突二叉树选择总路径长度最短的节点，总路径长度明显低于ICTS算法。

考虑运算时间，a）在AGV=5，10，15，20，25时，两种算法运算时间差距维持在88%～92%；b）而随着AGV数量增加更加密集，ICTS算法效果较差，运算时间更长，所以当AGV数量=30台时，差距明显增大为98.522%。基于CBS算法解决冲突时，只需要对产生冲突的单AGV重新规划路径，而ICTS算法需要对多AGV路径进行验证，运算时间上CBS算法明显低于ICTS算法。

3.2 改进CBS算法在60台AGV下的实验分析

考虑自动化码头AGV规模更大的情况，设置AGV数量为40，50，60台，实例的有效时间设置为60 s，其中起点终点表如表4所示。

随机选择起点和终点，当AGV数量大于30台时，ICTS算法不能在有效时间内求解。使用CBS算法分别进行100次实验，算法有效时间设置为60 s，实验结果如图10和表4所示。

运算时间如图10所示，正方形表示AGV数量=40，圆形表示AGV数量=50，三角形表示AGV数量=60，其中这三种情况总路径长度分布较为均匀，随着AGV数量增加，平均总路径长度也均匀增加。

如图10所示，随着AGV数量增加，运算时间增加，运算时间过高主要是因为冲突二叉树最小成本的限制，导致求解时间较长，当AGV数量为40台时，35次实验能在有效时间内求解，成功率为65%，而AGV数量为50台时，成功率为14%，AGV数量为60台时，成功率为2%，主要因为AGV数量增加，密度增大，冲突二叉树节点增多，导致计算时间过长。如表5所示，在AGV=60台时，能够在平均运算时间为27.681 s求解无冲突路径，求得的总路径长度为6 385.6 m。

为求改进CBS算法计算的最大阈值，设置AGV数量为61～65台，设置运算时间超出60 s时溢出，返回当前循环的运算时间。

如图11所示，在对61～65台的AGV进行实验时，运算时间均超过60 s，成功率为0%，AGV密度较高超出算法所能计算的阈值，使用CBS算法难以在60 s有效时间内求解，因此在本模型中使用CBS算法所能解决的AGV数量最多为60台。

4 结束语

本文以最小化自动化码头上的AGV总路径长度为目标，考虑AGV之间的点冲突和边冲突，建立多AGV无冲突路径规划模型，设计基于冲突二叉树的策略解决冲突，使用栅格法建立AGV路网。设计基于改进CBS算法和ICTS算法的运算时间和总路径长度的小规模算例对比实验，结果表明当AGV数量为30台时，基于改进CBS算法较基于代价增长树算法总路径长度缩短了11.65%，计算时间缩短了98.52%；对于大规模AGV算例，求得改进CBS算法计算自动化码头多AGV路径规划的阈值为60台，能够在平均运算时间27.681 s求解60台。算例结果验证本算法的有效性，以及改进CBS算法更加适合解决60台大规模的AGV无冲突路径规划问题。

本文后续将在保证路径无冲突和运算质量的条件下，对提高运算速度进行进一步研究。

参考文献：

[1]丁一，袁浩，方怀瑾，等.考虑冲突规避的自动化集装箱码头AGV优化调度方法［J］.交通信息与安全，2022，40（3）：96-107.（Ding Yi，Yuan Hao，Fang Huaijin，et al.An optimal scheduling method for AGVs in automated container terminals considering conflict avoidance［J］.Transportation Information and Safety，2022，40（3）：96-107.）

［2]张其娇，丁一，秦涛.考虑冲突规避的自动化码头多AGV路径规划［J/OL］.计算机工程与应用.［2023-03-23］.http：//kns.cnki.net/kcms/detail/11.2127.TP.20220705.1751.010.html.（Zhang Qijiao，Ding Yi，Qin Tao.Multi-AGV path planning for automated terminals considering conflict avoidance［J/OL］.Computer Engineering and Applications.［2022-12-17］.http：//kns.cnki.net/kcms/detail/11.2127.TP.20220705.1751.010.html.）

［3]牛雅倩，余芳，劉静雯，等.基于动态平衡策略的自动化码头多AGV路径优化算法研究［J］.计算机应用研究，2022，39（2）：385-390.（Niu Yaqian，Yu Fang，Liu Jingwen，et al.Research on multi-AGV path optimization algorithm for automated terminals based on dynamic balancing strategy［J］.Computer Application Research，2022，39（2）：385-390.）

［4]郭昆仑，朱瑾.基于多智能体系统的自动化码头多AGV无冲突路径规划［J］.制造业自动化，2021，43（8）：83-89.（Guo Kunlun，Zhu Jin.Conflict-free path planning for multi-AGVs in automated terminals based on multi-intelligent body system［J］.Manufacturing Automation，2021，43（8）：83-89.）

［5]兰培真，陈锦文，曹士连.基于Ant-agent的自动化码头AGV控制算法［J］.交通运输系统工程与信息，2020，20（1）：190-197.（Lan Peizhen，Chen Jinwen，Cao Shilian.Ant-agent-based control algorithm for automated terminal AGVs［J］.Transportation Systems Engineering and Information，2020，20（1）：190-197.）

［6]曾庆成，李明泽，薛广顺.考虑拥堵因素的自动化码头多AGV无冲突动态路径规划模型［J］.大连海事大学学报，2019，45（4）：35-44.（Zeng Qingcheng，Li Mingze，Xue Guangshun.A conflict-free dynamic path planning model for multi-AGVs at automated terminals considering congestion factors［J］.Journal of Dalian Maritime University，2019，45（4）：35-44.）

［7]Zhong Meisu，Yang Yongsheng，Dessouky Y，et al.Multi-AGV scheduling for conflict-free path planning in automated container terminals［J］.Computers & Industrial Engineering，2020，142：106371.

［8]Yue Lijun，Fan Houming.Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal［J］.IEEE/CAA Journal of Automatica Sinica，2022，9（11）：2005-2019.

［9]Goldenbnberg M，Felner A，Stern R，et al.Enhanced partial expansion A*［J］.Journal of ArtificialIntelligence Research，2014，50（1）：141-187.

［10]Sharon G，Stern R，Goldenberg M，et al.The increasing cost tree search for optimal multi-agent pathfinding［J］.Artificial intelligence，2013，195：470-495.

［11]Surynek P.Towards optimal cooperative path planning in hard setups through satisfiability solving［C］//Proc of Pacific Rim International Conferenceson Artificial Intelligence.Piscataway，NJ IEEE Press，2012：564-576.

［12]Sharon G，Stern R，Felner A，et al.Conflict-based search for optimal multi-agent pathfinding［J］.Artificial Intelligence，2015，219：40-66.

［13]Hnig W，Kiesel S，Tinka A，et al.Persistent and robust execution of mapf schedules in warehouses［J］.IEEE Robotics and Automation Letters，2019，4（2）：1125-1131.

［14]黄鼎勇，周芳，路遥，等.基于冲突搜索的数字战场多无人机路径规划与仿真［J］.指挥信息系统与技术，2022，13（4）：32-39.（Huang Dingyong，Zhou Fang，Lu Yao，et al.Conflict search-based path planning and simulation of multiple UAVs on digital battlefield［J］.Command Information Systems and Technology，2022，13（4）：32-39.）

［15]郭超，陈香玲，郭鹏，等.基于时空A～*算法的多AGV无冲突路径规划［J］.计算机系统应用，2022，31（4）：360-368.（Guo Chao，Chen Xiangling，Guo Peng，et al.Conflict-free path planning for multiple AGVs based on spatio-temporal A～* algorithm［J］.Computer Systems Applications，2022，31（4）：360-368.）

［16]劉恒麟.多AGV路径规划算法的研究与实现［D］.南京：东南大学，2020.（Liu Henglin.Research and implementation of multi-AGV path planning algorithm［D］.Nanjing：Southeast University，2020.

收稿日期：2023-02-12；

修回日期：2023-03-29

基金项目：国家自然科学基金资助项目（62073212）

作者简介：周欣慈（2000-），女，安徽淮北人，硕士研究生，主要研究方向为AGV路径规划；朱瑾（1980-），女（通信作者），湖北武汉人，副教授，硕导，博士，主要研究方向为港口自动化、生产与物流建模与优化（jinzhu@shmtu.edu.cn）.