        |
 |
|
|||
|
|
 |
|
Howdy! I am a Computer Science graduate student at Texas A&M University. I work in the Parasol Lab with Dr. Nancy Amato. Our group develops randomized motion planning algorithms than can be applied to many different areas such as: mobile robots, virtual prototyping, computational biology and computational neuroscience. My research focus is on motion planning algorithms and their application to computational biology.
| CV (ps, pdf) | Course Work |
 |
Protein Folding and Motions
In this research, we study protein folding pathways and protein motions. It is critical that we better understand protein motion and the folding process for several reasons. First, understanding the folding process can give insight into how to develop better structure prediction algorithms, a major thrust of ongoing research. Second, some diseases such as Alzheimer's and Mad Cow disease are caused by misfolded proteins. By studying how these proteins misfold, scientists can develop better treatments. Third, many biochemical processes are regulated by proteins switching from one structure to another. We propose a technique for computing protein folding pathways and motions based on the successful probablistic roadmap (PRM) method for robotics motion planning. Our technique can compute thousands of pathways in just a few hours on a single desktop PC. We validated our approach against known experimental results for several small proteins. In addition, our approach is able to detect the subtle folding differences between structurally similar proteins G, L, and mutated forms of G and L. We are also able to use our technique to simulate exchange rates and identify the protein folding core. Publications |
 |
RNA Folding
We propose a novel motion planning based approach to approximately map the energy landscape of an RNA molecule. Our method is based on the probabilistic roadmap (PRM) motion planners we have successfully applied to study protein folding. The key advantage of our method is that it provides a sparse map that captures the main features of the landscape. We can use our roadmap to compute RNA population kinetics and transition rates. We validated our techinque by comparing population kinetics of the complete landscape to that of our roadmap for several small RNA. We also studied energy barriers along pathways between the correct RNA structure and the misfolded structure. Publications |
 |
Parallel Protein Folding
Our protein folding technique, although significantly more efficient than previous methods, still requires large amounts of computational resources. For example, a protein that takes several hours on a desktop PC using a coarse energy calculation will require two weeks with a more detailed one. In addition, running time increases quadradically with protein length. It is imperative that we find a faster technique. Here, we use the Standard Template Adaptive Parallel Library (STAPL) to parallelize our existing protein folding code. STAPL allows for easy transition from sequential code to parallel code by extending the ANSI C++ Standard Template Library, and it provides portable efficiency to different systems, both shared memory and distributed memory models, without requiring user code modification. We obtained good speedups on multiple platforms, ranging from small linux clusters, to distributed shared memory machines, to massively parallel machines. Publications |
 |
Protein-Protein Interactions (Undergraduate)
In 2001, I spent the summer working with Dr. Kavraki at Rice University as part of the CRAW Distributed Mentor Program. I investigated how to model interactions between large molecules like proteins, DNA, and RNA. I first studied how to compute Cartesian coordinates for every atom in a molecule given a set of torsional angles. I then did a literature survey to discover interaction examples and their biological function. After selecting a few target interactions, I began developing a probabilistic roadmap (PRM) method to model the interaction. |
 |
Unsupervised Adaptive Motion Planning
Since planning environments are complex and no single planner exists that is best for all problems, much work has been done to explore methods for selecting where and when to apply particular planners. However, these two questions have been difficult to answer, even when adaptive methods meant to facilitate a solution are applied. For example, adaptive solutions such as setting learning rates, hand-classifying spaces, and defining parameters for a library of planners have all been proposed. We demonstrate a strategy based on unsupervised learning methods that makes adaptive planning more practical. The unsupervised strategies require less user intervention, model the topology of the problem in a reasonable and efficient manner, can adapt the sampler depending on characteristics of the problem, and can easily accept new samplers as they become available. Through a series of experiments, we demonstrate that in a wide variety of environments, the regions automatically identified by our technique represent the planning space well both in number and placement. We also show that our technique has little overhead and that it out-performs two existing adaptive methods in all complex cases studied. Publications |
 |
Biasing / Composing PRM Samplers
Much work has been done to design new sampling techniques and distributions. To date, there is no sampling technique that out-performs all other sampling techniques in all motion planning problems. Instead, each sampling technique proposed has different strengths and weaknesses. We propose to bias one sampling distribution with another such that the resulting distribution out-performs either of its parent distributions. We provide a general framework for biasing samplers that is easily extendable to new distributions and can handle an arbitrary number of parent distributions by chaining them together. Our experimental results show that by combining distributions, we can out-perform existing planners. Our results also indicate that not one single combination of distributions performs the best in all problems, and we identify which combinations perform better for the specific application domains studied. Publications |
 |
Closed Chains
Motion planning for closed-chain systems is particularly difficult due to additional constraints, so-called closure constraints, placed on the system. In fact, the probability of randomly selecting a set of joint angles that satisfy the closure constraints is zero. We overcome this challenge by considering a representation of the chain as a hierarchy of sub-chains, each with its own reachable distance range, and instead of randomly sampling in the joint angle space, we recursively sample in the reachable distance space. This provides two distinct advantages over traditional approaches: (1) joint angles are quickly and easily calculated using basic trigonometry relationships instead of using more expensive inverse kinematics solvers, and (2) configurations are guaranteed to satisfy the closure constraints. We provided the necessary motion planning primitives to implement most sampling-based motion planners. Our method is fast and efficient in practice and easy to implement. Publications |
 |
RESAMPL: A Region-Sensitive Adaptive Motion Planner
In this work, we present RESAMPL, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. RESAMPL classifies regions based on the entropy of the samples in it, and then uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing RESAMPL to previous multi-query and single-query methods show that RESAMPL is generally significantly faster and also usually requires fewer samples to solve the problem. Publications |
 |
Incremental Map Generation
Probabilistic roadmap methods (PRMs) have been highly successful in solving many high degree of freedom problems. One important practical issue with PRMs is they do not provide an automated mechanism to determine what size roadmap to construct. In this work, we propose a new PRM-based framework called Incremental Map Generation (IMG) to address this problem. Our strategy is to break the map generation into several independent processes, each of which generates samples and connections independently. IMG proceeds by adding these collections of samples and connections to an existing roadmap until it satisfies some specified evaluation criteria. We propose some general evaluation criteria and show how they can be used to construct diferent types of roadmaps, e.g., roadmaps that coarsely or more finely map the space. In addition to addressing the roadmap size question, the fact that each roadmap increment is independently and deterministically seeded has several other benefits such as supporting roadmap reproducibility, the adaptive selection of sampling methods in different roadmap increments, and parallelization. We provide results illustrating the power of IMG. Publications |
 |
Medial Axis PRM
We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. In particular, our framework supports methods that can retract a given configuration exactly or approximately onto the medial axis. This helps address the narrow passage problem in that we increase the probability of sampling in a narrow passage over uniform random sampling. We show that the probability of sampling in a narrow passage depends not only on the volume of the passage, but also on the volume of the obstacles surrounding it. Publications |
 |
Customizable PRM
We propose a new approach for building and querying probabilistic roadmaps (PRMs). During roadmap construction, we build a coarse roadmap by performing only approximate node and/or edge validation. In the query stage, the roadmap is validated and refined only where necessary to solve the query. In addition, it is customized according to any specified query preferences at query time. Thus, the same roadmap can be used to solve multiple, variable query preferences. This approach yields more efficient solutions to many problems including protein folding, ligand binding, assembly planning, and nonholonomic planning for car-like robots. Publications |
 |
Using Spheres to Improve Motion Planning (Undergraduate)
In this work, we use configuration space spheres to aid in connecting and growing probabilistic roadmaps (PRMs). For each node, we define a sphere centered at that node with a radius equal to the node's clearance in configuration space. Because configuration space obstacles are never explicitly computed, we approximate this radius. We first use these spheres to identify likely collision-free edges between nodes. If two spheres overlap, then the straightline edge between the two corresponding nodes is likely to be collision-free. We also use these spheres to expand the roadmap. New nodes are sampled such that their spheres intersect spheres of existing nodes, thus exploring the space while keeping the number of connected components low. |
Publications
|
|
A Motion Planning Approach to Studying Molecular Motions, Lydia Tapia, Shawna Thomas, Nancy M. Amato, Technical Report, TR08-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2008.
Technical Report(abstract)
Protein Folding Core Identification from Rigidity Analysis and Motion Planning, Shawna Thomas, Lydia Tapia, Nancy M. Amato, Technical Report, TR08-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2008.
Technical Report(ps, pdf, abstract)
Using Dimensionality Reduction to Better Capture RNA and Protein Folding Motions, Lydia Tapia, Shawna Thomas, Nancy M. Amato, Technical Report, TR08-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Oct 2008.
Technical Report(ps, pdf, abstract)
Kinetics Analysis Methods For Approximate Folding Landscapes, Lydia Tapia, Xinyu Tang, Shawna Thomas, Nancy M. Amato, In Int. Conf. on Int. Sys. for Mol. Bio. (ISMB)/European Conf. on Comp. Bio.(ECCB), Vienna, Austria, Jul 2007. Also, Bioinformatics, 23(13):i539-i548, Jul 2007. Also, Technical Report, TR07-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Feb 2007.
Journal(pdf, abstract) Technical Report(ps, pdf, abstract)
Simulating Protein Motions with Rigidity Analysis, Shawna Thomas, Xinyu Tang, Lydia Tapia, Nancy M. Amato, Journal of Computational Biology, 14(6):839-855, Jul 2007. Also, In Proc. Int. Conf. Comput.
Molecular Biology (RECOMB), pp. 394-409, Apr 2006. Also, Technical Report, TR05-008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Journal(ps, pdf, abstract) Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
Roadmap-Based Methods for Studying Protein Folding Kinetics, Lydia Tapia, Xinyu Tang, Shawna Thomas, Nancy M. Amato, Technical Report, TR06-011, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2006.
Technical Report(ps, pdf, abstract)
Parallel Protein Folding with STAPL, Shawna Thomas, Gabriel Tanase, Lucia K. Dale, Jose M. Moreira, Lawrence Rauchwerger, Nancy M. Amato, Concurrency and Computation: Practice and Experience, 17(14):1643-1656, Dec 2005.
Journal(ps, pdf, abstract)
Protein Folding by Motion Planning, Shawna Thomas, Guang Song, Nancy M. Amato, Physical Biology, 2:S148-S155, Nov 2005.
Journal(ps, pdf, abstract)
Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Wkshp. on High Performance Computational Biology, Santa Fe, NM, Apr 2004.
Proceedings(ps, pdf, abstract)
A Path Planning-based Study of Protein Folding With a Case Study of Hairpin Formation in Protein G and L, Guang Song, Shawna Thomas, Ken A. Dill, J. Martin Scholtz, Nancy M. Amato, In Proc. Pac. Symp. of
Biocomputing (PSB), pp. 240-251, Lihue, HI, Jan 2003.
Proceedings(ps, pdf, abstract)
|
|
A Motion Planning Approach to Studying Molecular Motions, Lydia Tapia, Shawna Thomas, Nancy M. Amato, Technical Report, TR08-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2008.
Technical Report(abstract)
Simulating RNA Folding Kinetics on Approximated Energy Landscapes, Xinyu Tang, Shawna Thomas, Lydia Tapia, David P. Giedroc, Nancy M. Amato, Journal of Molecular Biology, 3811(4):1055-1067, Sep 2008. Also, Technical Report, TR07-008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2007.
Journal(pdf, abstract) Technical Report(ps, pdf, abstract)
Tools for Simulating and Analyzing RNA Folding Kinetics, Xinyu Tang, Shawna Thomas, Lydia Tapia, Nancy M. Amato, Technical Report, TR07-007, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2007. Also, In Proc. Int. Conf. Comput.
Molecular Biology (RECOMB), pp. 268-282, San Francisco, CA, Apr 2007.
Technical Report(ps, pdf, abstract) Proceedings(ps, pdf, abstract)
Using Motion Planning to Study RNA Folding Kinetics, Xinyu Tang, Bonnie Kirkpatrick, Shawna Thomas, Guang Song, Nancy M. Amato, Journal of Computational Biology, 12(6):862-881, Jul 2005. Also, In Proc. Int. Conf. Comput.
Molecular Biology (RECOMB), pp. 252-261, San Diego, CA, Mar 2004.
Journal(ps, pdf, abstract) Proceedings(ps, pdf, abstract)
|
|
Parallel Protein Folding with STAPL, Shawna Thomas, Gabriel Tanase, Lucia K. Dale, Jose M. Moreira, Lawrence Rauchwerger, Nancy M. Amato, Concurrency and Computation: Practice and Experience, 17(14):1643-1656, Dec 2005.
Journal(ps, pdf, abstract)
Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Wkshp. on High Performance Computational Biology, Santa Fe, NM, Apr 2004.
Proceedings(ps, pdf, abstract)
|
|
An Unsupervised Adaptive Strategy for Constructing Probabilistic Roadmaps, Lydia Tapia, Shawna Thomas, Bryan Boyd, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 4037-4044, Kobe, Japan, May 2009. Also, Technical Report, TR08-004, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Sep 2008.
Technical Report(ps, pdf, abstract)
|
|
Biasing Samplers to Improve Motion Planning Performance, Shawna Thomas, Marco Morales, Xinyu Tang, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 1625-1630, Rome, Italy, Apr 2007.
Proceedings(ps, pdf, abstract)
Biasing Samplers to Improve Performance, Shawna Thomas, Marco Morales, Nancy M. Amato, Technical Report, TR06-009, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2006.
Technical Report(ps, pdf, abstract)
|
|
Planning with Reachable Distances, Xinyu Tang, Shawna Thomas, Nancy M. Amato, In Proc. Int. Wkshp. on Alg.
Found. of Rob. (WAFR), Guanajuato, Mexico, Dec 2008.
Proceedings(ps, pdf, abstract)
Planning with Reachable Distances: Fast Enforcement of Closure Constraints, Xinyu Tang, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 2694-2699, Rome, Italy, Apr 2007. Also, Technical Report, TR06-008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
Efficient Planning of Spatially Constrained Robots Using Reachable Distances, Xinyu Tang, Shawna Thomas, Nancy M. Amato, Technical Report, TR07-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2007.
Technical Report(ps, pdf, abstract)
|
|
RESAMPL: A Region-Sensitive Adaptive Motion Planner, Samuel Rodriguez, Shawna Thomas, Roger Pearce, Nancy M. Amato, In Proc. Int. Wkshp. on Alg.
Found. of Rob. (WAFR), New York City, NY, Jul 2006. Also, Technical Report, TR06-004, Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
|
|
Incremental Map Generation (IMG), Dawen Xie, Marco Morales, Roger Pearce, Shawna Thomas, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Wkshp. on Alg.
Found. of Rob. (WAFR), New York City, NY, Jul 2006. Also, Technical Report, TR06-005, Department of Computer Science and Engineering, Texas A&M University, Mar 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
Incremental Map Generation (IMG), Dawen Xie, Shawna L. Thomas, Jyh-Ming Lien, Nancy M. Amato, Technical Report, TR05-007, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Technical Report(ps, pdf, abstract)
|
|
A General Framework for Sampling on the Medial Axis of the Free Space, Jyh-Ming Lien, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 4439-4444, Taipei, Taiwan, Sep 2003.
Proceedings(ps, pdf, abstract)
|
|
A General Framework for PRM Motion Planning, Guang Song, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 4445-4450, Taipei, Taiwan, Sep 2003.
Proceedings(ps, pdf, abstract)
Customizing PRM Roadmaps at Query Time, Guang Song, Shawna Miller, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 1500-1505, Seoul, Korea, May 2001. Also, Technical Report, TR00-029, Department of Computer Science and Engineering, Texas A&M University, College Station, Texas, U.S.A., Nov 2000.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
Parasol Home | Research | People | General info | Seminars | Resources Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 Contact Webmaster Phone 979.458.0722 Fax 979.458.0718 
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University Privacy statement: Computer Science and Engineering Engineering TAMU |