2026-07-23T21:03:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16073 2024-03-06T10:56:53Z ddc:004 open_access

Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition) Bourgeois, Julien Fekete, Sándor P. Kosfeld, Ramin Kramer, Peter Piranda, Benoît Rieck, Christian Scheffer, Christian Motion planning parallel motion bounded stretch scaled shape makespan connectivity swarm robotics How can a set of identical mobile agents coordinate their motions to transform their arrangement from a given starting to a desired goal configuration? We consider this question in the context of actual physical devices called Catoms, which can perform reconfiguration, but need to maintain connectivity at all times to ensure communication and energy supply. We demonstrate and animate algorithmic results, in particular a proof of hardness, as well as an algorithm that guarantees constant stretch for certain classes of arrangements: 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 in 𝒪(d), which is optimal up to constant factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Bourgeois and Sándor P. Fekete and Ramin Kosfeld and Peter Kramer and Benoît Piranda and Christian Rieck and Christian Scheffer 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.65 urn:nbn:de:0030-drops-160732 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.65 eng https://creativecommons.org/licenses/by/4.0/legalcode