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

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

Conflict-free path planning for multi-AGV in automated terminals based on improved CBS algorithm

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.