# Research on the A* Algorithm for Automatic Guided Vehicles in Large-Scale Maps
## 2 A* Algorithm and Analysis of Its Problems
### Problems with the A* Algorithm
The time complexity of the A* algorithm is mainly determined by the accuracy of the valuation function and the size of the search space. In the most unfavourable case, if the accuracy of the valuation function is insufficient or the search space is abnormally large, the time complexity of the A* algorithm may climb to the exponential level, which is expressed as \(O\left(b^{d}\right)\), where b represents the average number of branches at each node, and d represents the length of the shortest path from the start to the end. However, when the valuation function has sufficient accuracy, the A* algorithm is able to drastically reduce the search space, which in turn effectively reduces the time complexity. Typically, the time complexity of the A* algorithm is \(O\left(b^{h}\right)\), where h represents the minimum value of the heuristic function, which reflects the minimum estimation cost from the current node to the end point. As for the space complexity of the A* algorithm, it is mainly limited by its search strategy and the choice of data structure. In the worst-case scenario, the space complexity of the A* algorithm may equally reach exponential levels, but this often depends on the specific implementation and the size of the search space. Figure 3 clearly shows the results of the A* algorithm under various conditions with different obstacle ratios. Meanwhile, Table 2 lists the specific running results of the A* algorithm in three map environments with different specifications and different obstacle densities. Through the comparative analysis, we can intuitively observe that there exists a significant positive correlation between the complexity of the map and the running time of the algorithm, the number of expansion nodes, and the path length. Specifically, when the size and complexity of the map are larger and higher (i.e., the higher the proportion of obstacles), the running time of the A* algorithm will be extended accordingly, and at the same time, the number of nodes to be expanded will also increase significantly. This is because as the map complexity increases, the algorithm needs to face more decision points and path choices during the search process, which increases \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Map** & **Obstacle Ratio** & **Algorithm Time** & **Node** & **Length** \\ \hline
30 \(\times\) 30 & 0.11 & 0.0156 & 150 & 37.7899 \\
30 \(\times\) 30 & 0.25 & 0.0312 & 257 & 40.15 \\
50 \(\times\) 50 & 0.21 & 0.3124 & 715 & 72.1699 \\
50 \(\times\) 50 & 0.36 & 0.7524 & 1130 & 83.4399 \\
200 \(\times\) 200 & 0.29 & 105.3794 & 12,711 & 297.5700 \\
200 \(\times\) 200 & 0.47 & 118.5033 & 13,549 & 300.2400 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Table of results for different specifications with different complexities. the computational and time costs. In addition, the path length also grows as the map complexity increases because the algorithm needs to bypass more obstacles to find the best path to the goal. In summary, the complexity of the map is one of the key factors affecting the performance of the A* algorithm, which is directly related to the operational efficiency of the algorithm, the number of node extensions, and the merit of the path. Therefore, when designing and applying the A* algorithm, we need to fully consider the complexity of the map and take corresponding optimisation measures to improve the performance and efficiency of the algorithm. (2)  
Inadequate environment awareness of heuristic functions. The heuristic functions employed by traditional A* algorithms often fail to adequately take into account the obstacles in the map, a key environmental factor, when estimating the cost of travelling from the current node to the target node [35]. The distribution and number of obstacles actually have a crucial impact on path selection and search efficiency.