Paper by Erik D. Demaine

Reference:

Aaron Becker, Erik D. Demaine, Sándor Fekete, and James McLurkin, “Particle Computation: Designing Worlds to Control Robot Swarms with Only Global Signals”, in Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA 2014), Hong Kong, China, May 31–June 7, 2014, pages 6751–6756.

BibTeX

@InProceedings{Tilt_ICRA2014,
  AUTHOR        = {Aaron Becker and Erik D. Demaine and S\'andor Fekete and James McLurkin},
  TITLE         = {Particle Computation: Designing Worlds to Control Robot Swarms with Only Global Signals},
  BOOKTITLE     = {Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA 2014)},
  bookurl       = {http://www.icra2014.com/},
  ADDRESS       = {Hong Kong, China},
  MONTH         = {May 31--June 7},
  YEAR          = 2014,
  PAGES         = {6751--6756},
  doi           = {https://dx.doi.org/10.1109/ICRA.2014.6907856},
  dblp          = {https://dblp.org/rec/conf/icra/BeckerDFM14},
  comments      = {The paper is available as
                   <A HREF="http://arxiv.org/abs/1402.3749">
                   arXiv.org:1402.3749</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>, and from <A HREF="https://doi.org/10.1109/ICRA.2014.6907856">IEEE</A>.},
}

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.

Comments:

The paper is available as arXiv.org:1402.3749 of the Computing Research Repository (CoRR), and from IEEE.

Availability:

The paper is available in PDF (1710k).

See information on file formats.

[Google Scholar search]