# Research on the A* Algorithm for Automatic Guided Vehicles in Large-Scale Maps
## 2 A* Algorithm and Analysis of Its Problems
### Overview of the A* Algorithm
#### 2.1.2 Conceptual Illustration of the A* Algorithm in Practical Applications  
When considering a maze scenario(As shown in Figure 1), we can set the starting point to be S and the end point to be G, where black squares represent obstacles and each square in the maze corresponds to a node. Between these nodes, the distance between neighbouring nodes up and down is 1, and the distance between neighbouring nodes diagonally is root 2. The following is an illustration of an example of a shortest path successfully found by the A* algorithm. In this example, the valuation function \(f\left(n\right)\) consists of the following two parts:  
\(g(n)\): represents the actual path length traveled from the starting point S to the current node n.  
\(h(n)\): represents the heuristic estimated distance from the current node n to the end point G. Here, we adopt the Euclidean distance, etc., as the heuristic function to compute this estimate. During the search process from S to G, the path passes through nodes A, B, C, D, F, and G. Regarding the heuristic function values of these nodes, we organise them in Table 1 as well as Figure 1 for a detailed presentation. During the process of node expansion, it can be observed from Table 1 that the value of \(g(n)\) shows a continuous increasing trend. However, the value of \(h(n)\) is relatively uncertain due to the presence of obstacles. In the A* algorithm, the change in the value of \(f(n)\) depends on the relative movement of \(g(n)\) and \(h(n)\). In some specific contexts, as the search process gradually approaching the target node, the value of \(h(n)\) may gradually decrease, which in turn triggers a downward trend in the value of \(f(n)\) as well. However, in other contexts, especially when the search path is more complex, with twists and turns or a large number of obstacles, the increase in \(g(n)\) may exceed the decrease in \(h(n)\), which leads to a rise in the value of \(f(n)\). As shown in Figure 2, the value of \(f(n)\) does not always rise continuously. Nevertheless, during the selection of nodes, the algorithm always follows the principle of selecting the node with the smallest value of \(f(n)\) from the neighbourhood of the current node each time and expanding it until it finally reaches the end point. The A* algorithm, as an efficient heuristic search strategy, cleverly combines the global optimal property of [PERSON]'s algorithm with the local optimal selection wisdom of the greedy algorithm. The algorithm intelligently evaluates the potential value of each node, the so-called \"surrogate value\", between the starting point and the end point by means of a well-designed heuristic function and prioritises the exploration of those nodes that seem to be the most likely to lead to the goal. The core of this process is the design and \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Node** & \(g(n)\) & \(h(n)\) & \(f(n)=g(n)+h(n)\) \\ \hline S & 0 & 5.656 & 5.656 \\ A & 1 & 5 & 6 \\ B & 2 & 4.472 & 6.472 \\ C & 3 & 3.606 & 6.606 \\ D & 4 & 4.828 & 8.828 \\ F & 5 & 2.236 & 7.236 \\ G & 6 & 1.414 & 7.414 \\ E & 7.414 & 0 & 7.414 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Table of different node surrogate values. Figure 1: Maze pathfinding node graph. Figure 2: Graph of the value of different node generations. implementation of the heuristic function, which directly determines the efficiency and accuracy of the algorithm in finding the path. The heuristic function consists of two key components: \(g(n)\) and \(h(n)\). \(g(n)\), as the name suggests, represents the actual cost or distance accumulated from the starting node to the current node n. It faithfully records the \"distance\" of each step in the process of path exploration. \(h(n)\), on the other hand, is an estimate of the distance from the current node n to the goal node, and this estimate is crucial for guiding the search direction.