# 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
If the straight line is unobstructed, remove the intermediate node (\(n_{2}\)). If no node has been removed in the previous round, directly perform the above straight line connectivity test on the current three consecutive nodes (e.g., \(n_{1}\), \(n_{2}\), \(n_{3}\)) and decide whether to remove the intermediate node \(n_{2}\) based on the results. Step 3: Repeat the redundant node identification and removal process in Step 2, progressively moving forward along the path until reaching the end point E. At each step, an attempt is made to simplify the path by straight-line connectivity, removing intermediate nodes that do not change the passability of the path. Step 4: The algorithm ends when all the nodes have been traversed and all the possible redundant nodes have been removed, and the resulting path is the new smoothed path, which contains fewer nodes than the initial path and is more direct and efficient. By rewriting the algorithm in this way, we not only retain the core idea of the original algorithm, i.e., reducing the redundant points in the path by connecting them in a straight line, but also describe the process of identifying and removing the redundant nodes and \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Literatures** & **g(n)** & _h(n)_ & _f(n)_ \\ \hline
[38] & Manhattan distance & Horizontal, vertical, and diagonal & Manhattan distance + three-way \\  & Manhattan distance & direction decomposition of & decomposition of Euclidean \\  & Euclidean distances & distance + turn yaw angle constraints \\
[39] & Manhattan distance & Euclidean distance + projected distance & Manhattan distance + Euclidean \\  & Manhattan distance & Combination of Euclidean and & Manhattan distance + distance \\  & Manhattan distances & combination \(\times\) index weights \\  & Manhattan distance \(\times\) obstacle rate & Diagonal distance \(\times\) obstacle & Manhattan distance \(\times\) weights + directional guidance cost diagonal \\  & weights + directional guidance costs & rate weights & distance \(\times\) obstacle rate weights + turn cost \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Different ways of calculating path costs. \begin{table}
\begin{tabular}{l l l l l} \hline \hline
**Literature** & **Algorithm Time** & **Node** & **Cost** & **Length** \\ \hline
[38] & 0.3258 & 33 & 72.2847 & 36.1 \\
[39] & 0.1094 & 37 & 84.4264 & 42.1499 \\
[13] & 0.1527 & 37 & 80.4264 & 40.15 \\ Present article & 0.0312 & 30 & 83.3969 & 38.6099 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Results of different path costs in the same map. the iterative nature of the process in a clearer way. The effect of redundant node removal for the improved A* algorithm is shown in Figure 9.

### Subsections of This Chapter

The improvement of the A* algorithm is reflected in the following aspects. Firstly, based on the acquisition of local obstacle rate, a better path is quickly obtained. Secondly, based on the correlation coefficient of the local obstacle rate, the dynamic change of the neighbourhood and search step is carried out. Thirdly, the diagonal distance is chosen to calculate the estimated cost, the actual generation value is updated to add a direction guide for it, and the corresponding weight is updated according to the dynamic obstacle rate. By taking into account the problem of frequent steering, the cost of turning is added to the evaluation function. Fourthly, the simulated annealing idea is introduced into the node expansion selection to avoid falling into local optimum. Finally, for the problem of more redundant nodes in the path, the Floyd algorithm is used to delete the redundant nodes. The flowchart of the improved A* algorithm is shown in Figure 10.

Figure 10: Flowchart of the improved algorithm. Figure 9: Redundant point deletion diagram.