On the transformation capability of feasible mechanisms for programmable matter
From MaRDI portal
Publication:1741488
Abstract: In this work, we study theoretical models of emph{programmable matter} systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): emph{rotate} around a neighbor and emph{slide} over a line. In terms of modeling, there are nodes arranged in a 2-dimensional grid and forming some initial emph{shape}. The goal is for the initial shape to emph{transform} to some target shape by a sequence of movements. Most of the paper focuses on emph{transformability} questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes and can be transformed to each other, is in . We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in and study the problem of determining the minimum emph{seeds} that can make feasible, otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes of the same order, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is . We improve this to parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. In the last part of the paper, we turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformations.
Recommendations
- On the transformation capability of feasible mechanisms for programmable matter
- Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
- Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- CADbots: algorithmic aspects of manipulating programmable matter with finite automata
Cites work
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Brief announcement: Pattern formation problem for synchronous mobile robots in the three dimensional Euclidean space
- Computation in networks of passively mobile finite-state sensors
- Computation with finite stochastic chemical reaction networks
- Controlled module density helps reconfiguration planning
- Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
- Distributed reconfiguration of metamorphic robot chains
- Efficient reconfiguration of lattice-based modular robots
- Forming sequences of geometric patterns with oblivious mobile robots
- scientific article; zbMATH DE number 3588048 (Why is no real title available?)
- scientific article; zbMATH DE number 2038783 (Why is no real title available?)
- scientific article; zbMATH DE number 1834637 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- Keeping Mobile Robot Swarms Connected
- On the transformation capability of feasible mechanisms for programmable matter
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Pushing squares around
- Relationships between nondeterministic and deterministic tape complexities
- The computational power of population protocols
- The program-size complexity of self-assembled squares (extended abstract)
- Timing in chemical reaction networks
Cited in
(29)- 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
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- Building a nest by an automaton
- CADbots: algorithmic aspects of manipulating programmable matter with finite automata
- Universal reconfiguration of facet-connected modular robots by pivots: the \(O(1)\) musketeers
- Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
- On the transformation capability of feasible mechanisms for programmable matter
- 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
- Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach
- Fault tolerant network constructors
- Turning machines
- 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
- Pushing lines helps: efficient universal centralised transformations for programmable matter
- Fault tolerant network constructors
- The complexity of growing a graph
- Reconfiguration algorithms for cubic modular robots with realistic movement constraints
- All for one and one for all: an O(1)-musketeers generic transformation for rotating robots
- On the exponential growth of geometric shapes
- Transformation of modular robots by rotation: 3 + 1 musketeers for all orthogonally convex shapes
- Collision detection for modular robots -- it is easy to cause collisions and hard to avoid them
- Sliding squares in parallel
- Programmable reconfiguration of Physarum machines
This page was built for publication: On the transformation capability of feasible mechanisms for programmable matter
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741488)
