Pushing lines helps: efficient universal centralised transformations for programmable matter

DOI10.1016/J.TCS.2020.04.026MaRDI QIDQ2182711zbMATH OpenOpenAlexFDO

Authors Abdullah Almethen, Othon Michail, Igor Potapov

Publication date 26 May 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexitydistributed algorithmsprogrammable matterreconfigurable roboticsshape formationtransformation

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15)

Abstract: In this paper, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all $n$ nodes forms initially a connected shape $A$. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities, from 1 to $n$, in parallel in a single time-step. A target connected shape $B$ is also provided and the goal is to emph{transform} $A$ into $B$ via a sequence of line movements. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, $Theta(n^2)$) emph{universal transformations} carry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i.e., sub-quadratic worst-case, transformations. As a first step towards this, we restrict attention solely to centralised transformations and leave the distributed case as a direction for future research. Our results are positive. By focusing on the apparently hard instance of transforming a diagonal $A$ into a straight line $B$, we first obtain transformations of time $O(nsqrtn)$ without and with preserving the connectivity of the shape throughout the transformation. Then, we further improve by providing two $O(nlogn)$-time transformations for this problem. By building upon these ideas, we first manage to develop an $O(nsqrtn)$-time universal transformation. Our main result is then an $O(nlogn)$-time universal transformation. We leave as an interesting open problem a suspected $Omega(nlogn)$-time lower bound.

Recommendations

• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• On the transformation capability of feasible mechanisms for programmable matter
• On the transformation capability of feasible mechanisms for programmable matter
• Line reconfiguration by programmable particles maintaining connectivity

Cites work

• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Brief announcement: Pattern formation problem for synchronous mobile robots in the three dimensional Euclidean space
• Characterizing geometric patterns formable by oblivious anonymous mobile robots
• Computation in networks of passively mobile finite-state sensors
• Controlled module density helps reconfiguration planning
• Distributed computing by mobile robots: gathering
• Distributed reconfiguration of metamorphic robot chains
• Efficient reconfiguration of lattice-based modular robots
• Fault-Tolerant and Self-stabilizing Mobile Robots Gathering
• Forming sequences of geometric patterns with oblivious mobile robots
• scientific article; zbMATH DE number 1834637 (Why is no real title available?)
• Keeping Mobile Robot Swarms Connected
• On the transformation capability of feasible mechanisms for programmable matter
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• Pushing squares around
• Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves
• The computational power of population protocols
• The program-size complexity of self-assembled squares (extended abstract)

Cited in

(15)

• On the transformation capability of feasible mechanisms for programmable matter
• Distributed computation and reconfiguration in actively dynamic networks
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• On the transformation capability of feasible mechanisms for programmable matter
• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• Distributed transformations of Hamiltonian shapes based on line moves
• Distributed transformations of Hamiltonian shapes based on line moves
• Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
• On geometric shape construction via growth operations
• Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes
• On geometric shape construction via growth operations
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• All for one and one for all: an O(1)-musketeers generic transformation for rotating robots
• On the exponential growth of geometric shapes
• Collision detection for modular robots -- it is easy to cause collisions and hard to avoid them

Describes a project that uses

Uses Software

• AmoebotSim

This page was built for publication: Pushing lines helps: efficient universal centralised transformations for programmable matter

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