You are here

Reconfiguring Massive Particle Swarms with Limited, Global Control

code: http://www.mathworks.com/matlabcentral/fileexchange/42892
video: http://www.youtube.com/watch?v=eExZO0HrWRQ

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.

Author: 
Aaron Becker and Erik Demaine and S. Fekete and Golnaz Habibi and James McLurkin
Publication: 
(Accepted) International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)
Year: 
2013
Paper: