| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News

Algorithms & Applications Group
Motion Planning

The motion planning problem consists of finding a valid path for an object from a start configuration to a goal configuration. Traditionally, a valid path is any path that is collision-free, but for some applications such as computational biology, this can mean any path that is below some energy threshold. Motion planning has applications in robotics, games/virtual reality, computer-aided design/virtual prototyping, and bioinformatics. Our research is focused on developing motion planning algorithms and applying them to a wide range of problems.

## What is Motion Planning?

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

Motion Planning Strategies & Frameworks

We develop motion planning algorithms that can be applied to any type of robot, from simple rigid bodies to complex articulated linkages. We abstract the particular motion planning problem into configuration space (C-space) where each point in C-space represents a particular configuration/placement of the robot. Invalid configurations (e.g., in-collision, high energy) become C-obstacles in this higher dimensional space. We can then plan the path of the (now point) robot in C-space and later transform it back to the actual robot.

Sampling based motion planning uses randomization to construct a graph or tree (roadmap) in C-space on which queries (start/goal configurations) may be solved. We explore different general purpose techniques to improve planner performance. Some techniques adapt to different inputs, bias planning via features of the environment or via the medial axis, or employ user guidance to more efficiently plan. We also have general purpose algorithms for handling moving objects or constrained systems using reachable volumes or by iteratively relaxing them.

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

Learning-Based Methods

We explore different adaptive techniques to improve motion planning performance. We consider both multi-query methods and single-query methods. Some techniques learn best methods for sampling and/or best methods for connection, while others adapt the entire algorithm to current inputs.

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

Graph-Based Methods

In the context of multi-query problems, we have developed several PRM methods. We have examined constructing roadmaps incrementally, by toggling between free space and obstacle space, and by sparking PRMs with RRTs. We have studied ways to improve connectivity and to customize roadmaps at query time. These algorithms consider the entire roadmap construction process. Techniques for sampling (one of the sub-operations of roadmap construction) are explored here.

 Customizable (and Adaptable) PRM Improving Connectivity Incremental Map Generation Spark PRM Toggle PRM

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

Tree-Based Methods

In the context of single-query problems, we have developed several RRT methods. We have looked at biasing RRT growth toward the medial axis, along obstacle surfaces, and adaptive strategies for determining how best to expand. We have also developed algorithms for constructing RRTs in reachable volume space. These algorithms consider the entire roadmap construction process. Techniques for sampling (one of the sub-operations of roadmap construction) are explored here.

 Adaptive RRT Medial Axis RRT mRRG Obstacle Based RRT Reachable Volumes RRT

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

Sampling Techniques

Probabilistic roadmap (PRM) methods use randomization to construct a graph (roadmap) in C-space on which multiple quries (start/goal configurations) can be solved. Sampling is one important components of PRMs. Our work provides new sampling strategies to handle more challenging narrow passage problems. We have also studied now to combine existing samplers by biasing them with each other to improve performance.

 Biasing Samplers MAPRM: Medial Axis PRM OBPRM: Obstacle-Based PRM Uniform OBPRM Uniform MAPRM Dynamic Region RRT

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

Specialized for Specific Classes of Robots

We design algorithms for specialized classes of robots. These algorithms are more efficient than general purpose motion planning algorithms. For some robots, such as closed chains and foldable objects, the probability of randomly sampling key configurations is near zero. Other robots, like deformable objects, nonholonomic robots, and metamorphic robots, have unique capabilities/requirements that cannot be adequately expresssed with general purpose motion planners. Also, we work on incorporating mobile robot localization with the motion planning algorithm.

 Top | Motion Planning Strategies & Frameworks | Learning-Based Methods | Graph-Based Methods | Tree-Based Methods | Sampling Techniques | Specialized for Specific Classes of Robots

 Parasol Home | Research | People | General info | Seminars | Resources   Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  parasol-admin@cse.tamu.edu      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 Web Accessibility Policy and Law - Web Accessibility and Usability Standards  -   Contact Webmaster