Randomized Motion Planning: From Intelligent CAD to Protein Folding

April 27, 2001 - 10:00am to 11:00am
6-212 EE/CS Building
Motion planning arises not only in robotics but in many other areas such as intelligent CAD (virtual prototyping), mixed reality systems (training and computer-assisted operation), and even computational biology and chemistry (protein folding and drug design). Surprisingly, a single class of planners, called probabilistic roadmap methods (PRMs), have 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 the first part of this talk, we introduce the PRM framework and briefly describe several PRM variants developed in our group to address the "narrow passage problem" (when the solution path must pass through confined regions). We present results for difficult problems typical of virtual prototyping, and show that in some cases a hybrid system incorporating both an automatic planner and haptic user input leads to superior results. In the second part, we concentrate on our recent application of PRM-based motion planning techniques to protein folding. Here, we assume the native fold is known, and our goal is to study the folding process. Our results on several small to moderate sized proteins (60-150 amino acids) indicate that the PRM-based technique generates folding pathways that are in agreement with experimental data. Our technique naturally supports the study of folding pathways starting from any desired denatured starting conformation, and also appears to differentiate between proteins where secondary structure forms first and those where the tertiary structure is obtained more directly. If time allows, we will describe initial promising results using PRMs for ligand/protein binding; this work also utilizes haptic user input.