# 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
## 4 Simulation Experiment

In order to validate the feasibility of the improved algorithm, experiments were conducted on the effectiveness of various components of the proposed algorithm, i.e., validation of the effectiveness of individual strategies (Section 4.1), validation of the effectiveness of the overall strategy (Section 4.2), and validation of the comparison with the existing algorithm (Section 4.3). All of the above comparisons were made on three randomly generated raster maps, 50 \(\times\) 50, 100 \(\times\) 100, and 200 \(\times\) 200, with two map runs selected for each map size and the average of the run results selected. The simulation experiments were validated using a laptop computer with Intel(R) Core(TM) i5-8250U CPU @ 1.80 GHz, 8 GB of running memory, and PyCharm2020.1 as the experimental hardware and software. The simulation running experiments were conducted using Python 3.0 programming in a PyCharm 2020 programming environment. The parameters involved in the proposed algorithm were set in the experiment as follows: \(c=3,\ d=4,\ T=65,\ r=0.85\). ### Validation of Individual Strategy Effectiveness

In order to fully assess the independent contribution of the different strategies to the performance of the algorithms, we carried out a comparative study in which the base algorithm (labelled A*) was compared in detail with variants that incorporate each individual strategy. These strategies include dynamic neighbourhood selection (A*SC), simulated annealing (A*SA), local obstacle rate adjustment (A*OR), and modifying the evaluation function (A*IF). The comparative analysis focuses on the efficiency of the algorithm operation, the size of the exploration space (measured by the number of expansion nodes), and the degree of optimisation of the final path (using the path length as an indicator). The specific comparison results are summarised in Table 6, which shows the effectiveness of each strategy in improving the performance of the base A* algorithm. From Figure 11b, it can be seen that the basic A* algorithm tends to have multiple node iterations in the path search process, and the process of finding a path in a 100 \(\times\) 100 map requires more than 2000 iterations. And the iteration process is easy to fall into a local optimal loop, which is manifested as oscillating in a specific search space region. In order to improve this situation, we added the simulated annealing algorithm (A*SA) to the basic algorithm for the probabilistic selection of nodes so that the algorithm reduced the amount of computation and jumped out of the local optimum. This is shown in Figure 11d. With the addition of simulated annealing, the algorithm only needs about 120 iterations to find the path, and the node selection process does not fall into a certain optimal interval. Compared with Figure 11c, the running time of the A*SA algorithm was reduced by 99% on average, \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Map** & **Algorithm** & **Time** & **Node** & **Length** \\ \hline \multirow{4}{*}{\(50\times 50\)} & A*SC & 0.3124 & 715 & 72.1699 \\  & A*SA & 0.0014 & 63 & 77.3499 \\  & A*SC & 0.0156 & 62 & 72.7599 \\  & A*OR & 0.0158 & 63 & 72.7599 \\  & A*IF & 0.0119 & 62 & 72.7599 \\ \hline \multirow{4}{*}{\(100\times 100\)} & A*SC & 3.2336 & 2282 & 148.4399 \\  & A*SA & 0.0312 & 123 & 154.5699 \\ \cline{1-1}  & A*SC & 0.0468 & 119 & 151.3899 \\ \cline{1-1}  & A*OR & 0.0468 & 128 & 153.7499 \\ \cline{1-1}  & A*IF & 0.0398 & 124 & 154.3899 \\ \hline \multirow{4}{*}{\(200\times 200\)} & A*SC & 118.5033 & 13,549 & 300.2400 \\  & A*SA & 0.1718 & 248 & 309.9100 \\ \cline{1-1}  & A*SC & 0.1718 & 252 & 309.9100 \\ \cline{1-1}  & A*OR & 0.1562 & 255 & 308.5000 \\ \cline{1-1}  & A*IF & 0.1486 & 248 & 308.5000 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Comparison table of individual-strategy algorithms and base algorithms. and the number of expansion nodes was also reduced by 94% on average.