Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Home Page for Xinyu Tang | Parasol Laboratory


Picture Xinyu Tang
PhD Candidate
Algorithms & Applications Group

Parasol Laboratory url: http://parasol.tamu.edu/~xinyut/
Department of Computer Science and Engineering email:
Texas A&M University office: 407C HRBB
College Station, TX 77843-3112 tel: (979) 847-8835
USA fax: (979) 458-0718


I am a PhD candidate in the Department of Computer Science at Texas A&M University. I work with Dr. Nancy Amato in the Algorithms and Applications Group of the Parasol Lab. More information about me can be found on my CV, my research and teaching statements.

My current research interests include Bioinformatics (computational biology), motion planning and its applications in robotics, computational graphics and animation. Before coming to Texas A&M University, I was a software engineer and developed a variety of commercial computer aided design (CAD) systems. Information about my research and other projects can be found in the following descriptions and the list of my publications.


Descriptions of My Research and Other Projects

Computaional Biology    Motion Planning    Group (Flocking) Behaviors    CAD/CG    Visualization    Speech Process


Computational Biology:

Protein Folding and Motions [Publications]
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 two mutated forms of G.

Movies of Folding Pathways: mpg (3.4M)  gif (7.0M)

RNA Folding [Publications]
Many RNA functions (e.g., catalysis, plasmid copy number regulation and gene expression regulation) were recently found to be active only during the folding process. Using the our MMC and MME technologies, we can study those functions by simulating the RNA folding process. We validate our method against other computational methods or known experimental data. The results indicates that our method can use small roadmaps to capture the major features of much (10 order of magnitude) larger energy landscapes. We also show how our method can study kinetics-based functions for some real RNA with 200+ residues. Previously, those properties could only be studied for small RNA whose conformation space could be enumerated (e.g., RNA with 30-40 nucleotides) or for RNA whose kinetics were restricted in some way.
Movies of Folding Pathways: mpg(3.5M)

Motion Planning Algorithms:

Obstacle-Based Rapdily-Exploring Random Tree (OBRRT) [Publications]
Here we present a new variant of Rapidly-Exploring Random Tree (RRT) path planning algorithm that explores narrow passages or difficult areas more effectively. We show that both workspace obstacle information and C-space information can help decide which direction to grow. The method includes many ways to grow the tree, some taking into account the obstacles in the environment. Using obstacle hints for directions to grow a tree for path planning can be beneficial, especially when exploring difficult areas. Indeed, whereas the standard RRT can face difficulties planning in a narrow passage, the tree based planner presented here works best in these areas.

Movies: Alpha Puzzle (820k)
Motion Planning for Closed Chain Systems [Publications]
Closed chain systems are involved in many applications in robotics and beyond, such as the parallel robots, closed molecular chains, animation, and grasping for single and multiple robots. However, motion planning for closed-chain systems is particularly challenging due to additional constraints, called closure constraints , placed on the system. Using only the traditional joint angle representation, it is extremely difficult to randomly sample a set of joint angles that satisfy the closure constraints since the probability that a random set of joint angles lies on the constraint surface is zero. In this work, we propose a reachable-distance based representation of the closed-chain systems, which enables us to sample directly in the subspace subspace where closed constraints are satisfied. In particular, we show that we can sample the constraint surface with complexity linear in the complexity (number of links) of the robot system.

Movies: 20 Link Closed-loop Robot (0.3MB)  Two Arms Collaboration (0.5MB)
Motion Planning for Spatially Constrained Systems
Here, we generalize our reachable distance framework to include other types of spatially constrained systems. We demonstrate its utility on a variety of spatially constrained systems including collaboration, restricted end effector sampling for articulated linkages, on-line planning for drawing (or sculpting), and closed chain planning. Our method outperforms other randomized sampling methods such as PRM and RRT for sampling and planning for these spatially constrained systems. We demonstrate that our method is scalable to thousands of degrees of freedom making previously intractable problems solvable.

Movies: Drawing Robot (0.3MB) 
Biasing and Composing Motion Planners [Publications]
With the success of probabilistic planners, much work has been done to design new sampling techniques and distributions. However, little work has been done to combine these techniques to create new sampling distributions. We propose to bias a sampling distribution with another such that the resulting composed distribution out-performs either of its parent distributions. We present 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. We also notice that no single combination of distributions performs the best in all problems, and we identify which combinations perform better for the specific application domains studied.

Simulations of Group Behaviors:

Composable Group Behavior [Publications]
Creating animations with complex and realistic group behaviors can be a difficult and time consuming task. This generally involves associating all possible behaviors of agents and associating the behaviors with all environmental events. In this work, we investigate methods to ease the process of producing realistic group behaviors. More specifically, the main goal of this research is to simulate group behaviors by automatically combining a given set of simple composable behaviors for applications such as games, virtual reality, robotics and biological/ecological simulation. The result of this research is an easy to use, adaptive and flexible framework for simulating group behaviors.

Movie 1: Pursuit and Evasion (divx avi) 14.4 MB
Movie 2: Laser Tag (divx avi) 15.9 MB
Movie 3: Shepherding (divx avi) 9.3MB
Simulation of Fish Flocks
In this project, we simulated the fish flocking behaviors in a tank. There are two types of fishes, minnows and sharks. When hungry, sharks will chase minnows while minnows will chase fish food. The sea weeds are simulated using mass-spring model.

Movie: mpg (1.4M)

Visualization of Motion Planning:

Vizmo
VIZMO is a 3D visualization/authoring tool for files provided/generated by OBPRM motion planning library. This new version of VIZMO, VIZMO++, was developed for visualizing and editing motion planning environments, problem instances, and their solutions. VIZMO++ offers a nice and easy to use graphical user interface (GUI) that allows you to display workspace environments, roadmap, path, and start/goal positions. It enables users to interact with and edit the environment. For example, it lets users manipulate obstacles and robot configurations, set queries, save new environments to be able to work on them later, or select and move nodes and thus editing existing or creating new paths and roadmaps. VIZMO++ interfaces with the planners available in our motion planning library to enable users to run new queries. Our tool provides a convenient interface to select planners and set their parameters.
Campus Navigator [Publications]
In this project, we incorporate roadmap-based path planning techniques to a web-based route planner that covers the Texas A&M campus. The goal is to allow users to quickly find directions to all TAMU buildings, departments, and major services. Transportation information (e.g. bus routes and parking lots) is incorporated to provide meaningful answers to users questions such as "How do I get from the Bright building to Reed Arena, taking an on-campus bus." We use a layered roadmap approach to compose multiple transportation methods into a single queryable roadmap. The user interface is implemented using Google Maps API.

Commercial Software of Computer Aided Design (CAD):

Visual Interior Design CAD: e-CAD
A commercial CAD system for Interior Design. We first developed a generic CAD system similar to AutoCAD. Then we developed specialized modules for Interior Design (e.g., for wall, door and window) on top of it. I participated the initial system design and development of several modules including display, entity, user interface, command line center and Interior Design modules.
3D Feature based Parametric Modeling System: GS-CAD
A generic Computer Aided Design system. It includes solid modeling, sketching, feature parametric modeling, and advanced surface modeling techniques. The parameter auto-adaptation technique ensures the consistency of all steps from designing to manufacturing, thus all relevancies will be modified automatically on the change of a certain feature. I worked on geometric computation, user interface and entity management modules of GS-CAD.

Based on GS-CAD, later on we developed a commercial CAD system Jansteel-CAD for Steel Structure Design. I worked on the initial development of the user interface and geometric modeling and display modules of Jansteel-CAD.
Virtual Part Library
Part library is important for CAD design. However, deficiencies and problems exist in most libraries. For example, it is hard to reuse or share parts between different users/CAD systems. So we developed a part manage system - GS-PM. Using features instead of geometric primitives, it not only improves the efficiency but enables some high-level applications. For instance, parts can be shared by different CAD systems in Client/Server mode. It can also be applied to establish a customized Visual Part Library (a web-based part library), where users can build parts dynamically according to the user's need. I proposed the framework of this system and led a team of 5 people to implement it.

Speech Process:

Exaggerate Voice Distinctions
In our project, we followed [Proto, 1998] and reproduced their results to exaggerate pairwise similar sounds. Moreover, we tried several heuristics to extend their method to exaggerate a cluster of similar sounds, and to exaggerate those sequential sounds. Analysis on the results sounds shows that, physically, from the point of view of machine, those similar sounds are pushed away from each other as we want. After exaggeration, those distribution of sounds are more scattered and thus more different to each other. By listening to those sounds, a lot of people can also tell that those differences are bigger. In this project we were able to demonstrate a variety of useful techniques that in the machine domain perform extremely well. We believe the approaches we introduce can help non-native speakers distinguish hard sounds, but more controlled and monitored testing environments are needed to confirm our conjectures based.
Technical report: ppt

Publications

Reachable Distance Space: Efficient Sampling-Based Planning for Spatially Constrained Systems, Xinyu Tang, Shawna Thomas, Philip Coleman, Nancy M. Amato, International Journal of Robotics Research, 29(7):916-934, Jun 2010.
Journal(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)

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.
Journal(pdf, abstract)

Techniques for Modeling and Analyzing RNA and Protein Folding Energy Landscapes, Xinyu Tang, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Dec 2007.
Ph.D. Thesis(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.
Journal(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.
Journal(ps, pdf, abstract) 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.
Proceedings(ps, pdf, abstract)

Tools for Simulating and Analyzing RNA Folding Kinetics, Xinyu Tang, Shawna Thomas, Lydia Tapia, Nancy M. Amato, In Proc. Int. Conf. Comput. Molecular Biology (RECOMB), pp. 268-282, San Francisco, CA, Apr 2007.
Proceedings(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)

Supporting Path Planning Queries Incorporating Multiple Modes of Transportation using Layered Roadmaps, Roger Pearce, Bryan Boyd, Xinyu Tang, Darla Haigler, Akhil Patel, Nancy M. Amato, Technical Report, TR06-014, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2006.


An Obstacle-Based Rapidly-Exploring Random Tree, Samuel Rodriguez, Xinyu Tang, Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 895-900, Orlando, FL, May 2006. Also, Technical Report, TR05-009, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Proceedings(ps, pdf, abstract) Technical Report(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)