A fluid dynamics approach for self-reconfiguration planning of modular robots

Modular Robotic Systems (MRS) are arrays of interconnected simple robots which can change their morphology in order to perform various tasks. In modular robotics, Self-Reconfiguration Planning (SRP) is the problem of finding a sequence of module-level actions to transform an MRS from an initial configuration into a goal configuration considering modules´ kinematic constraints. SRP is very challenging problem as its solution approaches have to deal with exponential growth of configuration space, preserve connectedness of modular robot structure, and avoid deadlock configurations. SRP is proved to be NP-Complete and thus its solution methods generally suffer from limited scalability. In this paper, we introduce a novel approach for solving SRP inspired from the behavior of incompressible fluids in assuming shape of containers. Our approach formulates a given SRP problem as virtual casting model called Corresponding Casting Model (CCM) in which modules (as fluid cells) flow and fill a virtual mold analogous to the goal configuration. We also propose an SRP planning engine called Incompressible Fluid Flow (IFF) engine which computationally solves the CCM model and generates SRP plans. The proposed approach is independent from configuration space, and does not require explicit connectivity checking of modules. As it is shown and verified by the complexity analysis and simulation results, the proposed IFF engine can solve an SRP problem in O(n) time and thus is highly scalable to SRP problems with many modules.