Tapia, Lydia (2009-12). Intelligent Motion Planning and Analysis with Probabilistic Roadmap Methods for the Study of Complex and High-Dimensional Motions. Doctoral Dissertation. | Thesis individual record

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
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.

etd chair
publication date