# 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
### Modifications to the Evaluation Function
#### 3.4.3 Adding Direction Change Penalty
Despite a relatively modest direct effect on the algorithm's node extensions and runtime, evidenced by a 3.3% average increase in search nodes and a 19% average rise in execution time, this adjustment had a notable impact on path lengths, with an average increase of approximately 3.5%. This phenomenon is rooted in the fact that in scenarios where obstacles are densely distributed or fine steering is required, the selection of the second layer of neighbours is crucial for generating smooth and efficient paths. The removal of the variable step size strategy precisely limits the algorithm's ability to flexibly adjust the step size in these complex environments. As shown in Figure 11(d), in the early stage of path search, when encountering regions with relatively sparse obstacles, the algorithm failed to adopt the optimal step-size strategy due to the absence of the variable step-size policy, resulting in a long single step, which in turn increased the overall path length. Although these regions do not account for a high percentage of the overall map, their effect on path length is still significant, although this effect is relatively mild compared to other factors. In summary, variable step length strategies play an important role in improving the adaptability and efficiency of path planning algorithms. In exploring a variant of the fused path planning algorithm (PA*), we analysed the impact of removing the weights associated with local obstacle rates in favour of a uniform and simplified 1:1 weighting strategy (i.e., PA*-OR), as shown in Figure 11(e). While this change yielded minor success in the direct optimisation of path length, achieving a reduction of approximately 1.1%, the overall performance of the algorithm suffered a significant dip. Specifically, due to the lack of accurate guidance from local obstacle rate information, the algorithm was difficult to effectively identify and avoid high-risk regions during the search process, which directly led to a dramatic expansion of the search space, with the number of node extensions surging by as much as 26 times. At the same time, the time cost of path search also rose sharply, increasing by a staggering 157 times. This series of negative effects profoundly revealed the key role played by local obstacle rate information in improving the algorithm's search efficiency and path quality. It not only helps algorithms to quickly target and avoid potentially dense obstacle areas and reduce unnecessary search attempts but also facilitates the generation of more reasonable and efficient path planning schemes. Therefore, retaining and utilising local obstacle rate information is crucial for optimising the performance of path planning algorithms. Ultimately, when the optimised evaluation function was removed from the fused path planning algorithm (PA*) (to form the PA-IF version), through the comparative analysis in Table 7, we can clearly observe that the algorithm's runtime in larger map environments (e.g., 200 \(\times\) 200 pixel maps) appeared to increase extremely significantly compared to the full PA* algorithm by as much as 1000 times or more. Meanwhile, comparing the path results presented in Figure 12b,f, the path lengths generated by the PA*-IF algorithm were longer than those of the PA* algorithm by about 0.7%, despite the fact that there was not much difference between the two in terms of the overall morphology. The core reason for this phenomenon is that the modified heuristic function adopted by the original PA* algorithm not only provides clear directional guidance for the search process but it also intelligently selects the diagonal distance as the basis for evaluation based on the actual distribution of obstacles in the map, thus allowing the algorithm to cross obstacles more flexibly and realise efficient movement without directional constraints during path search.