Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

arXiv:2603.19502v2 Announce Type: replace-cross Abstract: We study unlabeled MRMP for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al.(SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least 4, and start--target distances of at least 3, but without optimality guarantees. Solovey et al.(RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least 4, and at least sqrt{5}approx2.236 from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different tradeoffs on the robots-separation rho and obstacles-separation omega, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) rho=2frac{2}{3} and omega=1frac{2}{3}, or (ii) rhoapprox3.291 and omegaapprox1.354. These solutions are weakly-monotone; we also provide a monotone solution requiring omega=approx1.614 and rho=4. We prove that monotone plans may not exist when omega<1.614, and weakly-monotone plans may not exist when omega<1.354. We then present tradeoffs between the separation bounds and the approximation factor, specifically achieving an (almost) optimal bound of rho=2 at the cost of a linear approximation factor and requiring omega=2. This applies also for the labeled variant of MRMP, in which case we show a tight bound on omega. Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 may be necessary for a solution to exist.

Source: arXiv cs.RO | 2026-09-15