## 2 Single-AGV Path Planning Algorithm
### Improved A* Algorithm  
#### 2.2.1 Traditional A* Algorithm  
The A* algorithm is derived from the Dijkstra algorithm. In comparison to the Dijkstra algorithm, the A* algorithm employs a greedy strategy that imparts a more pronounced sense of directionality during the search process. This characteristic enables it to narrow down the search space, thereby reducing path search complexity and enhancing overall efficiency [24]. Considering the constraint that the AGV in the packaging workshop is unable to move in the slope direction in transit, the A* algorithm employs a four-direction search mode in its search process. Starting from the current grid cell, only the unoccupied cells in the up, down, left, and right directions are utilized to search for the optimal path.  
The shortest path obtained using the A* algorithm is found by calculating and comparing the cost functions of different paths, and the cost function formula is as follows [25]:  
\[\text{f(n)}=\text{g(n)}+\text{h(n)} \tag{1}\]  
Among them, f(n) is the total cost from the current grid cell n to the target grid cell, g(n) is the actual cost that has occurred from the starting grid cell n to the current grid cell, and h(n) is the estimated cost from the current grid cell to the target grid cell. Commonly, h(n) is used to represent the Manhattan distance, Euclidean distance, and Chebyshev distance. However, considering that there is no oblique path for AGV operation in the packaging workshop environment, the Manhattan distance was used for calculation:  
\[\text{h(n)}=\mid\text{X}_{\text{n}}-\text{X}_{\text{z}}\mid+\mid\text{Y}_{ \text{n}}-\text{Y}_{\text{z}}\mid \tag{2}\]  
In Equation (2), \(\text{X}_{\text{n}}\) and \(\text{Y}_{\text{n}}\) are the X and Y coordinates of the current position of the AGV, and \(\text{X}_{\text{z}}\) and \(\text{Y}_{\text{z}}\) are the X and Y coordinates of the AGV transportation endpoint.  
The A* algorithm uses three tables in the search process: open list, closed list, and traceability list. Among them, the open list is used to store grid information that has not yet been retrieved, the closed list records grid information that has already been retrieved, and the traceability list stores the relationships between all grid cells. Assuming that the AGV travels from the starting grid cell S to the target grid cell E, black represents the obstacle cells, and the cost of AGV movement between adjacent grid cells is 1. The A* algorithm searches for the shortest path, as shown in Figure 5:  
Figure 4: Grid diagram of workshop.  
The algorithm search steps are as follows:  
Step 1: Add the starting point S as the parent node to the open list, and calculate the g(n) of m (m \(\leq\) 4) free grid cells above, below, left, and right at point S, as shown in Figure 4(a). Add the calculated g(n) for the free grid cell to the open list, and calculate the h(n) and f(n) values of the newly added grid cell to the open list.  
Step 2: Move the starting point S out of the open list and add it to the closed list. Select the grid cell with the smallest value in the open list as the new parent node.  
Step 3: Repeat steps 1 and 2 continuously until the endpoint E is added to the open list. Obtain the planned path by tracing back to the parent node, as shown in Figure 4(b).  
1. The AGV loading and unloading time is set to 1 s;
2. AGV will not collide with obstacle grids.