Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs

Abstract

In this paper, we present Batch Informed Trees (BIT*), a planning algorithm based on unifying graph- and sampling-based planning techniques. By recognizing that a set of samples describes an implicit random geometric graph (RGG), we are able to combine the efficient ordered nature of graph-based techniques, such as A*, with the anytime scalability of sampling-based algorithms, such as Rapidly-exploring Random Trees (RRT). BIT* uses a heuristic to efficiently search a series of increasingly dense implicit RGGs while reusing previous information. It can be viewed as an extension of incremental graph-search techniques, such as Lifelong Planning A* (LPA*), to continuous problem domains as well as a generalization of existing sampling-based optimal planners. It is shown that it is probabilistically complete and asymptotically optimal. We demonstrate the utility of BIT* on simulated random worlds in ${\mathbb{R}}^2$ and ${\mathbb{R}}^8$ and manipulation problems on CMU's HERB, a 14-DOF two-armed robot. On these problems, BIT* finds better solutions faster than RRT, RRT*, Informed RRT*, and Fast Marching Trees (FMT*) with faster anytime convergence towards the optimum, especially in high dimensions.

8 Pages. 6 Figures. Video available at http://www.youtube.com/watch?v=TQIoCC48gp4

References in corpus (1)

• Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic

Cited by in corpus (30)

• 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
• AIT* and EIT*: Asymmetric bidirectional sampling-based path planning
• Active SLAM: A Review On Last Decade
• MotionBenchMaker: A Tool to Generate and Benchmark Motion Planning Datasets
• Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints
• Motion Planning for Robotics: A Review for Sampling-based Planners
• Goal-conditioned dual-action imitation learning for dexterous dual-arm robot manipulation
• A Hybrid Method for Online Trajectory Planning of Mobile Robots in Cluttered Environments
• Neural Manipulation Planning on Constraint Manifolds
• A Fully-autonomous Framework of Unmanned Surface Vehicles in Maritime Environments using Gaussian Process Motion Planning
• Streamlines for Motion Planning in Underwater Currents
• Autonomous search of an airborne release in urban environments using informed tree planning
• Task and Motion Informed Trees (TMIT*): Almost-Surely Asymptotically Optimal Integrated Task and Motion Planning
• End-to-end deep learning-based framework for path planning and collision checking: bin picking application
• Enhance Connectivity of Promising Regions for Sampling-based Path Planning
• Flexible Informed Trees (FIT*): Adaptive Batch-Size Approach in Informed Sampling-Based Path Planning
• Learning from Experience for Rapid Generation of Local Car Maneuvers
• Safe Navigation using Density Functions
• Elliptical K-Nearest Neighbors -- Path Optimization via Coulomb's Law and Invalid Vertices in C-space Obstacles
• Informed Sampling for Asymptotically Optimal Path Planning (Consolidated Version)
• Tree-Based Grafting Approach for Bidirectional Motion Planning with Local Subsets Optimization
• PC-Planner: Physics-Constrained Self-Supervised Learning for Robust Neural Motion Planning with Shape-Aware Distance Function
• Asymptotically Optimal Path Planning With an Approximation of the Omniscient Set
• Advanced BIT* (ABIT*): Sampling-Based Planning with Advanced Graph-Search Techniques
• CVaR-based Flight Energy Risk Assessment for Multirotor UAVs using a Deep Energy Model
• Off the Beaten Track: Laterally Weighted Motion Planning for Local Obstacle Avoidance
• Informed Sampling-based Collision Avoidance with Least Deviation from the Nominal Path
• CoverLib: Classifiers-equipped Experience Library by Iterative Problem Distribution Coverage Maximization for Domain-tuned Motion Planning