Shape formation by programmable particles

DOI10.1007/S00446-019-00350-6zbMATH Open1433.68055OpenAlexW2963533232MaRDI QIDQ2174252FDOQ2174252

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

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

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)