Pushing lines helps: efficient universal centralised transformations for programmable matter

DOI10.1016/j.tcs.2020.04.026zbMath1443.68066arXiv1904.12777OpenAlexW2990073343MaRDI QIDQ2182711

Othon Michail, Abdullah Almethen, Igor Potapov

Publication date: 26 May 2020

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

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

zbMATH Keywords

complexitytransformationdistributed algorithmsprogrammable mattershape formationreconfigurable robotics

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Distributed algorithms (68W15) Other nonclassical models of computation (68Q09)

Related Items (10)

Distributed computation and reconfiguration in actively dynamic networks ⋮ Pushing lines helps: efficient universal centralised transformations for programmable matter ⋮ On geometric shape construction via growth operations ⋮ Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes ⋮ On geometric shape construction via growth operations ⋮ 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

Uses Software

• AmoebotSim

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizing geometric patterns formable by oblivious anonymous mobile robots
• On the transformation capability of feasible mechanisms for programmable matter
• The computational power of population protocols
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• 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
• 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
• Distributed Computing by Mobile Robots: Gathering
• The program-size complexity of self-assembled squares (extended abstract)
• Fault-Tolerant and Self-stabilizing Mobile Robots Gathering
• Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves
• Keeping Mobile Robot Swarms Connected
• Distributed reconfiguration of metamorphic robot chains
• Pushing squares around
• Brief Announcement
• Simple and efficient local codes for distributed stable network construction

This page was built for publication: Pushing lines helps: efficient universal centralised transformations for programmable matter