Distributed universal reconfiguration of 2D lattice-based modular robots

Abstract

We prove universal reconfiguration (i.e., reconfigura-tion between any two robotic systems with the same number of modules) of 2-dimensional lattice-based modular robots by means of a distributed algorithm. To the best of our knowledge, this is the first known reconfiguration algorithm that applies in a general set-ting to a wide variety of particular modular robotic systems, and holds for both square and hexagonal lattice-based 2-dimensional systems. All modules ap-ply the same set of local rules (in a manner similar to cellular automata), and move relative to each other. Reconfiguration is carried out while keeping the robot connected at all times. The total number of time steps, moves and communication required for the re-configuration is linear in the number of modules.