Universal coating for programmable matter

DOI10.1016/J.TCS.2016.02.039zbMATH Open1370.68090arXiv1601.01008OpenAlexW2962873476MaRDI QIDQ529029FDOQ529029

Authors: Zahra Derakhshandeh, Robert Gmyr, Andrea Richa, Christian Scheideler, Thim Strothmann 

Publication date: 18 May 2017

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

Abstract: The idea behind universal coating is to have a thin layer of a specific substance covering an object of any shape so that one can measure a certain condition (like temperature or cracks) at any spot on the surface of the object without requiring direct access to that spot. We study the universal coating problem in the context of self-organizing programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized way. Based on that matter, we present a worst-case work-optimal universal coating algorithm that uniformly coats any object of arbitrary shape and size that allows a uniform coating. Our particles are anonymous, do not have any global information, have constant-size memory, and utilize only local interactions.

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

Recommendations

• Shape formation by programmable particles
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Shape formation by programmable particles
• Collaborative computation in self-organizing particle systems

zbMATH Keywords

object coatingprogrammable matterself-organizing particle systems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Artificial intelligence for robotics (68T40)

Cites Work

• An introduction to tile-based self-assembly and a survey of recent results
• Computation in networks of passively mobile finite-state sensors
• Intrinsic universality and the computational power of self-assembly
• On the computational power of oblivious robots
• Local spreading algorithms for autonomous robot systems
• Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
• Leader election and shape formation with self-organizing programmable matter
• Universal coating for programmable matter
• \textit{Physarum} can compute shortest paths

Cited In (12)

• Tilt assembly: algorithms for micro-factories that build objects with uniform external forces
• On geometric shape construction via growth operations
• Deterministic Leader Election in Programmable Matter
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Shape formation by programmable particles
• Connected reconfiguration of lattice-based cellular structures by finite-memory robots
• Shape recognition by a finite automaton robot
• The canonical amoebot model: algorithms and concurrency control
• Shape formation by programmable particles
• On geometric shape construction via growth operations
• Stationary and deterministic leader election in self-organizing particle systems
• Universal coating for programmable matter

This page was built for publication: Universal coating for programmable matter

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