# The Improved A* Algorithm for Quadrotor UAVs under Forest Obstacle Avoidance Path Planning
## 1 Introduction
Among heuristic path planning algorithms, ABC [23] algorithm, GA [24; 25] algorithm, SA [26] algorithm, Grey Wolf [27; 28] algorithm, and PSO [29] algorithm are commonly used. However, the ABC algorithm and Grey Wolf algorithm have the problem of convergence speed being too fast or premature convergence, resulting in relatively low accuracy. The GA algorithm, SA algorithm, and PSO algorithm have the problem of slow convergence speed and being easily affected by parameters, which leads to their low efficiency. The Dijkstra algorithm [30], proposed by [PERSON], solves the problem of finding the shortest distance between two points through a breadth-first search. However, with increasing grid density, the computational volume rapidly expands, making it difficult to meet real-time performance requirements. Local path planning algorithms, such as the artificial potential field (APF) algorithm, have been utilized in numerous scenarios, including mobile robots [31; 32] and autonomous vehicles [33]. However, the traditional APF algorithm is susceptible to falling into local minima, which may prevent it from reaching the target point, and local oscillations. To address these issues, [PERSON] and colleagues [34] replaced the repulsive potential field function in the APF algorithm with a Gaussian function. Nevertheless, the path planning of Unmanned Aerial Vehicles (UAVs) may still become trapped in local minima when the obstacle is situated on the connecting line between the current position and the target position. Moreover, the D*Lite [35] algorithm, which is suitable for dynamic unknown environments and allows variable starting points but fixed target points, can result in non-smooth paths that are prone to colliding with obstacles, and the search process may also fail to converge, leading to the algorithm becoming stuck in a dead loop. The A* algorithm based on grid map search, originally proposed by [PERSON] et al. [36], combines the strengths of mathematical and heuristic searches, using a heuristic function to guide the search direction, thus reducing search volume and improving efficiency. Several researchers have contributed to the improvement of the A* algorithm in various ways. For example, [PERSON] et al. [37] developed novel distance formulas for the A* algorithm to obtain the shortest path under certain conditions, while [PERSON] et al. [38] assigned a fixed weight to the heuristic function to reduce the number of node searches and shorten the search time. [PERSON] proposed the anytime-tree-restoring-weighted A* (ATRA*) algorithm [39], which uses a heuristic approach to focus on the search scope and reuses previous search information to further reduce the search time. [PERSON] et al. [40] improved the A* algorithm's heuristic function by dynamically adjusting weights and optimizing the search and turning points to reduce data processing time and grid search. However, the four-directional search range reduces the possibility of obtaining the shortest path, and the path generated may not be smooth due to the large turning angles. To address these limitations, [PERSON] et al. [41] extended the search neighborhood of the A* algorithm to an infinite number of neighbors, resulting in shorter path lengths with a smaller number of turning points, but at the expense of significantly increased search time. [PERSON] et al. [42] improved the algorithm with directed search to reduce the number of traversed nodes by eliminating the path of symmetric search. [PERSON] et al. [43] introduced the bidirectional search mechanism, improved the traditional calculation method of the evaluation function, and selected the appropriate weight coefficient for the evaluation function to reduce redundant nodes in the search process and improve computational efficiency. [PERSON] et al. [44] optimized the path by analyzing the influence of the parent node of the current node on the heuristic function and using optimal weights to propose an improved A* algorithm to improve computational efficiency, albeit at the expense of the optimal path.