Bounds for self-reconfiguration of metamorphic robots

A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. A change in the macroscopic morphology results from the locomotion of each module over its neighbors. In this paper, lower and upper bounds are established for the minimal number of moves needed to change such systems from any initial to any final specified configuration. These bounds are functions of initial and final configuration geometry and can be computed very quickly, while solving for the precise number of minimal moves cannot be done in polynomial time. These bounds can be used to 'weed out' and improve inefficient reconfiguration strategies, and provide a benchmark for the evaluation of heuristics in general.