Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search

Abstract

Path planning in robotics often requires finding high-quality solutions to continuously valued and/or high-dimensional problems. These problems are challenging and most planning algorithms instead solve simplified approximations. Popular approximations include graphs and random samples, as respectively used by informed graph-based searches and anytime sampling-based planners. Informed graph-based searches, such as A*, traditionally use heuristics to search a priori graphs in order of potential solution quality. This makes their search efficient but leaves their performance dependent on the chosen approximation. If its resolution is too low then they may not find a (suitable) solution but if it is too high then they may take a prohibitively long time to do so. Anytime sampling-based planners, such as RRT*, traditionally use random sampling to approximate the problem domain incrementally. This allows them to increase resolution until a suitable solution is found but makes their search dependent on the order of approximation. Arbitrary sequences of random samples approximate the problem domain in every direction simultaneously and but may be prohibitively inefficient at containing a solution. This paper unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT* solves continuous path planning problems efficiently by using sampling and heuristics to alternately approximate and search the problem domain. Its search is ordered by potential solution quality, as in A*, and its approximation improves indefinitely with additional computational time, as in RRT*. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems.

International Journal of Robotics Research (IJRR). 32 Pages. 16 Figures

References in corpus (2)

• Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic
• Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs

Cited by in corpus (25)

• Adaptively Informed Trees (AIT*): Fast Asymptotically Optimal Path Planning through Adaptive Heuristics
• Asymptotically Optimal Sampling-Based Motion Planning Methods
• AIT* and EIT*: Asymmetric bidirectional sampling-based path planning
• Motion Planning for Robotics: A Review for Sampling-based Planners
• Safety-aware time-optimal motion planning with uncertain human state estimation
• Tube RRT*: Efficient Homotopic Path Planning for Swarm Robotics Passing-Through Large-Scale Obstacle Environments
• Reaching Through Latent Space: From Joint Statistics to Path Planning in Manipulation
• Flexible Informed Trees (FIT*): Adaptive Batch-Size Approach in Informed Sampling-Based Path Planning
• Learning from Experience for Rapid Generation of Local Car Maneuvers
• Elliptical K-Nearest Neighbors -- Path Optimization via Coulomb's Law and Invalid Vertices in C-space Obstacles
• 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
• Generation of Paths in a Maze using a Deep Network without Learning
• Tree-Based Grafting Approach for Bidirectional Motion Planning with Local Subsets Optimization
• iA*: Imperative Learning-based A* Search for Path Planning
• Advanced BIT* (ABIT*): Sampling-Based Planning with Advanced Graph-Search Techniques
• Speeding up deep neural network-based planning of local car maneuvers via efficient B-spline path construction
• Genetic Informed Trees (GIT*): Path Planning via Reinforced Genetic Programming Heuristics
• Near Time-Optimal Hybrid Motion Planning for Timber Cranes
• Real-Time Adaptive Motion Planning via Point Cloud-Guided, Energy-Based Diffusion and Potential Fields
• Global Tensor Motion Planning
• APT*: Asymptotically Optimal Motion Planning via Adaptively Prolated Elliptical R-Nearest Neighbors
• Nearest-Neighbourless Asymptotically Optimal Motion Planning with Fully Connected Informed Trees (FCIT*)
• Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities
• CAT-RRT: Motion Planning that Admits Contact One Link at a Time