Motion Planning for Unlabeled Discs with Optimality Guarantees

Abstract

We study the problem of path planning for unlabeled (indistinguishable) unit-disc robots in a planar environment cluttered with polygonal obstacles. We introduce an algorithm which minimizes the total path length, i.e., the sum of lengths of the individual paths. Our algorithm is guaranteed to find a solution if one exists, or report that none exists otherwise. It runs in time $\tilde{O}(m^4+m^2{n}^2)$, where $m$ is the number of robots and $n$ is the total complexity of the workspace. Moreover, the total length of the returned solution is at most $\text{OPT}+4m$, where OPT is the optimal solution cost. To the best of our knowledge this is the first algorithm for the problem that has such guarantees. The algorithm has been implemented in an exact manner and we present experimental results that attest to its efficiency.

References in corpus (2)

• Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee
• A Linear Time Algorithm for the Feasibility of Pebble Motion on Graphs

Cited by in corpus (9)

• On the hardness of unlabeled multi-robot motion planning
• Characterizing minimum-length coordinated motions for two discs
• Fast, High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups
• Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps
• Efficient sampling-based bottleneck pathfinding over cost maps
• Sampling-based bottleneck pathfinding with applications to Frechet matching
• Motion Planning for Multiple Unit-Ball Robots in ${\mathbb{R}}^d$
• Efficient Multi-Agent Global Navigation Using Interpolating Bridges
• Efficient, High-Quality Stack Rearrangement