Self-Repairing Line of Metamorphic Robots

Abstract

A Metamorphic Robots System is a modular self-reconfigurable robotic system composed of autonomous mobile modules in a 2D (or 3D) regular grid. The modules have limited computational capabilities, interact only with neighboring modules, and can move around adjacent modules from a cell to an empty neighboring cell under specific conditions. An important well-studied problem for these robotic systems is Motion Planning, also known as Shape Formationor Self-reconfiguration, requiring the modules to organize themselves into a pre-determined final configuration (i.e., shape); basic shapes such as the line (or chain) are especially important as they are utilized as a foundation for constructing more complicated shapes and are an initial measure for handling complicated tasks. A metamorphic robots system could offer a higher degree of reliability and robustness compared to fixed-architecture robots due to its capacity to self-repair: should some modules fail and no longer move, the shape could be reconstructed by the non-faulty modules. To do this correctly, efficiently, and without restricting the autonomy of the modules is a non-trivial task. In this paper, we study the Line Recoveryproblem, requiring the non-faulty modules to reconstruct the line without violation of connectivity requirements at any time during the recovery procedure. A thorough feasibility characterization of the problem, the necessary conditions for its solvability, and an algorithm that solves the problem, regardless of the number and distribution of faults, are provided.