# 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  
In the process of traditional A* algorithm pathfinding, four-neighbourhood or eight-neighbourhood is usually adopted as the neighbourhood extension of nodes. And the estimation of the heuristic function \(h(n)\) is often based on a single distance metric, such as Manhattan distance or Euclidean distance. Not fully considering the complexity of the actual terrain and the influence of environmental factors, these methods often lead to a deviation between the value of the estimated \(h(n)\) and the actual path cost, which in turn affects the accuracy and efficiency of the algorithm. The setting of the weighting factors also has a profound effect on the overall performance and results of the algorithm. The A* algorithm determines the next search direction by calculating the value of \(f(n)\) (the total evaluated value) for each node, which is the sum of the actual distance \(g(n)\) and the predicted distance \(h(n)\). In the traditional A* algorithm, the weights of \(g(n)\) and \(h(n)\) are fixed at 1:1, which is a balance between ensuring that the shortest path is found and search efficiency. The introduction of the weighting factor allows the relative importance of \(g(n)\) and \(h(n)\) to be flexibly adjusted when calculating \(f(n)\), which in turn affects the selection of search paths and the efficiency of the algorithm. When the weight of \(h(n)\) is set as large, the A* algorithm tends to prefer paths with shorter predicted distances, which usually speeds up the algorithm's approach to the target point [33]. However, this tendency may cause the algorithm to miss certain paths with shorter actual distances but longer predicted distances, thus affecting the optimality of the final path. On the contrary, if the weight of \(h(n)\) is smaller, the algorithm relies more on the actual distance travelled \(g(n)\), which helps to discover more accurate shortest paths. However, at the same time, the search speed of the algorithm may decrease as it needs to evaluate each potential path more thoroughly. In addition, the A* algorithm follows a strict principle of expanding nodes to neighbouring regions from near and far. At the heart of this process is the execution of a detailed cost estimation for each new node that is included in the scope of examination. It is based on a carefully designed heuristic function formulae, with the aim of filtering out the lowest-cost nodes as the focus of the next step in the exploration through comparison. Admittedly, this strategy ensures that the algorithm is able to find the optimal solution to the problem;however, its limitations are obvious when dealing with large-scale datasets or complex search environments: due to the large number of nodes to be processed, the algorithm's execution time is significantly increased, and it may involve a large number of unnecessary node extensions, which inevitably reduces the overall search efficiency and performance. In analysing the path-finding process of the A* algorithm, although the heuristic function-dominated A* algorithm demonstrates a powerful path planning capability, it also exposes a series of obvious limitations when facing complex application scenarios, which can be mainly summarised as follows:  
1. Search efficiency limited by map size. When facing a huge environmental map, the search efficiency of the A* algorithm encounters severe challenges, and the search time climbs sharply [34]. This problem is partly attributed to the limitations of its node neighbourhood selection, i.e., the expansion direction is relatively fixed, resulting in a large number of nodes that need to be explored and evaluated during the search process, which in turn increases the computational burden and the overall elapsed time. The computational complexity of the A* algorithm is strongly influenced by the size of the environment and its complexity. As the size and complexity of the environment increase, the computational complexity of the A* algorithm also increases.