2017/03/13 by Othon Michail, Michail, Othon, George Skretas +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Engineering · Physics and Astronomy · #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Micro and Nano Robotics #Modular Robots and Swarm Intelligence #Parallel #Robotics (cs.RO) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1703.04381
openalex publication_date 2017/03/13 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
In this work, we study theoretical models of \programmable matter\nsystems. The systems under consideration consist of spherical modules, kept\ntogether by magnetic forces and able to perform two minimal mechanical\noperations (or movements): \rotate around a neighbor and \slide\nover a line. In terms of modeling, there are n nodes arranged in a\n2-dimensional grid and forming some initial \shape. The goal is for the\ninitial shape A to \transform to some target shape B by a sequence of\nmovements. Most of the paper focuses on \transformability questions,\nmeaning whether it is in principle feasible to transform a given shape to\nanother. We first consider the case in which only rotation is available to the\nnodes. Our main result is that deciding whether two given shapes A and B\ncan be transformed to each other, is in \P. We then insist on\nrotation only and impose the restriction that the nodes must maintain global\nconnectivity throughout the transformation. We prove that the corresponding\ntransformability question is in \PSPACE and study the problem of\ndetermining the minimum \seeds that can make feasible, otherwise\ninfeasible transformations. Next we allow both rotations and slidings and prove\nuniversality: any two connected shapes A,B of the same order, can be\ntransformed to each other without breaking connectivity. The worst-case number\nof movements of the generic strategy is \Ω(n2). We improve this to\nO(n) parallel time, by a pipelining strategy, and prove optimality of both by\nmatching lower bounds. In the last part of the paper, we turn our attention to\ndistributed transformations. The nodes are now distributed processes able to\nperform communicate-compute-move rounds. We provide distributed algorithms for\na general type of transformations.\n