Extending OMPL support for optimal path planning
In some motion planning problems, you might not want just any valid path between your start and goal. You might be interested in the shortest path, or perhaps the path that steers farthest away from obstacles. In these cases you’re looking for an optimal path: a path that satisfies your constraints (connects start and goal states without collisions) and also optimizes some path quality metric. Path length and path clearance are two examples of path quality metrics, or optimization objectives.
As part of the 2013 Google Summer of Code, I have worked with Ioan Şucan and Mark Moll to extend OMPL’s support for optimal motion planning. Over the summer we made the following extensions to OMPL:
Generalized Optimization Objectives
We refined and extended the interface for defining optimization objectives for planning in OMPL. Users can define their own objectives by implementing the
ompl::base::OptimizationObjective interface. OMPL also includes predefined implementations of the following optimization objectives:
- path length
- minimum path clearance
- general state cost integrals
- mechanical work
We also include functionality to easily combine optimization objectives using the
Extending Optimizing Planner Support for Generalized Optimization Objectives
Motion planners that attempt to optimize path quality objectives are known as optimizing planners. OMPL comes with some optimizing planners, but before this summer they only supported the optimization of path length. We extended the following optimizing planners in OMPL to support generalized optimization objectives:
Check out the results of running RRT* on a motion planning problem using different optimization objectives:
Minimizing path length:
Maximizing minimum path clearance from obstacle:
Balancing clearance and path length:
More Detailed Planner Benchmarks
OMPL offers a powerful framework for benchmarking motion planning algorithms. Before the summer, the framework could only collect individual properties of a planner at the end of each planning run, such as execution time, number of configuration samples taken, or solution path length. Now, the benchmarking framework can collect data about how properties of a planner change over time in a planning run. This is very useful for benchmarking optimizing planners so we can analyze how the solution path quality improves over the planner’s execution. Planners can be implemented to specify any number of properties to “report” during execution, and during benchmarking we collect the reported data in a separate thread in such a way that doesn’t interfere with planner timing.
We then extended OMPL’s benchmark analysis script to output plots that chart the average values of these “planner progress properties” over time. Here’s a plot (automatically generated by our script) charting path length versus time for the RRT* planner on an example planning problem:
Want to learn more?