Potential-Field-RRT: A Path-Planning Algorithm for UAVs Based on Potential-Field-Oriented Greedy Strategy to Extend Random Tree

Abstract

This paper proposes a random tree algorithm based on a potential field oriented greedy strategy for the path planning of unmanned aerial vehicles (UAVs). Potential-field-RRT (PF-RRT) discards the defect of traditional artificial potential field (APF) algorithms that are prone to fall into local errors, and introduces potential fields as an aid to the expansion process of random trees. It reasonably triggers a greedy strategy based on the principle of field strength descending gradient optimization, accelerating the process of random tree expansion to a better region and reducing path search time. Compared with other optimization algorithms that improve the sampling method to reduce the search time of the random tree, PF-RRT takes full advantage of the potential field without limiting the arbitrariness of random tree expansion. Secondly, the path construction process is based on the principle of triangle inequality for the root node of the new node to improve the quality of the path in one iteration. Simulation experiments of the algorithm comparison show that the algorithm has the advantages of fast acquisition of high-quality initial path solutions and fast optimal convergence in the path search process. Compared with the original algorithm, obtaining the initial solution using PF-RRT can reduce the time loss by 20% to 70% and improve the path quality by about 25%. In addition, the feasibility of PF-RRT for UAV path planning is demonstrated by actual flight test experiments at the end of the experiment.

1. Introduction

With the development of technology for UAVs, the application of UAVs is becoming more and more widespread. Military UAVs can perform tasks such as intelligence collection, air early warning and electronic jamming [1,2,3]. Civil applications include aerial photography [4], agricultural plant protection [5], express transportation [6], geological mapping [7] and fault inspection [8]. UAVs complete their mission with a variety of capabilities, one of which is their path-planning capability.

Common path-planning algorithms can be classified as follows. Graph-based planning methods include A* [9], D* [10], and their optimization algorithms [11,12]. Since this type of algorithm is not suitable for path searching in high-dimensional space, it is often used for unmanned vehicles for path planning in the two-dimensional plane. Bionic-based planning methods, such as GA [13], ACO [14,15], and PSO [16], is a class of algorithms more often used to deal with patrols or secondary path optimization. Potential-field-based planning methods mainly include APF and its optimization algorithms [17,18,19], which have the problem of falling into local optimization. Sampling-based planning methods, such as RRT [20] and PRM [21], can be used to solve high-dimensional path-planning problems. In addition, their advantages are more obvious as the dimensionality increases. For this reason, the study of RRT and its optimization algorithm has received considerable attention from scholars in recent years.

Steven M. LaValle proposed the RRT algorithm [20] in 1998 to solve the robot path-planning problem, attempting to expand the path through node iteration, making the path branch like a tree until the branch touches the target point. Kuffner et al. proposed RRT-connect [22] in 2000, which introduces a dual-tree expansion strategy and adds a greedy strategy to the expansion of auxiliary trees to reduce the map complexity by expanding both trees simultaneously. Karaman et al. proposed the RRT* [23] algorithm in 2011, which improves path quality through root node reconstruction, sacrificing small time costs and saving a large amount of path costs, making RRT* the most successful variant of RRT. In 2019, Jeong proposed a Q-RRT* [24] algorithm based on RRT*, which optimizes the path cost of each node under the current expansion state through root node iteration. In addition, the development of RRT has also derived a series of optimization algorithms such as BG-RRT [25], Informed RRT* [26], PQ-RRT* [27], F-RRT* [28], and DPRRT* [29].

This paper proposes an improved path-planning algorithm: PF-RRT, which incorporates a potential-field-oriented greedy strategy in RRT. It uses the field strength matrix of the artificial potential field to calculate and determine whether to perform greedy extension of the random tree, and speeds up the search of the random tree to the target point. After a new node is generated, one iteration of its root node is performed, making PF-RRT improve the path quality without increasing the time cost. In addition, the performance and feasibility of PF-RRT is demonstrated by conducting simulation tests of the algorithm, ROS-based PX4 simulation flight tests, and actual UAV flight tests in turn.

The structure of this paper is as follows: In Section 2, the path-planning problem is described and defined, and the ideas of the RRT algorithm and APF algorithm are introduced to assist in understanding PF-RRT. In Section 3, DG-RRT is proposed to solve the path-planning problem. In Section 4, the superiority of the algorithm is analyzed by comparing the simulation experiments in two-dimensional and three-dimensional states, and the flight states of the UAV in the simulated and real environments are shown.

2. Related Works

In this section, the path-planning problem and its objectives are described. The principles of RRT and APF algorithms for path searching are also introduced in depth to aid in understanding the conception of PF-RRT.

2.1. Problem Definition

$X=(0,1{)}^n$ is a n-dimensional constructed space, $X_{hinder}$ is an obstacle region, and $X_{free}$ is a blank region satisfying

$$\left\{\begin{array}{l}{X}_{free}\cap X_{hinder}=\varnothing \\ X_{free}\cup X_{hinder}=X\end{array}\right..$$

(1)

Meanwhile, a path-planning problem is defined through $(X_{free},X_{init},X_{goal})$, where $X_{init}\in X_{free}$ is the initial starting point and $X_{goal}\in X_{free}$ is the target region. Let a continuous function $\Phi :[0,1]\mapsto X$ with bounded variation be a path, and the path $\Phi$ is an unobstructed path when $\forall \tau \in [0,1]$ and $\Phi \left(\tau \right)\in X_{free}$.

Definition 1. 

Effective path planning is finding a feasible path Φ for a given motion planning problem $(X_{free},X_{init},X_{goal})$ and making Φ collision-free, where

$$\left\{\begin{array}{c}\Phi \left(0\right)=X_{init}\\ \Phi \left(1\right)\in X_{goal}\end{array}\right..$$

(2)

Definition 2. 

Optimal path planning is to find a feasible path $\Phi *$ for a given motion planning problem $(X_{free},X_{init},X_{goal})$ such that the path cost Φ is minimized and such that it satisfies

$$\left\{\begin{array}{c}c\left(\Phi *\right)=min\left\{c(\Phi )\right\}\\ \Phi \in X_{free}\end{array}\right.,$$

(3)

where $c(\Phi )$ is the path cost of path Φ from $X_{init}$ to $X_{goal}$.

2.2. Rapidly-Exploring Random Tree

“Speed” is the biggest advantage of RRT, and randomness is also its biggest advantage, which makes it free from the trouble of falling into local optimization. The solution idea for the feasible path is to quickly expand the path like a tree, spreading from the starting point $x_{init}$ to the surrounding areas until the target point $x_{goal}$ is searched. It is very common to address the dynamic programming problem by constructing a weighted graph $G=(V,E)$, where $V=\{x_1,x_2,x_3,\cdots x_n\}$ is the vertex set composed of random tree nodes $x_i(i\in \{1,2,\cdots n\})$ and E is the edge set. Algorithm 1 provides a basic RRT construction idea, which is an iterative process that tries to generate a feasible new node $x_{new}$ for each iteration to expand the random tree after setting the end condition.

Algorithm 1 RRT

Input: Map, $x_{init}$, $x_{goal}$;

Output: $G=(V,E)$;

1  : $V=\left\{x_{init}\right\}$, $E=\varnothing$, $i=0$;

2  : while $True$ do

3  :    $x_{rand}\leftarrow Sampling\left(i\right)$;

4  :    $i\leftarrow i+1$;

5  :    $x_{nearest}\leftarrow Nearest(G,x_{rand})$;

6  :    $x_{new}\leftarrow GetNode(x_{rand},x_{nearest})$;

7  :    if $ObstacleFree(x_{new},x_{nearest})$ then

8  :     $V\leftarrow V\cup \left\{x_{new}\right\}$;

9  :     $E\leftarrow E\cup \left\{(x_{nearest},x_{new})\right\}$;

10:    if $x_{new}\approx x_{goal}$ then

11:       return $(V,E)$;

The original procedure used in the RRT algorithm is described below:

• $Sampling\left(\right)$: Given a weighted map $G=(V,E)$, it returns a random coordinate point in the map as a guide point $x_{rand}$.
• $Nearest\left(\right)$: Given $G=(V,E)$ and guide point $x_{rand}$, it calculates the point closest to $x_{rand}$ in V as the extended proximal point $x_{nearest}$, and returns it.
• $GetNode\left(\right)$: Given $x_{nearest}$ and $x_{rand}$, it takes $x_{nearest}$ as the starting point $x_{rand}$ as the guide, intercepts the point at which the set step length of the upper guide distance $x_{nearest}$ is $x_{new}$, and returns to $x_{new}$.
• $ObstacleFree\left(\right)$: Given $x_{nearest}$ and $x_{new}$, it returns $True$ or $False$ after collision checking. In addition, the calculated distances are all Euclidean distances.

2.3. Artificial Potential Field

The basic principle of the APF is to construct a potential-field function to quantify the influence of the current position by the potential field. Any position in the map is subject to the combined force of gravitational and repulsive forces, where the target point gives the gravitational force and the obstacle provides the repulsive force. It searches for the direction in which the potential energy decreases as the optimal path at the current moment, and ultimately moves to the target point. The gravitational and repulsive forces of an artificial potential field are shown in Figure 1.

Any position in space is affected by the gravitational force of the target point, and the farther away from the target point, the greater the gravitational force received. The gravitational potential-field function $U_{att}\left(q\right)$ can be defined as Equation (4):

$$U_{att}\left(q\right)=\left\{\begin{array}{cc}\frac{1}{2}{K}_{\xi }{\rho }^2(q,q_{goal})& q\in \Omega \\ 0& q\notin \Omega \end{array}\right.,$$

(4)

where q ($q\in \Omega$, $\Omega$ is the area for path planning) is the current position, $K_{\xi }$ is the gravitational gain parameter, and $\rho (q,q_{goal})$ is the Euclidean distance from the target point. The corresponding gravitational force calculation function through the gravitational potential-field model is as follows:

$$F_{aat}\left(q\right)=-\nabla U_{att}\left(q\right)=\left\{\begin{array}{cc}{K}_{\xi }\rho (q_{goal}-q)& q\in \Omega \\ 0& q\notin \Omega \end{array}\right..$$

(5)

The repulsive-field for the local field is subject to repulsive force when entering a specific range of the repulsive field, and the closer to the barrier it is, the greater the repulsive force. The repulsion field function $U_{rep}\left(q\right)$ is defined as Equation (6):

$$U_{rep}\left(q\right)=\left\{\begin{array}{cc}\frac{1}{2}{K}_{\eta }{(\frac{1}{\rho (q,q_{obs})}-\frac{1}{{\rho }_0})}^2& \rho (q,q_{obs})\le {\rho }_0\\ 0& \rho (q,q_{obs})>{\rho }_0\end{array}\right.,$$

(6)

where $K_{\eta }$ is the repulsive field gain coefficient, $q_{obs}$ is the obstacle position, $\rho (q,q_{obs})$ is the distance from the current position to the obstacle, and ${\rho }_0$ is the repulsive range. The corresponding repulsive force calculation function through the repulsive potential-field model is

$$F_{rep}\left(q\right)=-\nabla U_{rep}\left(q\right)=\left\{\begin{array}{cc}{K}_{\eta }(\frac{1}{\rho (q,q_{obs})}-\frac{1}{{\rho }_0})\frac{1}{{\rho }^2(q,q_{obs})}\nabla \rho (q,q_{obs})& \rho (q,q_{obs})\le {\rho }_0\\ 0& \rho (q,q_{obs})>{\rho }_0\end{array}\right..$$

(7)

Combining the gravitational occasion repulsive field, the combined force at the current position is

$$F\left(q\right)=F_{aat}\left(q\right)+\sum _1^n{F}_{rep\left(n\right)}\left(q\right).$$

(8)

2.4. Analysis of the Advantages and Disadvantages of Two Algorithms

APF is essentially a feedback control method that uses a gradient descent mechanism to construct a feasible path, which has the advantage of being somewhat robust to control. However, it has the very obvious disadvantage that it tends to fall into local minima in complex environments. In addition, it is accompanied by an exponential increase in the number of operations when solving high-dimensional path-planning problems. The RRT algorithm is the exact opposite of APF. RRT has a great advantage in high-dimensional path planning, but the stochastic nature of scaling causes its time advantage to be gradually canceled out. The ideal answer to solving path-planning problems is to obtain high-quality feasible paths quickly. By combining the advantages of the rapid scaling of random trees with the optimal orientation of potential fields, it becomes possible to quickly obtain better paths in high-dimensional environments.

3. Potential-Field-RRT

The APF algorithm has a good orientation to the path expansion trend, but it is easy to fall into local misconceptions in a slightly complex map. Combining APF to improve the RRT algorithm, a greedy algorithm based on potential-field orientation is added to the expansion process of the random tree, which accelerates its expansion to more optimal regions and avoids the problem of local errors. In addition, performing one iteration of the root node after generating new nodes makes it possible to improve the path quality without increasing the time cost.

3.1. Greedy Strategy Based on Potential-Field Orientation

First, the artificial potential field is constructed to calculate the force field for the path-planning map area. In practical applications, it is common to slice the large area, calculate the middle value of the small area as the field average force, and output the force field in the form of a matrix. This setup has two advantages:

I. It is more convenient to obtain the path field mean force in the form of a look-up table, and it can improve the efficiency of operation;

II. It is easier to distinguish between obstacle areas and blank areas based on the data of the field force matrix, thus making collision detection easy.

Setting the map length and width as W and L, each small area resolution is $R_{reso}$, then the length and width can be divided into the number of regions $M=W/R_{reso}$ and $N=L/R_{reso}$. Each small area subject to the potential-field force:

$$\left\{\begin{array}{c}{F}_{aat}\left(q_{i,j}\right)=K_{\xi }\rho (q_{goal}-q_{i,j})\hfill \\ F_{rep}\left(q_{i,j}\right)=K_{\eta }(\frac{1}{\rho (q_{i,j},q_{obs})}-\frac{1}{{\rho }_0})\frac{1}{{\rho }^2(q_{i,j},q_{obs})}\nabla \rho (q_{i,j},q_{obs})\hfill \\ F\left(q_{i,j}\right)=F_{aat}\left(q_{i,j}\right)+{\displaystyle \sum _1^n}{F}_{rep}\left(q_{i,j}\right)\hfill \end{array}\right.,$$

(9)

where $F\left(q_{i,j}\right)$ denotes the position coordinates of the calculated small area ($i\in [0,M-1]$, $j\in [0,N-1]$), n denotes the number of obstacles, and the final output $F_{con}$ is a two-dimensional matrix of size $M\times N$. The output field strength data are visualized as shown in Figure 2a,b.

Figure 2a is a flat gradient map; the deeper the color, the greater the force. The output data are stacked according to the size of the value to build Figure 2b. Ideally, the collision-free path extends from the high potential energy region to the low potential energy region. The potential field constructed in this section is only used to assist in the expansion of the random tree. f is a small-area potential field, which is mainly used to obtain the potential energy of a node through coordinate transformation and to calculate the average potential energy of the path. Let the coordinates of the node be $node(x,y)$, then the force on the point is $f_{node(x,y)}$:

$$f_{node(x,y)}=F\left(q_{\mathrm{int}(x/R_{reso}),\mathrm{int}(y/R_{reso})}\right),$$

(10)

where $int\left(x\right)$ means that x is forced to be converted to an integer. The calculation of the mean field force on a section of the path is performed by sampling the section of the path and then calculating the potential field for each sample point to find its mean value $f_x$:

$$f_x=\frac{1}{m}\sum _{a=1}^m{f}_{node(x_a,y_a)},$$

(11)

where m is the number of sampling points on the path. The selection of whether to use the greedy algorithm for path expansion is made by calculating and analyzing the $f_x$ values on the path, as shown in Figure 3.

Figure 3a,b show the schematic diagram of greedy strategy expansion based on the potential-field orientation, where Figure 3a generates random guide points $x_{rand}$, after calculating the proximity point $x_{nearest}$, after touch detection that satisfies $f_x<F_{threshold}$ ($F_{threshold}$ is a set threshold defining the obstacle area and blank area) after intercepting the end point of the set step as a new node $x_{new}$ according to the single-step expansion step after intercepting $x_{nearest}$ as the center of the circle $\overrightarrow{x_{nearest}{x}_{rand}}$ as the direction. The difference between other random tree algorithms is that instead of regenerating new bootstrap points immediately after generating new nodes to start the expansion of new arguments, the bootstrap points generated in the previous round are then used to further expand in the current direction by a factor of two steps to generate feasible nodes $x_{may}$, and calculate the field-average force $f_{last}$ on path $l_{x_{nearest}{x}_{new}}$ and the field-average force $f_x$ on path $l_{x_{new}{x}_{may}}$. When satisfied $f_x<f_{last}$, $x_{new}$ is used as the proximal point $x_{nearest}$, and $x_{may}$ is stored as the new node $x_{new}$ to repeat the round. The bootstrap point $x_{rand}$ is regenerated when $f_x>F_{threshold}$ or $f_x\ge f_{last}$ is obtained based on the potential-field matrix F. The expansion of the random tree is re-performed, as shown in Figure 3b.

As shown in Figure 4a,b, the potential-field stacking plots are shown for APF and combined with RRT improvement, respectively. As the blue area deepens, the potential-field force gradually increases. The yellow ‘star’ is the starting point, the blue ‘triangle’ is the end point, and the red route is the output path. In addition, the green route in Figure 4b is the extended random tree. In complex maps, APF is prone to fall into local minima, and the stochastic nature of RRT allows it to eliminate that problem. In addition, it can be seen from Figure 4b that the gradient descent mechanism makes the random tree expand more diffusely in the better region, so it can accelerate the search to the target point.

3.2. Root Node Iterates Once

To obtain a higher-quality path solution, when a new node $x_{new}$ is created, instead of storing $x_{nearest}$ as its root node, an iteration is performed on its root node. If the new path constructed passes the touch detection, the root node is updated forward once. Compared with the conventional algorithm, which directly takes nearest point $x_{nearest}$ as the root node, this approach sacrifices only a little time cost for more path cost. The schematic diagram is shown in Figure 5.

Where $x_{nearest}^{parent}$ is the root node of the proximal point $x_{nearest}$, when the new node $x_{new}$ is obtained, $x_{nearest}$ is no longer directly stored as its root node $x_{new}^{parent}$. As shown in Figure 5a, assuming that a triangle is constructed with $x_{nearest}^{parent}$, $x_{nearest}$, and $x_{new}$ as the vertex, it is known from the triangle theorem:

$$l_{x_{new}{x}_{nearest}^{parent}}<l_{x_{nearest}{x}_{nearest}^{parent}}+l_{x_{new}{x}_{nearest}}.$$

(12)

Therefore, its root node is selected by verifying the connectivity of $l_{x_{new}{x}_{nearest}^{parent}}$ and calculating the field-averaged force $f_x$ on $l_{x_{new}{x}_{nearest}^{parent}}$, as shown in Equation (13):

$$\left\{\begin{array}{cc}{x}_{new}^{parent}=x_{nearest}^{parent}& f_x<F_{threshold}\\ x_{new}^{parent}=x_{nearest}& f_x\ge F_{threshold}\end{array}\right..$$

(13)

When the calculated field-averaged force $f_b$ is less than the threshold $F_{threshold}$, as shown in Figure 5b, the reconfiguration path selects $x_{nearest}^{parent}$ as the root node of the new node $x_{new}$. The core idea of PF-RRT is to reduce the time cost of the search by accelerating the paths to better regions through a potential-field-oriented greedy strategy. In addition, a root node iteration is performed when a new node is generated, and the feasibility of path reconstruction is verified. The complete idea of the PF-RRT algorithm is shown in Algorithm 2.

Algorithm 2 PF-RRT

Input: $Map$, $x_{init}$, $x_{goal}$;

Output: $G=(V,E)$;

1  : $V=\left\{x_{init}\right\}$, $E=\varnothing$, $i=0$, $f_{last}=F_{threshold}=50$;

2  : $F_{con}=FieldCalculation\left(Map\right)$;

3  : while $True$ do

4  :    $x_{rand}\leftarrow Sampling\left(i\right)$;

5  :    $i\leftarrow i+1$;

6  :    $x_{nearest}\leftarrow Nearest(G,x_{rand})$;

7  :    while $True$ do

8  :     $x_{new}\leftarrow GetNode(x_{rand},x_{nearest},F_{con})$;

9  :     $f_x\leftarrow ObstacleFree(x_{new},x_{nearest},F_{con})$;

10:     if $f_x<F_{threshold}$ and $f_x<F_{last}$ then

11:       $V\leftarrow V\cup \left\{x_{new}\right\}$;

12:       if $ObstacleFree(x_{new},neares{t}_{nearest},F_{con})<F_{threshold}$ then

13:         $x_{nearest}\leftarrow neares{t}_{nearest}$;

14:       $E\leftarrow E\cup \left\{(x_{nearest},x_{new})\right\}$;

15:       $f_{last}\leftarrow f_x$;

16:       $x_{nearest}\leftarrow x_{new}$;

17:     else $break$;

18:     if $x_{new}\approx x_{goal}$ then

19:       return $(V,E)$;

The following explains the original procedure in the PF-RRT that differs from the RRT:

• $FieldCalcuation\left(\right)$: Given the map information, the map is sliced, and the potential-field force matrix $F_{con}$ is calculated and output according to Equation (9).
• $ObstacleFree\left(\right)$: Unlike other RRT algorithms, here the field-averaged force $f_x$ of the detected segment path is calculated and returned based on the input potential-field force matrix $F_{con}$.

4. Simulation Experiment and Analysis

As shown above, PF-RRT consists of two parts, path expansion and root node iterative optimization, in order to obtain high-quality initial solutions faster. Based on the idea of the original RRT (shown in Algorithm 1), RRT, RRT*, and Q-RRT* are programmed and used as comparison algorithms to verify the performance of PF-RRT.

This paper conducts a series of experiments to evaluate the performance of the PF-RRT algorithm. The simulation experiment selects RRT as the benchmark algorithm for longitudinal comparison, and the classical RRT* and the newer Q-RRT* as the cross-sectional comparison algorithm, and then quantifies the output of RRT as the benchmark value normalized cross-sectional algorithm output to prove the performance advantages and disadvantages of the four algorithms in obtaining the initial solution. Meanwhile, iterative convergence experiments are conducted to compare the four algorithms and verify the performance of PF-RRT.

4.1. Simulation Environment and Its Initial Conditions

Pycharm was chosen as the simulation platform, the programming language is Python 3.7, and the computing processing core is Intel Core i7-7700, RAM 16G DDRT. Figure 6a,b show the simple fragmented obstacle map and the more complex maze map in a two-dimensional plane, with the size of 200 m (horizontal direction) × 200 m (vertical direction). Figure 7a,b show the columnar map and the fragmented map in the three-dimensional space, with the size of 30 m (horizontal) × 30 m (vertical) × 20 m (vertical). In each map, the red pentagram represents the starting point, the blue triangle represents the target point $x_{init}$, and the gray area is the impassable obstacle area.

In order to obtain more realistic and comparable data, the single extension step size is set to 5 for each algorithm in the 2D environment, and the root node reconstruction search radius is set to 15 for both RRT* and Q-RRT*. The single extension step for each algorithm in the 3D environment is set to 1.5, and the root node reconstruction search radius for RRT* and Q-RRT* is 3. In order to keep the program construction as consistent as possible, the same program modules are used for all parts except for the original program specific to the algorithm itself.

4.2. Analysis of Experimental Results in the Two-Dimensional Plane

The simulation experiments are set up with 1000 sets of repeated trials to obtain the initial solutions from each algorithm searching in 2 different 2D test maps. The corresponding experiments counts 1000 initial solution path costs and search times for each algorithm in each map. In addition, iterative experiments are used to compare the convergence states of the optimal paths obtained by different algorithms in the same time span.

Figure 8a–d show the path expansion results of each of the four algorithms when searching for the target point in 2D-map1. Intuitively, the path of the RRT algorithm is more sinuous; the extended path of RRT* is “bundle-like” and relatively more rounded; Q-RRT* is an optimization algorithm based on RRT*, which iteratively searches the parent node during path reconstruction to make its path quality rise to a higher level, and the corresponding time loss is higher. Influenced by the potential-field orientation, the greedy strategy is no longer triggered arbitrarily and is only triggered when $\overrightarrow{x_{nearest}{x}_{new}}$ points to the direction of the falling potential field, making the path expand rapidly toward the target point.

Figure 9a,b show the statistics of the path cost and search time for each of the 4 algorithms in 2D-map1 for 1000 iterations of testing and their data distribution. Figure 9c shows the path-cost loss rate and time loss rate of different algorithms relative to RRT, which are calculated as follows:

$$\left\{\begin{array}{c}{l}_{c\left(i\right)}={\displaystyle \sum _{a=1}^{1000}}\frac{c_{a\left(i\right)}}{C_{mean\left(RRT\right)}}\\ l_{t\left(i\right)}={\displaystyle \sum _{a=1}^{1000}}\frac{t_{a\left(i\right)}}{T_{mean\left(RRT\right)}}\end{array}\right.,$$

(14)

where $l_{c\left(i\right)}$ and $l_{t\left(i\right)}$ are relative path-cost loss rate and time loss rate (i denotes the algorithm category), $c_{a\left(i\right)}$ and $t_{a\left(i\right)}$ are path cost and time; in addition, $C_{mean\left(RRT\right)}$ and $T_{mean\left(RRT\right)}$ denote the mean value of path cost and mean value of search time for the initial solution of RRT. The data in Figure 8a–c show that Q-RRT* and PF-RRT obtain better path quality for a single solution of the simple map, but the average time loss of Q-RRT* is about 7.7 times that of PF-RRT. PF-RRT makes the random tree accelerate to approach the target point quickly in a simple map by a greedy strategy based on potential-field orientation, and the iterative optimization of one root node makes the path smoother.

The results show that DG-RRT is able to obtain higher-quality initial solutions in relatively less time in a simple environment. In 2D-map1, the time loss of PF-RRT is only 22.6% of that of RRT, and its path quality is improved by about 22.1%.

As the nemesis of sampling-based algorithms, maze maps make the sampling process more complicated because of their winding paths. At the same time, it is used as a test map because it has fewer path channels and the trend of feasible solutions is more or less the same, so it is more intuitive to observe the strengths and weaknesses of its paths. Figure 10a–d show the status of the four algorithms for obtaining path solutions in single-channel maze maps, Figure 11a,b show the corresponding path cost and search time statistics, and Figure 11c shows the relative path-cost loss rate and time loss rate calculated based on Equation (14).

Q-RRT* is an upgraded version of RRT*, and the time loss is further increased with the improvement of the path quality. Even though the iterative process of one root node increases the arithmetic power requirement, the preprocessed field strength matrix for obstacle perception and touch detection greatly improves the computational efficiency and reduces the time loss by 68.3% compared with the original RRT algorithm. The results in Figure 11c shows that PF-RRT is able to maintain its characteristics and obtain better path results with less time loss in relatively complex maps. Meanwhile, the error bars based on the statistics in Figure 11c shows that the path search results of PF-RRT are more stable compared to several other algorithms.

Figure 12a,b show the cost of optimal paths for each of the four algorithms in 2D-map1 and 2D-map2 in the same time span, where $C_{optimal}$ is the optimal path generation value. It can be seen that all algorithms except RRT have optimal convergence properties and are able to converge to 1.05$C_{optimal}$ from Figure 12, with PF-RRT taking the shortest time to plan the suboptimal path. Statistical results show that the average time for PF-RRT to plan suboptimal paths is 0.1s and 7.5s in 2D-map1 and 2D-map2, respectively, requiring only 50% and 75 % of the time of Q-RRT*. Since PF-RRT generates near-suboptimal paths faster than other algorithms and it generates a solution in a much faster time, it is more suitable in a two-dimensional environment.

4.3. Analysis of Experimental Results in Three-Dimensional Space

The UAV flight environment is three-dimensional space, for which two sets of experiments were designed to test the performance of the algorithms based on three-dimensional space, and the test maps are shown in Figure 6a,b. Figure 13a–d and Figure 14a–d show the path search states of RRT, RRT*, Q-RRT*, and PF-RRT algorithms in 3D-map1 and 3D-map2. Simultaneously, 1000 sets of repetitive tests were conducted to obtain the initial solution search status of the 4 algorithms in each map, and the statistics are shown in

Table 1. Eigenvalues of the 1000 sets of initial solution data in 3D-map1.

Method	${\mathit{c}}_{\mathbf{mean}}\mathbf{/}\mathbf{m}$	${\mathit{c}}_{\mathbf{median}}\mathbf{/}\mathbf{m}$	${\mathit{c}}_{\mathbf{max}}\mathbf{/}\mathbf{m}$	${\mathit{c}}_{\mathbf{min}}\mathbf{/}\mathbf{m}$	${\mathit{t}}_{\mathbf{mean}}\mathbf{/}\mathbf{s}$	${\mathit{t}}_{\mathbf{median}}\mathbf{/}\mathbf{s}$	${\mathit{t}}_{\mathbf{max}}\mathbf{/}\mathbf{s}$	${\mathit{t}}_{\mathbf{min}}\mathbf{/}\mathbf{s}$
RRT	56.83	56.51	77.67	44.26	0.90	0.26	21.74	0.02
RRT*	45.93	45.43	60.44	37.90	1.37	0.39	28.21	0.03
RRT-C	39.52	39.07	49.91	35.71	1.49	0.48	20.14	0.04
DG-RRT	38.74	38.37	47.10	34.58	0.79	0.21	17.10	0.01

and

Table 2. Eigenvalues of the 1000 sets of initial solution data in 3D-map2.

Method	${\mathit{c}}_{\mathbf{mean}}\mathbf{/}\mathbf{m}$	${\mathit{c}}_{\mathbf{median}}\mathbf{/}\mathbf{m}$	${\mathit{c}}_{\mathbf{max}}\mathbf{/}\mathbf{m}$	${\mathit{c}}_{\mathbf{min}}\mathbf{/}\mathbf{m}$	${\mathit{t}}_{\mathbf{mean}}\mathbf{/}\mathbf{s}$	${\mathit{t}}_{\mathbf{median}}\mathbf{/}\mathbf{s}$	${\mathit{t}}_{\mathbf{max}}\mathbf{/}\mathbf{s}$	${\mathit{t}}_{\mathbf{min}}\mathbf{/}\mathbf{s}$
RRT	56.24	55.51	75.01	34.24	0.96	0.27	15.54	0.03
RRT*	45.68	45.34	59.29	35.56	1.79	0.53	20.36	0.06
RRT-C	39.25	39.04	45.71	37.83	2.64	1.01	18.05	0.12
DG-RRT	37.96	37.58	49.69	34.52	0.87	0.17	13.06	0.01

.

Figure 13a–d show the path search diagram in 3D-map1 for the four algorithms RRT, RRT*, Q-RRT*, and PF-RRT. Table 1 shows the eigenvalues of the path-cost statistics and time statistics of the four algorithms in obtaining the initial solution, where $c_{mean}$, $c_{median}$, $c_{max}$, and $c_{min}$ are the mean, median, maximum, and minimum values of the 1000 sets of path cost statistics in 3D-map1, respectively. Meanwhile, $t_{mean}$, $t_{median}$, $t_{max}$, and $t_{min}$ are the mean, median, maximum, and minimum values of 1000 sets of search time statistics, respectively. The statistical results show that PF-RRT has a higher quality and more stable path, and that it takes less time on average to search.

Figure 15a,b compare the paths output by the four algorithms in 3D-map1. It is obvious, both in the three-dimensional view and in the top view, that PF-RRT has a much smoother path. In the top view of Figure 15b, the effect of the path crossing the obstacle can be seen because of the perspective view of the route.

Figure 14a–d show the final paths output from the path search in 3D-map2 for four different algorithms. Table 2 shows the 4 algorithms performing 1000 sets of replicate trials in 3D-map2 to obtain the eigenvalues of the time and cost statistics during the initial solution, where its special symbols express the same meaning as in Table 1.

The effect plots shown in Figure 15 and Figure 16 clearly show that the trajectories obtained by Q-RRT* and PF-RRT planning are smoother compared to RRT and RRT*. Based on the $c_{mean}$ and $t_{mean}$ data in Table 1 and Table 2, it is obvious that PF-RRT has more advantages in both path quality and search time. In addition, comparing the time extremes $t_{max}$ and $t_{min}$ in the statistics of Table 1 and Table 2 with the path acquisition time in two dimensions, it is found that the time span for path search in three dimensions is larger and the uncertainty is higher.

To facilitate comparison of the combined efficiency of the four algorithms, the relative path-cost loss rate $l_{c\left(i\right)}$ and relative time loss rate $l_{t\left(i\right)}$ are calculated for each algorithm in the two maps, respectively, as shown in Equation (15), and the combined loss rate is calculated by assigning weights $\mu$ and $\omega$.

$$\left\{\begin{array}{c}{L}_{com}\left(i\right)=\mu ·l_{c\left(i\right)}+\omega ·l_{t\left(i\right)}\hfill \\ \mu +\omega =1\hfill \end{array}\right.$$

(15)

Here, the weight of $l_{c\left(i\right)}$ and $l_{t\left(i\right)}$ are set to 1:1, and by calculating the results according to Equation (15), the combined loss rate and its regional distribution of different algorithms in 3D-map1 and 3D-map2 are obtained, as shown in Figure 17a,b, respectively. The results show a very good improvement in the overall performance of PF-RRT in 3D space, and the integrated loss rate is only 77.7% compared with the original RRT. At the same time, the error bars indicate that the results of PF-RRT are more stable.

Figure 18a,b show the four algorithms in 3D-map1 and 3D-map2, respectively, in the same time span. From Figure 18, it can be seen that only Q-RRT* and PF-RRT in 3D space have the optimal convergence characteristics and can converge to 1.05$C_{optimal}$. The average time taken by PF-RRT to plan suboptimal paths in the two maps is 1.50 s and 1.75 s, respectively. Meanwhile, Q-RRT* not only has a worse initial result performance than PF-RRT, but also has a more limited convergence.

4.4. 3D Simulation and Physical Flight

Based on the performance testing map, a realistic 3D scene was built here for simulation testing to verify the effectiveness of the algorithm. The simulation model of PX4 UAV was loaded into the ROS system under Ubuntu environment, a simple UAV flight environment scenario was set up by Gazebo9. Finally, the PF-RRT path-planning program is loaded into the simulated UAV and simulated flight tests are performed. The simulation experiment senses the environment using LIDAR and visualizes the environment and flight trajectory using Rviz.

PF-RRT is used as the global path-planning algorithm in the flight test, and the test results are shown in Figure 19a–c, where Figure 19a is the PX4 UAV simulation model, and the map shown in Figure 19b is built for the flight test, and finally, the UAV’s travel trajectory is marked and displayed in Rviz as shown in Figure 19c. In the simulation flight, the planned path is updated by refreshing the current position of no earth in real time and using PF-RRT until the UAV approaches the target point and finally obtains the complete flight trajectory. The output trajectory is smoother, as shown in Figure 19c, and the shorter time required for PF-RRT to obtain the initial solution makes the refresh frequency of real-time path planning higher.

The current UAV pilot study is based on ’red track’ rail fault detection. The test site is the red track test line of Jiangxi University of Technology Golden Campus. The UAV selected is PX4 equipped with 2D LIDAR and lntel T265 camera. The purpose of the test to be achieved is as follows:

I. Accurate arrival at the designated detection point;

II. Planning a no-touch path.

In the actual flight, PF-RRT is used as a global path-planning algorithm and an initial unobstructed path is obtained. The local path-planning algorithm then uses a dynamic windowing algorithm to prevent other irresistible force factors, such as birds, maintenance personnel, and trains running on the track.

Figure 20a–c show the actual flight effect of the UAV, where Figure 20a shows the PX4 UAV. Figure 20b shows the UAV inspecting the suspended track of the ’red track’, and Figure 20c shows the UAV flight trajectory shown by the ground station. At present, it has been initially achieved by drones to monitor the track at fixed points. The preliminary test results prove that it is also feasible to use PF-RRT for path planning of UAVs and to apply UAVs to spot detection, cruising, and tracking in complex environments in the field.

5. Conclusions

In this paper, an efficient path-planning algorithm, PF-RRT, is proposed based on RRT. It is based on the idea of preprocessing the map by constructing a potential field and constructing a greedy strategy oriented by the potential field to accelerate the extension of the path towards a better region, which makes the random tree search reach the target point quickly. In addition, the path quality is improved in path reading by performing one iteration of the root node for the new node. The experimental results show that PF-RRT performs better in both simple or complex environments, and in two-dimensional planes or three-dimensional spaces. PF-RRT is able to reduce the time loss by 20% to 70% and improve the path quality by about 25% compared to RRT in the process of obtaining the initial solution. PF-RRT not only obtains high-quality initial solutions quickly, but also has better convergence properties. UAV real-time path planning is more responsive, by using the PF-RRT algorithm to quickly obtain feasible paths in high-dimensional environments. The feasibility of UAV path planning using PF-RRT was verified by simulation flight and actual flight testing.

In addition, PF-RRT is a tree extension algorithm, and the greedy strategy based on potential-field orientation can be combined with any other random tree optimization algorithm to further improve the performance. The performance of the current algorithm for UAV path planning based on PF-RRT and the feasibility of its actual flight have been initially verified, but there are several directions for further research, as follows:

I. The proposed PF-RRT algorithm has a great advantage over other algorithms in obtaining the initial solution in a two-dimensional environment, and further explores how to ensure that its advantage is not reduced when performing a path search in three-dimensional space;

II. Applying 3D LIDAR to current UAVs to enhance their environmental awareness and to adapt to interference from dynamic obstacles;

III. The incorporation of cameras and machine vision technology in UAVs enables them to perform fault detection in unmanned conditions in complex environments.