Quad-Rotor Unmanned Aerial Vehicle Path Planning Based on the Target Bias Extension and Dynamic Step Size RRT* Algorithm

Quad-rotor UAVs (unmanned aerial vehicles) are becoming more and more popular among the general public in recent years, and their flight status offers some advantages, such as the following: stable hovering characteristics [1], high maneuverability and agility [2], small size, simple mechanical structures, easy maintenance [3], precise identification, and obstacle avoidance in flight [4]. Therefore, they have received more extensive attention from and been the subject of more in-depth research by experts and scholars [5]. In the civil field, quad-rotor UAVs are used in many sectors, such as industry, agriculture, forestry, and so on [6,7], so they can cooperate with human beings to carry out inspection tasks involving electric power, high altitudes, and other situations. They can also help farmers to carry out spraying and fertilizing for plant protection. In the military field, they are mainly used for the patrol of the national defense boundary line [8], the inspection of battlefield ground, and the evaluation of battle results.

The autonomous navigation problem of quad-rotor UAVs can be divided into three processes: environment sensing, path planning, and motion control [9]. In this paper, the path-planning problem is studied in depth. Path planning consists of planning an optimal path from an initial position to an end position, with quad-rotor UAVs flying in the presence of obstacles on the terrain and the required constraints being met at the same time [10]. At present, the most common algorithms for path planning include Dijkstra’s algorithm [11], the A* algorithm [12,13,14], the Artificial Potential Field Method [15], the RRT (Rapid-exploring Random Trees) algorithm [16,17,18,19,20], and the RRT* algorithm [21,22,23,24,25], the last of which is progressively optimized for the RRT algorithm.

The Dijkstra algorithm was proposed by the Dutch computer scientist Edsger Wybe Dijkstra in 1959, so it is also called Dijkstra’s algorithm. The main feature of this algorithm is to start from a starting point and employ the strategy of the greedy algorithm from the optimal solution of each step to finally obtain the global optimal solution, each time traversing the adjacent node of the vertex that is closest to the starting point and has not been visited until it reaches the end point. The authors of [26] used Dijkstra’s algorithm for indoor navigation to locate objects and move them along the shortest path. The disadvantage is that this algorithm is more complex if the environment is too large. Originally presented in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael from the Stanford Institute, the A* algorithm can be considered an extension of the Dijkstra algorithm; it sets the weight for each edge length, constantly calculating the distance from each vertex to the starting vertex to obtain the shortest route, as well as exploiting the advantage of constantly advancing toward the target as directed by the greedy best-priority-search algorithm so as to search for fewer vertices and keep the search path efficient. In [27], in order to solve the problems of long computation times and large memory occupation in collaborative tasks of quad-rotor UAV obstacle avoidance path-planning algorithms, the authors propose a method combining the A* algorithm and the task allocation algorithm to create a fast and effective path-planning method. The disadvantage in this case is that when there are many targets, a large number of duplicate data and complex valuation functions are introduced. The artificial potential field method was proposed by Khatib in 1986, and its basic idea is to construct a repulsive potential field around an obstacle and a gravitational potential field around the target point. The controlled object is subjected to repulsive and gravitational forces in the composite field composed of these two potential fields, and the combined force of the repulsive and gravitational forces guides the movement of the controlled object, allowing for a search for the obstacle avoidance path without touching any obstacles. In [28], an artificial potential field method was introduced to position a local attractor around an obstacle, thereby guiding the robot employed around the preferred region. The zero-potential-energy point is its fatal shortcoming; it causes the agent to fall into local minima, meaning that the agent cannot achieve path planning when it cannot proceed to the minimum. The rapidly exploring random trees (RRT) algorithm was proposed by Prof. Steven M. LaValle of Iowa State University [29]; it has a powerful and flexible search and processing capability and is applied to complex environment path planning. Through the comparison of these path plans, combined with the overly complex terrain of quad-rotor UAVs’ flight environments, the RRT algorithm finds only a feasible path; it cannot obtain the optimal path. We optimized it using the RRT* algorithm, and after each iteration of the route plan, the entire search tree was reworked to optimize the route. In [30], target heuristics were added, and the dynamics constraints of quad-rotor UAVs were fused to generate a flyable path. By pruning and reconstructing the original random tree when the surrounding environment changed abruptly, the convergence speed of the quad-rotor UAVs for adjusting and re-planning the route was accelerated, but the algorithm’s adaptability was poor. In [31], an AI-RRT* (Anytime-Informed RRT*) algorithm was designed; it performs path planning online at any time and adds the heuristic selection of rolling programming sub-goals. It also suffers from problems such as poor adaptability. In [32], a TRH-RRT* (three-dimensional rapidly exploring random tree* based on receding horizon) path-planning algorithm was proposed; it uses partial random samples to improve the utilization efficiency of sampling points, and the researchers combined the artificial potential field method with the RRT* algorithm to inspire node growth and reduce the unnecessary scanning process. In [33], an RRT* forest algorithm was designed to improve the path-planning efficiency of quad-rotor UAVs in a complex terrain environment by randomly selecting root nodes, generating random trees, connecting random trees, and merging random trees. In [34], the authors propose an improved method based on adaptive target bias and heuristic cyclic sampling. The adaptive target bias function method was used to make the random trees continuously approach the target point; then, a method combining heuristic cyclic sampling and the direction deviation strategy is designed to resample the nodes next to obstacles. In [35], the authors propose a path-planning algorithm named RRT*Smart-AD; it satisfies the two characteristics of obstacle avoidance constraints and dynamic characteristics in a dynamic environment. In [36], the authors propose an upgrade-based RRT* algorithm. By limiting the generation of random sampling points in the variable region, the number of path-planning iterations can be reduced. Then, the improved APF (Artificial Potential Field) method is introduced into the RRT* algorithm to improve its convergence speed. Finally, the cubic B-spline algorithm is used to optimize the path. In [37], the authors propose an algorithm based on PF-RRT*. First, the dichotomy method was used to re-establish a new parent node near an obstacle, and then the improved APF (Artificial Potential Field) method is established to repel obstacles while it moves towards the target point. At the same time, it was combined with the target bias strategy to enhance the guiding effect for the target. In [38], the authors propose an improved RRT* algorithm named F-RRT*, which can find a good initial solution and exhibits good convergence speed. The F-RRT* algorithm optimizes the path cost for creating a parent node for random points. In [39], the authors propose the TSRRT* algorithm; it expands new nodes through a variety of sampling methods and cost evaluation, and then it optimizes the new nodes with the time coordination cost function, so it can improve the efficiency of path planning.