PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling-Based Motion Planning: A Comparative Review

Andreas Orthey, Constantinos Chamzas, Lydia E. Kavraki

arXiv:2309.13119v1cs.RO

TL;DR

Sampling-based motion planning lacks an up-to-date guide connecting planner classes, historical development, alternative frameworks, and application scenarios. This review synthesizes and categorizes the field, discusses extensions, and evaluates planners on 24 challenging scenarios. The evaluation shows that planners solve a broad range of problems but no single planner performs best across all problems.

  • Problem

    Researchers and practitioners lack an up-to-date guideline covering SBMP history, planner categories, alternative frameworks, and planner suitability across scenarios.

  • Method

    The review synthesizes SBMP history and algorithms, compares alternative motion-generation frameworks, discusses extensions, and evaluates planners across 24 scenarios.

  • Results

    SBMP algorithms successfully solve a broad class of problems, but no single planner performs best across all problems.

  • Takeaways & Limitations

    Choosing a suitable planner depends significantly on the robot and environment.

  • Takeaways & Limitations

    Hyperparameter choices were not covered in the experiments, although they can drastically affect planning performance.

Abstract

from arXiv · show

Sampling-based motion planning is one of the fundamental paradigms to generate robot motions, and a cornerstone of robotics research. This comparative review provides an up-to-date guideline and reference manual for the use of sampling-based motion planning algorithms. This includes a history of motion planning, an overview about the most successful planners, and a discussion on their properties. It is also shown how planners can handle special cases and how extensions of motion planning can be accommodated. To put sampling-based motion planning into a larger context, a discussion of alternative motion generation frameworks is presented which highlights their respective differences to sampling-based motion planning. Finally, a set of sampling-based motion planners are compared on 24 challenging planning problems. This evaluation gives insights into which planners perform well in which situations and where future research would be required. This comparative review thereby provides not only a useful reference manual for researchers in the field, but also a guideline for practitioners to make informed algorithmic decisions.

1. Introduction

Sampling-based motion planning has become a major robotics paradigm, but researchers and practitioners lack an up-to-date guide for choosing and understanding its methods. This review addresses that gap through historical synthesis, algorithm categorization, framework comparison, and evaluation across 24 scenarios.

  • Sampling-based motion planning methods have enabled applications including robotics construction, multi-robot coordination, autonomous driving, industrial manufacturing, and protein folding.
  • SBMP finds robot motions by sampling configurations to quickly obtain feasible and sometimes optimal paths, especially in problems with many degrees of freedom.
  • The review addresses missing historical coverage, planner categorization, comparisons with alternative frameworks, and guidance for matching planners to scenarios.
  • Its contributions span a history from 1979 to 2023, algorithm categorization, comparison with alternative frameworks, and evaluation of success, runtime, and optimality on 24 scenarios.
  • Together, these contributions position the review as a guideline and reference manual for using SBMP methods.

2. Motion Planning History and the Emergence of Sampling-based Methods

Motion planning evolved from theoretically rigorous but computationally expensive methods toward sampling-based approaches that improved practical efficiency. The field later expanded through graph and tree planners, biased sampling, asymptotic optimality, and learning from prior experience.

  • Motion Planning History: Motion planning history is divided into pre-sampling, sampling-advent, sampling-consolidation, and optimality-and-learning eras spanning roughly 40 years.
  • Pre-sampling Era: Configuration-space formulations established motion planning as a general problem, while NP-hardness and single-exponential algorithms exposed the difficulty of obtaining practical solutions.
  • Pre-sampling Era: Potential fields improved practical robot control but sacrificed guarantees such as completeness.
  • Sampling-advent Era: Graph-based planners such as PRM support multiple queries through reusable graphs, whereas tree-based planners such as EST and RRT grow from a start configuration.
  • Sampling-consolidation Era: Biased sampling improved runtime by concentrating samples near obstacles, narrow passages, workspace geometries, or other selected regions.
  • Optimality and Learning Era: PRM* and RRT* introduced asymptotic optimality, while learning methods began using prior planning experiences to accelerate future searches.

3. Motion Planning

Motion planning formalizes robot movement through a constrained state space, where feasible paths connect an initial state to a goal region. The review defines core problem variants, structural assumptions, metrics, and constraints that shape planner design.

  • Motion Planning: A state space contains all states describing a mechanical system, while a motion-planning problem seeks a continuous feasible path from an initial state to a goal region.
  • Problem Variations: Motion-planning problems include path planning, kinodynamic planning with dynamics and control constraints, and optimal planning for minimum-cost paths.
  • Problem Variations: The discussion focuses on path planning, treats kinodynamic planning separately, and interleaves optimal planning with both topics.
  • State Space Structure: Most planners assume a topological state space that is often a manifold locally resembling R^n, together with metrics, constraints, dynamics, or topology as needed.
  • Metric Function: Metric functions are characterized by identity of indiscernibles, symmetry, and the triangle inequality; pseudometrics, quasimetrics, and semimetrics relax these properties when necessary.
  • Metric Function: Relaxing metric properties can affect methods such as nearest-neighbor computation, although some sampling-based planners operate without a metric.
  • Constraints: Constraint functions classify states as feasible when ϕ ≤ 0 and infeasible when ϕ > 0, covering requirements such as collision avoidance, joint limits, and tool-center-point bounds.

4. Sampling-based Motion Planning

Sampling-based planners implicitly represent state spaces by generating samples and connecting them with local planners. Their main design choices concern sampling bias, planner organization, local connection methods, and extensions for specialized planning problems.

  • Planner Architecture: Sampling-based motion planning generates state samples and connects them with a local planner, using tree-based or graph-based planners to coordinate the process.
  • Planner Extensions: Planner extensions address unbounded spaces, infeasible problems, kinodynamic constraints, and other variations of the canonical problem.
  • Sampling Functions: Sampling sequences may need to be dense in the state space for planners to provide guarantees.
  • Sampling Functions: Unbiased sampling treats outcomes equally, whereas biased sampling concentrates probability in interesting regions.
  • Sampling Biases: Obstacle-based sampling improves planning in narrow passages but introduces a path-length bias that may conflict with clearance objectives.
  • Sampling Biases: Clearance-based sampling can mitigate execution uncertainty on real robots, but clearance queries are often expensive.
  • Sampling Biases: Deterministic samplers repeat sampling sequences and can learn from similar environments or improve coverage through low-dispersion sequences.
  • Local Planning: Local planners connect nearby samples with path segments, while specialized cases may require optimal-cost bounds or satisfaction of differential constraints.

4.3. Categorization of Sampling-based Planners

Sampling-based planners are organized mainly as graph-based or tree-based methods, with general-purpose improvements targeting efficiency, path quality, and guarantees. Their properties include probabilistic completeness and, for some planners, asymptotic optimality or near-optimality.

  • Planner categories: Graph-based planners sample constraint-free states, connect nearby nodes with local plans, and build a roadmap for planning.Basic-PRM illustrates this workflow by adding valid samples and collision-free edges until termination.
  • Planner categories: Tree-based planners extend the nearest tree state toward random samples, adding constraint-free edges; they are often single-query methods.Basic-RRT recomputes its tree for different start states or goal regions.
  • General-purpose improvements: Planner efficiency can mean lower memory, shorter runtime, fewer samples, or improved path cost.General-purpose improvements modify planner components to optimize one or more of these criteria.
  • General-purpose improvements: Bidirectionality generally decreases runtime, while sparsity reduces planner memory by limiting redundant samples or retaining lower-cost states.Bidirectional planners grow trees from the start and goal, whereas sparse planners reject nearby samples or prune by cost-to-come.
  • Planner properties: Asymptotic optimality uses adaptive neighbor radii or tree rewiring so solution costs converge to the global optimum over time.Asymptotically near-optimal planners instead guarantee an ϵ-near solution and can trade memory consumption for weaker optimality guarantees.
  • General-purpose improvements: Admissible heuristics provide lower-bound cost estimates and can reduce runtime without sacrificing completeness or optimality.Informed sets identify states that could improve solution quality; examples include BIT* and AIT*.
  • General-purpose improvements: Choosing planner hyperparameters remains an open research problem because parameters such as Basic-PRM’s K can significantly affect performance.Frameworks may provide reasonable defaults, while recent work investigates Bayesian optimization for automatic selection.
  • Planner properties: Probabilistic completeness guarantees finding a solution if one exists when time goes to infinity, while asymptotic optimality guarantees convergence to the global optimum.RRT*, PRM*, and BIT* are examples with asymptotic optimality.

4.4. Special Cases of Motion Planning

Special motion-planning cases challenge standard assumptions about bounded sampling spaces and feasible solutions. Proposed responses include adaptive sampling regions, selection-extension schemes, sparse-roadmap infeasibility estimates, and infeasibility certificates.

  • Planner properties: Asymptotic optimality is defined for planners that find the global optimal solution when time goes to infinity.This property provides the reference guarantee for handling special cases that modify the sampling domain.
  • Unbounded state spaces: Unbounded space-time planning conflicts with sampling sequences that require bounded spaces to generate dense samples.Adaptive goal regions shift bounds while preserving asymptotic optimality, whereas selection-extension schemes repeatedly expand selected nodes.
  • Infeasible problems: Sampling-based planners often cannot directly handle infeasible problems, where obstacles prevent the robot from reaching the goal.The illustrated disk robot can generate motions but cannot reach its goal because of obstacles.
  • Infeasible problems: Sparse roadmaps can provide a probabilistic infeasibility estimate when no new samples can be added for a specified period.Their visibility radius rejects nearby samples, causing the number of added samples to approach zero over time.
  • Infeasible problems: Infeasibility certificates can verify infeasibility in lower-dimensional problems by forming a closed hull around the start state or goal region.The method uses samples to construct the hull used for verification.

4.5. Kinodynamic Motion Planning

Kinodynamic motion planning incorporates system dynamics and limits on velocity, acceleration, or torque. Planners handle these constraints either by computing controls between states or by forward-propagating sampled controls.

  • Problem formulation: Kinodynamic motion planning addresses dynamics and constraints on velocity, acceleration, or torques beyond kinematic constraints.The dynamics equation constrains which paths the system can take.
  • Problem formulation: The dynamics equation represents the state derivative as a function of the current state and applied control.Here, u is a control in the applicable control space U, and f is the dynamical-systems equation.
  • Steering method: Steering computes a control and duration that move an initial state to a target while respecting the dynamics.The computation may be analytical or numerical, but can be difficult and costly because it involves a two-point boundary-value problem.
  • Forward propagation: Forward propagation applies a control from an initial state for a specified time to compute the next state, treating the dynamics as a black box.Kinodynamic-RRT uses random control sampling for forward propagation, while AO-RRT can achieve asymptotic optimality.

4.6. Extensions Solved by Sampling-based Motion Planning

Sampling-based planning can be extended to state spaces with additional problem-imposed or performance-oriented structure. Extensions address abstraction, differentiability, manifold constraints, changing environments, partial observability, and external forces.

  • Extension framework: Extensions impose additional structure on the state space, either because the problem requires it or to improve planner performance.Examples include contact constraints, partial observability, projections, and differentiability.
  • Projections: Projections simplify high-dimensional planning through multiple abstraction levels and can guide sampling as biased samplers or planning adjustments.When projections are admissible, asymptotic optimality can be guaranteed.
  • Differentiability: Differentiable motion planning exploits gradients from costs, goals, or constraints to help converge faster toward optimal solutions.Planners must weigh when computing differentiable information is useful.
  • Manifold constraints: Manifold-constraint planning addresses contact-like constraints that create zero-measure regions unlikely to be sampled directly.These constraints require specialized ways to construct or navigate feasible states.
  • Dynamic environments: Dynamic-environment planners handle obstacles that move, appear, or disappear and can invalidate previously successful plans.RRTX updates a goal-centered search tree online, while precomputed roadmaps support rapid path recomputation.
  • Partial observability: Partial-observability planning samples belief space, which combines hypotheses about the world with robot states.Because the hypothesis space can become large, it must be simplified to remain searchable.
  • External forces: Sampling-based frameworks can represent gravity, friction, or wind as vector fields on the robot’s state space.Applications described include wind disturbances for UAVs and water draft for AUVs.

5. Competing Motion Generation Frameworks

The review contrasts sampling-based motion planning with optimization, motion primitives, search-based planning, and control-based planning. These alternatives trade guarantees, dimensional scalability, reactivity, and solution quality differently.

  • 5.1. Motion Optimization: Motion optimization formulates motion generation as an optimization problem, often improving an existing path.Gradient-based methods can quickly find low-cost paths when costs, goals, and constraints are differentiable.
  • 5.1. Motion Optimization: Optimization-based methods usually find locally optimal solutions and lack completeness or optimality guarantees.An infeasible starting path can remain invalid even when a feasible solution exists.
  • 5.2. Motion Primitives: Motion primitives provide predefined or learned state-space vector fields for reaching targets, fulfilling tasks, or avoiding obstacles.They can compose several simple task policies into complex motions and support reactive planning when feedback is crucial.
  • 5.3. Search-based Planning: Search-based planning discretizes the state space into a grid and connects neighboring states to construct a graph for search.A*-like methods can achieve optimality relative to graph resolution, but fine grids are expensive and coarse grids can miss narrow passages.
  • 5.4. Control-based Planning: Control-based approaches drive robots toward goals using current state information, optimization, or learned policies.Controllers are often reactive, incorporate execution feedback continuously, and compute locally optimal paths quickly, but may get stuck in local minima or lack completeness and optimality guarantees.

6. Comparative Evaluations

The review evaluates sampling-based planners across 24 scenarios, measuring success, runtime, and solution cost under standardized experimental settings. Results show that planner performance depends on the problem type, with different planners excelling in classical, manipulation, narrow-passage, and extension experiments.

  • Evaluation Setup: 24 scenarios were evaluated using 100 runs per scenario, default OMPL parameters, and scenario-dependent timeouts up to 300s.Experiments ran on a 4-core, 8GB RAM laptop with Ubuntu 16.04; parameter fine-tuning was not performed.
  • Evaluation Setup: Success-cost plots encode time on the x-axis and success rate and solution cost on the y-axis; non-optimizing planners appear as single crosses.A missing color indicates that a planner found no solution path, and solution cost is path length unless stated otherwise.
  • Classical Experiments: In classical experiments, BIT*, EST, FMT, and RRT-Connect perform well in success rate on 4 of 6 scenarios, while BIT* has the best cost convergence in 5 of 6.FMT is slightly slower but solves the Home scenario in 50% of cases; graph-based PRM planners take longer but can reuse graphs for future queries.
  • Overall Findings: No single planner performs best across all scenarios, so planner selection depends substantially on the robot and environment.The evaluation compares several planner classes across classical, manipulation, narrow-passage, and extended planning problems.
  • Manipulation Experiments: In manipulation experiments, RRT-Connect has the best overall success rate and uniquely reaches 100% success in 5 of 6 scenarios.PRM* converges quickly to low-cost solutions in 4 scenarios, while AIT* does so in 3 and RRT* in 1.
  • Narrow Passage Experiments: In narrow-passage experiments, RRT-Connect and TRRT achieve nearly 100% success in 3 scenarios, while no planner solves the Twister scenario.FMT finds low-cost solutions in 5 of 6 scenarios, despite optimal planners generally finding low-cost solutions in only one.
  • Extension Experiments: In extension experiments, EST, BIT*, and RRTConnect solve two constrained scenarios at 100%, while only Kinodynamic-RRT finds solutions in dynamic cases.BIT* finds low-cost solutions in three scenarios, whereas SST* cannot solve any dynamic scenarios.

7. Discussion

The review serves as a reference manual and evaluates planners across 24 challenging scenarios. Its results show broad problem-solving capability but no universally best planner, while hyper-parameter selection remains uncovered and important.

  • The evaluation compared different planners on 24 challenging scenarios.
  • Planning algorithms successfully solve a broad class of problems, including narrow passages, constraints, and dynamics.
  • No single planner performs best across all problems.
  • The experiments did not cover hyper-parameter choice, which can drastically affect motion-planning performance.
  • The review also covers state-space structures, planner categories, motion-planning extensions, and alternative motion-generation frameworks.

8. Other Reviews of Interest

Earlier reviews addressed motion-planning history, sampling-based methods, specific planner variants, and application areas. This review offers a broader, more application-oriented guide that compares popular planners across different problem areas.

  • Earlier work includes a historical treatise on motion planning by Latombe.
  • Tsianos et al. examined sampling-based developments during the early 2000s.
  • Elbanhawi and Simic provided an overview of different planners with general principles.
  • Other reviews focus on specific variants or applications, including asymptotically optimal planners, heuristic approaches, molecular simulations, and UAV planning.
  • This review is broader and more application-oriented because it shows the relative performance of popular planners across problem areas.
Loading 2309.13119v1…