# 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
Calculate the increment

Since the difference in the objective function is caused by the change in the nodes, the difference is calculated incrementally by the amount of change in the energy function:

\[\Delta T=h\big{(}n^{\prime}\big{)}-h(n) \tag{6}\]

Judge whether to accept the current solution \(n^{\prime}\) or not

The decision of whether to accept a new solution is based on the difference between the objective function of the current node and the new node, and the judgment is based on the amount of change in the cost function, i.e., the magnitude of \(\Delta T\) is used to judge whether to accept the new solution or not. The most commonly used acceptance criterion is the Metropolis criterion. \[M= \begin{cases}\frac{1,E(n+1)<E(n)}{T},E(n+1)\geq E(n)\end{cases}  \tag{7}\]

When \(\Delta T<0\), accept \(n^{\prime}\) as the new current solution. Otherwise, a uniformly distributed random number \(\varepsilon\) is generated, and if \(exp(-\Delta T/T)>\varepsilon\), it accepts \(n^{\prime}\) as the new current solution \(n^{\prime}\). If \(exp(-\Delta T/T)\ \leq\ \varepsilon\) does not accept \(n^{\prime}\) as the new current solution \(n\), a new node \(n^{\prime}\) is selected based on the minimum of the predicted value of the heuristic function to the target node \(h(n^{\prime})\). Update each parameter

Update the annealing temperature \(T=T*r\) and the annealing rate \(r=0.85\) according to the changes in the nodes, expand the new node \(n^{\prime}\), and keep updating the open list and closed list according to the proposed dynamic neighbourhood expansion. Termination conditions

Repeat the previous steps and terminate the iteration when the target node is in the close list or the open list is empty (all traversable nodes have been traversed), i.e., the target node has been found or the optimal path has not been found by traversing all nodes. ### Redundant Point Removal

It can be seen that after designing the weights based on the local obstacle rate, modifying the evaluation function, and using the ideas of simulated annealing, the generated routes are more tortuous. This is mainly because we not only consider the cost of a single estimated distance in the evaluation function but also include various factors such as

Figure 8: Simulated annealing parameter selection chart. turn penalty and repulsive potential field in it. In addition, because we chose a two-layer neighbourhood in the neighbourhood selection, there will be many turns in the process of node expansion, and the smoothness of the path will be poor. To address this problem, we use the Floyd algorithm [37] to perform redundant point deletion on the generated paths, aiming at eliminating redundant nodes in the paths and merging co-located nodes to make the paths smoother while reducing the path length. The steps of the Floyd smoothing path are as follows:

The optimisation process of the Floyd smoothing path algorithm can be restated as follows, focusing on smoothing the path by reducing redundant nodes in the path:

Step 1: In the initialisation phase, an initial path is computed from the starting point S using the augmented A* algorithm, containing a sequence of nodes S, \(n_{1}\)\(n_{2}\)\(\ldots\)\(\ldots\)\(n_{m}\) up to the end point E. Subsequently, the Bresenham algorithm is applied to try to directly connect the starting point S with the second node \(n_{2}\). If no obstacles block this straight path, \(n_{1}\) is determined to be a redundant node and is removed from the path. Step 2: Redundant node identification and removal loop. In this step, for the currently considered sequence of nodes (nodes that start at S and terminate before the nodes that have not yet been processed), the following operations are performed:

If a node has been removed in the previous round (e.g., \(n_{1}\) in Step 1), the immediately following node (e.g., \(n_{2}\)) is considered for a straight-line connectivity test with the node further ahead (e.g., S) and the next node to be checked (e.g., \(n_{3}\)).