LIPIcs.SoCG.2022.65.pdf
- Filesize: 2.46 MB
- 6 pages
Document
Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition)
Authors
Julien Bourgeois 
,
Sándor P. Fekete ,
Ramin Kosfeld ,
Peter Kramer ,
Benoît Piranda ,
Christian Rieck ,
Christian Scheffer
-
Part of:
Volume:
38th International Symposium on Computational Geometry (SoCG 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-01
File
Document Identifiers
Author Details
- FEMTO-ST Institute, University of Bourgogne Franche-Comté, CNRS, Montbeliard, France
Cite As Get BibTex
Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer. Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.65
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Computing methodologies → Motion path planning
Keywords
- Motion planning
- parallel motion
- bounded stretch
- scaled shape
- makespan
- connectivity
- swarm robotics
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amira Abdel-Rahman, Aaron T. Becker, Daniel Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi. Space Ants: Constructing and reconfiguring large-scale structures with finite automata. In Symposium on Computational Geometry (SoCG), pages 73:1-73:6, 2020. Video at https://youtu.be/SFI57l5dOvk. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.73.
- Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer. Coordinated motion planning: The video. In Symposium on Computational Geometry (SoCG), pages 74:1-74:6, 2018. Video at https://www.ibr.cs.tu-bs.de/users/fekete/Videos/CoordinatedMotionPlanning.mp4. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.74.
- Loïc Crombez, Guilherme Dias da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks approach to low-makespan coordinated motion planning. In Symposium on Computational Geometry (SoCG), pages 63:1-63:9, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.63.
- Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch. SIAM Journal on Computing, 48(6):1727-1762, 2019. URL: https://doi.org/10.1137/18M1194341.
- Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected coordinated motion planning with bounded stretch. In Symposium on Algorithms and Computation (ISAAC), pages 9:1-9:16, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.9.
- Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell. Computing coordinated motion plans for robot swarms: The CG:SHOP Challenge 2021, 2021. URL: http://arxiv.org/abs/2103.15381.
- Seth Copen Goldstein, Jason D. Campbell, and Todd C. Mowry. Programmable matter. Computer, 38(6):99-101, 2005. URL: https://doi.org/10.1109/MC.2005.198.
- Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Coordinated motion planning through randomized k-opt. In Symposium on Computational Geometry (SoCG), pages 64:1-64:8, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.64.
- Benoît Piranda and Julien Bourgeois. Designing a quasi-spherical module for a huge modular robot to create programmable matter. Autonomous Robots, 42(8):1619-1633, 2018. URL: https://doi.org/10.1007/s10514-018-9710-0.
- Benoît Piranda and Julien Bourgeois. Datom: A deformable modular robot for building self-reconfigurable programmable matter. In Symposium on Distributed Autonomous Robotic Systems (DARS), pages 70-81, 2021. URL: https://doi.org/10.1007/978-3-030-92790-5_6.
- David Soloveichik and Erik Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6):1544-1569, 2007. URL: https://doi.org/10.1137/S0097539704446712.
- Pierre Thalamy, Benoît Piranda, and Julien Bourgeois. Engineering efficient and massively parallel 3d self-reconfiguration using sandboxing, scaffolding and coating. Robotics and Autonomous Systems, 146:103875, 2021. URL: https://doi.org/10.1016/j.robot.2021.103875.
- Hyeyun Yang and Antoine Vigneron. A simulated annealing approach to coordinated motion planning. In Symposium on Computational Geometry (SoCG), pages 65:1-65:9, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.65.