Modular robot motion planning using similarity metrics

In order for a modular self-reconfigurable robotic system to autonomously change from its current state to a desired one, it is critical to have a cost function (or metric) that reflects the effort required to reconfigure. A reconfiguration sequence can consist of single module motions, or the motion of a "branch" of modules. For single module motions, the minimization of metrics on the set of sets of module center locations serves as the driving force for reconfiguration. For branch motions, the question becomes which branches should be moved so as to minimize overall effort. Another way to view this is as a pattern matching problem in which the desired configuration is viewed as a void, and we seek branch motions that best fill the void. A precise definition of goodness of fit is therefore required. In this paper, we address the fundamental question of how closely geometric figures can be made to match under a given group of transformations (e.g., rigid-body motions), and what it means to bisect two shapes. We illustrate these ideas in the context of applications in modular robot motion planning.