License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.73
URN: urn:nbn:de:0030-drops-122310
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12231/
Go to the corresponding LIPIcs Volume Portal

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

Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)

pdf-format:
LIPIcs-SoCG-2020-73.pdf (6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{abdelrahman_et_al:LIPIcs:2020:12231,
  author =	{Amira Abdel-Rahman and Aaron T. Becker and Daniel E. Biediger and Kenneth C. Cheung and S{\'a}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},
  title =	{{Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{73:1--73:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12231},
  URN =		{urn:nbn:de:0030-drops-122310},
  doi =		{10.4230/LIPIcs.SoCG.2020.73},
  annote =	{Keywords: Finite automata, reconfiguration, construction, scaling}
}

Keywords: Finite automata, reconfiguration, construction, scaling
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI