摘要：针对传统A*搜索算法搜索范围广、收敛速度慢的问题，采用基于关键点和时间窗口的多AGV路径规划，通过定义路口关键点的可行方向限制A*算法的搜索范围，降低路径规划时间和AGV转向次数，再结合时间窗口算法对多AGV路径进行碰撞分析，有效避免可能发生的拥堵，减少AGV
摘要：针对传统A*搜索算法搜索范围广、收敛速度慢的问题，采用基于关键点和时间窗口的多AGV路径规划，通过定义路口关键点的可行方向限制A*算法的搜索范围，降低路径规划时间和AGV转向次数，再结合时间窗口算法对多AGV路径进行碰撞分析，有效避免可能发生的拥堵，减少AGV在关键点的等待时间。
关键词：路径规划；A*算法；多AGV；时间窗口
自动引导车（Automated Guided Vehicle，AGV）在现代化制造系统中发挥了重要的作用，并广泛运用于仓库、港口、工厂等，有效降低了工厂中的物料运输成本，并且降低了工人误操作和受伤的可能性。多AGV系统在工厂中相对单AGV系统更常见[1]，设计多AGV的路径需要综合考虑路线、调度、布局以及AGV运输时间等[2]问题。如果能够有效进行多AGV路径规划，就可以进一步优化工厂中的物料运输系统结构，降低物料运输的成本，提高系统运行效率，这在智能物料运输中具有很大的应用价值[3]。
对于单个AGV的路径规划问题，通常使用人工蜂群算法、蚁群算法、A*算法，Dijkstra算法等在空间上求解。对于AGV的路径规划问题，A*算法已经成为大多数研究的首选方法，例如改进A*算法和双向A*算法等，该方法利用启发式函数快速搜索可行解，相较于Dijkstra算法效率更高，且得到的路径在启发函数合适的情况下仍能得到最短路径解。对于多AGV的路径规划求解，由于可能存在路径冲突，即两AGV发生碰撞的问题：有研究提出了基于时间窗口的动态路径规划方法，基于时间窗口动态地求解最短路径问题[4]；也有基于Dijkstra算法和动态时间窗算法的多AGV最短无冲突路径规划[5]；为了更高效地完成物料运输工作，提出在改进A*算法的基础上增加转弯成本以减少曲线，并结合时间窗口来避免AGV发生碰撞[6]；也有研究提出基于二分图和KM算法匹配最优解，来解决多AGV的调度问题[7]。
上述研究包括了转弯成本和避免碰撞AGV的路径规划问题，以及基于时间窗口来完成多AGV的路径规划问题，但大部分研究都进行了完整的全局路径搜索，而实际工厂中由于工厂的布局相对规范，很多搜索是不需要的。
本文结合真实工厂场景，提出了一种基于关键点和时间窗口的多AGV路径规划方法。首先，通过定义路口关键点的可行方向限制A*算法的搜索范围，显著降低了路径规划时间和AGV转向的次数，使AGV的行驶路径符合工厂实际工况中的单向行驶要求；其次，结合时间窗口算法，对多AGV路径进行碰撞分析，通过路径切换和停止等待相结合的方式，有效地避免了可能发生的拥堵，减少了AGV在关键点的等待时间。
一、多AGV路径规划方法
1.A*算法
A*算法通常用于已知障碍物环境下最优路径的求解，代价函数是在给定障碍物环境下选择一条从起始点到目标点的最优路径，传统A*算法的代价函数为：
式中：g(n)表示从起始点到当前节点n的实际代价，h(n)表示当前节点n到目标点的预估距离代价，也称为启发值。当预估距离代价小于实际距离时，搜索范围广，效率低，但可以找到最优解；预估距离等于实际距离时，严格按照最短路径进行搜索，效率最高；预估距离大于实际距离时，搜索范围小，效率高，但不一定能找到最优解。当前代价采用实际代价即曼哈顿进行计算。
式中：(xn.yn)为节点n当前位置，(xstart,ystart)为起始点坐标，(xgoal,ygoal)为目标点坐标。
2.基于关键点的A*算法
（1）关键点定义方法
本文将AGV需要转向的情况分为三类，分别是直角路口、丁字路口和十字路口。本小节对三种需要转向的特殊路口进行编码。
定义数据结构structMapPoint，用于保存地图中数据点信息，定义数据结构中isKeyPoint布尔变量用于判定该地图点是否为关键点，即潜在的转向点。在数据结构中定义direction变量，其中包含L、R、U、D四个布尔变量，用于记录该地图点的可行方向。
直角路口的定义确保了算法在路口的路径搜索中，AGV均按照限定方向进行搜索，保证AGV靠右侧行驶，且不会跨越到对向车道。以图1为例，若AGV当前在（d,3）位置，则可行方向限定其下一路径搜索点为（c,3）或（d,4），若下一路径点为（c,3），该点的可行方向限定为向R，AGV不会继续运行到下一车道发生碰撞。直角路口中的可行方向定义参见表1。
表1 直角路口地图关键点可行方向
图1 直角路口示意图
丁字路口的定义确保了在路口的每次路径搜索中，若AGV跨越到对向车道，不会在对向车道中逆行。以图2为例，若当前路径点为（b, 3），则下一路径搜索点为（a, 3）或（b, 2），若下一路径点为（b, 2），该路径点的可行方向为L、D，该可行方向保证了跨车道运行的AGV不会向上或向右逆向行驶。丁字路口中的可行方向定义参见表2。
表2 丁字路口地图关键点可行方向
图2 丁字路口示意图
十字路口的定义与直角路口和丁字路口类似，该可行方向定义确保了每次搜索后AGV仍然保持靠右行驶的规则，不发生跨车道逆行，如图3所示。十字路口中的可行方向定义参见表3。
表3 十字路口地图关键点可行方向
图3 十字路口示意图
至此，三种路口的编码全部完成，通过编码可以限制A*算法在路径搜索时的范围，例如原本需要搜索的四条车道，会因为地图关键点限制的可行方向受限，搜索范围降低到两条车道，既满足了实际工厂运行中AGV需要按照靠右行驶的路径约束，同时提高了A*算法的搜索效率。
（2）搜索算法
首先完成地图的初始化和关键点定义。定义待检测地图点列表setOpen用于存储即将访问的节点，定义已检测地图点列表为setClose用于存储已经计算出代价的地图。定义初始节点为start，目标节点为goal。
步骤一，将初始节点加入setOpen。
步骤二，判断若setOpen为空，则未找到可行路径，算法结束，否则转步骤三。
步骤三，在setOpen中查找当前f(n)=g(n)+h(n)的最小值对应的地图点Cur。
步骤四，判断若Cur地图点为目标点goal，则找到可行路径，算法结束，否则转步骤五。
步骤五，将Cur弹出setOpen并加入setClose。
步骤六，获取Cur的编号，判断该点是否为关键点。若是关键点，转步骤七，若不是，转步骤八。
步骤七，Cur是关键点，根据Cur编号读取地图定义信息中的可行方向，并根据可行方向判断可以向周围哪些点进行移动，计算可行点的f(n)，并记录可行点的运动方向。若可行点不存在于setOpen或setClose，则将该点加入setOpen并更新其当前代价值；若存在于setOpen，则查看本次代价是否最优更新代价值；若存在于setClose，则查看本次代价是否最优更新代价值。转步骤二。
步骤八，Cur不是特殊点，Cur仅可以延续上一次运行方向继续前进，更新setOpen和setClose。转步骤二。
具体的算法流程如图4所示，通过定义地图中的关键点，改进A*算法仅可以在关键点处进行转向的搜索，其余非关键点处必须延续上一路径点的运动方向，可以大幅缩小路径搜索点的数量，同时满足双向四车道行驶的规定。
图4 单AGV路径规划流程图
3.基于时间窗和关键点A*算法的多AGV路径规划
单AGV路径规划可以通过基于关键点的A*算法问题进行静态求解，并且提高了搜索效率，但考虑工厂实际情况，静态算法很难满足工厂中多AGV同时工作的实际环境需要。在进行多AGV路径规划时，需要考虑多条路径间的冲突、碰撞，甚至死锁的情况。所以在多AGV路径规划时，除了需要考虑最优路径，还需要解决可能的冲突和碰撞，以达到整体上路径最优的情况。本文使用时间窗方法，结合基于关键点的A*算法进行优化。
在多AGV任务系统中，为了完成躲避障碍物和其他动态运行的AGV，需要引入时间窗模型来记录具体每一时刻的AGV位置，判断是否存在碰撞情况。本文约束在同一时刻，同一地图上的点位内，仅允许一个AGV进入。为了更好地完成时间窗模型的计算，本文定义：
（1）所有AGV的运动速度相同。
（2）定义AGV转向时间为2个单位地图点耗时。
（3）忽略AGV的体积。
假定场景中共有n个运行中的AGV，并且已经使用基于关键点的A*算法生成了其最优路径，记作集合P。基于时间窗的路径规划算法具体实施步骤如图5所示。
图5 时间窗多AGV路径规划方法
步骤一，根据已有的路径集合P生成其对应的时间窗集合T。根据运行中AGV的优先级进行排序，得到一组AGV序列，第一个AGV的优先级最高，最后一个AGV的优先级最低。
步骤二，获取第一个AGV的路径时间窗，分别按顺序与第二个到第n个AGV的路径时间窗进行比对。若发生冲突，则对优先级较低的AGV，针对冲突发生的碰撞点进行一次道路切换，以碰撞点为界限，分别向路径前后搜索路径中的2个转向点，并对2个转向点进行一次道路切换。判断是否仍然存在碰撞，若存在碰撞，则使用原路径并进行一次停止等待，更新时间窗集合T。若未发生碰撞，则更新时间窗集合T和路径集合P。
在时间窗中完成碰撞判断，若碰撞发生在地图中定义的关键点处（即三类路口），则根据碰撞点前后的关键点进行一次路线修正，修正方法为针对关键点进行一次道路切换。
二、实验与分析
本文基于Matlab进行路径规划对比实验，每条路径上共有4条通道供AGV进行运行。为了验证算法的有效性，本文将栅格数量设置为90×90大小的地图，复杂程度较高。在单个AGV路径规划上，与传统A*算法进行对比，以验证本文基于关键点的A*算法的有效性。同时本小节将完成多AGV路径规划和发生碰撞时重规划的验证，以证明本文方法在部分场景下对多AGV规划效率提升的有效性验证。
1.单AGV路径规划分析
在实际场景下，AGV所工作的地图并不是随机生成地图的那样障碍物分散复杂，而是存在大量设备占用某一区域，AGV不允许在设备中穿梭，仅可以在规定路线上行驶。如图6至图10所示，分别对应了复杂程度不同，起始点和终止点不同的五组搬运任务，用于测试不同工况下本文算法的有效性。传统A*算法与本文提出算法在耗时、路径点个数以及拐点个数上的比较结果见表4。在五组任务中，本文方法搜索耗时均小于传统算法。由于规定了路径方向以及预先设定了地图上的关键拐点，本文的路径搜索方法所需的搜索量大大降低。在拐点个数上，同样受限于路径上的关键点限制，本文搜索算法得到的路径结果拐点均小于等于传统方法，在实际的AGV运行过程中，耗时也会相对更短。在平均值上，本文方法计算平均耗时3.77s，平均拐点个数4.8个，与传统算法相比，本文算法规划所需的计算时间与传统方法相比提升44.43%，路径转弯个数上相较于传统A*算法下降了47.83%。
表4 不同任务仿真统计结果
图6 工作任务1
图7 工作任务2
图8 工作任务3
图9 工作任务4
图10 工作任务5
2.多AGV路径规划分析
在实际场景下，会存在多个AGV同时执行多个任务的情况，此种情况下会发生多AGV执行任务过程中路径冲突，因此需要对多AGV执行多任务时进行路径规划。本小节完成多AGV路径规划的验证，任务场景设定如下：任务1，在0时刻出发，任务优先级为A，设定其颜色为粉色；任务2，在0时刻出发，任务优先级为A，设定其颜色为绿色；任务3，在47个地图单位时间后出发，任务优先级为A，设定其颜色为蓝色；任务4，在5个地图单位时间后出发，任务优先级为B，设定其颜色为红色。任务3和任务4在第85个地图单位时间发生碰撞。如图11（a）所示，绿色圆圈内为碰撞点，图11（b）显示了四条路径的任务时间窗口划分，黑色框放大部分描述了该时刻两AGV发生碰撞，时间窗口发生重叠。
图11 碰撞示例
由于任务3和任务4发生碰撞，且任务4的路径优先级更低，所以对任务4进行一次道路切换。如图12所示。为方便理解，假设碰撞时刻为第6个单位时间，
图12 路径切换示意图
图12（a）标注了6个单位时间内，两AGV在地图上的行进顺序。在完成道路切换后的AGV行进顺序如图12（b）所示，可以看到红色任务4路径在第5个时间单位通过交叉路口，而蓝色任务3路径在第7个时间单位通过交叉路口，在不改变路径长度和拐弯数量的情况下，通过切换道路成功避免了一次碰撞。完成重新规划的AGV路径规划图以及时间片划分情况如图13所示。
图13 重新规划后结果
三、结论
本文研究了A*算法在AGV路径规划中的应用，并基于A*算法和工厂实际场景对其进行改进，得到了基于关键点的A*路径规划算法。在算法规划所需计算时间上与传统方法相比提升了44.43%，路径转弯个数上相较于传统A*算法下降了47.83%。并且本文方法规划的AGV路径方向完全符合工厂实际场景的道路方向需求。除此之外，将基于关键点的A*路径规划方法与时间窗口方法相结合，并结合工厂的道路场景，提出一种道路切换的方式来降低碰撞带来的时间损耗，得到了较好的效果。
参考文献:
[1] J. Zając, W. Małopolski, Structural on-line control policy for collision and deadlock resolution in multi-AGV systems, Journal of Manufacturing Systems, 60 (2021) 80-92.
[2] P. Xia, A. Xu, Y. Zhang, A Multi-AGV Optimal Scheduling Algorithm Based on Particle Swarm Optimization, in: X. Sun, J. Wang, E. Bertino (Eds.) Artificial Intelligence and Security, Springer Singapore, Singapore, 2020, pp. 527-538.
[3] I. Draganjac, D. Miklić, Z. Kovačić, G. Vasiljević, S. Bogdan, Decentralized Control of Multi-AGV Systems in Autonomous Warehousing Applications, IEEE Transactions on Automation Science and Engineering, 13 (2016) 1433-1447.
[4] N. Smolic-Rocak, S. Bogdan, Z. Kovacic, T. Petrovic, Time Windows Based Dynamic Routing in Multi-AGV Systems, IEEE Transactions on Automation Science and Engineering, 7 (2010) 151-155.
[5] T.J. Chen, Y. Sun, W. Dai, W. Tao, S. Liu, On the Shortest and Conflict-Free Path Planning of Multi-AGV System Based on Dijkstra Algorithm and the Dynamic Time-Window Method, Advanced Materials Research, 645 (2013) 267-271.
[6] G. Sheng, C. Qin, L. Chen, X. Lu, J. Xu, H. Luo, X. Zhang, A Timewindow-Based Multi-AGV Path Planning Method Using Improved A Star Algorithm, 2024 IEEE 7th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), 2024, pp. 365-368.
[7] Y. Liang, M. Liu, Multi-AGV Simulation System Based on Bipartite Graph, Space-Time A*, and Conflict Search, 2022 China Automation Congress (CAC), 2022, pp. 3767-3772.
来源：物流技术与应用杂志
