Motion Planning for Unlabeled Discs with Optimality Guarantees
This addresses motion planning for unlabeled robots with optimality guarantees, which is incremental as it builds on existing planning methods but adds specific bounds for indistinguishable agents.
The paper tackles the problem of path planning for indistinguishable unit-disc robots in a cluttered planar environment, introducing an algorithm that minimizes total path length with guarantees of finding a solution if one exists and achieving a solution cost at most OPT + 4m, where OPT is optimal and m is the number of robots.
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^2n^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.