# 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.2 Modification of \(g(n)\) Cost  
The search process of the A* algorithm is guided by the heuristic function as the main principle, which will select the minimum value of the cost of each node operation. The  
Figure 5: Bilayer neighbourhood node graph.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Layer 1 Neighbourhood Selection Nodes** & **Layer 2 Neighbourhood Selection Nodes** \\ \hline
0, 1, 2, 3, 4 & 9, 10, 11, 8 \\
1, 2, 3, 4, 5 & 11, 12, 9, 10 \\
2, 3, 4, 5, 6 & 9, 10, 13, 14 \\
3, 4, 5, 6, 7 & 11, 12, 13, 14 \\
4, 5, 6, 7, 0 & 11, 8, 15, 12 \\
5, 6, 7, 0, 1 & 15, 8, 13, 14 \\
6, 7, 0, 1, 2 & 13, 14, 9, 10 \\
7, 0, 1, 2, 3 & 15, 8, 9, 10 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Bi-level neighbourhood search table.  
value consists of two parts, \(g(n)\) and \(h(n)\). In the pre-search period, far away from the target point, at this time, the generation value of \(g(n)\) is smaller, and \(h(n)\) plays a major role in guiding; in the late search gradually close to the target point, the starting point to the current node of the actual generation value is more important. During the node search, there will be a situation where the values of \(h(n)\) are equal. At this time, \(g(n)\) will dominate the search and play a decisive role in guiding the direction of the whole search process. Therefore, this subsection proposes modifying the cost of \(g(n)\) by adding the factor of angle to \(g(n)\) to enhance the search enlightenment of \(g(n)\).  
When the direction of node expansion converges to the straight-line direction indicated by the direct line connecting the current node and the end point, the actual moving distance of the node will be shortened accordingly. In this case, the node's pathfinding path will naturally converge to the direction of the optimal path, and this fitting process not only accelerates the search speed but also makes the final path obtained closer to the optimal solution in terms of quality. As shown in the Figure 6, the start node, the child node to be expanded, and the target node are denoted by S, N, and E, respectively. The black solid line represents the moving vector from the start node to the current node for expansion, and the black dashed line represents the moving vector from the current node to the target node, and the angle between the two vectors is denoted as \(\theta\).  
Let the start node be S(\(x_{1},y_{1}\)), the current node be N(\(x_{n},y_{n}\)), the target node be E(\(x_{2},y_{2}\)), \(a=(x_{2}-x_{n},y_{2}-y_{n})\), and \(b=(x_{2}-x_{1},y_{2}-y_{1})\).  
\[cos\theta=\frac{a\cdot b}{|a|\times|b|}=\frac{ax\times bx+ay\times by}{\sqrt{ \left(ax\right)^{2}+\left(ay\right)^{2}+\sqrt{\left(bx\right)^{2}+\left(by \right)^{2}}}} \tag{4}\]  
According to the relative position relationship between the search vector of the current node and the move vector of the next extension, it can be seen that the smaller the vector angle \(\theta\) is, the closer the move direction to the optimal path, and the better the fit is. Therefore, the function of \(cos\theta\) is added to the cost of \(g(n)\) as part of the actual moving cost, so as to enhance the enlightenment and guidance of \(g(n)\) and improve the search speed. However, the function should be set reasonably, and the value should be moderate. If the value is too large, the computation in the complex environment may become too huge, and if it is too small, it is not very inspiring for the path. The new \(g(n)\) calculation formula is  
\[g^{\prime}(n)=g(n)+\left(\frac{1-cos\theta}{8}+1\right)\times\sqrt{2} \tag{5}\]  
In (5), \(g(n)\) is the distance from the start node to the current node, calculated by the diagonal distance.