Shape formation by programmable particles

DOI10.1007/S00446-019-00350-6MaRDI QIDQ2174252zbMATHOpenAlexFDO

Authors P. Flocchini, N. Santoro, G. Viglietta, Yukiko Yamauchi, Giuseppe Antonio Di Luna

Publication date 21 April 2020

Published in Distributed Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane and have limited computational power (they have constant memory), strictly local interaction and communication capabilities (only with particles in neighboring nodes of the grid), and limited motorial capabilities (from a grid node to an empty neighboring node); their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization (i.e., particles can flip coins). In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of $n$ particles. As a byproduct, if randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that $n$ is large enough. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation in terms of both the number of rounds and of moves performed by the particles. We prove that our solution has a complexity of $O(n^2)$ rounds and moves: this number of moves is also asymptotically optimal.

Recommendations

• Shape formation by programmable particles
• Leader election and shape formation with self-organizing programmable matter
• On the transformation capability of feasible mechanisms for programmable matter
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Line reconfiguration by programmable particles maintaining connectivity

Cites work

• A Markov chain algorithm for compression in self-organizing particle systems
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• An introduction to tile-based self-assembly and a survey of recent results
• Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
• Characterizing geometric patterns formable by oblivious anonymous mobile robots
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Distributed reconfiguration of metamorphic robot chains
• Forming sequences of geometric patterns with oblivious mobile robots
• Improved Leader Election for Self-organizing Programmable Matter
• Leader election and shape formation with self-organizing programmable matter
• On the transformation capability of feasible mechanisms for programmable matter
• Pattern formation by oblivious asynchronous mobile robots
• Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract)
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• Universal coating for programmable matter
• Universal computation and optimal construction in the chemical reaction network-controlled tile assembly model

Cited in

(26)

• Terminating distributed construction of shapes and patterns in a fair solution of automata
• The canonical amoebot model: algorithms and concurrency control
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• Line reconfiguration by programmable particles maintaining connectivity
• On geometric shape construction via growth operations
• Connected reconfiguration of lattice-based cellular structures by finite-memory robots
• Shape recognition by a finite automaton robot
• Shape formation by programmable particles
• Leader election and shape formation with self-organizing programmable matter
• Collision-free pattern formation
• Forming tile shapes with simple robots
• On the transformation capability of feasible mechanisms for programmable matter
• On geometric shape construction via growth operations
• Building a nest by an automaton
• Geometric self-assembly of rigid shapes: a simple Voronoi approach
• Improved Leader Election for Self-organizing Programmable Matter
• A Markov chain algorithm for compression in self-organizing particle systems
• Reconfiguring massive particle swarms with limited, global control
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Universal coating for programmable matter
• Full tilt: universal constructors for general shapes with uniform external forces
• Distributed transformations of Hamiltonian shapes based on line moves
• Distributed transformations of Hamiltonian shapes based on line moves
• Particle computation: complexity, algorithms, and logic
• Forming tile shapes with simple robots

This page was built for publication: Shape formation by programmable particles

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