Automatic motion planning is a fundamental problem for which no general, practical solution has been found. Applications for motion planning include not only robotics, but problem domains such as intelligent CAD (virtual prototyping), virtual and augmented reality systems (training and computer-assisted operation), and computational biology and chemistry (protein folding and drug design).
Recently, a class of randomized planners called probabilistic roadmap methods (PRMs) has gained much attention. Briefly, during preprocessing randomly generated configurations of the moving object are connected to form a graph, or roadmap, that encodes representative feasible paths for the moving object. During query processing, the start and goal are connected to the roadmap and a path between them is extracted from the roadmap. While PRMs have solved many difficult, previously unsolved problems, they have not been very effective when the solution path must pass through narrow passages. In this talk, we describe several PRM variants developed in our group to address this issue: OBPRM (obstacle-based PRM) which generates roadmap nodes near obstacle surfaces, MAPRM (medial-axis PRM) which samples points on the medial axis of the free space, and a PRM which can be used for systems with closed kinematic chains. Since human insight can sometimes greatly decrease the solution time, we describe randomized techniques, inspired by PRMs, for transforming approximate, user-generated paths collected with a PHANToM haptic device into collision-free paths. Finally, we will discuss recent work on the localization problem for mobile robots. We show results for difficult problems arising in complex 3D environments arising in applications such as part removal studies for complex mechanical products and protein folding.