Abstract
The amoebot model [Derakhshandeh et al., SPAA 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigurable circuit extension [Feldmann et al., JCB 2022] of the geometric (variant of the) amoebot model that allows the amoebot structure to interconnect amoebots by socalled circuits. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits.
We start with some fundamental problems like the stripe computation problem where, given any connected amoebot structure S, an amoebot u in S, and some axis X, all amoebots belonging to axis X through u have to be identified. Second, we consider the global maximum problem, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can then be used to solve the skeleton problem, where a (not necessarily simple) cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can then be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions will then allow the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure.
The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmictime solutions to all of these problems.
BibTeX  Entry
@InProceedings{padalkin_et_al:LIPIcs.DNA.28.8,
author = {Padalkin, Andreas and Scheideler, Christian and Warner, Daniel},
title = {{The Structural Power of Reconfigurable Circuits in the Amoebot Model}},
booktitle = {28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
pages = {8:18:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772532},
ISSN = {18688969},
year = {2022},
volume = {238},
editor = {Ouldridge, Thomas E. and Wickham, Shelley F. J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16793},
URN = {urn:nbn:de:0030drops167935},
doi = {10.4230/LIPIcs.DNA.28.8},
annote = {Keywords: progammable matter, amoebot model, reconfigurable circuits, spanning tree, symmetry detection}
}
Keywords: 

progammable matter, amoebot model, reconfigurable circuits, spanning tree, symmetry detection 
Collection: 

28th International Conference on DNA Computing and Molecular Programming (DNA 28) 
Issue Date: 

2022 
Date of publication: 

04.08.2022 