Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach

Connor, Matthew, Michail, Othon ORCID: 0000-0002-6234-3960 and Potapov, Igor (2021) Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach. ALGORITHMS FOR SENSOR SYSTEMS, ALGOSENSORS 2021, 12961. pp. 45-60.

Text
2108.09250v1.pdf - Submitted version
Download (1MB) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-030-89240-1_4

Abstract

We study a model of programmable matter systems consisting of $n$ devices lying on a 2-dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape A into a target shape B. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming nice shapes, a class of shapes consisting of a central line $L$ where for all nodes $u$ in $S$ either $u \in L$ or $u$ is connected to $L$ by a line of nodes perpendicular to $L$. We prove that by introducing a minimal 3-node seed it is possible for the canonical shape of a line of $n$ nodes to be transformed into a nice shape of $n-1$ nodes. We use this to show that a 4-node seed enables the transformation of nice shapes of size $n$ into any other nice shape of size $n$ in $O(n^2)$ time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes.

Item Type:	Article
Additional Information:	22 pages, 10 figures
Uncontrolled Keywords:	Programmable matter, Transformation, Reconfigurable robotics, Shape formation, Centralised algorithms
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	02 Sep 2021 08:15
Last Modified:	12 Oct 2023 12:59
DOI:	10.1007/978-3-030-89240-1_4
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3135611