# Improved JPS Path Optimization for Mobile Robots Based on Angle-Propagation Theta* Algorithm
## 2 JPS Algorithm
\begin{table}
\begin{tabular}{c c c} \hline
**Classification** & **Algorithm** & **Problems** \\ \hline Path planning methods & A* Algorithm & The A* algorithm has a large number of redundant nodes in the search process leading to the inefficiency of the algorithm, especially when the map size is large. \\ \hline Artificial potential field [35] & The RRT algorithm is particularly important for the design of the step length. A step length length that is too long leads to crossing obstacles. Too short a step length leads to inefficiency of the algorithm. In addition, the path found by the RRT algorithm is suboptimal, not optimal. \\ \hline Path smoothing method & RRT* algorithm [33] & The RRT* algorithm is asymptotically optimized, which means that the resulting path is increasingly optimized as the number of iterations increases [34]. Therefore, the convergence time of the RRT* algorithm is a more prominent problem. \\ \hline Artificial potential field [35] & The combined force generated by the gravitational field and the repulsive field is zero, then it is easy to fall into the local optimum solution. \\ \hline JPS algorithm & The fixed direction search results in a gap between the resulting path and the path available to the mobile robot. \\ \hline \multirow{4}{*}{Path smoothing method} & Bessel curve optimization & The Bessel curve is less flexible, and the generated path does not guarantee the continuity of velocity and acceleration. \\ \cline{2-3}  & B-sample curve optimization & The B spline curve is more flexible than the Bessel curve because of its local modifiable feature. However, the optimized path still cannot guarantee the continuity of velocity and acceleration. \\ \cline{2-3}  & Polynomial interpolation method & The polynomial interpolation method is better for continuity treatment, but the possibility of reccurrence of collisions in the fitted curves needs to be taken into account. \\ \hline \multirow{4}{*}{Any-angle path planning method} & Line of sight method [29] & The line-of-sight method is inefficient for optimization and requires LOS detection for a large number of nodes, leading to a decrease in the efficiency of the algorithm. \\ \cline{2-3}  & Field D* & The path obtained by the Field D* algorithm is not the optimal path. \\ \cline{2-3}  & Basic Theta* & The time required by the Basic Theta* algorithm to expand each vertex increases linearly with the number of rasters. When the map size is too large, the algorithm becomes less efficient. \\ \hline \multirow{4}{*}{AP-Theta*} & Although the consumption of AP Theta* in expanding vertices is no longer linearly related to the number of lattices, but becomes constant in magnitude. \\ \cline{1-1}  & & However, the search process of a large number of useless nodes still exists in the Theta* family of algorithms, resulting in inefficiency \\ \hline \end{tabular}
\end{table} 
Table 1: Map information selected for the dataset. vertical and horizontal nodes in the extension direction, as shown in Figure 3a,b. That is, JPS will start expanding in the direction of vertical and horizontal natural neighbors first until they are blocked or jump points are found before considering the search in the diagonal direction. In the JPS algorithm, the current node \(x\) has obstacles among its eight neighbors, and \(n\) is a non-obstacle, non-search direction neighbor node of the current node. Then, the distance cost of \(x\)'s parent node \(parent(x)\) to reach n through \(x\) is smaller than the distance cost of any path to reach \(n\) without going through \(x\). Then, \(n\) is said to be a forced neighbor of \(x\). If the current node is found to have forced neighbors, the node is identified as a jump point, and the expansion in the direction of forced neighbors must be considered, as shown in Figure 3c,d.