Particle computation: complexity, algorithms, and logic

DOI10.1007/S11047-017-9666-6MaRDI QIDQ6150976zbMATH OpenOpenAlexFDO

Authors Aaron Becker, Erik D. Demaine, Sándor P. Fekete, Jarrett Lonsford, Rose Morris-Wright

Publication date 9 February 2024

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.01197, https://hdl.handle.net/1721.1/131277.2

zbMATH Keywords

array permutationscomplexityefficient algorithmslogic gatesnano-particlesNP-completenessparallel motion planningprogrammable matterPSPACE-completenessrobot swarmsuniform inputsuniversal computation

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Other nonclassical models of computation (68Q09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). We show that a maze of obstacles to the environment can be used to create complex systems. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates and, nand, nor, and or operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a fan-out gate cannot be generated. We resolve this missing component with the help of 2x1 particles, which can create fan-out gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.

Recommendations

• Reconfiguring massive particle swarms with limited, global control
• Tilt: the video -- designing worlds to control robot swarms with only global signals
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Shape formation by programmable particles
• Shape formation by programmable particles

Cites work

• 2048 without new tiles is still hard
• Algorithmic Aspects of Wireless Sensor Networks
• Assembling molecules in ATOMIX is hard
• Conservative logic
• Deterministic boundary recognition and topology extraction for large sensor networks
• scientific article; zbMATH DE number 5506240 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 2085303 (Why is no real title available?)
• scientific article; zbMATH DE number 1568804 (Why is no real title available?)
• Intrinsic universality in tile self-assembly requires cooperation
• Limitations of Self-assembly at Temperature One
• Manipulation of pose distributions
• Motion planning in the presence of movable obstacles
• Orienting polygonal parts without sensors
• Parts feeding on a conveyor with a one joint robot
• Playing games with algorithms: algorithmic combinatorial game theory
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguring massive particle swarms with limited, global control
• SOKOBAN and other motion planning problems
• The complexity of finding minimum-length generator sequences
• Tilt: the video -- designing worlds to control robot swarms with only global signals
• Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly
• Winning ways for your mathematical plays. Vol. 1.

Cited in

(6)

• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Coordinating Swarms of Objects at Extreme Dimensions
• Particle-based assembly using precise global control
• Fast reconfiguration of robot swarms with uniform control signals
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• Drainability and fillability of polyominoes in diverse models of global control

This page was built for publication: Particle computation: complexity, algorithms, and logic

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