# Improved JPS Path Optimization for Mobile Robots Based on Angle-Propagation Theta* Algorithm
## 5 Simulation
### Randomness Map Test  
The first set of experiments was conducted using 10 sets of grid maps ranging from 10 \(\times\) 10 to 100 \(\times\) 100, with each set of map obstacles set from 10% to 55%, respectively, for the JPS algorithm, the AP-JPS algorithm, and the polynomially optimized AP-JPS algorithm for 100 sets of randomness experiments. To better distinguish the resultant path from the obstacle grid, this experiment places the starting point of the path planning at the middle point of the grid. The distance calculation in the heuristic function of the JPS algorithm and AP-JPS algorithm in the simulation uses the Euclidean distance formula, and the actual results are the average of 10 experiments. In this paper, the polynomially optimized AP-JPS algorithm is referred to as Op-AP-JPS to facilitate the presentation of experimental results. The results of the simulation experiment were selected from 20 \(\times\) 20, 40 \(\times\) 40 and 80 \(\times\) 80 size raster maps, and the obstacles were selected from 10%, 30% and 50% for display. As can be seen in Figure 9, the JPS algorithm searches in a fixed number of eight directions during the path search. If the JPS algorithm encounters an obstacle during the search process, it will reselect the path according to other fixed directions, resulting in a large path turning angle and long search path edges, thus making it difficult to approach the actual optimal solution. The AP-JPS algorithm shown in Figure 8 reselects the path nodes by means of optimization in this paper to obtain a shorter path. Meanwhile, the AP-JPS algorithm has better path smoothing after trajectory optimization by minimum snap seventh-order polynomial interpolation. The specific 100 experimental comparisons are shown in Figure 10, where the total turning angle change rate is the reduction rate of the total turning angle of the path of the AP-JPS algorithm compared to the JPS algorithm. Figure 9: Comparison of JPS algorithm, AP-JPS algorithm and polynomial optimized AP-JPS algorithm under three size maps. (**a**) 10% obstacles, (**b**) 30% obstacles, (**c**) 50% obstacles, (**d**) 10% obstacles, (**e**) 30% obstacles, (**f**) 50% obstacles, (**g**) 10% obstacles, (**h**) 30% obstacles, (**i**) 50% obstacles. From Figure 11a-c, it can be seen that as the number of grids and the percentage of obstacles increase, the total turning angle of the path and the difference of the total turning angle between the JPS algorithm and the AP-JPS algorithm are on an increasing trend, with the largest angle difference for 100 \(\times\) 100 grids and the percentage of obstacles reaching 55%. Figure 11d shows that the rate of change of the total turning angle for both algorithms shows a decreasing trend with the increase in the obstacle percentage. Among them, the 90 \(\times\) 90 grid map has the highest ratio at 10% obstacle percentage, and the total path turning angle of the AP-JPS algorithm is 88.4% lower than that of the JPS algorithm. The 40 \(\times\) 40 grid map, with the lowest ratio at 50% obstacle share, shows a 13.7% reduction in total path turning angle for the AP-JPS algorithm compared to the JPS algorithm. From Figure 12a-c, it can be seen that the path length and path length difference of both the AP-JPS algorithm and JPS algorithm show an increasing trend as the raster size and obstacle percentage increase. In the case of the 100 \(\times\) 100 grid map with a 50% obstacle ratio, the path length difference is the largest, and the AP-JPS algorithm generates a path length 5.27 m shorter than the JPS algorithm. In addition, in the case of a 10 \(\times\) 10 grid map with a 20% obstacle ratio, the path length difference is the smallest, and the generated path length of the AP-JPS algorithm is 0.41 m shorter than that of the JPS algorithm. It can be seen in Figure 12d that the rate of change of path length shows a decreasing trend with the growth of the number of grids.