# Research on Path Planning for Robots with Improved A* Algorithm under Bidirectional JPS Strategy
## 2 Traditional A* Algorithm
### Traditional A* Algorithm  
The A* algorithm is a heuristic path planning algorithm designed for static scenarios that introduces a Best First Search algorithm, i.e., heuristic function, based on the Dijkstra algorithm, which enhances the heuristic of the algorithm, makes the algorithm more purposeful in searching towards the goal point, and reduces the algorithm's traversal of the redundant nodes. The evaluation function of the A* algorithm is given in the following equation:  
\[f(n)=g(n)+h(n) \tag{1}\]  
In Equation (1), \(g(n)\) denotes the total actual cost accumulated from the start node to the current node \(n\); \(h(n)\) is a heuristic function representing the predicted cost from the current node \(n\) to the target node; and \(f(n)\) is an evaluation function representing the total predicted cost for the start node to reach the target node via node \(n\).  
The heuristic function \(h(n)\) is crucial in determining the efficiency of the algorithm. When \(h(n)\) is smaller than the actual cost \(h^{\star}(n)\), the algorithm can definitely plan the optimal path, but it may traverse more nodes, slowing down the search speed; when \(h(n)\) is 0, \(h(n)\) must be less than or equal to \(h^{\star}(n)\), i.e., when the algorithm degenerates into the Dijkstra algorithm; when \(h(n)\) is greater than the actual cost \(h^{\star}(n)\), the algorithm reduces the number of traversed nodes, speeding up the search, but it will ensure that the path planning result is not the optimal solution; when \(h(n)\) is much larger than \(h^{\star}(n)\), the algorithm evolves to the Best First Search algorithm; the A* algorithm needs to consider the search speed during the search process while ensuring that the optimal path is found. Therefore, for optimal efficiency, \(h(n)\) should closely approximate \(h^{\star}(n)\).  
Figure 3: Eight-neighborhood expansion.  
Figure 2: Grid map.  
Commonly used representations of heuristic functions are Euclidean distance and Manhattan distance. Let the coordinates of the current node be \((x_{n}\),\(y_{n})\) and the coordinates of the target point be \((x_{g}\),\(y_{g})\); then, the Euclidean distance formula is as below:  
\[h(n)=\sqrt{\left(x_{g}-x_{n}\right)^{2}+\left(y_{g}-y_{n}\right)^{2}} \tag{2}\]  
The Manhattan distance formula is as follows:  
\[h(n)= \left|x_{g}-x_{n}\right|+\left|y_{g}-y_{n}\right| \tag{3}\]  
Due to the presence of obstacles in the actual environment and the selected expansion method in this paper being eight-neighborhood expansion, when using a Euclidean distance of \(h(n)\), the distance value must be smaller than the actual cost \(h^{\star}(n)\); when using a Manhattan distance of \(h(n)\), the distance value is larger than the actual cost \(h^{\star}(n)\). In this paper, we need to select an appropriate distance formula that makes \(h(n)\) closer to \(h^{\star}(n)\).  
The A* algorithm will add the node with the smallest value of the current evaluation function as the current node to CloseList during the path search and, at the same time, visit the neighboring nodes reachable by this node and add them to OpenList, then calculate the node with the smallest value of the evaluation function in OpenList to add it to CloseList. It will repeat this process until the target point becomes the current node, completing the pathfinding. Finally, the final path is generated by backtracking the parent-child relationships of the nodes. The pathfinding process is illustrated in Figure 4, which highlights that the A* algorithm generates a large number of redundant nodes, represented by the light blue grids in the figure. Maintaining and accessing these nodes increases the computational workload of the algorithm and wastes storage space, thereby impacting the efficiency of path planning.