Paper by Erik D. Demaine
- Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Jarrett Lonsford, and Rose Morris-Wright, “Particle computation: complexity, algorithms, and logic”, Natural Computing, volume 18, number 1, December 2019, pages 181–201.
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). Upon activation of
the field, each particle moves maximally in the same direction until forward
progress is blocked by a stationary obstacle or another stationary particle.
In an open workspace, this system model is of limited use because it has only
two controllable degrees of freedom—all particles receive the same inputs and
move uniformly. We show that adding a maze of obstacles to the environment can
make the system drastically more complex but also more useful. 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 2 × 1 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
- This paper is also available from SpringerLink.
- The paper is 27 pages.
- The paper is available in PDF (4650k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Tilt_SoCG2015v (Tilt: The Video – Designing Worlds to Control Robot Swarms with Only Global Signals)
- Tilt_ICRA2015 (Particle computation: Device fan-out and binary memory)
- Tilt_ICRA2014 (Particle Computation: Designing Worlds to Control Robot Swarms with Only Global Signals)
- Tilt_ALGOSENSORS2013 (Reconfiguring Massive Particle Swarms with Limited, Global Control)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2021 by