# The Improved A* Algorithm for Quadrotor UAVs under Forest Obstacle Avoidance Path Planning
## 2 Materials and Methods
### Improved A* Algorithm
#### 2.2.1. Segmented Evaluation Function with Dynamic Heuristics and Weighted Processing  
In the A* algorithm, both the cost function and the heuristic function are typically composed of distances. However, the value of the heuristic function can significantly impact the algorithm's performance. If the estimated value of \(h(n)\) is much smaller than \(g(n)\), then the value of \(f(n)\) depends on \(g(n)\), and the A* algorithm behaves similarly to the Dijkstra algorithm, which conducts an extensive search with a slower convergence speed. Conversely, if the estimated value of \(h(n)\) is much larger than \(g(n)\), then the A* algorithm evolves into the Best-First-Search algorithm (BFS), which can quickly find a path, but the path may not be optimal for a UAV. Therefore, the A* algorithm can balance the rate of convergence and path quality by assigning weights to \(g(n)\) and \(h(n)\) and adjusting them dynamically.  
Additionally, assuming that the actual cost of the shortest distance from the current point to the target point is \(d(n)\), three situations may arise. When \(h(n)<d(n)\), the algorithm may need to search more nodes, leading to lower efficiency, but the shortest path can be found. When \(h(n)>d(n)\), the number of search nodes decreases, and the search efficiency increases, but the shortest path cannot be guaranteed. When \(h(n)=d(n)\), the shortest path can be searched with high efficiency. Based on these considerations, different weights are assigned to \(g(n)\) and \(h(n)\), respectively, with the weight coefficient of \(h(n)\) set as the dynamic response. If the current node is far away from the target position, the weight coefficient of \(h(n)\) is larger. As the UAV approaches the target point, the weight coefficient of \(h(n)\) gradually decreases. Therefore, a preliminary evaluation function can be obtained.  
\[f(n)=ag(n)+\left(b+\frac{d}{L}\right)h(n) \tag{2}\]  
where \(a\) and \(b\) are the weight factors, \(d\) is the distance from the current node to the target position, and \(L\) is the distance between the starting position and the target position.  
To balance search speed and path quality, this study adopts a segmented evaluation function that assigns different weights to the cost function and heuristic function in different stages. This approach enhances heuristics to speed up search without compromising path quality. The evaluation function of the algorithm is calculated as follows:  
\[f(n)=\left\{\begin{array}{ll}ag(n)+\left(b+\frac{d}{L}\right)h(n),&h(n)\geq \frac{L}{3}\\ g(n)+\left(\frac{d}{L}\right)h(n),&h(n)<\frac{L}{3}\end{array}\right. \tag{3}\]  
According to the above discussion on the weight relationship between \(g(n)\) and \(h(n)\), the factors of \(a\) and \(b\) in the second segment of the evaluation function to 1 and 0, respectively, in order to maintain the accuracy of the later path search. To determine the appropriate values of weight factors \(a\) and \(b\) for \(g(n)\) and \(h(n)\) in the first segment of the evaluation function, the experiments were conducted using a randomly distributed grid map of size 30 \(\times\) 30 with an obstacle proportion of 0.4. The experimental results are presented in Section 3.1.