2026-07-28T01:14:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15442 2024-03-06T10:55:18Z ddc:004 open_access

Connected Coordinated Motion Planning with Bounded Stretch Fekete, Sándor P. Keldenich, Phillip Kosfeld, Ramin Rieck, Christian Scheffer, Christian Motion planning parallel motion bounded stretch scaled shape makespan connectivity swarm robotics We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is 𝒪(d), which is optimal up to constant factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor P. Fekete and Phillip Keldenich and Ramin Kosfeld and Christian Rieck and Christian Scheffer 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.9 urn:nbn:de:0030-drops-154423 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.9 eng https://creativecommons.org/licenses/by/4.0/legalcode