プログラマブルマターの実現可能な機構における形状変換能力について
On the Transformation Capability of Feasible Mechanisms for Programmable Matter
球状モジュールが回転・滑りで形状を変えるプログラマブルマターの理論モデルを解析し、回転のみの場合の変換可否判定がP、連結性維持下ではPSPACEであることを示し、回転と滑りの併用で任意の連結形状間の変換が可能(普遍性)であることを証明した。
著者: Othon Michail, George Skretas, Paul G. Spirakis
分類: cs.DS, cs.DC, cs.RO
原文アブストラクト
In this work, we study theoretical models of \emph{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): \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 and forming 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 $\mathbf{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 $\mathbf{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 order, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is $\Omega(n^2)$. We improve this to $O(n)$ parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. In the last part of the paper, we 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 transformations.
関連論文
- 押し出しで効率化:プログラマブルマターのための高速な集中型形状変換プログラマブルマター
