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

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.

Computational Geometry (cs.CG); Robotics (cs.RO)

arXiv:2603.19502 [cs.CG]

(or arXiv:2603.19502v2 [cs.CG] for this version)

https://doi.org/10.48550/arXiv.2603.19502 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.