Home research People General Info Seminars Resources Intranet
| 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?

Click here for full screen.

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.

Adaptive Neighbor Connection Feature-Sensitive Motion Planning Iterative Relaxation of Constraints Medial Axis Planning
Metrics Planning Under Uncertainty Reachable Volumes Single Shot Planning
Uniform Sampling Framework for PRMs User-Guided Motion Planning Region Steering

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.

Adaptive Neighbor Connection Adaptive RRT Feature-Sensitive Motion Planning RESAMPL: Region Sensitive Adaptive Motion Planner
Single Shot Planning Unsupervised Adaptive Strategy

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

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.

Constrained & Closed Chain Systems Deformable Objects Foldable Objects Metamorphic Robots
Mobile Robot Navigation & Localization Nonholonomic Car-like Robots

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