Characterizing Universal Reconfigurability of Modular Pivoting Robots
This work provides fundamental insights into the reconfigurability limits and capabilities of modular robots for researchers and engineers designing such systems, particularly highlighting the differences between hexagonal and square modules.
This paper investigates the reconfigurability of modular robots in a hexagonal grid using "pivot" moves. It presents the first universal reconfiguration algorithm for hexagonal modules using both restricted and monkey moves, achieving transformation between any two connected configurations in O(n^3) monkey moves. Conversely, the paper proves that reconfiguration with only restricted moves is PSPACE-complete for hexagons, and PSPACE-complete for squares regardless of the move set.
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using $O(n^3)$ monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.