Collision-Aware Route Planning in Warehouses Made Efficient: A Strip-based Framework

Multi-robot systems are deployed in modern warehouses to reduce operational cost. The robots are tasked to deliver items stored on racks to pickers for fast distribution. A central algorithmic problem is collision-aware route planning, which aims to plan shortest routes for robots to deliver racks while avoiding collision with racks, pickers, and other robots. Prior solutions are inefficient in real-world warehouses, where route planning requests emerge online and at large scale. In this paper, we identify collision judgement in grid-based warehouse representation as the primary efficiency bottleneck, and propose a novel Strip-based Route Planning framework (SRP). Specifically, we exploit the regularity in warehouse layouts, and aggregate grids into strips. The strip-based representation also converts collisions of 3-dimensional (2-dimensional space and 1dimensional time) routes into 2-dimensional (1-dimensional space and 1-dimensional time) segment intersections, which can be fast checked via computational geometry. We further accelerate the collision judgement via indexing on segments within strips. Theoretical analysis shows a reduction of time complexity from square to linear-logarithmic. Experimental results on datasets collected from real-world robotized warehouses show that our SRP is up to 227× faster than existing methods.

• We propose a strip-based representation for fast collision awareness. It breaks the efficiency bottleneck in gridbased representations leveraging the regularity of warehouse layouts, and transforming collisions in routes into segment intersections in computational geometry.

• We devise an end-to-end collision awareness route planning solution suited for large-scale warehouses. It drastically reduces the time complexity of prior algorithms from O((HW ) 2 ) to O((HW ) log(HW )), where W and H are the width and length of a warehouse in grids.

• Experimental results on real-world datasets show that our solution can be up to 227× faster than existing methods while maintaining high effectiveness.