Continuous-Time Priority-Based Search with Offline Collision Detection and Roadmap Annotation for Efficient Multi-AGV Coordination

This paper addresses the coordination of automated guided vehicles (AGVs) in industrial warehouse environments, where roadmaps are highly connected and redundant, making scalability and safety critical challenges. We introduce continuous-time priority-based search with continuous-time conflicts (CPBS-CTC), a continuous-time extension of prioritybased search (PBS) combined with an offline roadmap annotation that enables efficient collision detection. The contribution is two-fold. From a methodological perspective, the paper advances the multi-agent path finding (MAPF) literature by extending PBS to continuous-time domains. From an application perspective, the algorithm is integrated into an industrial-grade simulator that provides a realistic digital twin of warehouse layouts and AGV fleets, paving the way for practical deployment in real-world scenarios. We benchmark CPBS-CTC against stateof-the-art continuous-time MAPF solvers, including continuoustime conflict-based search (CCBS), an annotated CCBS variant, and prioritized planning baselines with and without restarts, on five real-world warehouse layouts. Results show a clear trade-off: CCBS guarantees optimal solution cost but fails to scale, whereas prioritized planning baselines achieve very fast runtimes but become unreliable in dense scenarios. Overall, CPBS-CTC provides the best compromise, achieving the highest success rates on several layouts while maintaining competitive runtime and solution quality.