# Research on Path Planning for Robots with Improved A* Algorithm under Bidirectional JPS Strategy
## 3 Improved A* Algorithm
### Combining the Bidirectional JPS Algorithm
#### 3.2.2 Bidirectional JPS Algorithm  
The traditional JPS algorithm can better deal with the problems of the A* algorithm accessing more redundant nodes and having a high computation and memory consumption. However, in larger scenes or with more obstacles, a substantial number of jump points can still be generated, leading to slower pathfinding. Therefore, this paper proposes to improve the A* algorithm by using the bidirectional JPS algorithm on the basis of the traditional JPS algorithm.  
Using the bidirectional JPS algorithm means that both the starting point and the goal point are used as the starting point and each takes the other as the goal point for path planning. Typically, the search from the starting point to the goal point is referred to as the forward search while the search from the goal point to the starting point is known as the reverse search. A successful path search is indicated when the currently expanded node of one party is the currently expanded node of the other party or exists in the CloseList of the other party.  
Figure 9: Screening rules with adjacent obstacles: (**a**) horizontal move; (**b**) diagonal move.  
The pathfinding process of the A* algorithm incorporating the bidirectional JPS algorithm is shown in Figure 10. Node s represents the start node, node g represents the target node, the black grids denote obstacles, and the red arrows and green arrows represent the paths for the forward and reverse searches, respectively. The flow of the algorithm is as follows:  
* Create four lists, _OpenList1_, _OpenList2_, _CloseList1_, and _CloseList2_. Place node \(s\) into _OpenList1_ and node \(g\) into _OpenList2_;
* Start the bidirectional search; during the forward search, place jump point \(a\) into _OpenList1_; during the reverse search, place jump point \(b\) into _OpenList2_. Place node \(s\) into _CloseList1_ and node \(g\) into _CloseList2_;
* Continuing the forward search with \(a\) as the current node yields jump points \(c\) and \(d\), which are added to _OpenList1_. In the reverse search, jump point \(e\) is found for \(b\) and added to _OpenList2_. Nodes \(a\) and \(b\) are placed into _CloseList1_ and _CloseList2_, respectively;
* Since \(d\) is the node with the smallest value of _f(n)_ in _OpenList1_, the forward search expands \(d\) to obtain jump points \(e\) and \(f\), which are added to _OpenList1_. In the reverse search, jump point \(h\) is found for \(e\) and added to _OpenList2_. Nodes \(d\) and \(e\) are placed into _CloseList1_ and _CloseList2_, respectively;
* Node \(e\) has the smallest value of _f(n)_ in _OpenList1_, so \(e\) is selected as the current node for forward expansion. Since \(e\) exists in _CloseList2_, the path search is successful.  
According to the process diagram of pathfinding using bidirectional JPS shown in Figure 10, theoretically, bidirectional JPS can double the efficiency compared to unidirectional JPS. However, bidirectional JPS also has drawbacks. When there is symmetry in the environment map, bidirectional JPS may plan two symmetric paths. This results in the paths searched in the forward direction not intersecting with the paths searched in the reverse direction. At this time, each search may independently plan a path, which not only fails to improve the efficiency of path planning but may even reduce it. To address this issue, this paper proposes an improved method where each search considers the other's current extended node as the target node.