Asymptotically Optimal Sampling-Based Motion Planning Methods
arXiv:2009.10484 · doi:10.1146/annurev-control-061920-093753
Abstract
Motion planning is a fundamental problem in autonomous robotics that requires finding a path to a specified goal that avoids obstacles and takes into account a robot's limitations and constraints. It is often desirable for this path to also optimize a cost function, such as path length. Formal path-quality guarantees for continuously valued search spaces are an active area of research interest. Recent results have proven that some sampling-based planning methods probabilistically converge toward the optimal solution as computational effort approaches infinity. This survey summarizes the assumptions behind these popular asymptotically optimal techniques and provides an introduction to the significant ongoing research on this topic.
arXiv commentPosted with permission from the Annual Review of Control, Robotics, and Autonomous Systems, Volume 4. Copyright 2021 by Annual Reviews, https://www.annualreviews.org/. 25 pages. 2 figures
References in corpus (10)
- Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments
- Potential Functions based Sampling Heuristic For Optimal Path Planning
- Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search
- Adaptively Informed Trees (AIT*): Fast Asymptotically Optimal Path Planning through Adaptive Heuristics
- dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning
- Sampling-based Incremental Information Gathering with Applications to Robotic Exploration and Environmental Monitoring
- Sampling-based optimal kinodynamic planning with motion primitives
- An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning
- Dispertio: Optimal Sampling for Safe Deterministic Sampling-Based Motion Planning
- Toward Asymptotically-Optimal Inspection Planning via Efficient Near-Optimal Graph Search
Cited by in corpus (16)
- AIT* and EIT*: Asymmetric bidirectional sampling-based path planning
- A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approaches
- Motion Planning for Robotics: A Review for Sampling-based Planners
- OpenStreetMap-based Autonomous Navigation With LiDAR Naive-Valley-Path Obstacle Avoidance
- Estimated Informed Anytime Search for Sampling-Based Planning via Adaptive Sampler
- Effort Informed Roadmaps (EIRM*): Efficient Asymptotically Optimal Multiquery Planning by Actively Reusing Validation Effort
- Tree-Based Grafting Approach for Bidirectional Motion Planning with Local Subsets Optimization
- Asymptotically Optimal Path Planning With an Approximation of the Omniscient Set
- Genetic Informed Trees (GIT*): Path Planning via Reinforced Genetic Programming Heuristics
- Kernel-based diffusion approximated Markov decision processes for autonomous navigation and control on unstructured terrains
- Informed Sampling-based Collision Avoidance with Least Deviation from the Nominal Path
- APT*: Asymptotically Optimal Motion Planning via Adaptively Prolated Elliptical R-Nearest Neighbors
- Constrained Nonlinear Kaczmarz Projection on Intersections of Manifolds for Coordinated Multi-Robot Mobile Manipulation
- Better Safe Than Sorry: Enhancing Arbitration Graphs for Safe and Robust Autonomous Decision-Making
- Enhancing Sampling-based Planning with a Library of Paths
- CAT-RRT: Motion Planning that Admits Contact One Link at a Time