Distributed transformations of Hamiltonian shapes based on line moves

DOI10.1007/978-3-030-89240-1_1MaRDI QIDQ5918708zbMATH OpenOpenAlexFDO

Authors Abdullah Almethen, Othon Michail, Igor Potapov

Publication date 24 June 2022

Published in Algorithms for Sensor Systems (Search for Journal in Brave)

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

zbMATH Keywords

discrete transformationsdistributed algorithmsline movementprogrammable matterreconfigurable roboticsshape formation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15)

Abstract: We consider a discrete system of $n$ simple indistinguishable devices, called emph{agents}, forming a emph{connected} shape $S_I$ on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a emph{line move}, by which an agent can push a whole line of consecutive agents in one of the four directions in a single time-step. We study the problem of transforming an initial shape $S_I$ into a given target shape $S_F$ via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. Our main contribution is the first distributed connectivity-preserving transformation that exploits line moves within a total of $O(nlo{g}_{2}n)$ moves, which is asymptotically equivalent to that of the best-known centralised transformations. The algorithm solves the emph{line formation problem} that allows agents to form a final straight line $S_L$, starting from any shape $S_I$, whose emph{associated graph} contains a Hamiltonian path.

Recommendations

• 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

Cites work

• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Building a nest by an automaton
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• 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 reconfiguration of metamorphic robot chains
• Efficient reconfiguration of lattice-based modular robots
• Hamilton Paths in Grid Graphs
• On the computational power of DNA
• On the transformation capability of feasible mechanisms for programmable matter
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• Pushing squares around
• Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves
• Shape formation by programmable particles
• The program-size complexity of self-assembled squares (extended abstract)
• Universal reconfiguration of facet-connected modular robots by pivots: the \(O(1)\) musketeers

Cited in

(1)

• Distributed transformations of Hamiltonian shapes based on line moves

Describes a project that uses

Uses Software

• CADbots

This page was built for publication: Distributed transformations of Hamiltonian shapes based on line moves

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