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
Overview
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=2\frac{2}{3}$ and $\omega=1\frac{2}{3}$, or (ii) $\rho\approx3.291$ and $\omega\approx1.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
Originally published at arxiv.org.
Related Articles
Source: https://arxiv.org/abs/2603.19502