Connor, Matthew, Michail, Othon 
ORCID: 0000-0002-6234-3960 and Potapov, Igor
(2022)
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach.
In: ALGOSENSORS, 2021-9-9 - 2021-9-10.
|
Text
CMP-ALGOSENSORS-21.pdf - Author Accepted Manuscript Download (926kB) | Preview |
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∈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(n2) 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: | Conference or Workshop Item (Unspecified) |
|---|---|
| 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:12 |
| Last Modified: | 18 Jan 2023 21:30 |
| DOI: | 10.1016/j.tcs.2022.09.016 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3135615 |
Dimensions
Dimensions
