# Research on the A* Algorithm for Automatic Guided Vehicles in Large-Scale Maps
## 3 Improved A* Algorithm Based on Local Obstacle Rate and Dynamic Neighbourhood
### Improved A* Algorithm Based on Local Obstacle Rate Search and Dynamic Weighting
#### 3.2.2 Calculation of Evaluation Function Weight Values  
In the A* algorithm, the assignment of weights to the heuristic function \(h(n)\) is a key regulating factor. Specifically, when the weight of \(h(n)\) is assigned a large value, the algorithm tends to prioritise paths that appear to be less costly to the end point, thus speeding up the search process, but this strategy may sometimes lead to an increase in the final path length. On the contrary, if the weight of \(h(n)\) is set smaller, the algorithm, although slightly slower in search speed, can explore the path space more carefully and thus obtain more optimised paths.  
In order to find an ideal balance between the two, this paper proposes an innovative approach to incorporate into the evaluation function the key information of the local obstacle rate discussed in Section 3.2.1. This strategy allows the algorithm to take into account not only the direct cost and heuristic estimates but also the obstacle complexity in different regions of the environment when evaluating paths. By dynamically adjusting the evaluation function, the algorithm is able to intelligently optimise the search space according to the characteristics of different map regions, ensuring both an increase in search efficiency and the quality of the generated paths. In this way, the algorithm achieves better performance overall. The obtained evaluation function is shown in (1).  
\[f(n)=\frac{c-p}{c+d-p}*g(n)+\frac{d}{c+d-p}*h(n) \tag{1}\]  
In (1), the \(c\) and \(d\) are weight adjustment parameters, and \(p\) is the local obstacle rate. The local obstacle rate is changed according to the current node's position movement. When \(p\) changes, the weights of \(h(n)\) and \(g(n)\) change accordingly, but the sum of the two is 1. A larger value of \(p\) represents that the obstacles near the current node are denser. At the same time, the weight of \(h(n)\) becomes smaller, and the algorithm searches slower, so that the algorithm will not miss the end point. A smaller value of \(p\) means the \(h(n)\) weights become larger, and the algorithm searching speed is sped up. When the value of \((c-p+d)/d\) is 1, then \(f(n)=g(n)+h(n)\). For the standard A* algorithm, the search speed, search space and the final path, and the basic algorithm results are the same, and the \(c\), \(d\) are both constant.  
Figure 4: Localised obstacle rate acquisition map.  
After many experiments, the authors found that these two numbers and the local obstacle rate of \(p_{min}\), \(p_{max}\) meet the relationship of (2), as shown as follows:  
\[\begin{cases}\frac{d}{c+p_{max}-d}=\lambda_{1},\lambda_{1}\in\cup(0.57)\\ \frac{d}{c+p_{min}-d}=\lambda_{2},\lambda_{2}\in\cup(0.43)\end{cases} \tag{2}\]  
There is a large amount of experimental proof that the corresponding relationship to determine the values of the constants \(c,\ d\) are 4 and 3, as well as to ensure that the value of \(p\) is within the range of \([p_{min},p_{max}]\), where the value of the weight \((c-p+d)/d\) is always maintained within the range of \([\lambda_{1},\lambda_{2}]\). \(\lambda_{1}\) and \(\lambda_{2}\) are the customised search area adjustment factors when the two values are roughly within the range of 0.45 and 0.55. When these two values are roughly within the range of 0.45 and 0.55, the algorithm will not produce a large number of redundant nodes due to slow search speed, nor will it miss the optimal path due to too fast search speed. \(h(n)\) weights are maintained within a reasonable range, and under the influence of different local obstacle rates, the algorithm will adaptively adjust the weights according to the \(p\) value, which produces different search spaces and search speeds according to the map situation. While making the path relatively optimal, it also ensures the flexibility as well as efficiency of the algorithm.