Integration of improved APF and RRT algorithms for enhanced path planning in mobile robotics

Abstract

In the process of path planning for mobile robots, situations occur such as local optimal solutions and failure to reach the target point when the traditional Artificial Potential Field (APF) method is used independently for path search; When the traditional Rapidly-exploring Random Tree method (RRT) is used independently for path search, the generated random path tree has multiple branching branches, thereby resulting in high time and distance costs. In response to the above issues, it’s attempted that the two methods were integrated and compensated for each other’s shortcomings. Firstly, the mathematical model of the traditional APF algorithm was improved to solve the problems of unbalanced force and unreachable targets. Secondly, the improved APF was established in the RRT algorithm space by the guide of geometric probability model, and APF contributed to enhancing the target directionality of RRT. Simulation experiments had shown that the fusion algorithm had significant advantages in path length and runtime.

Introduction

Currently, robots have been widely used in various fields of production and life, such as intelligent manufacturing, deep-sea exploration, ¹ the military, and life services. And robot technology keeps evolving rapidly. ² In the field of mobile robot applications, improved motion accuracy and efficiency by planning path is the unremitting pursuit of many experts and scholars. ³ The path planning algorithms reported in various literature include Dijkstra algorithm, Artificial Potential Field method, A* algorithm, PRM algorithm, Rapidly-exploring Random Tree method, genetic algorithm, and ant colony algorithm,^4–10 etc. Among them the most commonly used and classic are Artificial Potential Field method and Rapidly-exploring Random Tree method. The Artificial Potential Field method (Abbreviated as APF) is a virtual force method with the advantages of strong target directionality and short planning path. On the other hand, it has the disadvantage of poor robustness, local optimal solution, and the possibility of not reaching the target point.^11–14 The path of the Rapidly-exploring Random Tree method (Abbreviated as RRT) is randomly and rapidly expanding outward, just like the growth of a tree branch. It features good robustness and always reaches the target point while its disadvantages are strong randomness entailing high cost of time and distance.^15–19

A new path planning algorithm was studied in this article. Firstly, the mathematical model of the APF algorithm had been improved to address the issues of imbalanced forces and unreachable targets. Secondly, the improved APF was established in the RRT algorithm space, whereby two algorithms were fused together through geometric probability model. And AFP would contribute to enhancing the target directionality of RRT. The process of the fusion algorithm in planning the path is akin to the way plants grow toward the sun, with two main advantages. On one hand, guided by the virtual forces, it has a shorter path and stronger robustness compared to the pure RRT algorithm, effectively reducing the cost in terms of time and distance. On the other hand, due to the retention of a certain degree of randomness in each step of the path selection, it can help the robot break free from local force equilibrium points, avoiding the situation where the target point may not be reached as can happen with the pure APF algorithm.

The principles of traditional APF algorithm and RRT algorithm

The principle of APF algorithm

For the APF algorithm, a virtual composite field formed by the superposition of multiple fields is established in the map, including two parts: gravitational potential field and repulsive potential field. The gravitational potential field radiates outward from the endpoint, generating gravity on robots at any position on the map, with the direction pointing toward the endpoint, as shown in Figure 1. The repulsive potential field exists around all obstacles in the map, generating repulsive force on the robot inside, pointing in the direction away from the obstacle, as shown in Figure 2. The gravitational potential field draws the robot toward the endpoint, while the repulsive potential field moves the robot away from obstacles. The combination of the two fields enables the robot to find an automatic obstacle avoidance navigation path in the map. ¹

Figure 1.

Schematic diagram of gravitational potential field.

Figure 2.

Schematic diagram of repulsive potential field.

Assuming there is a mobile robot in the modeling environment with its size taken into account while its shape dismissed. And its motion is only affected by potential field forces. There is an target point that radiates a gravitational field from the center of itself. The target point is attractive to all mobile robots in the modeling environment, and the farther the distance is, the stronger the gravitational field will be. At the same time, there are t obstacles occupying a certain space and the obstacles only generate repulsive force on the surrounding mobile robots. The farther the distance is, the smaller the repulsive force will be. If the distance is greater than the threshold, no repulsive force will be generated. The expression for the potential energy function is:

$$\{\begin{array}{c}{U}_{\mathrm{plu}}=U_{\mathrm{att}}+\sum U_{\mathrm{rep},t}\hfill \\ U_{\mathrm{att}}=\frac{1}{2}{\mathrm{kd}}_e^2\hfill \\ U_{\mathrm{rep},t}=\{\begin{array}{c}\frac{1}{2}\eta {(\frac{1}{d(t)}-\frac{1}{D})}^2{d}_t(x)\le D\hfill \\ 0d_t(x)>D\hfill \end{array}\hfill \end{array}$$

(1)

Among them, $U_{\mathrm{plu}}$ represents the composite potential energy function; $U_{\mathrm{att}}$ represents the gravitational potential energy function; k represents the gravitational coefficient; $d_e$ represents the distance between the endpoint and the current position of the robot; t represents the obstacle number; $U_{\mathrm{rep},t}$ represents the repulsive potential energy function of the obstacle t; $\eta$ represents the repulsive coefficient; $d(t)$ represents the distance between the obstacle t and the current position of the robot; and $D$ represents the distance threshold.

According to the relationship between potential field and force, the expression of the function of force is:

$$\{\begin{array}{c}\overrightarrow{F_{\mathrm{plus}}}=\overrightarrow{F_{\mathrm{att}}}+\sum \overrightarrow{F_{\mathrm{rep},t}}\hfill \\ F_{\mathrm{att}}=-\nabla U_{\mathrm{att}}=k{d}_e\hfill \\ F_{\mathrm{rep},t}=-\nabla U_{\mathrm{rep},t}=\hfill \\ \{\begin{array}{c}\eta (\frac{1}{d(t)}-\frac{1}{D})\frac{1}{d{(t)}^2}d(t)\le D\hfill \\ 0d(t)>D\hfill \end{array}\hfill \end{array}$$

(2)

Among them, $\overrightarrow{F_{\mathrm{plus}}}$ represents the resultant force function; $\overrightarrow{F_{\mathrm{rep},t}}$ represents the repulsive force function of obstacle t, and $\overrightarrow{F_{\mathrm{att}}}$ represents the gravitational function.

Principle of RRT algorithm

For the traditional RRT algorithm, sampling points are randomly obtained in the state space and obstacle avoidance is achieved through collision detection of the sampling points. ² The specific algorithm flow is shown in Figure 3.

Figure 3.

Flow chart of traditional RRT algorithm.

According to the principle and process, it can be seen that the growth direction of the random tree in the RRT algorithm is random, and the obstacle avoidance path from the starting point to the end point is found through aimless growth. Therefore, multiple iterations will give rise to a large number of useless branches and heavy the computational workload, entailing high time, and distance costs.

Improvement of APF algorithm and its fusion with RRT algorithm

Improved APF algorithm model

According to formula (2), it can be seen that under the traditional APF algorithm rules, the gravitational force of the target on the robot is proportional to the distance between the two. This will result in two drawbacks: firstly, when the distance is large, it will cause excessive gravity, and if the gravity value is much greater than the repulsive force, it is easy to cause collisions between the robot and obstacles; Secondly, when the distance is very small, it will lead to too small gravity. And when it is much smaller than the repulsive force, the robot will fail to reach the target point. To solve these two problems, the gravitational potential energy function in formula (1) was segmented and optimized. The optimized function was:

$$U_{\mathrm{att}}^{*}=\{\begin{array}{c}\frac{1}{2}{\mathrm{kd}}_e^2{d}_e\le D^{*}\hfill \\ k{D}^{*}{d}_e-\frac{1}{2}k{D^{*}}^2{d}_e\ge D^{*}\hfill \end{array}$$

(3)

Among them, $U_{\mathrm{att}}^{*}$ represents the improved gravitational potential energy function, $D^{*}$ represents the distance threshold of the gravitational potential field. In the area within the distance from the endpoint $D^{*}$ , the gravitational potential energy $U_{\mathrm{att}}^{*}$ is proportional to the square of $d_e$ , while in the area outside the distance from the endpoint $D^{*}$ , the gravitational potential energy $U_{\mathrm{att}}^{*}$ is proportional to $d_e$ . The setting of the value of $D^{*}$ is crucial yet intricate. If the value is set too high, it cannot completely prevent collisions from occurring; if set too low, it will diminish the guiding effect of the target on the robot, thereby extending the path length. In practical problems, one should select an appropriate value based on factors such as map characteristics, the robot’s distance detection accuracy, detection frequency, and the robot’s inertia, through multiple trials. Generally, one can start with a smaller $D^{*}$ value and gradually increase it without causing collisions, until a collision occurs. The maximum value of $D^{*}$ that does not result in a collision is the final chosen value.

Correspondingly, the expression of the gravitational function becomes:

$$F_{\mathrm{att}}^{*}=-\nabla U_{\mathrm{att}}^{*}=\{\begin{array}{cc}k{d}_e\hfill & d_e\le D^{*}\hfill \\ \multicolumn{1}{c}{k{D}^{*}}& d_e\ge D^{*}\hfill \end{array}$$

(4)

According to formula (4), it can be seen that by segmenting and reducing the order of the gravitational potential energy function, the problem of excessive gravity under the circumstance that the robot is far from the target can be solved.

At the same time, another judgment condition was added to the gravitational potential energy function as follows:

$$k=\{\begin{array}{cc}k\hfill & d_e>D_r\hfill \\ \multicolumn{1}{c}{10*k}& d_e\le D_r\hfill \end{array}$$

(5)

Among them, D_r is the constraint threshold when the distance is close, to prevent the repulsive force from imposing a greater impact than the gravitational force when the distance is small, resulting in the robot not reaching the endpoint.

Fusion algorithm for integrating RRT with improved APF

In order to obtain an algorithm that combines the advantages of RRT and APF, and compensates for each other’s shortcomings, it’s attempted that the two algorithms were integrated. RRT algorithm taken as the main architecture, the improved APF algorithm was introduced to guide path selection, in order to address the drawbacks of RRT path selection such as irregularrity and high time and distance costs. The improved APF was established in the RRT algorithm space. So each point was taken with a certain probability toward the direction of the resultant force. This enhanced target directionality, while also not losing random landing points that can help break away from the local optimal solution. And ultimately the optimal planning path would be located. The algorithm flowchart was shown in Figure 4.

Figure 4.

The flowchart of the fusion algorithm for integrating RRT with improved APF.

For the direction judgment of each step, the random number discrimination method was employed in this article. Thus the random number was used to make a choice. The specific discrimination method was as follows:

A random number r is generated within the interval [a, b] (a, b are constants and satisfy a < b). The condition for event A to occur is m ≤ r ≤ n (m, n are constants and a ≤ m, n ≤ b). So the probability of event A occurring is:

$$\begin{array}{c}\multicolumn{1}{c}{P\left(A\right)=\frac{\mathrm{Interval}\mathrm{length}\mathrm{of}\mathrm{event}\mathrm{A}}{\mathrm{Interval}\mathrm{length}\mathrm{of}\mathrm{all}\mathrm{experimental}\mathrm{results}}}\\ =\frac{n-m}{b-a}\hfill \end{array}$$

(6)

Obviously, the probability of event A occurring is [0, 1]. When selecting the next direction of movement, if the generated random number r falls within the [m, n] interval, that is, when event A occurs, the direction in which the potential energy falls is chosen, otherwise the random direction is chosen. The probability of selecting two directions can be changed by adjusting the values of the four constants a, b, m, and n.

If a robot moves to a point where the gravitational and repulsive forces are exactly balanced, according to the principles of the APF algorithm, the robot cannot continue to move when the resultant force is zero, thus becoming trapped in a local optimum. As shown in Figure 4, in the hybrid algorithm, the path planning process will revert to the “generating random numbers” step at this point, thereby providing an opportunity to execute the “generate random points’ branch,” which can assist the robot in escaping from the dilemma.

Application analysis

Simulation of traditional algorithms

In the feature map environment of a group of circular obstacles, path planning simulation of mobile robots was carried out based on traditional algorithm principles. The simulation results were shown in Figures 5 to 8.

Figure 5.

Potential field schematic diagram of APF algorithm.

Figure 6.

Path planned by APF algorithm.

Figure 7.

Local minimum dilemma.

Figure 8.

Path planned by RRT algorithm.

As shown in Figure 5, under the 3D rendering effect, the potential field sizes at various locations on the map are obvious, the potential energy at the endpoint is the smallest, and the surrounding obstacles rise sharply.

Figure 6 shows a 2D feature map, with red dots as the starting point, green dots as the ending point, and black circles as obstacles. The yellow brown curve is the path planned by the traditional APF algorithm. From Figure 6, it can be seen that the robot points directly from the starting point to the endpoint, with strong target directionality. When encountering obstacles, the robot automatically avoids them. And once it crosses the distance threshold, it continues moving straight. Certain turning points can be improved, the overall path is short and the obstacle avoidance effect is good. However, when the path passes through the force equilibrium point, as shown in Figure 7, the robot will stop moving due to being trapped in a local optimal solution.

The blue line in Figure 8 represents the path planned by the traditional RRT algorithm. From the figure, it can be seen that the robot searches for a path in an irregular manner on the global scale. When there are enough points, a path from the starting point to the endpoint can always be found. Although the RRT algorithm has a very good obstacle avoidance effect and its path finding never fails, the randomness is too high, and the speed varies from fast to slow, lacking stability.

Simulation of the fusion algorithm integrating RRT and improved APF

In the same feature map environment as traditional algorithm simulation, the fusion algorithm was used to simulate the path planning of mobile robots, and the results are shown in Figure 9. The overall path planned by the fusion algorithm is similar to the APF algorithm, but has significant improvements compared with the RRT algorithm, as the overall distance of the path is considerably shortened. For the local minimum dilemma shown in Figure 7, a certain probability of random landing points can play an important role. As shown in Figure 10, random landing points can effectively help robots overcome the dilemma.

Figure 9.

Path planned by fusion algorithm: (a) The result of the first attempt and (b) The result of the second attempt.

Figure 10.

Robot escaping local minimum dilemma with the help of random landing points.

To verify the performance of the fusion algorithm in different feature maps, replace the above feature maps with new ones. The new map is randomly composed of five obstacles of different sizes. Reconduct the experiment and observe the motion trajectory of the robot. The simulation results are shown in Figure 11.

Figure 11.

Path planned by fusion algorithm in random maps: (a) The first random map and (b) The second random map.

After multiple runs of the fusion algorithm, the simulation results obtained are consistent with expectations. There may be some unnecessary points in the path at times. Nevertheless, generally speaking, the fusion algorithm can perform obstacle avoidance tasks well with robustness better than the APF algorithm and comparable to the RRT algorithm, whether in a self set map or a randomly generated map.,

The runtime and path distance of the three algorithms were compared and the results are shown in Table 1. The straight-line distance between the starting and ending points is 104 (unit length). Due to the obstacle avoidance process, the average distance of the APF algorithm path increases by 19.2%, the RRT algorithm path increases by 325%, and the fusion algorithm path increases by 21.1%. For the distance of the planned path, the fusion algorithm increases by less than 2% compared to the APF algorithm and decreases by 303.9% compared with the RRT algorithm. It’s assumed that path distance planned by the fusion algorithm is similar to that of the APF algorithm while significantly reduced distance costs compared with the RRT algorithm. For the average running time, the fusion algorithm is 5.8% shorter than the APF algorithm and 86.5% shorter than the RRT algorithm, indicating that the fusion algorithm can reduce time costs. Therefore, the distance and time costs of the fusion algorithm are lower, and the optimization effect is significant.

Table 1.

Experimental data of the three algorithms.

Algorithms	Average distance / unit length	Average running time / s
APF	124	0.155
RRT	442	1.083
The fusion algorithm	126	0.146

Conclusion

A robot path planning algorithm integrating RRT algorithm with improved APF algorithm was studied.

• (1) The gravitational potential energy function of the APF algorithm has been improved. Through segmented reduction, the problem of excessive gravity and easy collision with obstacles has been solved when the robot is far from the target. By segmenting the gravitational coefficient proportionally, the gravitational value of the robot when approaching the target has been increased to prevent the situation where the robot cannot reach the endpoint.

• (2) The improved APF algorithm and RRT algorithm were integrated together, guided by a geometric probability model, to enhance the target directionality of the RRT algorithm and reduce time and distance costs.

Simulation experiments show that in terms of average path distance, the fusion algorithm increases by less than 2% compared with the APF algorithm and decreases by 303.9% compared with the RRT algorithm; In terms of average running time, the fusion algorithm is 5.8% shorter than the APF algorithm and 86.5% shorter than the RRT algorithm; In terms of achieving goals, the fusion algorithm does not have the problem of local optimal solutions compared with the APF algorithm. Therefore, it can be considered that the overall performance of the fusion algorithm is superior to traditional APF and RRT methods, and has high application value. But in practical applications, key parameters such as the long-distance threshold $D^{*}$ of the gravitational potential field, the close-distance threshold $D_{\mathrm{r}}$ , and the probability P of branch path selection need to be chosen based on the performance parameters of the robot and the characteristics of the environmental map. Currently, there is no clear theoretical derivation method, which requires multiple simulations, trial and error, and optimizations, increasing the workload of path planning. This is an issue that requires further research.