Extending OMPL support for optimal path planning

Luis Torres

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 ompl::base::MultiOptimizationObjective class.

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:

  • PRM*
  • RRT*
  • TRRT

Check out the results of running RRT* on a motion planning problem using different optimization objectives:

Minimizing path length:

Minimizing path length

Maximizing minimum path clearance from obstacle:

Maximizing minimum path clearance from obstacle

Balancing clearance and path length:

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:

Minimizing path length

Want to learn more?

Check out our optimal planning overview for a deeper introduction to the optimal planning framework, as well as the optimal planning tutorials in the tutorials page.