Particle computation: Designing worlds to control robot swarms with only global signals
Authors:
Open Access
- 1 May 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 6751-6756
Abstract
Micro- and nanorobots are often controlled by global input signals, such as an electromagnetic or gravitational field. These fields move each robot maximally until it hits a stationary obstacle or another stationary robot. This paper investigates 2D motion-planning complexity for large swarms of simple mobile robots (such as bacteria, sensors, or smart building material). In previous work we proved it is NP-hard to decide whether a given initial configuration can be transformed into a desired target configuration; in this paper we prove a stronger result: the problem of finding an optimal control sequence is PSPACE-complete. On the positive side, we show we can build useful systems by designing obstacles. We present a reconfigurable hardware platform and demonstrate how to form arbitrary permutations and build a compact absolute encoder. We then take the same platform and use 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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Particle computation: Designing worlds to control robot swarms with only global signals2014
- Reconfiguring Massive Particle Swarms with Limited, Global Control2013
- Feedback control of many magnetized: Tetrahymena pyriformis cells by exploiting phase inhomogeneity2013
- Control of magnetotactic bacterium in a micro-fabricated maze2013
- Adapting the clinical MRI software environment for real‐time navigation of an endovascular untethered ferromagnetic bead for future endovascular interventionsMagnetic Resonance in Medicine, 2008
- Assembling molecules in ATOMIX is hardTheoretical Computer Science, 2004
- Low-power logic styles: CMOS versus pass-transistor logicIEEE Journal of Solid-State Circuits, 1997
- The complexity of finding minimum-length generator sequencesTheoretical Computer Science, 1985
- Conservative logicInternational Journal of Theoretical Physics, 1982