Linear Heterogeneous Reconfiguration of Cubic Modular Robots via Simultaneous Tunneling and Permutation

Reconfiguring heterogeneous modular robots in which all modules are not identical is much more time consuming than reconfiguring homogeneous ones, because ordinary heterogeneous reconfiguration is a combination of homogeneous transformation and heterogeneous permutation. While linear homogeneous transformation has been accomplished in previous research, linear heterogeneous permutation has not. This paper studies a reconfiguration algorithm for heterogeneous lattice modular robots with linear operation time cost. The algorithm is based on simultaneous tunneling and permutation, where a robot transforms its configuration via tunneling motion while permutation of each module's position is performed simultaneously during the tunneling transformation. To achieve this, we introduce the idea of a transparent meta-module that allows modules belonging to a meta-module to pass through the spaces occupied by other meta-modules. We prove the correctness and completeness of the proposed algorithm for a 2×2×2 cubic meta-module-based connected robot structure. We also show examples of the reconfiguration simulations of heterogeneous modular robots by the proposed algorithm.