Self-reconfiguration planning for modular robots

摘要

The key feature of modular self-reconfigurable robots is their ability to deliberately change shape by rearranging the connectivity of their modules, so as to adapt to dynamic environments, perform new tasks and recover from damages. This thesis addresses the challenge of reconfiguration planning between two arbitrary configurations, and advances the state-of-the-art in self-reconfiguration planning for modular robots through several key innovations. Our results are measured by: completeness of solution guarantee, compatibility to the hardware implementation, time-efficiency in quickly finding a solution, cost-efficiency in avoiding redundant reconfiguration steps, and scalability to the size of robot. First, we developed a reconfiguration planning algorithm called MorphLine, by which the robot can autonomously and rapidly self-reconfigure from one arbitrary configuration to another in a distributed way. To our knowledge, it is the first reconfiguration planning algorithm that features on (1) It can guarantee finding a reconfiguration sequence between two arbitrary configurations if exists; (2) Reconfiguration steps are compatible with kinematic constrains and implementable on the robot; (3) It has low time complexity and is scalable to the robot with large size; (4) It allows parallel reconfiguration to speed up the reconfiguration execution. To minimize the reconfiguration cost, we presented the first analysis on the computational complexity of optimal reconfiguration planning problem, i.e. finding the least number of reconfiguration steps to transform from one arbitrary configuration to another. We proved that this problem is NP-complete, even for the simpler case where the configurations are acyclic. This result gives a compelling reason that a polynomial algorithm for optimal reconfiguration plan is unlikely to exist. To facilitate future evaluation of reconfiguration algorithms, we also provided the lower and the upper bounds of the minimum number of reconfiguration steps. To find the optimal reconfiguration plan in theory, we rephrased the optimal reconfiguration problem into configuration matching problem, and proposed two different configuration matching methods for different needs. The first one is called MDCOP, which has a theoretical guarantee to find the optimal graph-based reconfiguration plan. The other one is call GreedyCM, whose solution is extremely close to the shortest graph-based reconfiguration sequence, and can run in polynomial time. Last, configuration matching methods are combined with MorphLine planner, which achieves a more efficient hardware-compatible reconfiguration plan with reduced reconfiguration cost. Our algorithms are implemented on the modular robot called SuperBot. Symmetry features of SuperBot are studied and symmetrically isomorphic configurations are detected to be equivalent. Many reconfiguration examples are shown to demonstrate the strength of our algorithms.