Source-linked AI summary
Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments
Ahmed Hussain Qureshi, Yasar Ayaz
TL;DR
Motion-planning RRT* offers asymptotic optimality but can converge slowly and consume substantial memory, while B-RRT* retains computational limitations. The paper introduces IB-RRT*, combining bidirectional trees with intelligent sample insertion under uniform sampling. Experiments and analysis report faster convergence, lower memory use, and almost-sure optimal-path convergence than the compared methods.
Problem
RRT* provides optimality but remains limited by slow convergence and large memory requirements, while B-RRT* can be computationally expensive and slow to converge.
Method
IB-RRT* uses bidirectional trees and an intelligent sample insertion heuristic while retaining uniform sampling.
Results
IB-RRT* is reported to converge faster, consume less memory, and achieve almost-sure convergence to an optimal path than RRT* and B-RRT*.
Takeaways & Limitations
IB-RRT* enables rapid convergence to optimal solutions without tuning the sampling operation for optimal paths.
Takeaways & Limitations
The analysis assumes continuously distributed, unbiased samples and an environment containing obstacles that hinder expansion of the two trees.
Abstract
from arXiv · showhide
The sampling based motion planning algorithm known as Rapidly-exploring Random Trees (RRT) has gained the attention of many researchers due to their computational efficiency and effectiveness. Recently, a variant of RRT called RRT* has been proposed that ensures asymptotic optimality. Subsequently its bidirectional version has also been introduced in the literature known as Bidirectional-RRT* (B-RRT*). We introduce a new variant called Intelligent Bidirectional-RRT* (IB-RRT*) which is an improved variant of the optimal RRT* and bidirectional version of RRT* (B-RRT*) algorithms and is specially designed for complex cluttered environments. IB-RRT* utilizes the bidirectional trees approach and introduces intelligent sample insertion heuristic for fast convergence to the optimal path solution using uniform sampling heuristics. The proposed algorithm is evaluated theoretically and experimental results are presented that compares IB-RRT* with RRT* and B-RRT*. Moreover, experimental results demonstrate the superior efficiency of IB-RRT* in comparison with RRT* and B-RRT in complex cluttered environments.
1 Introduction
Motion planning seeks collision-free robot paths, but deterministic and discretization-based methods can be computationally inefficient in practical or higher-dimensional settings. RRT* improves on RRT by offering eventual optimality, while B-RRT* still faces convergence and computational limitations.
- Motivation: Motion planning finds collision-free paths from an initial state to a goal while avoiding obstacles or other agents.Its applications span robotics, assembly maintenance, animation, surgery, manufacturing, and daily life.
- Limitations of Existing Methods: Complete planning algorithms converge to a solution in finite time when one exists but are computationally inefficient for many practical problems.
- Limitations of Existing Methods: Resolution-complete methods require resolution tuning, while Artificial Potential Fields suffer from local minima and perform poorly in narrow passages.
- Limitations of Existing Methods: Exact roadmaps discretize the search space, making them computationally expensive in higher-dimensional spaces.
- RRT-Based Methods: RRT* eventually converges to an optimal path but has slow convergence and large memory requirements from its many iterations.
- RRT-Based Methods: B-RRT* uses a hybrid neighbor-search and greedy connection heuristic that slows convergence and increases computational expense.
2 Problem Definition
The paper formulates motion planning in a Euclidean configuration space partitioned into obstacle and obstacle-free regions. It defines feasible and optimal paths between an initial state and a goal region, with Euclidean distance as the cost.
- Space and Trees: The state space X is a subset of R^n with dimension n ≥ 2, containing obstacle, obstacle-free, and goal regions.
- Space and Trees: Two random trees, Ta and Tb, grow within the obstacle-free space, with vertices and edges represented by V and E.
- Geometric Definitions: The configuration space uses Euclidean distance, and closed balls define neighborhoods around configuration states.
- Planning Objectives: A feasible path connects xinit to Xgoal entirely within Xfree; if no such path exists, the algorithm reports failure.
- Planning Objectives: The optimal-path problem seeks a collision-free path in Xfree with minimum cost, where cost is measured by Euclidean distance.
3 RRT* Algorithm
RRT* repeatedly samples obstacle-free space, connects samples through collision-free trajectories, selects low-cost parents, and rewires nearby vertices. These operations provide asymptotic optimality while improving computational efficiency over the original implementation.
- Algorithm Overview: The modified RRT* reduces calls to the ObstacleFree procedure to improve computational efficiency.
- Core Procedures: Random Sampling returns independent, uniformly distributed samples from Xfree.
- Core Procedures: NearVertices selects tree vertices within radius γ(log i/i)^(1/n) of a sample.
- Core Procedures: GetSortedList orders nearby candidate vertices by ascending path cost for parent selection.
- Core Procedures: Steering generates a straight trajectory between two states through small discrete steps.
- Optimization: RRT* rewires a nearby vertex when routing through the new sample yields a shorter collision-free path, providing asymptotic optimality.
4 B-RRT* algorithm
B-RRT* extends RRT* with two trees and a connection procedure. It samples and expands one tree, then attempts to connect the new node to the other tree using a modified greedy RRT-Connect heuristic.
- Algorithm Structure: B-RRT* maintains two trees and reuses RRT* procedures, adding bidirectional connection operations.
- Additional Procedures: Extend moves from x1 toward x2 and returns a new node closer to x2.
- Additional Procedures: Connect performs RRT* operations using x1 as the random-sample role while searching neighboring vertices in the other tree.
- Iteration: After inserting a random sample into the active tree, B-RRT* finds a nearby node in the opposite tree and executes Connect.
5 IB-RRT* algorithm
IB-RRT* builds two trees incrementally in cluttered configuration spaces, using uniform random samples, intelligent parent selection, and region-limited tree connection. The procedure returns a globally connected path when the connection is feasible and improves on the existing path cost.
- IB-RRT* is designed for motion planning in complex cluttered environments where configuration-space exploration is difficult.
- The algorithm samples xrand uniformly from the obstacle-free configuration space and constructs near-vertex sets for both trees.A radius-r ball centered at xrand defines the candidate neighborhoods; empty sets fall back to each tree’s closest vertex.
- GetBestTreeParent selects the lower-cost tree and its best parent vertex for inserting each random sample.The boolean flag records which tree was selected, while the procedure may also return a final connecting path.
- ConnectTrees updates the global path only when concatenating the two collision-free paths yields lower cost than the existing end-to-end path.Connection succeeds only when both trees have near vertices in the ball centered at xrand.
- Unlike the greedy connect heuristic, IB-RRT* connects the trees only within the ball region around xrand, producing an end-to-end global path.
6 Analysis
IB-RRT* is presented as asymptotically optimal and probabilistically complete, while its intelligent insertion and rewiring strategy is intended to accelerate convergence in cluttered spaces. Theoretical analysis and experiments compare its computational complexity and path-finding performance with RRT* and bidirectional RRT variants.
- Asymptotic Optimality: IB-RRT* is argued to inherit probabilistic completeness from RRT* because it uses the same random-sampling operation with bidirectional trees and intelligent sample insertion.The paper defines probabilistic completeness as the probability of finding a path approaching one as samples approach infinity.
- Asymptotic Optimality: IB-RRT* is argued to inherit RRT*’s asymptotic optimality because both trees are generated like RRT* and connected through the random sample without an extra connection heuristic.The connection occurs when the sampling ball contains near vertices from both trees.
- Rapid Convergence to Optimal Path: By increasing the number of path variations minimized per iteration, IB-RRT* can greatly improve its convergence rate to an optimal solution.This conclusion is stated as Corollary 1 and supports the rapid-convergence analysis.
- Rapid Convergence to Optimal Path: IB-RRT* inserts each random sample into the tree whose initial state is closer, targeting regions with higher near-vertex intensity and enabling more rewiring per iteration.The insertion rule compares the costs of the two paths to the random sample.
- Computational Complexity: The running time per iteration of IB-RRT* is a constant factor higher than RRT* and BiRRT, while the paper also concludes it has the same computational complexity as RRT*.The running-time ratio is reported to approach a constant as iterations increase.
- Experimental Evaluation: Experiments compare IB-RRT*, RRT*, and B-RRT* under constant configuration-space conditions, with figures showing IB-RRT* and RRT* tree expansion.The supplied experimental passages identify these comparisons but do not provide the complete Table 1 values.
7 Experimental Results
Experiments across complex cluttered 2D and 3D environments show that IB-RRT* reaches optimal paths faster and with lower resource use than B-RRT* and RRT*. Its convergence advantage is attributed to intelligent sample insertion while retaining uniform sampling.
- 2-D and 3-D environments: In a 3-D barrier environment, IB-RRT* reached an optimal path after 204,321 iterations, compared with 838,692 for B-RRT* and 1,961,825 for RRT*.The authors attribute the faster convergence to maximizing rewiring per iteration through intelligent sample insertion.
- Convergence: Across the tested environments, IB-RRT* rapidly converged to optimal solutions, followed by B-RRT* and then RRT*.In the complex maze, RRT* did not sample near the goal even after many iterations, whereas IB-RRT* explored the space in a few thousand iterations.
- Computational cost: As iterations increased, IB-RRT*'s running-time ratio approached a constant; in the reported environment, viable-path computation took four times BiRRT's time and 1.4 times RRT*'s.Before the ratio stabilized, IB-RRT*'s computational complexity remained fairly lower than BiRRT and almost equal to RRT*.
8 Conclusions and Future work
The paper concludes that IB-RRT* combines near-RRT* computational complexity with almost-sure optimal convergence and faster convergence than RRT* and B-RRT*. It also reports lower memory use and identifies real-time motion planning as an application scope.
- Conclusions: IB-RRT* has almost similar computational complexity to RRT* and BiRRT while providing almost-sure convergence to an optimal path solution.These properties are supported by both analytical and experimental results.
- Conclusions: IB-RRT* converges more rapidly and consumes less memory than RRT* and B-RRT* when reaching the optimal solution.The lower memory use is linked to fewer iterations, with each iteration consuming memory.
- Future work: The proposed planner is presented as relevant to real-time motion planning without tuning the sampling operation for optimal paths.The authors anticipate applying IB-RRT* to online motion planning of animated characters in complex 3-D environments.