2026-09-05T11:58:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25849 2026-06-23T12:59:30Z ddc:004 open_access

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs Farhana, Tsuri Filtser, Omrit Goldshtein, Shalev multi-robot motion planning 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. Solovey et al. (RSS'15) provide a near-optimal solution assuming that start/target positions must have pairwise distance at least 4, and at least √5≈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 and the obstacles-separation is 1 2/3, or (ii) the robots-separation is ≈3.291 and the obstacles-separation ≈1.354. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only 2, and the obstacles-separation is 3. Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 may be necessary for a solution to exist. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tsuri Farhana and Omrit Filtser and Shalev Goldshtein 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.43 urn:nbn:de:0030-drops-258495 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.43 eng https://creativecommons.org/licenses/by/4.0/legalcode