Cooperative Path Planning for Four-Way Shuttle Vehicles in Storage and Retrieval Systems: A Hierarchically Dynamic Graph Based Approach

Recently, Shuttle-based Storage and Retrieval Sys- tems (SBS/RSs) have garnered significant attention from both academia and industry, owing to their high spatial utilization and rapid response speed. However, the weak connectivity of roadmaps in densely stored environments increases the likelihood of congestion and deadlocks when multiple four-way shuttles operate simultaneously, thereby imposing greater de- mands for collaborative path planning. Instead of exhaustively coordinating the shuttle motions during the off-line planning or online local control stages, we solve the cooperative path planning challenge from the perspective of altering the road graph structure dynamically. More specifically, we propose an approach to automatically transfer the typical road graph of SBS/RSs into a hierarchical graph with a reduced size, and then dynamically adjust its edge properties to prohibit any motion conflicts. In this manner, the planning problem of large-scale shuttle groups can be easily resolved and all the potential congestions can be eliminated inherently. Finally, we build a complete multi-shuttle cooperative path planning system adaptable for large-scale problems.