Solving motion planning problems by iterative relaxation of constraints

摘要

This dissertation presents a new approach to improve automated motion planners. Automatic motion planning has application in many areas such as robotics, virtual reality systems, and computer-aided design. Surprisingly, a single class of planners, called probabilistic roadmap methods (PRMs), have proven effective on problems from all these domains. Strengths of PRMs are simplicity and efficiency, even in high-dimensional configuration spaces. Nevertheless, PRMs are not as effective in environments where the solution path requires the robot to pass through a narrow passage. In this dissertation, we suggest a hierarchical strategy addressing this problem where we first simplify the problem by relaxing some feasibility constraints, solve the easier version of the problem, and then use that solution to help find a solution for the harder problem. We show how this strategy can be applied to (i) “virtual prototype” analysis, where the goal is to find a removal path for one part (the robot) from an assembly of other parts (obstacles), (ii) “ligand binding,” where we generate candidate binding sites for a ligand in a large protein molecule, and (iii) “deformable objects,” where the robot can deform itself to avoid collision while following a path.