Abstract
Lydia Tapia, "Intelligent Motion Planning and Analysis with Probabilistic Roadmap Methods for the Study of Complex and High-Dimensional Motions," Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Dec 2009.
Ph.D. Thesis(pdf, abstract)
At first glance, robots and proteins have little in common. Robots
are commonly thought of as tools that perform tasks such as vacuuming
the floor, while proteins play essential roles in many biochemical
processes. However, the functionality of both robots and proteins is
highly dependent on their motions. In order to study motions in these
two divergent domains, the same underlying algorithmic framework can
be applied. This method is derived from probabilistic roadmap
methods (PRMs) originally developed for robotic motion planning. It
builds a graph, or roadmap, where configurations are represented as
vertices and transitions between configurations are edges. The
contribution of this work is a set of intelligent methods applied to
PRMs. These methods facilitate both the modeling and analysis of
motions, and have enabled the study of complex and high-dimensional
problems in both robotic and molecular domains.
In order to efficiently study biologically relevant molecular
folding behaviors we have developed new techniques based on
Monte Carlo solution, master equation calculation,
and non-linear dimensionality reduction to run simulations and
analysis on the roadmap. The first method, Map-based master
equation calculation (MME), extracts global properties of the folding
landscape such as global folding rates. On the other hand, another
method, Map-based Monte Carlo solution (MMC), can be used to extract
microscopic features of the folding process. Also, the application of
dimensionality reduction returns a lower-dimensional representation
that still retains the principal features while facilitating both
modeling and analysis of motion landscapes. A key contribution of our
methods is the flexibility to study larger and more complex structures,
e.g., 372 residue Alpha-1 antitrypsin and 200 nucleotide ColE1 RNAII.
We also applied intelligent roadmap-based techniques to the
area of robotic motion. These methods take advantage of
unsupervised learning methods at all stages of the planning process and
produces solutions in complex spaces with little cost and less
manual intervention compared to other adaptive methods. Our results
show that our methods have low overhead and that they
out-perform two existing adaptive methods in all complex cases studied.