Particle Computation: Design worlds for Boolean gates and matrix permutations
Companion to ICRA 2014 paper: "Particle Computation: Designing Worlds to Control Robot Swarms with only Global Signals"
by Aaron Becker, Erik D. Demaine, Sándor P. Fekete, James McLurkin
Paper 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.
Matlab code implementation:
http://www.mathworks.com/matlabcentra...
http://mrsl.rice.edu/
www.icra2014.com