# 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
In addition, the heuristic function is carefully designed to be based on a cost evaluation that is closer to the actual cost, a feature that greatly contributes to the algorithm's search efficiency and significantly reduces unnecessary node expansions, which in turn shortens the overall running time. Therefore, the optimised evaluation function plays an indispensable and important role in improving the performance and path quality of the PA* algorithm. In conclusion, for the three key metrics of algorithm runtime, path length, and number of extended nodes, the fusion algorithm (PA*) achieved the best overall performance through the combined application of simulated annealing, local obstacle rate optimisation, and two-layer neighbourhood search strategies. Each strategy improved the efficiency and path quality of the algorithm to a different extent, and the synergy between the strategies further amplified these advantages. Therefore, the fusion strategy is an effective means to enhance the path search capability of the A* algorithm in complex environments. ### Comparison with Existing Algorithms

This section verifies the state of the art of the proposed algorithm by comparing it with the existing algorithms in the literature. Based on local obstacle rate, dynamic neighbourhood, and simulated annealing, the improved algorithm is denoted as the PA* algorithm, the PA* algorithm plus the algorithm for removing redundant nodes is called PA*F, and the improved A* algorithm proposed by [PERSON] [26] is denoted as the A*Xu algorithm. The weighted-average-distance-based algorithm proposed by [PERSON] et al. [13] is denoted as the A*Yu improved algorithm. The A* algorithm based on jump point search, denoted as A*JPS, was proposed by [PERSON] [11] et al. The comparison results are shown in Table 8. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Map** & **Algorithm** & **Time** & **Node** & **Length** \\ \hline \multirow{4}{*}{50 \(\times\) 50} & PA* & 0.0156 & 62 & 72.7599 \\  & PA*F & 0.1306 & 62 & 68.7525 \\  & A*[PERSON] & 0.1823 & 344 & 69.2527 \\  & A*JPS & 1.5035 & 182 & 69.9575 \\  & A*[PERSON] & 0.1679 & 62 & 72.7599 \\ \hline \multirow{4}{*}{100 \(\times\) 100} & PA* & 0.0468 & 119 & 151.3899 \\  & PA*F & 0.1286 & 119 & 147.0273 \\ \cline{1-1}  & A*[PERSON] & 0.1395 & 1240 & 149.4097 \\ \cline{1-1}  & A*JPS & 1.9397 & 372 & 147.3245 \\ \cline{1-1}  & A*[PERSON] & 0.4890 & 126 & 153.7499 \\ \hline \multirow{4}{*}{200 \(\times\) 200} & PA* & 0.1874 & 252 & 303.2700 \\  & PA*F & 1.5842 & 252 & 297.5900 \\ \cline{1-1}  & A*Xu & 0.5357 & 4215 & 297.6360 \\ \cline{1-1}  & A*JPS & 34.1087 & 5977 & 297.3460 \\ \cline{1-1}  & A*Yu & 1.7506 & 282 & 308.4500 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Comparison chart with existing algorithms. Through the in-depth analysis and comparison of the data in the table, it can be clearly seen that the PA*F algorithm demonstrated a significant performance improvement compared to the traditional algorithm. Specifically, the algorithm achieved an average path length reduction of 2.3% in path planning, while its algorithmic running time and the number of expansion nodes were reduced by an amazing 84% and 94%, respectively. This excellent performance is mainly attributed to the various efficient optimisation strategies integrated into the PA*F algorithm, including the incorporation of simulated annealing techniques, the implementation of local obstacle rate optimisation, and the flexible and versatile neighbourhood search mechanism. These strategies complement each other in the core operations of the algorithm, effectively reducing unnecessary node expansion and computation, thus greatly accelerating the search process and improving the overall efficiency. Further, the PA*F algorithm also carries out a refined smoothing process after path generation to ensure the continuity and feasibility of the path.