Self-reconfiguration in modular robots using coalition games with uncertainty

We consider the problem of dynamic self-reconfiguration in a modular self-reconfigurable robot (MSR). Previous MSR self-reconfiguration approaches search for new configurations only within the modules of the MSR that needs reconfiguration. In contrast, we describe a technique where an MSR that needs to reconfigure communicates with other MSRs in its vicinity to determine if modules can be shared from other MSRs, and then determines the best possible configuration among the combined set of modules. We model the MSR self-reconfiguration problem as a coalition structure generation problem within a coalition game theoretic framework. We formulate the coalition structure generation problem as a planning problem in the presence of uncertainty and propose an MDP-based algorithm to solve it. We have implemented our algorithm within an MSR called ModRED that is simulated on the Webots simulation platform. Our results show that using our self-reconfiguration algorithm, when an MSR needs to reconfigure, a new configuration that is within 5-7% of the globally optimal configuration can be determined. We have also shown that our algorithm performs comparably with another existing algorithm for determining optimal coalition structure.