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.