On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Michail, O ORCID: 0000-0002-6234-3960, Skretas, G ORCID: 0000-0003-2514-8004 and Spirakis, PG ORCID: 0000-0001-5396-3749 (2019) On the Transformation Capability of Feasible Mechanisms for Programmable Matter. Journal of Computer and System Sciences, 102. pp. 18-39.

Text MSS18JCSS.pdf - Author Accepted Manuscript Download (510kB)

Abstract

We study theoretical models of programmable matter systems, consisting of n spherical modules kept together by magnetic or electrostatic forces and able to perform two minimal mechanical operations (movements): rotate and/or slide. The goal is for an initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability (feasibility) questions. When only rotation is available, we prove that deciding whether two given shapes can transform to each other, is in P. Under the additional restriction of maintaining global connectivity, we prove inclusion in PSPACE and explore minimum seeds that can make otherwise infeasible transformations feasible. Allowing both rotations and slidings yields universality: any two connected shapes of the same order can be transformed to each other without breaking connectivity, in O(n2) sequential and O(n) parallel time (both optimal). We finally provide a type of distributed transformation.

Item Type:	Article
Uncontrolled Keywords:	programmable matter, transformation, reconfigurable robotics, shape formation, complexity, distributed algorithms
Depositing User:	Symplectic Admin
Date Deposited:	20 Dec 2018 16:05
Last Modified:	19 Jan 2023 01:09
DOI:	10.1016/j.jcss.2018.12.001
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3030147