In the field of robot technology, path planning is a critical component that enables autonomous navigation in various environments. As mobile robots become increasingly integral to applications like logistics, surveillance, and domestic assistance, the need for efficient and robust path planning algorithms has grown. Traditional methods, such as A* and artificial potential fields, often struggle with dynamic or complex scenarios, leading to the adoption of sampling-based approaches like the Rapidly-exploring Random Tree (RRT) algorithm. RRT excels in exploring high-dimensional spaces quickly, but its inherent randomness results in suboptimal paths and inefficiencies, particularly in constrained environments like narrow passages. To address these limitations, the RRT* algorithm was developed, offering asymptotic optimality by continuously refining paths through iterative sampling. However, RRT* still faces challenges in convergence speed and search efficiency, especially in robot technology applications where real-time performance is crucial. In this article, I present an improved RRT* algorithm that enhances path planning for indoor mobile robots by incorporating goal-biased expansion, an advanced ellipse sampling strategy, and path smoothing techniques. This approach not only accelerates convergence but also ensures smoother, more practical paths for robot technology deployments.
The foundation of robot technology in path planning lies in algorithms that can handle uncertainty and complexity. RRT* builds upon the basic RRT by introducing a rewiring process that optimizes paths over time. Specifically, after generating a new node, RRT* evaluates nearby nodes to find cheaper connections, gradually improving the path cost. The algorithm operates in a free configuration space $X_{\text{free}}$, starting from an initial node $x_{\text{start}}$ and expanding toward a goal node $x_{\text{goal}}$. For each iteration, a random sample $x_{\text{rand}}$ is drawn from $X_{\text{free}}$, and the nearest node $x_{\text{nearest}}$ in the tree is identified. A new node $x_{\text{new}}$ is then generated by steering from $x_{\text{nearest}}$ toward $x_{\text{rand}}$ with a step size $\eta$, as shown in the equation: $$x_{\text{new}} = x_{\text{nearest}} + \eta \frac{x_{\text{rand}} – x_{\text{nearest}}}{\|x_{\text{rand}} – x_{\text{nearest}}\|}.$$ If the path between $x_{\text{nearest}}$ and $x_{\text{new}}$ is obstacle-free, $x_{\text{new}}$ is added to the tree, and a rewiring step checks for better parent nodes within a neighborhood radius. This process continues until a path to $x_{\text{goal}}$ is found and optimized over multiple iterations. However, in robot technology, the uniform sampling of RRT* leads to excessive exploration of irrelevant regions, slowing down convergence. Moreover, in environments with narrow channels, the probability of sampling critical areas is low, resulting in prolonged search times and inefficient paths. These issues highlight the need for enhancements tailored to the demands of modern robot technology.
To overcome the limitations of RRT* in robot technology, I propose an improved algorithm that integrates goal-biased expansion. This method reduces the aimless exploration of traditional RRT* by directing the tree growth toward the goal. In standard RRT*, the expansion toward $x_{\text{rand}}$ is purely random, which can waste computational resources. In contrast, the goal-biased approach introduces attraction factors that bias the sampling toward $x_{\text{goal}}$, while maintaining randomness to avoid local minima. The modified steering function is given by: $$x_{\text{new}} = x_{\text{nearest}} + q_1 \frac{x_{\text{rand}} – x_{\text{nearest}}}{\|x_{\text{rand}} – x_{\text{nearest}}\|} + q_2 \frac{x_{\text{goal}} – x_{\text{nearest}}}{\|x_{\text{goal}} – x_{\text{nearest}}\|},$$ where $q_1$ and $q_2$ are tuning parameters representing the random and goal-directed components, respectively. By setting $q_2 > q_1$ when no obstacles are detected, the tree expands efficiently toward the goal, accelerating initial path discovery. If an obstacle is encountered, the values are swapped to $q_1 > q_2$, promoting random exploration to escape local minima. This adaptive behavior is particularly beneficial in robot technology for navigating cluttered indoor spaces, as it balances exploration and exploitation, leading to faster convergence and reduced computation time.
Another key improvement in this robot technology-focused algorithm is the enhanced ellipse sampling strategy, which builds upon the Informed-RRT* concept. After an initial path is found, the sampling space is restricted to an elliptical region defined by the current best path cost $c_{\text{best}}$ and the straight-line distance $c_{\min}$ between $x_{\text{start}}$ and $x_{\text{goal}}$. This ellipse contains all points $x$ where the sum of distances to $x_{\text{start}}$ and $x_{\text{goal}}$ is less than or equal to $c_{\text{best}}$, mathematically expressed as: $$X_f^* = \{ x \in X \mid \|x – x_{\text{start}}\| + \|x – x_{\text{goal}}\| \leq c_{\text{best}} \}.$$ Samples within this ellipse, denoted $x_{\text{ellipse}}$, are generated using: $$x_{\text{ellipse}} = x_{\text{center}} + C L x_{\text{ball}},$$ where $x_{\text{center}} = (x_{\text{start}} + x_{\text{goal}})/2$ is the ellipse center, $x_{\text{ball}}$ is a uniform sample from a unit ball, $C$ is a rotation matrix aligning the ellipse with the world coordinates, and $L$ is a diagonal matrix scaling the ellipse based on $c_{\text{best}}$ and $c_{\min}$. As $c_{\text{best}}$ decreases with each iteration, the ellipse shrinks, focusing sampling on promising regions. To further optimize this process, I incorporate path pruning: once a feasible path is found, redundant nodes are removed by greedily connecting non-adjacent nodes if the path remains obstacle-free. This reduces $c_{\text{best}}$ more rapidly, tightening the ellipse and accelerating convergence. This refinement is crucial in robot technology for handling narrow passages, as it increases the sampling density in critical areas, leading to more efficient path optimization.
Path smoothing is essential in robot technology to ensure that generated paths are practical for real-world navigation. The raw paths from RRT* often contain sharp turns and unnecessary detours, which can cause jerky movements and increased energy consumption in mobile robots. To address this, I apply Bézier curves for post-processing. A Bézier curve of degree $n$ is defined by control points $P_i$ and a parameter $t \in [0,1]$: $$P(t) = \sum_{i=0}^{n} \binom{n}{i} (1-t)^{n-i} t^i P_i.$$ For path smoothing, I use cubic Bézier curves (n=3), which provide a balance between simplicity and smoothness: $$P(t) = (1-t)^3 P_0 + 3(1-t)^2 t P_1 + 3(1-t)t^2 P_2 + t^3 P_3.$$ The control points are selected around path转折点s, such that $P_0$ and $P_3$ coincide with adjacent nodes, and $P_1$ and $P_2$ are chosen to ensure the curve avoids obstacles and satisfies curvature constraints. For a robot with a minimum turning radius $R$, the maximum curvature $k_{\max} = 1/R$ must not be exceeded at any point on the curve. The curvature $k(t)$ is computed as: $$k(t) = \frac{\|P'(t) \times P”(t)\|}{\|P'(t)\|^3} \leq k_{\max},$$ where $P'(t)$ and $P”(t)$ are the first and second derivatives of the curve. By enforcing this constraint, the smoothed path becomes feasible for robot technology applications, enabling smooth and stable motion. This step not only enhances the quality of the path but also improves the overall performance of robot technology in dynamic environments.
To validate the improved RRT* algorithm, I conducted experiments in simulation and real-world settings, focusing on metrics relevant to robot technology, such as computation time, path length, and success rate. The simulation used MATLAB R2018b on a Windows 10 system with an Intel i7-6500U CPU and 8GB RAM. Three distinct environments were tested: a pillar-filled space, a narrow passage, and a T-shaped obstacle layout, each with a map size of 1000mm × 1000mm. For each environment, the algorithms—standard RRT*, Informed-RRT*, and the improved RRT*—were run 100 times with parameters set to a maximum of 1500 iterations, a step size $\eta$ of 30mm (3% of map width), and for the improved algorithm, $q_1 = 30$mm and $q_2 = 50$mm. The results demonstrated significant advantages for the improved RRT* in robot technology scenarios. In the pillar environment, the improved algorithm reduced the average computation time by over 60% compared to RRT* and 80% compared to Informed-RRT*, while also shortening the path length by approximately 9%. In narrow passages, where traditional algorithms often fail, the improved RRT* achieved a success rate of over 90%, compared to 60% for Informed-RRT* and lower for RRT*. The table below summarizes the average performance across environments, highlighting the efficiency gains in robot technology applications.
| Algorithm | Average Time (s) | Average Path Length (mm) | Success Rate in Narrow Passages (%) |
|---|---|---|---|
| RRT* | 6.40 | 1035.37 | 40 |
| Informed-RRT* | 3.53 | 1017.73 | 60 |
| Improved RRT* | 1.25 | 939.00 | 90 |
The real-world experiments involved a TurtleBot3 Burger robot equipped with a Raspberry Pi 3, OpenCR board, and LIDAR sensor, operating in an ROS-based environment. The robot was tasked with navigating a narrow passage in a known map, and the improved RRT* algorithm was applied for global path planning. The results showed a computation time of 0.71 seconds and a path length of 10.81 meters, outperforming RRT* (4.32 seconds, 12.84 meters) and Informed-RRT* (2.13 seconds, 11.28 meters). This practical validation underscores the algorithm’s suitability for robot technology, as it enables faster, more reliable navigation in constrained spaces. The integration of goal-biased expansion, ellipse sampling, and path smoothing not only improves efficiency but also enhances the robustness of robot technology systems, making them better adapted to real-world challenges.
In conclusion, the improved RRT* algorithm presented here addresses key issues in robot technology path planning, such as slow convergence and inefficient sampling in narrow environments. By combining goal-biased expansion, an advanced ellipse sampling strategy with path pruning, and Bézier curve smoothing, the algorithm achieves faster computation times, shorter paths, and higher success rates. These advancements are critical for the evolution of robot technology, as they enable more autonomous and efficient navigation in complex indoor settings. Future work could focus on extending this approach to dynamic environments, incorporating real-time obstacle avoidance, and adapting it to multi-robot systems. As robot technology continues to advance, such innovations will play a vital role in expanding the capabilities of mobile robots across various domains.