Coordinating the Motion of Labeled Discs with Optimality Guarantees under Extreme Density
This addresses motion planning for densely packed robots, offering theoretical guarantees and practical algorithms for applications like warehouse automation or swarm robotics.
The paper tackles the problem of planning collision-free motions for routing uniform labeled discs in 2D, achieving constant-factor time-optimal routing with a polynomial-time algorithm at over 50% density and providing a high-performance algorithm for near-optimal solutions under the same conditions.
We push the limit in planning collision-free motions for routing uniform labeled discs in two dimensions. First, from a theoretical perspective, we show that the constant-factor time-optimal routing of labeled discs can be achieved using a polynomial-time algorithm with robot density over $50\%$ in the limit (i.e., over half of the workspace may be occupied by the discs). Second, from a more practical standpoint, we provide a high performance algorithm that computes near-optimal (e.g., $1.x$) solutions under the same density setting.