Useful metrics for modular robot motion planning

In this paper the problem of dynamic self-reconfiguration of a class of modular robotic systems referred to as metamorphic systems is examined. A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. We examine the near-optimal reconfiguration of a metamorphic robot from an arbitrary initial configuration to a desired final configuration. Concepts of distance between metamorphic robot configurations are defined, and shown to satisfy the formal properties of a metric. These metrics, called configuration metrics, are then applied to the automatic self-reconfiguration of metamorphic systems in the case when one module is allowed to move at a time. There is no simple method for computing the optimal sequence of moves required to reconfigure. As a result, heuristics which can give a near optimal solution must be used. We use the technique of simulated annealing to drive the reconfiguration process with configuration metrics as cost functions. The relative performance of simulated annealing with different cost functions is compared and the usefulness of the metrics developed in this paper is demonstrated.