Motion planning arises in many application domains such as computer animation (digital actors), mixed reality systems and intelligent CAD (virtual prototyping and training), and even computational biology and chemistry (protein folding and drug design). Surprisingly, one type of sampling-based planner, the probabilistic roadmap method (PRM), has proven effective on problems from all these domains.
In this talk, we describe the PRM framework and give an overview of some PRM variants developed in our group. We describe in more detail our work related to virtual prototyping, crowd simulation, and protein folding. For virtual prototyping, we show that in some cases a hybrid system incorporating both an automatic planner and haptic user input leads to superior results. For crowd simulation, we describe PRM-based techniques for pursuit evasion, evacuation planning and architectural design. Finally, we describe our application of PRMs to simulate molecular motions, such as protein and RNA folding. More information regarding our work, including movies, can be found at at our lab link.