2026-08-11T00:28:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8787 2024-03-06T10:42:39Z ddc:004 open_access

Coordinated Motion Planning: The Video (Multimedia Exposition) Becker, Aaron T. Fekete, Sándor P. Keldenich, Phillip Konitzny, Matthias Lin, Lillian Scheffer, Christian Motion planning robot swarms complexity stretch approximation We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron T. Becker and Sándor P. Fekete and Phillip Keldenich and Matthias Konitzny and Lillian Lin and Christian Scheffer 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.74 urn:nbn:de:0030-drops-87872 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.74 eng https://creativecommons.org/licenses/by/3.0/legalcode