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.

Authors

• Keith Kotay
• Daniela Rus

Keywords

• Robot kinematics
• Motion planning
• Trajectory
• Shape
• Orbital robotics
• Bonding
• Robotic assembly
• Computer science
• Educational institutions
• Parallel processing
• Path Planning
• Motion Of Molecules
• Single-molecule
• Set Of Molecules
• Interior Structure
• Trajectory Planning
• Prototype
• Running Time
• Shortest Path
• Robotic System
• Individual Molecules
• Linear Time
• Electromagnetic
• Storage Space
• Overlap Area
• Shape Memory
• Connection Point
• Matching Problem
• Need For Planning
• Planning Algorithm
• Number Of Rotations
• Priority Queue
• Global Motion
• Dijkstra’s Algorithm
• Parallel Algorithm