Available Planners

All implementations listed below are considered fully functional. Within OMPL planners are divided into three categories:

To see how to benchmark planners, click here.

Geometric planners

Planners in this category only accounts for the geometric and kinematic constraints of the system. It is assumed that any feasible path can be turned into a dynamically feasible trajectory. Any of these planners can be used to plan with geometric constraints. Planners in this category can be divided into several overlapping subcategories:

  • Multi-query planners
    These planners build a roadmap of the entire environment that can be used for multiple queries.
    • Probabilistic Roadmap Method (PRM)
      This is the sampling-based algorithm. Our implementation uses one thread to construct a roadmap while a second thread checks whether a path exists in the roadmap between a start and goal state. OMPL contains a number of variants of PRM:
      • LazyPRM
        This planner is similar to regular PRM, but checks the validity of a vertex or edge “lazily,” i.e., only when it is part of a candidate solution path.
      • PRM*
        While regular PRM attempts to connect states to a fixed number of neighbors, PRM* gradually increases the number of connection attempts as the roadmap grows in a way that provides convergence to the optimal path.
      • LazyPRM*
        A version of PRM* with lazy state validity checking.
    • SPArse Roadmap Spanner algorithm (SPARS)
      SPARS is a planner that provides asymptotic near-optimality (a solution that is within a constant factor of the optimal solution) and includes a meaningful stopping criterion. Although (because?) it does not guarantee optimality, its convergence rate tends to be much higher than PRM*.
    • SPARS2
      SPARS2 is variant of the SPARS algorithm that works through similar mechanics, but uses a different approach to identifying interfaces and computing shortest paths through said interfaces.
  • Single-query planners
    These planners typically grow a tree of states connected by valid motions. These planners differ in the heuristics they use to control where and how the tree is expanded. Some tree-based planners grow two trees: one from the start and one from the goal. Such planners will attempt to connect a state in the start tree with another state in the goal tree.
    • Rapidly-exploring Random Trees (RRT)
      This is one of the first single query planners. The algorithm is easy to understand and easy to implement. Many, many variants of RRT have been proposed. OMPL contains several RRT variants:
      • RRT Connect (RRTConnect)
        This planner is a bidirectional version of RRT (i.e., it grows two trees). It usually outperforms the original RRT algorithm.
      • RRT*
        An asymptotically optimal version of RRT: the algorithm converges on the optimal path as a function of time. This was the first provably asymptotically planner (together with PRM). Since its publication, several other algorithms have appeared that improve on RRT*'s convergence rate, such as RRT# and RRTX.
      • Lower Bound Tree RRT (LBTRRT)
        LBTRRT is a asymptotically near-optimal version of RRT: it is guaranteed to converge to a solution that is within a constant factor of the optimal solution.
      • Sparse Stable RRT
        SST is an asymptotically near-optimal incremental version of RRT.
      • Transition-based RRT (T-RRT)
        T-RRT does not give any hard optimality guarantees, but tries to find short, low-cost paths.
      • Vector Field RRT
        VF-RRT is a tree-based motion planner that tries to minimize the so-called upstream cost of a path. The upstream cost is defined by an integral over a user-defined vector field.
      • Parallel RRT (pRRT)
        Many different parallelization schemes have been proposed for sampling-based planners, including RRT. In this implementation, several threads simultaneously add states to the same tree. Once a solution is found, all threads terminate.
      • Lazy RRT (LazyRRT)
        This planner performs lazy state validity checking (similar to LazyPRM). It is not experimental, but in our experience it does not seem to outperform other planners by a significant margin on any class of problems.
      • Task-space RRT (TSRRT)
        TSRRT is a variant of RRT where exploration is guided by the task space. It requires an ompl::geometric::TaskSpaceConfig instance that defines how to project configuration space states to the task spaces and an inverse operation to lift task space states to the configuration space.
    • Expansive Space Trees (EST)
      This planner was published around the same time as RRT. In our experience it is not as sensitive to having a good distance measure, which can be difficult to define for complex high-dimensional state spaces. There are actually three versions of EST: the original version that is close to the first publication, a bidirectional version, and a projection-based version. The low-dimensional projection is used to keep track of how the state space has been explored. Most of the time OMPL can automatically determine a reasonable projection. We have implemented a few planners that not necessarily simple variants of EST, but do share the same expansion strategy:
    • Kinematic Planning by Interior-Exterior Cell Exploration (KPIECE)
      KPIECE is a tree-based planner that uses a discretization (multiple levels, in general) to guide the exploration of the (continuous) state space. OMPL's implementation is a simplified one, using a single level of discretization: one grid. The grid is imposed on a projection of the state space. When exploring the space, preference is given to the boundary of that part of the grid that has been explored so far. The boundary is defined to be the set of grid cells that have fewer than 2n non-diagonal non-empty neighboring grid cells in an n-dimensional projection space. There are two variants of KPIECE:
    • Search Tree with Resolution Independent Density Estimation (STRIDE)
      This planner was inspired by EST. Instead of using a projection, STRIDE uses a Geometric Near-neighbor Access Tree to estimate sampling density directly in the state space. STRIDE is a useful for high-dimensional systems where the free space cannot easily be captured with a low-dimensional (linear) projection.
    • Path-Directed Subdivision Trees (PDST)
      PDST is a planner that has entirely removed the dependency on a distance measure, which is useful in cases where a good distance metric is hard to define. PDST maintains a binary space partitioning such that motions are completely contained within one cell of the partition. The density of motions per cell is used to guide expansion of the tree.
    • Fast Marching Tree algorithm (FMT∗)
      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. Unlike all other planners, the numbers of valid samples needs to be chosen beforehand.
    • Bidirectional Fast Marching Tree algorithm (BFMT∗)
      Executes two FMT* trees, one from the start and another one from the goal resulting in a faster planner as it explores less space.
  • Multi-level planners
    Planning algorithms which can exploit multiple levels of abstractions. If you want to use them, you should call them with a vector of ompl::base::SpaceInformationPtr. All planner then guarantee probabilistic completeness, if the supplied abstractions are admissible. There is extensive documentation in the form of a guide, tutorial and demos.
  • Optimizing planners
    In recent years several sampling-based planning algorithms have been proposed that still provide some optimality guarantees. Typically, an optimal solution is assumed to be shortest path. In OMPL we have a more general framework for expressing the cost of states and paths that allows you to, e.g., maximize the minimum clearance along a path, minimize the mechanical work, or some arbitrary user-defined optimization criterion. See Optimal Planning for more information. Some of the planners below use this general cost framework, but keep in mind that convergence to optimality is not guaranteed when optimizing over something other than path length.
    • PRM*
      An asymptotically optimal version of PRM; uses the general cost framework.
    • LazyPRM*
      Lazy version of PRM*; uses the general cost framework.
    • RRT*
      An asymptotically optimal version of RRT; uses the general cost framework.
    • RRT#
      A variant of RRT* with an improved convergence rate. It uses the general cost framework.
    • RRTX
      A variant of RRT* with an improved convergence rate. It uses the general cost framework.
    • Informed RRT*
      A variant of RRT* that uses heuristics to bound the search for optimal solutions. It uses the general cost framework.
    • Batch Informed Trees (BIT*)
      An anytime asymptotically optimal algorithm that uses heuristics to order and bound the search for optimal solutions. It uses the general cost framework.
    • Advanced BIT* (ABIT*)
      An extension to BIT* that uses advanced graph-search techniques to find initial solutions faster. It uses the general cost framework.
    • Adaptively Informed Trees (AIT*)
      An anytime asymptotically optimal algorithm that simultaneously estimates and exploits problem-specific heuristics. It uses the general cost framework.
    • Lower Bound Tree RRT (LBTRRT)
      An asymptotically near-optimal version of RRT.
    • Sparse Stable RRT
      SST is an asymptotically near-optimal incremental version of RRT.
    • Transition-based RRT (T-RRT)
      T-RRT does not give any hard optimality guarantees, but tries to find short, low-cost paths. It uses the general cost framework.
    • SPARS
      An asymptotically near-optimal roadmap-based planner.
    • SPARS2
      An asymptotically near-optimal roadmap-based planner.
    • FMT*
      An asymptotically optimal tree-based planner.
    • ST-RRT*
      a bidirectional, time-optimal planner for planning in space-time.
    • CForest
      A meta-planner that runs several instances of asymptotically optimal planners in different threads. When one thread finds a better solution path, the states along the path are passed on to the other threads.
    • AnytimePathShortening (APS)
      APS is a generic wrapper around one or more geometric motion planners that repeatedly applies shortcutting and hybridization to a set of solution paths. Any number and combination of planners can be specified, each is run in a separate thread.
Attention
How OMPL selects a geometric planner
If you use the ompl::geometric::SimpleSetup class (highly recommended) to define and solve your motion planning problem, then OMPL will automatically select an appropriate planner (unless you have explicitly specified one). If the state space has a default projection (which is going to be the case if you use any of the built-in state spaces), then it will use LBKPIECE if a bidirectional planner can be used and otherwise it will use KPIECE. These planners have been shown to work well consistently across many real-world motion planning problems, which is why these planners are the default choice. In case the state space has no default projection, RRTConnect or regular RRT will be used, depending on whether a bidirectional planner can be used. The notion of a goal is very general in OMPL: it may not even be possible to sample a state that satisfies the goal, in which case OMPL cannot grow a second tree at a goal state.
Feasibility and Optimality
The line between feasible and optimal planners is not so black and white in practice. The line between them can be blurred with an appropriate ompl::base::PlannerTerminationCondition. For instance, the ompl::base::exactSolnPlannerTerminationCondition function returns a termination condition that causes optimizing planners to terminate once the first solution is found. As another example, using a ompl::base::CostConvergenceTerminationCondition with parameters solutionsWindow=10 and epsilon=1, causes an optimizing planner to terminate when exactly 10 solutions have been found. You can use ompl::base::plannerOrTerminationCondition and ompl::base::plannerAndTerminationCondition to combine planner termination conditions (e.g., “terminate when either 10 solutions have been found or a time limit of 10 seconds is exceeded”). See Planner Termination Conditions for details.

Other tools:

Control-based planners

If the system under consideration is subject to differential constraints, then a control-based planner is used. These planners rely on state propagation rather than simple interpolation to generate motions. These planners do not require a steering function, but all of them (except KPIECE) will use it if the user implements it. The first two planners below are kinodynamic adaptations of the corresponding geometric planners above.
Attention
How OMPL selects a control-based planner
If you use the ompl::control::SimpleSetup class (highly recommended) to define and solve your motion planning problem, then OMPL will automatically select an appropriate planner (unless you have explicitly specified one). If the state space has a default projection (which is going to be the case if you use any of the built-in state spaces), then it will use KPIECE. This planner has been shown to work well consistently across many real-world motion planning problems, which is why it is the default choice. In case the state space has no default projection, RRT will be used. Note that there are no bidirectional control-based planners, since we do not assume that there is a steering function that can connect two states exactly.

Multilevel-based planners

To solve problems involving high-dimensional state spaces, we often can use multilevel abstractions to simplify the state spaces, thereby allowing dedicated planner to quicker find solutions. The planner in this class support sequences of state spaces and can be utilized both for state spaces with geometric and dynamic constraints. There is extensive documentation in the form of a guide, tutorial and demos.