# 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
### On Factors Affecting the Algorithm  
Before starting the A* algorithm, a series of key parameters and quantities must be explicitly set, and these parameters have a profound impact on the operating results of the algorithm. The following are the key parameters that must be explicitly set before starting the A* algorithm in this study, as well as their specific impact on the operational results of the algorithm:  
1. Start and end points of path planning  
The start and end points of path planning must be clearly defined, because different start and end positions will directly lead to very different path planning results. In this paper, the start and end points were roughly located in the two diagonal positions of the map, aiming to comprehensively show the whole process of path planning and fully consider the interference of obstacles on the algorithm's performance.  
1. Neighbourhood selection strategy  
Neighbourhood selection plays an important role in the length of path planning and in the practical application of AGVs (automated guided vehicles). Generally speaking, the larger the range of neighbourhood selection, the relatively fewer nodes required for path expansion, while the smaller the range of neighbourhood selection, the fewer path turning points are planned. In this paper, we adopted a two-layer neighbourhood strategy and combined it with a dynamic approach to flexibly adjust the neighbourhood based on the relative number of obstacles, so as to ensure the accessibility of the path while quickly finding the path and reducing node expansion.  
(3) Estimating the cost \(h(n)\)  
\(h(n)\) is used to estimate the cost from the current node n to the target node (i.e., the termination point), and its accuracy and efficiency play a decisive role in the efficacy and precision of the A* algorithm. If the heuristic function \(h(n)\) is too optimistic (i.e., the estimated value is much lower than the actual value), it may lead to the algorithm searching for too many nodes, which reduces the efficiency; if \(h(n)\) is too pessimistic (i.e., the estimated value is much higher than the actual value), the algorithm may not be able to find the optimal path. In addition, the calculation of \(h(n)\) in the traditional A* algorithm is fixed and will not be adjusted with environmental changes (e.g., changes in the location and number of obstacles), which may lead to the algorithm needing to visit more nodes in the search process. Therefore, the heuristic function \(h(n)\) designed in this paper considers dynamic weights and turning costs, aiming to dynamically adjust the computation of \(h(n)\) according to the changes of obstacles to reflect the latest environmental information, as well as balancing the algorithm turning by increasing the turning costs to achieve the comprehensive optimisation of the shortest path length with the least number of turns.  
(4) Actual cost \(g(n)\)  
The actual cost function \(g(n)\) reflects the true path cost from the start node to the current node, and together with the estimated cost function \(h(n)\), it forms the heuristic function of the A* algorithm. The operation of the A* algorithm is guided by the sum of the two, and the node selection is based on the minimum value of the sum of the two. If the actual cost function \(g(n)\) is inaccurate, it may lead the algorithm to choose the wrong path. Therefore, this paper introduces direction guidance in \(g(n)\), which aims to provide the correct direction guidance for path planning.  
In summary, the A* algorithm must explicitly set key parameters such as start node, target node, estimated cost \(h(n)\), actual cost \(g(n)\), and neighbourhood selection strategy before launching, which together determine the algorithm's operation results. Therefore, this paper is designed accordingly on the basis of fully considering the impact of these conditions on the results.