In the field of robot technology, path planning is a fundamental problem that enables autonomous navigation and task execution. It involves finding an optimal path from a start point to a goal point while avoiding obstacles, with criteria such as minimal path length and fewest turns. Traditional methods include graph search algorithms like A*, model-based approaches, machine learning techniques, and sampling-based methods. Among these, sampling-based approaches, particularly the Rapidly-exploring Random Tree (RRT) algorithm and its variants, have gained popularity due to their efficiency in high-dimensional spaces. However, RRT* algorithm, an optimal version of RRT, often suffers from long computation times and poor adaptability to environmental changes. In this paper, we propose an enhanced RRT* algorithm that addresses these limitations through adaptive step sizing, improved sampling strategies, and path optimization techniques. Our contributions focus on increasing the efficiency and smoothness of paths in robot technology applications, making it suitable for real-world scenarios.
Path planning in robot technology typically involves modeling the environment to represent obstacles and free space. We employ a grid-based map approach, where the environment is discretized into a 500×500 grid. Each cell stores a value of “1” for obstacles or “0” for free space, allowing for straightforward collision detection. The start point is set at (20, 480) and the goal at (480, 20), creating a challenging navigation task. This modeling method provides a clear representation for testing algorithms in both simple and complex obstacle environments, as commonly used in robot technology simulations.
The standard RRT* algorithm builds a tree from the start point by randomly sampling points in the space, extending the tree towards these samples with a fixed step size, and performing rewiring to optimize the path. While it guarantees asymptotic optimality, its random nature can lead to inefficiencies. For instance, the fixed step size may not adapt well to dense or sparse obstacle regions, resulting in unnecessary computations. In robot technology, where real-time performance is crucial, such drawbacks can hinder deployment. Our improved RRT* algorithm introduces a reward-based adaptive step size mechanism, which dynamically adjusts the step length based on environmental feedback, enhancing adaptability in various robot technology settings.
To improve the sampling efficiency, we combine biased goal sampling with greedy sampling. The biased goal sampling directs the tree growth towards the goal by generating temporary samples along the line between random points and the goal, while greedy sampling occasionally sets the goal as the sample directly. This reduces random exploration and focuses on promising regions. Additionally, we impose a path length threshold to discard samples that would lead to overly long paths, further refining the search. This strategy is particularly beneficial in robot technology applications where computational resources are limited, as it minimizes unnecessary node expansions and accelerates convergence.
The adaptive step size is inspired by reinforcement learning concepts, where a reward function guides the step length adjustments. Let $R(t)$ denote the reward at time step $t$, and $\Delta R(t+1)$ represent the change in reward based on whether the robot avoids obstacles. The reward update is given by:
$$ R(t+1) = R(t) + \Delta R(t+1) $$
where $\Delta R(t+1)$ is computed as:
$$ \Delta R(t+1) = \frac{1}{2} – |R(t)| $$
Here, the value 2 is chosen empirically for balance. To prevent rapid reward accumulation that could cause unstable step sizes, we introduce an inertia factor $\theta(t)$ that decreases linearly over iterations. The inertia factor is defined as:
$$ \theta(1) = \theta_{\text{max}} $$
$$ \theta(t) = \theta_{\text{max}} – \frac{\theta_{\text{max}} – \theta_{\text{min}}}{T^2} t^2 $$
where $\theta_{\text{max}}$ and $\theta_{\text{min}}$ are the maximum and minimum inertia values, $T$ is the total number of iterations, and $t$ is the current iteration. The step size $\lambda(t+1)$ is then determined by combining the previous step size with the reward-based change:
$$ \lambda(t+1) = \theta(t) \lambda(t) + [1 – \theta(t)] \Delta \lambda(t+1) $$
and $\Delta \lambda(t+1)$ is calculated as:
$$ \Delta \lambda(t+1) = \lambda_{\text{max}} \cdot \tan^{-1} \left( \frac{R(t+1) + 1}{2} \right) $$
where $\lambda_{\text{max}}$ is the maximum allowable step size. This formulation allows the step size to shrink in obstacle-dense areas and expand in open spaces, improving the algorithm’s responsiveness in dynamic robot technology environments.
For path optimization, we first apply a stretching process to remove redundant nodes. This involves checking if a direct connection between non-adjacent nodes is collision-free; if so, intermediate nodes are eliminated. Subsequently, we use cubic B-spline curves to smooth the path, reducing sharp angles and making it more suitable for robot motion. The B-spline curve for control points $p_0, p_1, \ldots, p_n$ is expressed as:
$$ P(\mu) = \sum_{i=0}^{n} p_i B_{i,3}(\mu) $$
where $B_{i,3}(\mu)$ are the basis functions for a cubic B-spline, defined for $\mu \in [0,1]$ as:
$$ B_{0,3}(\mu) = \frac{1}{6} (-\mu^3 + 3\mu^2 – 3\mu + 1) $$
$$ B_{1,3}(\mu) = \frac{1}{6} (3\mu^3 – 6\mu^2 + 4) $$
$$ B_{2,3}(\mu) = \frac{1}{6} (-3\mu^3 + 3\mu^2 + 3\mu + 1) $$
$$ B_{3,3}(\mu) = \frac{1}{6} \mu^3 $$
This smoothing technique ensures that the path is continuous and differentiable, which is essential for the kinematic constraints in robot technology.
We conducted simulations in MATLAB 2021 to evaluate our improved RRT* algorithm against standard RRT, RRT*, and RRT-Connect algorithms. The experiments were performed in both simple and complex obstacle environments, with 10 trials each. Performance metrics included the number of sampling points, path length, computation time, and path smoothness. The results demonstrate the superiority of our approach in robot technology applications, as it achieves shorter paths and faster execution while maintaining smooth trajectories.
In terms of sampling efficiency, our improved RRT* algorithm significantly reduces the number of sampling points compared to other methods. The following table summarizes the average and optimal number of sampling points in both environments:
| Algorithm | Complex Environment (Avg) | Complex Environment (Optimal) | Simple Environment (Avg) | Simple Environment (Optimal) |
|---|---|---|---|---|
| RRT | 870.6 | 664 | 472.6 | 364 |
| RRT* | 719.8 | 471 | 480.5 | 275 |
| RRT-Connect | 467.1 | 297 | 147.5 | 77 |
| Improved RRT* | 235.9 | 191 | 52.9 | 44 |
This reduction in sampling points indicates that our method is more directed and efficient, which is critical for resource-constrained robot technology systems. The adaptive step size and biased sampling contribute to this improvement by minimizing unnecessary expansions.
Path length comparisons reveal that our algorithm produces competitive results, particularly in average path length. The table below shows the path length metrics:
| Algorithm | Complex Environment (Avg) | Complex Environment (Optimal) | Simple Environment (Avg) | Simple Environment (Optimal) |
|---|---|---|---|---|
| RRT | 1233.38 | 1132.25 | 847.25 | 779.47 |
| RRT* | 1225.10 | 1132.25 | 835.79 | 756.55 |
| RRT-Connect | 1291.55 | 1140.18 | 851.85 | 750.00 |
| Improved RRT* | 1191.84 | 1157.09 | 797.06 | 777.29 |
Although the optimal path length of our method is slightly longer in some cases, the average performance is better, indicating consistency. This is advantageous in robot technology, where predictable behavior is valued over occasional optima.
Computation time is a key factor in real-time robot technology applications. Our improved RRT* algorithm demonstrates substantial speed improvements, as shown in the following table:
| Algorithm | Complex Environment (Avg) | Complex Environment (Optimal) | Simple Environment (Avg) | Simple Environment (Optimal) |
|---|---|---|---|---|
| RRT | 13.81 | 8.91 | 4.79 | 3.41 |
| RRT* | 10.85 | 5.53 | 5.05 | 2.92 |
| RRT-Connect | 5.59 | 3.39 | 1.40 | 0.76 |
| Improved RRT* | 2.69 | 1.79 | 0.55 | 0.47 |
In complex environments, our method is approximately 52% faster than RRT-Connect, and in simple environments, it achieves a 60% speedup. This efficiency stems from the adaptive step size and targeted sampling, which reduce the number of iterations required to reach the goal.
Path smoothing using cubic B-spline curves further enhances the practicality of our algorithm for robot technology. The stretching process removes redundant nodes, and the B-spline smoothing eliminates sharp turns, resulting in paths that are easier for robots to follow. For example, the path length after smoothing is reduced compared to the original and stretched paths, as illustrated in the following equations for a sample path segment. If $l(g_{\text{begin}}, g_{\text{new}})$ is the cumulative path length from start to a new node, and $d(g_{\text{new}}, g_{\text{end}})$ is the Euclidean distance to the goal, the total path length $D$ is:
$$ D = l(g_{\text{begin}}, g_{\text{new}}) + d(g_{\text{new}}, g_{\text{end}}) $$
After smoothing, this length decreases due to the elimination of detours. The B-spline formulation ensures that the path remains within the free space while being geometrically smooth, which is essential for the mechanical constraints in robot technology.
In conclusion, our improved RRT* algorithm offers significant advancements in robot technology by integrating adaptive step sizing, efficient sampling, and path optimization. The simulations confirm that it outperforms existing methods in terms of sampling efficiency, computation time, and path quality. Future work will involve incorporating robot motion models to enhance realism and applicability in dynamic environments. This research contributes to the ongoing development of autonomous systems in robot technology, paving the way for more reliable and efficient navigation solutions.
The robustness of our algorithm is evident from the consistent performance across multiple trials, with minimal variation in results. This reliability is crucial for robot technology deployments in unpredictable settings. By leveraging adaptive mechanisms and mathematical optimizations, we have created a path planning method that balances speed and accuracy, addressing key challenges in the field. As robot technology continues to evolve, such improvements will play a vital role in enabling complex autonomous behaviors.