# 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.1 Traditional JPS Algorithm  
Jump Point Search (JPS) is a more efficient path planning algorithm that screens natural neighbor nodes and forced neighbor nodes through specific screening rules and further screens to obtain the jump points needed for path planning, which well solves the problem of the A* algorithm accessing more redundant nodes. Natural neighbor nodes are nodes that extend directly along the current search direction in the hopping point search algorithm; using these nodes can efficiently skip intermediate invalid nodes, reduce the search space, and improve the speed of path planning. Forced neighbor nodes are the nodes that must be considered in the jump point search algorithm in order to bypass obstacles. By checking these nodes, JPS can effectively avoid obstacles in path search and ensure that it remains the optimal path. The screening rules are as follows. (1) No obstacles around the node  
As shown in Figure 8, node \(x\) represents the current node, node \(P(x)\) is the parent of node \(x\), and \(n\) is a neighboring node of \(x\). The length of the path taken by the parent node \(P(x)\) to reach node \(n\) through \(x\), when moving horizontally, must be shorter than the lengths of other paths that do not pass through \(x\) to reach node \(n\). Similarly, the length of the path taken by the parent node \(P(x)\) to reach node \(n\) through \(x\), when moving diagonally, must be less than or equal to the lengths of other paths that do not pass through \(x\) to reach node \(n\). Therefore, the following screening rules for natural neighbor nodes can be derived:  
* When moving horizontally, the natural neighbor node \(n\) satisfies the following equation:  
\[L(<P(x),x,\dots,n>)<L(<P(x),\dots,n>|x) \tag{8}\]  
Here, \(L(<P(x),x,\dots,n>)\) denotes the length of the path from the starting point \(P(x)\) through \(x\) to reach \(n\) and \(L(<P(x),\dots,n>|x)\) denotes the length of the path from the starting point \(P(x)\) to reach \(n\) without passing through \(x\). * When moving diagonally, the natural neighbor node \(n\) satisfies the following equation:  
\[L(<P(x),x,\dots,n>)\leq L(<P(x),\dots,n>|x) \tag{9}\]  
(2) Presence of obstacles around the node  
As shown in Figure 9, the black grid indicates the obstacles. At this time, in addition to screening the natural neighbor nodes, it is also necessary to screen out the forced neighbor nodes. The forced neighbor nodes are shown in the green grid in the figure. Figure 8: Screening rules without adjacent obstacles: (**a**) horizontal move; (**b**) diagonal move. The screening rules for natural neighbor nodes are the same as the screening rules when there are no obstacles around a node. The screening rules for the forced neighbor nodes are as follows:  
* \(n\) is not a natural neighbor of node \(x\);
* \(n\) satisfies the following equation: \[L(<P(x),x,\ldots,n>)<L(<P(x),\ldots,n>|x)\] (10)  
For the natural neighbor nodes and forced neighbor nodes obtained by the above screening rules, it is necessary to further screen them to obtain the jump point. The jump point screening rules are as follows:  
* If node \(n\) is a starting or goal point, then \(n\) is a jump point;
* If node \(n\) has at least one forced neighbor, then \(n\) is a jump point;
* A node \(n\) is a jump point if the parent node \(P(x)\) is in a diagonal direction from node \(n\) and \(n\) has nodes in the horizontal or vertical directions that satisfy conditions (1) and (2) above. The purpose of the integration of the A* algorithm with the JPS algorithm is to first use the JPS algorithm to preprocess to obtain representative jump points, then add these jump points to OpenList and select the node with the smallest cost as the current node for expansion, then continue to screen its jump points to be added to OpenList. At the same time, the jump points after the expansion is completed are added to CloseList. This process is repeated until the current node is the target point, at which point the path planning is complete.