Scalable parallel algorithm for configuration planning for self-reconfiguring robots

In this paper we present algorithms for planning the motion of robotic Molecules on a substrate of other Molecules. Our approach is to divide self-reconfiguration planning into three levels: trajectory planning, configuration planning, and task-level planning. This paper focuses on algorithms for configuration planning, moving a set of Molecules from a starting configuration to a goal configuration. We describe our scaffold planning approach in which the interior of a structure contains three-dimensional tunnels. This allows Molecules to move within a structure as well as on the surface, simplifying Molecule motion planning as well as increasing parallelism. In addition, we present a new gripper-type connection mechanism for the Molecule which does not require power to maintain connections.