Paper by Erik D. Demaine

Reference:

Aaron Becker, Erik D. Demaine, Sándor Fekete, Golnax Habibi, and James McLurkin, “Reconfiguring Massive Particle Swarms with Limited, Global Control”, in Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013), Lecture Notes in Computer Science, volume 8243, Sophia Antipolis, France, September 5–6, 2013, pages 51–66.

BibTeX

@InProceedings{Tilt_ALGOSENSORS2013,
  AUTHOR        = {Aaron Becker and Erik D. Demaine and S\'andor Fekete and Golnax Habibi and James McLurkin},
  TITLE         = {Reconfiguring Massive Particle Swarms with Limited, Global Control},
  BOOKTITLE     = {Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013)},
  bookurl       = {http://www.icra2014.com/},
  VOLUME        = 8243,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  ADDRESS       = {Sophia Antipolis, France},
  MONTH         = {September 5--6},
  YEAR          = 2013,
  PAGES         = {51--66},

  doi           = {https://dx.doi.org/10.1007/978-3-642-45346-5_5},
  dblp          = {https://dblp.org/rec/conf/algosensors/BeckerDFHM13},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-45346-5_5">SpringerLink</A>.},
}

Abstract:

In this paper we investigate 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, e.g., provided by gravity or a magnetic field. Upon activation, each robot moves in the same direction, maximally until it hits a stationary obstacle or another stationary robot. In a workspace with only simple exterior boundaries, this system model is of limited use because it has only two controllable degrees of freedom—all robots 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 and more useful.

We prove that it is NP-hard to decide whether a given initial configuration can be transformed into a desired target configuration, if we are given a fixed set of stationary obstacles. On the positive side, we provide constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (3043k).

See information on file formats.

[Google Scholar search]