Shape formation by programmable particles

DOI10.1007/S00446-019-00350-6zbMATH Open1433.68055arXiv1705.03538OpenAlexW2963533232MaRDI 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
• On the Runtime of Universal Coating for Programmable Matter
• 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 (9)

• On geometric shape construction via growth operations
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• Building a nest by an automaton
• Connected reconfiguration of lattice-based cellular structures by finite-memory robots
• Improved Leader Election for Self-organizing Programmable Matter
• Distributed transformations of Hamiltonian shapes based on line moves
• Distributed transformations of Hamiltonian shapes based on line moves
• The canonical amoebot model: algorithms and concurrency control
• On geometric shape construction via growth operations

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)