On the Transformation Capability of Feasible Mechanisms for Programmable Matter

23^rd October 2018, 14:00
Georgios Skretas

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 neighbour and slide over a line. In terms of modelling, 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 in feasible 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.

[Joint work with Othon Michail and Paul Spirakis.]