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.