In this paper we propose novel algorithms for reconfiguring modular robots
that are composed of n atoms. Each atom has the shape of a unit cube
and can expand/contract each face by half a unit, as well as attach to or
detach from faces of neighboring atoms. For universal reconfiguration, atoms
must be arranged in 2 × 2 × 2 modules. We
respect certain physical constraints: each atom reaches at most unit velocity
and (via expansion) can displace at most one other atom. We require that one
of the atoms can store a map of the target configuration.
Our algorithms involve a total of O(n2) such atom
operations, which are performed in O(n) parallel steps. This
improves on previous reconfiguration algorithms, which either use
O(n2) parallel steps [7, 9, 4] or do not
respect the constraints mentioned above [1]. In fact, in the setting
considered, our algorithms are optimal, in the sense that certain
reconfigurations require Ω(n) parallel steps. A further advantage
of our algorithms is that reconfiguration can take place within the union of
the source and target configurations.