InBi-RRT: Incremental Bidirectional Tree Based Real-Time Path Planning/Replanning in Unknown Non-Convex Environments
Bo Cui, Yang Li, Weisheng Yan, ao feng, Zhanwei Yang, Rongxin Cui
AI summary
Problem
Real-time path planning in unknown non-convex environments is challenging because dynamic obstacle updates invalidate existing paths, while narrow passages restrict connectivity and force costly full replanning.
Approach
The framework grows a reverse tree from the goal and incrementally expands a reusable forward tree from the robot’s position, using a cost-guided heuristic to quickly repair invalid paths without rebuilding search structures.
Key results
- Up to 5.5× faster replanning than RT-RRT and 22× faster than RRTX
- Paths up to 19.8% shorter than RRTX under identical sample counts
- Efficiently navigates narrow passages by reusing previously explored forward-tree branches
- Validated in large-scale unknown simulations and real-world indoor maze environments
Why it matters
Enables reliable, real-time autonomous navigation for robots operating in complex, dynamic, and poorly mapped spaces like caves, underground structures, or cluttered indoor environments.
Abstract
Real-time path planning in unknown non-convex environments is challenging, as obstacle updates can invalidate existing paths while narrow passages restrict feasible connectiv- ity. This paper presents InBi-RRT, an incremental bidirectional tree-based framework that grows a reverse tree from the goal and maintains a reusable forward tree from the start. When the current path becomes invalid, a cost-guided expansion selectively extends the forward tree to establish collision-free connections with the reverse tree, followed by backtracking and lightweight path optimization for efficient repair. Simulation results in unknown and non-convex scenarios demonstrate that InBi-RRT achieves significantly faster replanning than baseline methods, being up to 5.5× faster than RT-RRT and 22× faster than RRTX, with paths up to 19.8% shorter than RRTX under the same sample count. Furthermore, real-world experiments in an indoor maze-like environment verify the practicality and robustness of the proposed planner in unknown non-convex scenarios.