On the transformation capability of feasible mechanisms for programmable matter

DOI10.1016/j.jcss.2018.12.001zbMath1421.68158arXiv1703.04381OpenAlexW2914430938WikidataQ128549725 ScholiaQ128549725MaRDI QIDQ1741488

George Skretas, Othon Michail, Paul G. Spirakis

Publication date: 3 May 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

complexitytransformationdistributed algorithmsprogrammable mattershape formationreconfigurable robotics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15)

Related Items

Distributed computation and reconfiguration in actively dynamic networks, Search by a metamorphic robotic system in a finite 2D square grid, Shape formation by programmable particles, Universal reconfiguration of facet-connected modular robots by pivots: the \(O(1)\) musketeers, Pushing lines helps: efficient universal centralised transformations for programmable matter, Fault tolerant network constructors, On geometric shape construction via growth operations, Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes, The complexity of growing a graph, On geometric shape construction via growth operations, Unnamed Item, Building a nest by an automaton, On efficient connectivity-preserving transformations in a grid, Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach, Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach, Distributed transformations of Hamiltonian shapes based on line moves, Distributed transformations of Hamiltonian shapes based on line moves, Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

Uses Software

• AmoebotSim

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computation with finite stochastic chemical reaction networks
• The computational power of population protocols
• Forming sequences of geometric patterns with oblivious mobile robots
• Computation in networks of passively mobile finite-state sensors
• Efficient reconfiguration of lattice-based modular robots
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• The program-size complexity of self-assembled squares (extended abstract)
• Keeping Mobile Robot Swarms Connected
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• On the Transformation Capability of Feasible Mechanisms for Programmable Matter
• Distributed reconfiguration of metamorphic robot chains
• Pushing squares around
• Brief Announcement
• Timing in chemical reaction networks
• Simple and efficient local codes for distributed stable network construction