# 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
This is because, by giving the algorithm greater decision weighting, especially for local obstacle information that is critical for path selection, A*OR is able to steer the search process more efficiently and avoid wasting computational resources in unimportant areas, thus significantly improving the overall search efficiency. The refinement of the modified evaluation function (A*IF) for the base algorithm is centred on the introduction of turn cost considerations, the incorporation of a direction guidance mechanism, and the use of diagonal distance as the basis for evaluation. This series of innovations achieved significant results in significantly improving the performance of the algorithm, as evidenced by the drastic reduction of the running time (up to 97%) and the number of expansion nodes (about 94%), which undoubtedly enhanced the efficiency and practicality of the algorithm compared to the original algorithm. However, it is worth noting that this revision of the heuristic function is accompanied by potential side effects. Specifically, due to the incorporation of complex factors such as steering cost and path direction in the design of the heuristic function, the valuation process may tend to be slightly higher than the actual path cost in certain situations. This feature, while enhancing the comprehensiveness and accuracy of the algorithm, inevitably leads to an increase in the length of the final generated paths compared to the base algorithm, with an increase of about 2.5%. Therefore, while enjoying the convenience of the improvedperformance, we need to carefully evaluate the impact of this increase in path length on practical application scenarios. In terms of overall effectiveness, each of these single strategy improvements significantly outperforms the base algorithm. Although there may be a slight sacrifice in some specific metrics (e.g., path length or running speed), the algorithms' improvements in the number of expansion nodes, search efficiency, and avoidance of useless directions are more significant. This overall performance improvement proves the effectiveness and usefulness of the proposed strategy, providing strong support for the application of the A* algorithm in complex environments. However, the individual strategies can increase the immediate cost of the path, but in the long run, they greatly improve the global search capability of the algorithm and the quality of the final solution. ### Validation of the Effectiveness of Fusion Strategies

In order to comprehensively assess the overall efficacy of the algorithm after the combined application of multiple strategies, this study designed a series of comparative experiments in which the fusion algorithm integrating all individual strategies (labelled PA*) was exhaustively compared with its individual strategy variants. These variants are the fusion algorithm with the simulated annealing strategy removed (PA*-SA), the fusion algorithm with the local obstacle rate optimisation strategy removed (PA*-OR), the fusion algorithm with the dynamic neighbourhood strategy removed (PA*-SC), and the fusion algorithm with the modification of the evaluation function removed (PA*-IF). The experimental results show that these algorithms with different configurations exhibit their own characteristics and performance differences under specific test conditions. Table 7 details the specific performance of each algorithm on a number of evaluation metrics, including but not limited to key parameters such as algorithm running time, number of extended nodes, path length, etc. Meanwhile, Figure 12 shows the path search effect of these algorithms on the 50 \(\times\) 50 map in a visual way, further verifying the accuracy of the experimental data. The comparative analysis clearly shows that the PA* algorithm fused with all individual strategies exhibited significant advantages in all three metrics, demonstrating the effectiveness of strategy fusion in improving the overall effectiveness of the algorithm.