# 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
### Improved \(A^{\star}\) Algorithm Based on Two-Layer Neighbourhoods  
Traditional A* algorithms, whether they employ a four-neighbourhood or eight-neighbourhood search strategy, inevitably involve the expansion of a large number of nodes. More specifically, when the algorithm searches in these fixed directions (e.g., 45 or 90\({}^{\circ}\)), even in an open space without obstacles, it may result in the generation of less direct paths [36], thus increasing the total length of the path.  
To overcome this limitation, we propose an innovative dynamic two-layer neighbourhood search strategy. The core of this strategy lies in constructing two layers of neighbourhood structures with different selection strategies. In the first layer, we introduce the 5-neighbourhood search method, an adaptation that aims to initially optimise the search paths by eliminating nodes that significantly deviate from the desired search direction through a more fine-grained consideration, i.e., the relative positional relationship between the current node and the start and end points, in order to optimise the orientation of the search path [12]. Immediately after that, for the second level of neighbourhood selection, we make full use of the local obstacle rate information derived from the previous calculations. This step empowers the algorithm to dynamically adjust the search range according to the real-time environment (especially the distribution of obstacles around the nodes). Specifically, when the local obstacle rate is high, the algorithm tends to reduce or avoid unnecessary neighbourhood extensions in order to reduce redundant path segments that may be introduced due to blind expansion. Through this dynamic adjustment, we can not only control the growth of the search space more effectively, but also further shorten the path length on the basis of ensuring the feasibility of the path, thus improving the overall search efficiency and path quality.  
The use of one layer neighbourhood search may increase the path length with less obstacle rate. As shown in Figure 5, the parent node has to reach the child node9. If the traditional one-layer neighbourhood search method is used, then it needs the parent node to reach the child node2 first, and then walk from the child node2 to the child node9, and then the distance from the parent node to the child node9 is \(\sqrt{2}+1\) (approximately 2.414). If the parent node walks directly to the child node9, then the length of the path taken is \(\sqrt{5}\) (approximately 2.236). Therefore, we choose to take a two-layer neighbourhood approach as shown in Figure 5. Eight nodes of the second layer neighbourhood are added on top of the one-layer neighbourhood, and the value of the local obstacle rate mentioned in the previous section is used as a principle for the step length change, i.e., whether to extend the one-layer neighbourhood or the two-layer neighbourhood. The criterion for the judgment is as follows. Obstacle rate p is obtained based on the local obstacle rate, and then the step length is classified based on the obstacle rate. A basic idea is that, first of all, according to the ground layer neighbourhood, a step length is to select the corresponding five nodes, at this time to judge the value of \(p\). If \(p<0.5\), the second layer of neighbourhood is selected. When the value of the local obstacle rate exceeds the threshold value of 0.5, it indicates that the obstacles between the current nodes are closely distributed. In this case, choosing the second layer of neighbourhood for searching may increase the risk of the algorithm planning a path \"through the wall\" or crossing an infeasible region. Therefore, in order to ensure the feasibility and safety of the path, the algorithm will only use the first layer of neighbourhood for search and evaluation.  
The selection of nodes for the second level neighbourhood is shown in Table 3.