2026-07-23T03:27:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12231 2024-03-06T10:49:46Z ddc:004 open_access

Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition) Abdel-Rahman, Amira Becker, Aaron T. Biediger, Daniel E. Cheung, Kenneth C. Fekete, Sándor P. Gershenfeld, Neil A. Hugo, Sabrina Jenett, Benjamin Keldenich, Phillip Niehs, Eike Rieck, Christian Schmidt, Arne Scheffer, Christian Yannuzzi, Michael Finite automata reconfiguration construction scaling In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amira Abdel-Rahman and Aaron T. Becker and Daniel E. Biediger and Kenneth C. Cheung and Sándor P. Fekete and Neil A. Gershenfeld and Sabrina Hugo and Benjamin Jenett and Phillip Keldenich and Eike Niehs and Christian Rieck and Arne Schmidt and Christian Scheffer and Michael Yannuzzi 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.73 urn:nbn:de:0030-drops-122310 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.73 eng https://creativecommons.org/licenses/by/3.0/legalcode