Source-linked AI summary
Potentially Guided Bidirectionalized RRT* for Fast Optimal Path Planning in Cluttered Environments
Zaid Tahir, Ahmed H. Qureshi, Yasar Ayaz, Raheel Nawaz
TL;DR
RRT* provides strong completeness and optimality guarantees but converges slowly, while bidirectional variants can struggle in cluttered environments. The paper introduces PB-RRT* and PIB-RRT*, which use bidirectional potential-gradient guidance, and reports faster convergence with lower memory use across challenging environments.
Problem
RRT* converges slowly to optimal paths, and bidirectional variants based on pure exploration can struggle in highly cluttered environments.
Method
PB-RRT* and PIB-RRT* incorporate artificial potential fields into bidirectional RRT* variants through a bidirectional potential-gradient heuristic.
Results
Across challenging two- and three-dimensional environments, PB-RRT* and PIB-RRT* are reported to converge faster than RRT*, IB-RRT*, and P-RRT*, with less memory consumed.
Takeaways & Limitations
Potentially guided bidirectional trees improve efficiency and convergence while retaining asymptotic optimality and avoiding the local-minima issue associated with APF.
Takeaways & Limitations
The reported future work extends the algorithms to dynamic environments and experience-based planning with machine learning, indicating that these settings remain outside the presented scope.
Abstract
from arXiv · showhide
Rapidly-exploring Random Tree star (RRT*) has recently gained immense popularity in the motion planning community as it provides a probabilistically complete and asymptotically optimal solution without requiring the complete information of the obstacle space. In spite of all of its advantages, RRT* converges to an optimal solution very slowly. Hence to improve the convergence rate, its bidirectional variants were introduced, the Bi-directional RRT* (B-RRT*) and Intelligent Bi-directional RRT* (IB-RRT*). However, as both variants perform pure exploration, they tend to suffer in highly cluttered environments. In order to overcome these limitations, we introduce a new concept of potentially guided bidirectional trees in our proposed Potentially Guided Intelligent Bi-directional RRT* (PIB-RRT*) and Potentially Guided Bi-directional RRT* (PB-RRT*). The proposed algorithms greatly improve the convergence rate and have a more efficient memory utilization. Theoretical and experimental evaluation of the proposed algorithms have been made and compared to the latest state of the art motion planning algorithms under different challenging environmental conditions and have proven their remarkable improvement in efficiency and convergence rate.
1. Introduction
Motion planning seeks collision-free paths without requiring explicit configuration-space representations, but RRT* converges slowly and bidirectional methods can struggle in clutter. The paper proposes potentially guided bidirectional trees and evaluates them against recent optimal planners.
- Explicit configuration-space representations and discretization impose substantial computational burdens, especially for higher-dimensional systems.
- RRT* is probabilistically complete and performs well in high-dimensional spaces, but its convergence to an optimal solution remains slow.
- Bidirectional RRT* variants improve convergence by growing trees from both the initial and goal states, but pure exploration can suffer in cluttered environments.
- PB-RRT* and PIB-RRT* use bidirectional potential-gradient heuristics to guide two trees toward each other for faster convergence.
- The proposed algorithms are evaluated theoretically and experimentally against RRT*, IB-RRT*, and P-RRT* in challenging two- and three-dimensional environments.
2. Problem definition
The problem is to find a minimum-cost collision-free path from an initial configuration to a goal region in an obstacle-containing configuration space. The formulation represents two trees growing from the initial and goal states and connects them into a solution path.
- The configuration space Z contains obstacle states Zobs and traversable states Zfree, with the two-tree search restricted to Zfree.
- Tree Ta grows from zinit and tree Tb grows from zgoal, with their vertices and edges represented within the free configuration space.
- A solution is formed when both trees connect at a shared state, allowing their initial-to-connection and goal-to-connection paths to be concatenated.
- Path cost is defined using the Euclidean metric in the configuration space, while ϑALG records total rewiring per iteration.
- Optimal path planning seeks a collision-free path from zinit to Zgoal that minimizes the cost function J over all feasible paths.
3. Related work
Prior work improves RRT* through potential guidance, bidirectional growth, and intelligent parent selection. These methods retain asymptotic-optimality goals while altering sampling, connection, or rewiring behavior.
- 3.1. P-RRT* Algorithm: P-RRT* extends RRT* with random gradient descent that guides samples toward the goal using artificial potential fields.
- 3.1. P-RRT* Algorithm: RRT* implementations use neighborhood search, parent selection, insertion, rewiring, steering, and cost-based list sorting to build and improve the tree.
- 3.1. P-RRT* Algorithm: P-RRT* retains probabilistic completeness and asymptotic optimality while targeting faster optimal-solution discovery, particularly in cluttered environments.
- 3.2. B-RRT* Algorithm: B-RRT* grows trees from the initial and goal states, connects them through a greedy heuristic, and keeps a lower-cost solution when available.
- 3.3. IB-RRT* Algorithm: IB-RRT* selects the lower-cost parent from neighborhoods in both trees before inserting and rewiring the sampled state.
4. Potentially Guided Bidirectionalized RRT*
PB-RRT* and PIB-RRT* incorporate artificial potential fields into bidirectional RRT* variants through the BPG heuristic. BPG alternates attraction toward the goal and initial state while accounting for nearby obstacles.
- 4.1. PB-RRT* & PIB-RRT*: PB-RRT* combines APF with B-RRT*, while PIB-RRT* combines APF with IB-RRT*, using BPG to guide bidirectional samples.
- 4.1. PB-RRT* & PIB-RRT*: The attractive field pulls samples toward the goal or initial state, while the repulsive field pushes them away from obstacles.
- 4.1. PB-RRT* & PIB-RRT*: BPG transforms a random free-space sample zrand into a potentially guided bidirectional sample zpb before tree expansion.
- 4.1. PB-RRT* & PIB-RRT*: BPG applies goal-directed attraction on even iterations and initial-state attraction on odd iterations, thereby alternating the guidance direction.
- 4.1. PB-RRT* & PIB-RRT*: The nearest-obstacle search supplies the obstacle distance used by the repulsive component of the potential guidance.
10 else
The BPG() heuristic alternates guidance toward the goal and initial roots, using obstacle-distance stopping and bounded potential-gradient steps to bring the bidirectional trees closer.
- 10 else: The heuristic stops when the nearest-obstacle distance falls below a small threshold or when the bounded guidance loop reaches its iteration limit.This stopping condition is applied during both goal-directed and initial-root-directed guidance.
- 10 else: For each guided step, the sample moves downhill in decreasing potential toward the relevant attractive pole using epsilon-sized increments.The goal region is the attractive pole on even iterations, and the initial root is the attractive pole on odd iterations.
- 10 else: Even iterations guide samples toward the goal region, while odd iterations guide them toward the initial root.The alternating directions potentially bring the two trees closer during bidirectional growth.
- 10 else: The guidance-loop limit must balance exploitation and exploration: too many steps overexploit, while too few provide little exploitation.The parameter n controls the number of potential-guidance steps.
5. Analysis
The proposed PB-RRT* and PIB-RRT* retain probabilistic completeness and asymptotic optimality while using BPG() to guide samples toward dense, weak-clearance regions and accelerate convergence.
- 5.1. Probabilistic Completeness: PB-RRT* and PIB-RRT* find feasible solutions with probability approaching one as the iteration count approaches infinity.Their proof uses connected bidirectional trees rooted at the initial and goal states, with alternating BPG() guidance toward the opposite tree.
- 5.2. Asymptotic Optimality: PB-RRT* and PIB-RRT* are asymptotically optimal under the stated conditions for dimension d ≥ 2 and γ > γ∗.The argument follows the RRT* neighborhood and rewiring procedures after potentially guiding sampled states.
- 5.3. Swift Convergence to Optimal Path: The BPG() heuristic guides samples toward δ-exterior regions with weak clearance and toward areas with higher near-vertex intensity.These regions provide the basis for increased rewiring and faster convergence claims.
- 5.3. Swift Convergence to Optimal Path: BPG() increases rewiring per iteration relative to RRT*, with ϑPB−RRT∗ > ϑRRT∗ and ϑPIB−RRT∗ > ϑRRT∗.The paper attributes the faster convergence claim to guiding samples toward higher-intensity regions.
- 5.3. Swift Convergence to Optimal Path: Theorem 5 states that BPG()-guided samples have positive probability of entering δ-exterior regions and that the resulting path rapidly converges toward the optimal path.The theorem combines guidance, rewiring, and convergence properties under the paper’s assumptions.
- 5.4. Complexity Analysis: The proposed algorithms’ computational complexity is a constant factor higher than RRT* while their convergence is reported as faster.The analysis also compares PB-RRT* with B-RRT* and PIB-RRT* with IB-RRT*.
6. Experimental Results
Experiments compare PB-RRT* and PIB-RRT* with asymptotically optimal sampling-based planners across varied environments, showing faster convergence and efficient behavior in cluttered settings.
- Environment comparisons: PIB-RRT* found the optimum fastest in highly cluttered environments, while PB-RRT* also outperformed IB-RRT*, P-RRT*, and RRT* in several tests.In Fig. 1, PIB-RRT* required 198,608 average iterations and RRT* failed 70% of runs; in Fig. 3, PIB-RRT* required 20,539 iterations while RRT* failed 50%.
- Cost and running time: PIB-RRT* and PB-RRT* converged to optimal cost faster than RRT* in an obstacle-filled 3D environment.The comparison uses Euclidean path cost versus running time and attributes the faster convergence to the BPG() heuristic combined with bidirectional tree search.
- Complexity behavior: Running-time ratios of PIB-RRT* and PB-RRT* relative to RRT* settle at a constant value as iterations increase.This behavior agrees with the computational-complexity analysis and Theorem 6.
- Parameter analysis: The BPG() parameter k controls the exploration–exploitation balance: lower values favor exploration, while higher values favor exploitation.The experiments indicate that an appropriate balance is needed for different environments.
- Initial-solution comparison: 30 samples enabled PIB-RRT* to find an initial path, compared with 1,398 samples for RRT* in the same environment.The RRT* path was non-optimal, whereas PIB-RRT* found the solution with substantially fewer samples.
7. Conclusions and Future work
The paper concludes that PIB-RRT* and PB-RRT* combine bidirectional potential guidance with asymptotically optimal sampling to accelerate path planning. Future work targets dynamic environments and machine-learning-assisted reuse of feasible paths.
- Conclusions: PIB-RRT* and PB-RRT* use the BPG() heuristic to guide two RRT* trees toward each other while retaining asymptotic optimality.The authors report comparable computational complexity to IB-RRT*, B-RRT*, and RRT*, avoidance of APF local minima, faster convergence, and lower memory use.
- Future work: The authors plan to extend the algorithms to dynamic environments and use machine learning to cache feasible paths for experience-based planning.The stated goal is informed search in new unseen environments.
8. Ackowledgements
The authors acknowledge Dr. Sertac Karaman of MIT for sharing an RRT* implementation.
- Acknowledgements: The authors acknowledge Dr. Sertac Karaman of MIT for sharing the RRT* implementation.