# 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.3 Adding Direction Change Penalty
However, as seen in Figure 11,c, the A*SA algorithm may be slightly longer than the base A* algorithm in terms of paths, and from Table 6, it can be found that the average percentage increase in path length was 4.8%. And this was mainly due to the fact that the algorithm has a certain probability of accepting non-optimal solutions (i.e., those nodes that appear to be more costly in the short term but may lead to the global optimal solution), i.e., in the short term, the algorithm may have chosen a relatively better rather than optimal node. Although the slight increase in path length is a side effect of the simulated annealing algorithm, the significant increase in algorithmic efficiency and search capability it brings makes this strategy particularly important in complex path search problems. Figure 11: Diagram of the results of the single-strategy algorithm run. In this paper, we designed an innovative two-layer neighbourhood search mechanism (A*SC) shown in Fig. 11e, which provides the core algorithm a high degree of flexibility and intelligence to dynamically adjust its search strategy according to the real-time changes in the distribution density of obstacles in the environment. With the reasonable expansion of the neighbourhood expansion range, the number of nodes to be evaluated and expanded by the algorithm was significantly reduced. It is attributed to the double-layer neighbourhood structure effectively covering a wider potential path area, thus significantly reducing the frequency of repeated calculations and ineffective explorations, as well as ultimately optimising the overall running time of the algorithm by up to 97%, while the number of node evaluations was reduced by an average of 94.7%. As shown in Figure 11b,f, when analysed from the perspective of the node selection iteration process, the A*SC algorithm achieved a significant reduction in the number of iterations under a single strategy compared to the base algorithm, regardless of whether it faces complex environments with dense or sparse obstacles, with an average reduction of 90%. Particularly noteworthy is that in the early stage of the search process, the algorithm demonstrated a prioritisation of the g-value (the actual cost from the starting point to the current point), resulting in a relatively high h-value (the estimated cost from the current point to the end point), a strategic adjustment that further accelerates the algorithm's search efficiency. Specifically, by intelligently regulating the search scope and neighbourhood selection strategy, the A*SC algorithm achieved rapid convergence to the optimal or near-optimal solution while ensuring that the quality of the path solution is not compromised, which fully verifies the efficiency and practicality of its design strategy. This result not only provides new ideas for the field of path planning but also shows the great potential of algorithmic optimisation in dealing with complex dynamic environments. On the other hand, the performance of the algorithm will be further improved if weights related to local obstacle rates (denoted as A*OR) are introduced into the base A* algorithm. Specifically, by assigning weights based on local obstacle rates to different regions or nodes on the path, the algorithm is able to more intelligently evaluate and select nodes with higher weights (i.e., paths that are more likely to be efficient or safe) for expansion. This strategy significantly reduces the running time of the algorithm and the number of nodes to expand, allowing the algorithm to more quickly focus on path segments that are more likely to constitute the final solution. Although the A*OR algorithm may slightly increase the direct length of the path search (by about 3%) due to an imperfect match between the actual cost and the heuristically estimated cost (i.e., the weight ratio is not strictly 1:1), this small cost is exchanged for a significant increase in the speed of the search (on average, 91% shorter).