Evaluating efficiency of self-reconfiguration in a class of modular robots

In this article we examine the problem of dynamic self-reconfiguration of a class of modular robotic systems referred to as metamorphic systems. 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. Metamorphic systems can therefore be viewed as a large swarm of physically connected robotic modules that collectively act as a single entity. What distinguishes metamorphic systems from other reconfigurable robots is that they possess all of the following properties: (1) a large number of homogeneous modules; (2) a geometry such that modules fit within a regular lattice; (3) self-reconfigurability without outside help; (4) physical constraints which ensure contact between modules. In this article, the kinematic constraints governing metamorphic robot self-reconfiguration are addressed, and 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 it appears that solving for the precise number of minimal moves cannot be done in polynomial time. It is then shown how the bounds developed here are useful in evaluating the performance of heuristic motion planning/reconfiguration algorithms for metamorphic systems. © 1996 John Wiley & Sons, Inc.