Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints

Automated Guided Vehicles (AGV) are becoming increasingly important in modern warehouses to cope with the enormous logistic demands of developing e-commerce and the growing operational costs. The key component of implementing such a system is planning the paths of a large horde of AGVs to deliver orders from shelves to packing locations. The existing solutions regard it as a Multi Agent PathFinding (MAPF) problem, but they can hardly be applied in practice because none of them could satisfy the continuous (temporal), lifelong (future task unknown and keeps appearing), kinematic (acceleration/deceleration/rotation), online (fast response), and scalability (large network, large AGV number, large task number) at the same time. Therefore, we first propose an AGV routing framework that can satisfy all these properties with its corresponding routing algorithm. Then, to improve the efficiency, we propose the Multi-Hop Conflict-Aware Search method (MHCAS) with action combination, MHSC to reduce the search space, and OHSMD to decompose motions such that routing time is reduced by three orders of magnitude. Extensive experimental studies verify the superiority of our methods compared with the state-of-the-art.