# Research on AGV Path Planning Integrating an Improved A* Algorithm and DWA Algorithm
## 2 Alternative Implementation of the A* Algorithm
### Alternative A* Algorithm  
In a grid map, obstacles are represented as unit grids, with their locations defined as obstacle grids. The more obstacle grids present, the more complex the path selection within the map becomes, resulting in the minimum path distance between the initial and target positions being greater than the Euclidean distance between the two points [21]. To estimate the minimum path distance, we introduce the obstacle rate \(Q\) to represent the environmental complexity within the map. The obstacle rate \(Q\) is defined as the ratio of the number of obstacle grids to the total number of grids within the local grid map between the current position and the target position. The total number of obstacle grids between the current and target positions is \(N\). The coordinates of the initial position are \(\left(X_{i},Y_{i}\right)\), and the coordinates of the target position are \(\left(X_{t},Y_{t}\right)\). The expression is as follows:  
\[Q=\frac{N}{(|X_{i}-X_{t}|+1)(|Y_{i}-Y_{t}|+1)}\ (Q\in(0,1)) \tag{3}\]  
In this formula, \(N\) represents the total number of grids within the matrix region defined by the initial and target positions. In the evaluation function, the heuristic function \(H(n)\) represents the estimated cost from the current position \(\left(X_{c},Y_{c}\right)\) to the target position \(\left(X_{t},Y_{t}\right)\). Specifically, \(H(n)\) is the Euclidean distance from node n to the target position, which is the shortest path length between two points. \[H(n)=\sqrt{\left(X_{c}-X_{t}\right)^{2}+\left(Y_{c}-Y_{t}\right)^{2}} \tag{4}\]  
In the presence of obstacles, the actual distance from node n to the target can only be equal to or greater than the Euclidean distance. Assuming \(H(n)\) is greater than the actual minimum cost from node n to the target, denoted as \(H^{*}(n)\), implies the existence of a node n where \(H(n)>h^{*}(n)\). However, since the Euclidean distance \(\sqrt{\left(X_{n}-X_{t}\right)^{2}+\left(Y_{n}-Y_{t}\right)^{2}}\) is the shortest straight-line distance between two points, this situation cannot occur. Therefore, the assumption is invalid, meaning \(H(n)\leq H^{*}(n)\), and the heuristic function \(H(n)\) is admissible. The evaluation function \(F(n)\) consists of the actual cost \(G(n)\) and the heuristic function \(H(n)\), and adjusts the weight of the heuristic function based on the obstacle rate Q.  
\[F(n)=G(n)+H(n)\Big{(}e^{-lnQ}\Big{)} \tag{5}\]  
\[G(n)=\sum_{k=1}^{n}\sqrt{(X_{k}-X_{k-1})^{2}+(Y_{k}-Y_{k-1})^{2}}(X_{0},Y_{0}) =(X_{i},Y_{i}) \tag{6}\]  
Here, \(G(n)\) is the actual cumulative cost from the starting position \((X_{i},Y_{i})\) to the current position \((X_{c},Y_{c})\). In the evaluation function of the A* algorithm, the heuristic function \(H(n)\) determines the search performance of the algorithm. The heuristic function values vary with the number of obstacles in different map environments. When there are fewer obstacles in the map, the obstacle rate \(Q\) is lower, causing the A* algorithm to be biased towards the target position during the search. This increases the heuristic function value \(H(n)\), thus enhancing the search speed and directional accuracy towards the target position. Conversely, when the map contains many obstacles, the search speed decreases. Simply increasing the heuristic function value \(H(n)\) to speed up the search can lead the AGV into local optima [22], resulting in more convoluted paths and higher distance costs. This forces the AGV to search multiple paths even in traversable areas, making the optimal path more difficult to find. Therefore, when there are many obstacles, the heuristic function value \(H(n)\) should be reduced to lower the search speed and improve search precision, thereby obtaining the optimal global path. As shown in Equation (3), the obstacle rate \(Q\) is jointly determined by the number of grids \(N\), the initial position \((X_{i},Y_{i})\), and the target position \((X_{t},Y_{t})\). The search space of the A* algorithm changes with variations in the initial and target positions.