2019/09/09 by Sándor P. Fekete, Eike Niehs, Fekete, Sándor P. +5
Computer Science · Engineering · Physics and Astronomy · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Micro and Nano Robotics #Modular Robots and Swarm Intelligence #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1909.03880
openalex publication_date 2019/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider methods for connected reconfigurations by finite automate in the so-called hybrid or Robot-on-Tiles model of programmable matter, in which a number of simple robots move on and rearrange an arrangement of passive tiles in the plane that form polyomino shapes, making use of a supply of additional tiles that can be placed. We investigate the problem of reconfiguration under the constraint of maintaining connectivity of the tile arrangement; this reflects scenarios in which disconnected subarrangements may drift apart, e.g., in the absence of gravity in space. We show that two finite automata suffice to mark a bounding box, which can then be used as a stepping stone for more complex operations, such as scaling a tile arrangement by a given factor, rotating arrangements, or copying arrangements to a different location. We also describe an algorithm for scaling monotone polyominoes without the help of a bounding box.