Sampling-Based Motion Planning: From Intelligent CAD to Crowd Simulation to Protein Folding
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. Strengths of PRMs, in addition to versatility, are simplicity and efficiency, even in high-dimensional configuration spaces. 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 http://parasol.tamu.edu/~amato/
Nancy M. Amato is Unocal Professor in the Department of Computer Science and Engineering at Texas A&M University where she co-directs the Parasol Lab and is a Deputy Director of the Institute for Applied Math and Computational Science (IAMCS). She received undergraduate degrees in Mathematical Sciences and Economics from Stanford University, and M.S. and Ph.D. degrees in Computer Science from UC Berkeley and the University of Illinois at Urbana-Champaign. She was an AT&T Bell Laboratories PhD Scholar, she is a recipient of a CAREER Award from the National Science Foundation, is a Distinguished Speaker for the ACM Distinguished Speakers Program, was a Distinguished Lecturer for the IEEE Robotics and Automation Society, and is an IEEE Fellow. She was co-Chair of the NCWIT Academic Alliance (2009-2011), is a member of the Computing Research Association's Committee on the Status of Women in Computing Research (CRA-W) and of the ACM, IEEE, and CRA sponsored Coalition to Diversity Computing (CDC). Her main areas of research focus are motion planning and robotics, computational biology and geometry, and parallel and distributed computing. Current representative projects include the development of a technique for modeling molecular motions (e.g., protein folding), investigation of new strategies for crowd control and simulation, and STAPL, a parallel C++ library enabling the development of efficient, portable parallel programs.