Algorithms for self-reconfiguring molecule motion planning

In this paper we present algorithms for planning the motion of robotic "molecules" (modules) 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 trajectory planning, moving a single molecule from a start location to a goal location, and configuration planning, moving a set of molecules from a starting configuration to a goal configuration. We also present 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