Multi-Robot Path Planning Using Medial-Axis-Based Pebble-Graph Embedding
This addresses path planning for multiple robots in cluttered environments, offering a solution for scenarios with high density and narrow passages, though it is incremental as it builds on existing pebble-graph methods.
The paper tackles the problem of multi-robot path planning in continuous planar workspaces with high robot-packing densities, achieving an average success rate of 83% in environments with narrow passages where state-of-the-art methods fail.
We present a centralized algorithm for labeled, disk-shaped Multi-Robot Path Planning (MPP) in a continuous planar workspace with polygonal boundaries. Our method automatically transform the continuous problem into a discrete, graph-based variant termed the pebble motion problem, which can be solved efficiently. To construct the underlying pebble graph, we identify inscribed circles in the workspace via a medial axis transform and organize robots into layers within each inscribed circle. We show that our layered pebble-graph enables collision-free motions, allowing all graph-restricted MPP instances to be feasible. MPP instances with continuous start and goal positions can then be solved via local navigations that route robots from and to graph vertices. We tested our method on several environments with high robot-packing densities (up to $61.6\%$ of the workspace). For environments with narrow passages, such density violates the well-separated assumptions made by state-of-the-art MPP planners, while our method achieves an average success rate of $83\%$.