This page includes a list of extensions to OMPL provided by the community. Please read the directions on writing a contribution and the suggested style guide if you would like to submit your own contribution.
CForest is a parallelization framework that is designed for single-query shortest path planning algorithms. It is not a planning algorithm per se.
CForest is designed to be used with any random tree algorithm that operates in any configuration space such that: 1) the search tree has almost sure convergence to the optimal solution and 2) the configuration space obeys the triangle inequality. It relies in the OptimizationObjective set for the underlying planners.
See also the extensive documentation here. This also describes how our implementation differs from the algorithm as described in:
- M. Otte, N. Correll, C-FOREST: Parallel Shortest Path Planning With Superlinear Speedup, IEEE Transactions on Robotics, Vol 20, No 3, 2013. DOI: 10.1109/TRO.2013.2240176
FMT∗ is a new asymptotically optimal algorithm contributed by Marco Pavone's Autonomous Systems Laboratory. The FMT∗ algorithm performs a “lazy” dynamic programming recursion on a set of probabilistically-drawn samples to grow a tree of paths, which moves outward in cost-to-come space. The algorithm is described in:
- L. Janson, E. Schmerling, A. Clark, M. Pavone. Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. The International Journal of Robotics Research, 34(7):883-921, 2015. DOI: 10.1177/0278364915577958 [PDF]
BFMT∗ is a new asymptotically optimal algorithm contributed by Marco Pavone's Autonomous Systems Laboratory. The BFMT∗ algorithm expands two Fast Marching Trees, one from the initial state and the other from the goal, resulting in faster convergence rates are less space is explored by the trees. The algorithm is described in:
- J. A. Starek, J. V. Gomez, E. Schmerling, L. Janson, L. Moreno, and M. Pavone, An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning, in IEEE/RSJ International Conference on Intelligent Robots Systems, 2015. [PDF]
Extend OMPL's support for optimal path planning. Users can plan robot paths that optimize a variety of ready-to-use metrics such as path length and clearance from obstacles. Users can also plan optimal paths under their own customized path metrics without changing OMPL's optimizing planners. Additional benchmarking data has also been added so users can efficiently track the progress of an optimizing planner on their planning problem. Tutorials for use of the framework can be found here.
LBT-RRT (Lower Bound Tree RRT) is a near-asymptotically optimal incremental sampling-based motion planning algorithm. LBT-RRT is guaranteed to converge to a solution that is within a constant factor of the optimal solution. The notion of optimality is with respect to the distance function defined on the state space we are operating on. The algorithm is described in:
- Oren Salzman and Dan Halperin, Asymptotically near-optimal RRT for fast, high-quality, motion planning, arXiv, 2013 [PDF]
- SPARS and SPARS2 are roadmap-based planners that operate similarly to Visbility-based PRM, but provide asymptotic near-optimality guarantees. The SPARS and SPARS2 algorithms a described in:
- T-RRT is an RRT variant and tree-based motion planner that takes into consideration state costs to compute low-cost paths that follow valleys and saddle points of the configuration-space costmap. It uses transition tests from stochastic optimization methods to accept or reject new potential sates. An example use of TRRT.
- L. Jaillet, J. Cortés, T. Siméon, Sampling-Based Path Planning on Configuration-Space Costmaps, in IEEE Transactions on Robotics, 26(4):635–646, August 2010, [PDF]
- MoveIt! wraps OMPL as a planning plugin.
- RRT* (optimal RRT) is an asymptotically-optimal incremental sampling-based motion planning algorithm. RRT* algorithm is guaranteed to converge to an optimal solution, while its running time is guaranteed to be a constant factor of the running time of the RRT. The RRT* algorithm was introduced and analyzed in:
- S. Karaman and E. Frazzoli, Sampling-based algorithms for optimal motion planning Int. Journal of Robotics Research, 2011. Also available at https://arxiv.org/abs/1105.1186.
- Generalized the implementation of PRM so that different variations can be created by passing connection strategies and filters. Provided such functions for PRM and PRM*.
- Generalized the implementation of RRT (with controls) so that intermediate states generated along motions are also optionally added to that tree of motions.
- QRRT A generalization of RRT to plan on different abstraction levels. The abstraction levels are represented by quotient-spaces, and QRRT grows random trees sequentially and simultaneously on each quotient-space. See also our guide, tutorial and demos.
- A Orthey and M Toussaint, Rapidly-Exploring Quotient-Space Trees: Motion Planning using Sequential Simplifications, 2019. Also available at https://arxiv.org/abs/1906.01350.
- A Orthey, A Escande and E Yoshida, Quotient Space Motion Planning, ICRA, 2018. Also available at https://arxiv.org/abs/1807.09468.