In this work, we study theoretical models of \emph{programmable matter} systems. The systems under consideration consist of spherical modules, that are kept together by magnetic or electrostatic forces and are able to perform two minimal mechanical operations (or movements): \emph{rotate} around a neighbor and \emph{slide} over a line. In terms of modeling, there are $n$ nodes arranged in a 2-dimensional grid that form some initial \emph{shape}. The goal is for the initial shape $A$ to \emph{transform} to some target shape $B$ by a sequence of movements. Most of the paper focuses on \emph{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 $\rem{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 $\rem{PSPACE}$ and study the problem of determining the minimum \emph{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.
@article{MSS18,
author={Michail, Othon and Skretas, George and Spirakis, Paul G},
title={On the Transformation Capability of Feasible Mechanisms for Programmable Matter},
journal={Journal of Computer and System Sciences},
volume = {},
number = {},
pages = {--},
year = {2018},
issn = {},
doi = {},
url = {},
publisher = {Elsevier}
}
@inproceedings{MSS17,
title={On the Transformation Capability of Feasible Mechanisms for Programmable Matter},
author={Michail, Othon and Skretas, George and Spirakis, Paul G},
booktitle={44th International Colloquium on Automata, Languages and Programming (ICALP)},
pages={136:1--136:15},
year={2017},
url={https://doi.org/10.4230/LIPIcs.ICALP.2017.136},
doi={10.4230/LIPIcs.ICALP.2017.136},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}
}
