Linear-Time Reconfiguration of Sliding-Only Cubic Modular Robots Under Severe Space Requirements

Abstract

This article presents a fast reconfiguration algorithm for cubic modular robots moving in narrow spaces. We assume that the cubic module can only slide across other modules’ surfaces, which saves space compared with previously studied cubic modules, such as those with rotating primitives. The algorithm can take arbitrary start and goal configurations and arrangements thereof and operates in a time that is linear to the number of modules. The algorithm is designed for cases with multiple overlapping regions between the start and goal configurations as well as cases with only one overlapping region. It assumes the use of a 2 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \times $</tex-math></inline-formula> 2 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \times $</tex-math></inline-formula> 2 meta-module robot structure for connectivity and mobility. It consists of two stages. In the first stage, a compact scaffolding structure is formed that does not extend outside the space of the start and goal configurations. In the second stage, the modules reconfigure themselves by moving along the scaffolding structure. We proved the completeness of the algorithm, and performed simulations showing that the algorithm can reconfigure a 2 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \times $</tex-math></inline-formula> 2 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \times $</tex-math></inline-formula> 2 meta-module robot structure with sliding-only cubic modules within a time that grows linearly with the number of modules.