# 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
\(h(n)\), as a heuristic estimation, reflects the predicted cost of travelling from the current node n to the goal node, and it is intended to steer the search in a more promising direction, while \(g(n)\), computed on the basis of the actual number of steps that have already been travelled, is the exact cost of travelling from the start to the current node n. The cost of \(h(n)\) is calculated as the number of steps travelled to the current node. The A\({}^{\star}\) algorithm selects the next node to be expanded by taking into account the cost of reaching the node (g-value) and the estimated cost of travelling from the node to the target node (h-value), and uses the sum of these two, i.e., the f-value, as the basis of the selection, in order to prioritise the exploration of those nodes that have the smallest value of their f-value, i.e., those that are close to both the starting point and the target point. However, this approach may encounter a problem when dealing with complex environments or dense node graphs: a large number of nodes have similar f-values, causing the selection process to become sensitive and prone to local optima. In order to solve this problem, we can borrow the probabilistic selection mechanism in the simulated annealing algorithm to improve the node selection process of the traditional A\({}^{\star}\) algorithm. Initialisation parameters

When configuring the strategy of combining simulated annealing with the A\({}^{\star}\) algorithm, the first step is to set a reasonable initialisation temperature T and annealing rate r. In order to ensure that the algorithm can extensively explore the solution space at the initial stage and avoid premature convergence to the local optimum, the initialisation temperature T should be set to a relatively high value. For example, in this case, given that the initial node selection is close to the starting point and the range of surrogate values is taken into account, we assume a larger value such as 65 as the starting point. The choice of the annealing rate, \(r\), is a value that indicates how quickly the algorithm \"cools down\" during the search process, which determines the moment at which the algorithm shifts from extensive exploration to refined search. Generally speaking, the value of \(r\) ranges from 0.8 to 0.99, and the specific value should be adjusted according to the actual application scenario. In view of the subtle differences in the algebraic values between expending nodes in this case, we experimentally selected multiple annealing rate values (0.99, 0.985, 0.9, 0.85, 0.8) for testing. Ultimately, by comparing the running time, the number of expansion nodes and the path length with different parameter combinations, we found that the algorithm's comprehensive performance is optimal when \(T=65\) and \(r=0.85\). When \(T=65\) and \(r=0.85\), the results of the A\({}^{\star}\) algorithm for paths and extended nodes in the 50 \(\times\) 50 map are as shown in Figure 8.

Once the parameters are set, the execution phase of the algorithm follows. This phase takes the estimated value of the heuristic function \(h(n)\) as the initial value of energy, which reflects the estimated cost from the current node to the end point. Subsequently, following the standard procedure of the A\({}^{\star}\) algorithm, the algorithm starts with the initial node and first adds it to the CLOSED list (the set of evaluated nodes), and then based on a two-tier neighbourhood expansion strategy, it adds the starting point and its direct neighbours to the OPEN list (the set of nodes to be evaluated). This process is repeated until the target node is found or other termination conditions are satisfied. Get the new solution \(n^{\prime}\)

A new node \(n^{\prime}\) is selected from the open list based on the estimated value of the node with the smallest generation value \(f(n)\), and the energy of the new node n' is calculated (i.e., the estimated generation value of \(n^{\prime}\)).