View PDF HTML (experimental)

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.

Submission history

From: Tsuri Farhana [view email]
[v1] Thu, 19 Mar 2026 22:10:47 UTC (732 KB)
[v2] Mon, 14 Sep 2026 12:18:30 UTC (850 KB)