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.ICALP.2017.136
URN: urn:nbn:de:0030-drops-74341
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7434/
Michail, Othon ;
Skretas, George ;
Spirakis, Paul G.
On the Transformation Capability of Feasible Mechanisms for Programmable Matter
Abstract
In this work, we study theoretical models of programmable matter systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes A and B can be transformed to each other is in P. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in PSPACE and study the problem of determining the minimum seeds that can make feasible otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes A,B of the same number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is Theta(n^2). We improve this to O(n) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformation.
BibTeX - Entry
@InProceedings{michail_et_al:LIPIcs:2017:7434,
author = {Othon Michail and George Skretas and Paul G. Spirakis},
title = {{On the Transformation Capability of Feasible Mechanisms for Programmable Matter}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {136:1--136:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7434},
URN = {urn:nbn:de:0030-drops-74341},
doi = {10.4230/LIPIcs.ICALP.2017.136},
annote = {Keywords: programmable matter, transformation, reconfigurable robotics, shape formation, complexity, distributed algorithms}
}
|
Keywords: |
|
programmable matter, transformation, reconfigurable robotics, shape formation, complexity, distributed algorithms |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
