# 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
The performance of each strategy variant reveals the specific role and contribution of the different strategies in the algorithm. For instance, the simulated annealing strategy significantly mitigates the risk of algorithms becoming trapped in local optima. Meanwhile, the local obstacle rate optimisation accelerates the discovery of feasible paths in complex \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*-SA & 0.0312 & 188 & 101.7099 \\  & PA*-SC & 0.0169 & 65 & 77.3499 \\  & PA*-OR & 0.2343 & 702 & 72.7599 \\  & PA*-IF & 0.3151 & 352 & 72.45 \\ \hline \multirow{4}{*}{100 \(\times\) 100} & PA* & 0.0468 & 119 & 151.3899 \\  & PA*-SA & 0.7810 & 214 & 181.4199 \\  & PA*-SC & 0.0625 & 125 & 154.5699 \\  & PA*-OR & 2.8547 & 2258 & 150.4399 \\  & PA*-IF & 1.0920 & 193 & 150.4799 \\ \hline \multirow{4}{*}{200 \(\times\) 200} & PA* & 0.1874 & 252 & 303.2700 \\  & PA*-SA & 0.4842 & 591 & 373.5800 \\ \cline{1-1}  & PA*-SC & 0.2187 & 252 & 309.9100 \\ \cline{1-1}  & PA*-OR & 77.3190 & 13,549 & 303.5400 \\ \cline{1-1}  & PA*-IF & 209.7842 & 14,253 & 305.2400 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Comparison of the fusion algorithm and fusion algorithm removal strategies table. environments. In summary, a series of meticulously designed comparative experiments in this study confirms the efficacy of integrating these strategies in enhancing algorithm performance. Furthermore, it delves into the specific functions and interactions of each strategy within the algorithms, offering insightful references and inspiration for future algorithm optimisation and enhancement. In comparing the fusion algorithm (PA\({}^{\star}\)) with its simplified version (i.e., the variant that removes a specific strategy), we identified the key role of strategy fusion in improving

Figure 12: Fusion algorithm and removing a certain strategy result graph. the performance of the algorithm. First, when the simulated annealing strategy was removed from the fusion algorithm (to form PA*-SA), the performance of the algorithm dropped significantly. Specifically, the path length increased by 25% on average, and the number of expansion nodes and the algorithm runtime also increased by factors of 1.3 and 6, respectively. This was mainly due to the fact that after removing the simulated annealing algorithm, the algorithm relies on the node selection mechanism of the A\({}^{\star}\) algorithm, which lacks the global search capability and probabilistic acceptance of inferior solutions of the simulated annealing algorithm. The algorithm must then rely on a more extensive search to find feasible paths, thus increasing the computational burden. Since the algorithm may fall into local optimal solutions and the search range is limited, the quality of the final path obtained (e.g., path length) may be degraded. This is confirmed by the increased tortuosity of the paths, as shown in Figure 11(c), as the algorithm is more likely to adopt a non-optimal steering strategy in the absence of directional guidance and can fall into local optimal solutions, resulting in the searched paths constantly wandering within a certain range. On the other hand, although the local obstacle rate and the two-layer neighbourhood expansion strategy reduce the number of node expansions and shorten the algorithm's runtime to a certain extent, they do not completely offset the negative impact of the simulated annealing flaw as they are also intrinsically constrained by the complexity of the multi-layer neighbourhood selection. We then delved into the impact of removing the variable step-size strategy (form PA*-SC) from the comprehensive path planning algorithm (PA*).