  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.
