Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes

DOI10.1007/978-3-031-22050-0_5MaRDI QIDQ6111997zbMATH OpenOpenAlexFDO

Authors Matthew Connor, Othon Michail

Publication date 4 August 2023

Published in Algorithmics of Wireless Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.03062

zbMATH Keywords

centralised algorithmsprogrammable matterreconfigurable roboticsshape formationtransformation

Mathematics Subject Classification ID

Wireless sensor networks as related to computer science (68M18) Artificial intelligence for robotics (68T40)

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 are interested in characterising the class of shapes which can be transformed into each other in such a scenario, under the additional constraint of maintaining global connectivity at all times. This was one of the main problems left open by $[$Michail et al., JCSS'19$]$. Note that the considered question is about structural feasibility of transformations, which we exclusively deal with via centralised constructive proofs. Distributed solutions are left for future work and form an interesting research direction. Past work made some progress for the special class of nice shapes. We here consider the class of orthogonal convex shapes, where for any two nodes $u,v$ in a horizontal or vertical line on the grid, there is no empty cell between $u$ and $v$. We develop a generic centralised transformation and prove that, for any pair $A$, $B$ of colour-consistent orthogonal convex shapes, it can transform $A$ into $B$. In light of the existence of blocked shapes in the considered class, we use a minimal 3-node seed to trigger the transformation. The running time of our transformation is an optimal $O(n^2)$ sequential moves, where $n=|A|=|B|$. We leave as an open problem the existence of a universal connectivity-preserving transformation with a small seed. Our belief is that the techniques developed in this paper might prove useful to answer this.

Cites work

• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• Computation in networks of passively mobile finite-state sensors
• Computation with finite stochastic chemical reaction networks
• Leader election and shape formation with self-organizing programmable matter
• On the transformation capability of feasible mechanisms for programmable matter
• On the transformation capability of feasible mechanisms for programmable matter
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• The program-size complexity of self-assembled squares (extended abstract)
• Timing in chemical reaction networks
• Universal reconfiguration of facet-connected modular robots by pivots: the \(O(1)\) musketeers

Cited in

(3)

• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• Optimal in-place compaction of sliding cubes
• Transformation of modular robots by rotation: 3 + 1 musketeers for all orthogonally convex shapes

This page was built for publication: Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6111997)