Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Tsuri Farhana, Omrit Filtser, Shalev Goldshtein · 2026
Read Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs by Tsuri Farhana, Omrit Filtser, Shalev Goldshtein (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19502.txt.
Introduction
Farhana and co-authors improve separation trade-offs for unlabeled multi-robot motion planning. Unit-disk robots move in a polygonal space, and any robot may take any target. Fast algorithms exist only when starts, targets, and obstacles stay well apart. The team gives polynomial-time constant-approximation algorithms at much tighter spacing. Some plans are monotone, others weakly so, with matching lower bounds on spacing. A near-optimal plan at robot spacing 2 costs a linear approximation factor.
Catalog record
| CREATOR | Tsuri Farhana, Omrit Filtser, Shalev Goldshtein |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 112505 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19502
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs Tsuri Farhana, Omrit Filtser, Shalev Goldshtein Abstract We study unlabeled multi-robot motion planning 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 4 , and start–target distances of at least 3 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 4 , and at least 5 ≈ 2.236 \sqrt{5}\approx 2.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 trade-offs on the robots-separation and obstacles-separation bounds, 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) the robots-separation is 2 2 3 2\tfrac{2}{3} and the obstacles-separation is 1 2 3 1\tfrac{2}{3} , or (ii) the robots-separation is ≈ 3.291 \approx 3.291 and the obstacles-separation ≈ 1.354 \approx 1.354 . These solutions are weakly-monotone; we also provide a monotone solution requiring obstacles-separation of ≈ 1.614 \approx 1.614 and robots-separation of 4. We prove that monotone plans may not exist below obstacles-separation ≈ 1.614 \approx 1.614 , and weakly-monotone plans may not exist below ≈ 1.354 \approx 1.354 . Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only 2 2 , and the obstacles-separation is 3 3 . Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 1.5 may be necessary for a solution to exist. \crefname constraintconstraintconstraints \Crefname constraintConstraintConstraints Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. [email protected] https://orcid.org/0009-0006-7246-6805 Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel [email protected] https://orcid.org/0000-0002-3978-1428This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 2135/24) Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel [email protected] https://orcid.org/0009-0001-7975-7721This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 2135/24) {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10010061.10010063¡/concept_id¿ ¡concept_desc¿Theory of computation Computational geometry¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ We thank Dan Halperin for introducing us to the problem and for helpful discussions. We are also grateful to the anonymous reviewers for their insightful comments, which helped improve the structure and presentation of the paper. ccs Theory of computation Computational geometry keywords multi-robot motion planning † † runningtitle: Unlabeled MRMP with Improved Separation Trade-offs † † runningauthor: T. Farhana, O. Filtser and S. Goldshtein † † copyright: Tsuri Farhana, Omrit Filtser and Shalev Goldshtein † † relatedversion: A shorter version of this paper appeared in the Proceedings of the 42nd International Symposium on Computational Geometry (SoCG 2026). † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: SoCG 2026 † † event-acronym: SoCG † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction In the classic multi-robot motion-planning (MRMP) problem, a set of robots operate in a common workspace, and need to reach a set of target positions. More precisely, given a set of m starting positions and a set of m target positions in a workspace \mathcal{W} , the goal is to compute a motion strategy for the robots to reach the targets while avoiding collisions with the boundary of the workspace and with other robots. In this paper we consider unit-disk robots that are moving in a polygonal workspace in the plane. If each robot is assigned to a specific target, the problem is referred to as labeled MRMP, and otherwise it is unlabeled MRMP. Unless otherwise specified, the variant of MRMP that we consider in this paper is unlabeled. The MRMP problem and its variants have been widely investigated, both from theoretical and practical perspectives; for some of the more recent results, see, for example, [ 3 , 4 , 5 , 6 , 11 , 12 ] . Very recently, both the labeled and unlabeled variants of MRMP for unit disks in polygons with holes were shown to be PSPACE-hard [ 1 ] . Many other variants of the problem are known to be hard as well, see e.g. [ 8 , 13 , 17 , 19 ] . Interestingly, the separation between the robots plays a key role in the difficulty of the problem. Adler, de Berg, Halperin, and Solovey [ 2 ] show that in a simple polygonal workspace with n vertices and m unit-disk robots, when the robots-separation , denoted \rho , is 4 (i.e., all the start and target positions are at least distance 4 apart), a solution for unlabeled MRMP always exists, and can be found in \tilde{O}(mn+m^{2}) time. In [ 7 ] this result is further improved by distinguishing between two types of robots-separation bounds: (i) monochromatic robots-separation — the distance between two start positions or between two target positions, and (ii) bichromatic robots-separation — the distance between a start and a target positions. They present an algorithm with the same running time of O(n\log n+mn+m^{2}) , but under weaker assumptions: monochromatic separation of 4 , and bichromatic separation of 3 . Moreover, they prove that these bounds are tight, i.e., a solution for unlabeled MRMP in a simple polygon may not always exist when the monochromatic separation is 4-{\varepsilon} , or when the bichromatic separation is 3-{\varepsilon} . In addition, they show that when the free space consists of a single connected component, the bichromatic separation is not required for a solution to always exist. The algorithmic approach in both papers [ 7 , 2 ] is similar : restricting the robots to move one at a time (a monotone strategy) on a motion graph that has the start and target positions as vertices. A drawback of this approach is that it does not provide any reasonable approximation on the length of the solution, i.e., the total length of the paths in the motion plan. Solovey, Yu, Zamir, and Halperin [ 18 ] present a different approach for unlabeled MRMP, with optimality guarantee even in polygons with holes, but at the cost of adding an additional assumption on the distance between the obstacles to any start and target position. Specifically, they consider the case when the robots-separation is \rho=4 , and the obstacles-separation , denoted \omega , is \sqrt{5}\approx 2.236 (i.e., the distance between any start/target position and any obstacle is at least \sqrt{5} ). Under these assumptions, they present an algorithm that runs in \tilde{O}(m^{4}+n^{2}m^{2}) time and returns a solution of total length at most \text{OPT}+4m . Here and throughout the paper, OPT denotes the minimum possible sum of lengths of the paths in a collision-free motion plan. Notice that when assuming a large robots-separation ( \rho\geq 4 ), the overall “density” of the robots inside the workspace becomes small, which may require the workspace to be much larger than the number