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.
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.
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.
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.
Guided Planning
Strategies to guide or bias sampling-based planning algorithms to improve performance.
Learning to Guide Sampling-Based Planners
Our group proposed one of the earliest approaches that use learning to guide the sampling-based exploration of the motion planning space. Instead of applying the same planning strategy across the problem, we dynamically adapt sampling parameters such as the region being explored, the planner used, the number of samples to use, and the connection strategies.
Reachability Analysis for Sampling-Based Planning
Planning constained motions, such as cooperatively carrying an object, is very hard for sampling-based methods. We have developed specialized methods that exploit reachability analysis for such problems.
Obstacle-Based Planning
We have developed sampling-based strategies that bias sampling near C-Space obstacle surfaces, which can improve planning for hard problems with crowded environments with narrow passages.
Medial Axis Guided Planning
We have developed sampling-based strategies that bias planning towards the medial axis of the planning space, potentially yielding safer paths with higher clearance.
Toggle Planning: Coordinated Mapping of C-free and C-obst
The toggle strategy of coordinated mapping of the free and the blocked C-space provides practical and theoretical benefits when solving motion planning problems with narrow passages.
Multi-Robot Motion Planning
We show several contributions to solve pure motion planning problems for multi-robot systems.
Algorithmic Strategies
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 to improve performance.
Feedback-based Information Roadmap
The Feedback-based Information Roadmap (FIRM) method family for motion planning under uncertainty.