# 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  
In traditional applications of the A* algorithm, the calculation of the \(g(n)\) cost is usually based on two different scenarios for the eight neighbourhoods. When the AGV is moving along the grid in the four cardinal directions of up, down, left, and right, it  
Figure 6: \(g(n)\) search direction map. is assumed that the cost of travelling in a straight line is 1 (As shown in Figure 7 where parentnode1 moves to currentnode). As shown in Figure 7 where parentnode2 moves to currentnode, when it is turning to move diagonally, such as up left, down left, up right, or down right, the cost is usually set to a root of 2 to reflect the turning, because more turns usually mean shorter paths. However, in real-world operating environments, frequent turns not only increase the AGV's running time but may also exacerbate mechanical wear and tear. Therefore, it becomes particularly important to optimise path planning to reduce the number of turns. To achieve this goal, we introduce a direction penalty mechanism in the evaluation function of the A* algorithm. This mechanism evaluates the degree of steering of a path based on the principle of angle change. Specifically, we calculate the angular difference between the line connecting the current node and its parent node. If the two are on the same straight line (i.e., the angle difference is close to or equal to 180\({}^{\circ}\)), the path is considered to be travelling in a straight line, while the direction penalty is small or negligible. On the contrary, when the path turns, the angle difference changes, and based on the amount of this change, we increase the value of the direction penalty accordingly, as a way to encourage the algorithm to favour paths that can reduce the number of turns during the search process. The pseudo-code of Algorithm 1 outlines the calculation of directional penalties to optimise paths and reduce turns. ``` Require: MinF: current minimum node cost, point1: coordinates of current minimum node, point2: coordinates of parent node of current minimum node. Ensure: turningcost: turning cost
1: Define the coordinates between two points. 2: if minF.father then
3: point1 \(\leftarrow\) minF.point.x, minF.point.y (coordinates of current minimum cost node)
4: point2 \(\leftarrow\) minF.father.point.x, minF.father.point.y [coordinates of the parent of the current minimum cost node]
5: Calculate the distance between two points
6: delta_x \(\leftarrow\) point2[0]-point1[0] [calculate the horizontal distance between two points]
7: delta_y \(\leftarrow\) point2[1]-point1[1] [calculate the vertical distance between two points]
8: Convert the distance between two points to an angle using the math equation
9: angle \(\leftarrow\) math.atan2(delta_x,delta_y) [calculate angle]
10: angle degrees \(\leftarrow\) math.degrees(angle) [convert angle to angle system]
11: Calculate turning cost
12: turningcost \(\leftarrow\) angle--stepv [convert angle to cost]
13: return turningcost

Figure 7: Node direction change diagram. ### Definitions of Various Costs

1. Dynamic path consumption:

In the application scenario of the A* algorithm, dynamic path consumption refers specifically to the actual cost of traveling from the starting node to the current node, labelled \(g(n)\). This cost is dynamically adjusted according to the different paths selected. In the calculation, the traveling cost between nodes is taken into account, e.g., horizontal or vertical traveling may be set to a unit cost of 1, while diagonal traveling may be set to a cost of \(\sqrt{2}\) (or an approximate value of 1.4). 2. Minimum energy path dissipation:

Although the A* algorithm itself does not directly define the concept of \"energy dissipation\", energy dissipation can be considered as a specific cost of travel. If energy consumption is to be considered, it can be taken as a component of the traveling cost, and the calculation of \(g(n)\) can be adjusted accordingly.