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 1-dimensional 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.