A Modular Underwater Robot Self-Reconfiguration Planning Method Based on Graph Isomorphism

This article focuses on the problem of configuration generation in underwater modular robot systems. In this problem, a set of modules with different initial configurations need to self-reconstruct to form a specific target configuration in order to achieve the corresponding task objectives. This paper proposes a hybrid task allocation algorithm that combines graph isomorphism and game theory to address the problems of connection breakage and reconnection loss during self-reconstruction, as well as the challenges of center of gravity change and power source misalignment caused by topological structure changes. This algorithm approximates the search of isomorphic subgraphs to reduce the time and energy required for configuration generation, while maintaining the original topological connections of the robot as much as possible. On this basis, distributed motion planning is performed on the decomposed submodules, and their final allocation positions are determined while considering interference constraints between modules. The simulation experiment demonstrated the complete allocation process, and the results verified the feasibility and effectiveness of the proposed algorithm.