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

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

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

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

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

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