# Research on Path Planning for Robots with Improved A* Algorithm under Bidirectional JPS Strategy
## 4 Simulation Analysis and Experimental Validation  
### Simulation Analysis  
In order to verify the effectiveness of the improved algorithm, this paper simulates and tests the A* algorithm, the JPS algorithm, and the improved A* algorithm on ten different grid maps. The computer we use is configured with a Windows 11 operating system, an R7-5800H processor with 3.2 GHz, and 16 GB of RAM. The results of the three algorithms tested on a grid map of size 40 \(\times\) 40 with a 30% obstacle ratio are shown in Figure 13. In the figure, the green grid indicates the start node, the red grid indicates the target node, the black grids indicate obstacles, the blue grids indicate nodes added to OpenList, and the yellow grids indicate nodes added to CloseList. The blue solid line represents the planned path, the green solid line represents the path obtained by primary smoothing, and the red solid line represents the final path obtained after secondary smoothing. As can be seen from Figure 13, the length and the number of turns of the optimal path obtained by the improved A* algorithm are better than those of the other two algorithms in the same environment. Other data obtained from the simulations are shown in Tables 1 and 2. Table 1 compares the three algorithms in terms of the nodes traversed, path lengths, numbers of turns, and search times in grid maps of different sizes with a consistent obstacle percentage of 30%. It is evident that the number of nodes traversed by the improved algorithm is better than that of the A* algorithm and worse than that of the JPS algorithm. However, due to the nature of bidirectional search, it is guaranteed that the search time will outperform the other two algorithms. In 20 \(\times\) 20 maps, the improved algorithm's search time efficiency improves by 50.29% and 26.37%, respectively, relative to the other algorithms; in 40 \(\times\) 40 maps, it improves by 62.07% and 30.59%, respectively; in 60 \(\times\) 60 maps, it improves by 68.66% and 37.13%, respectively; in 80 \(\times\) 80 maps, it improves by 72.62% and 42.41%, respectively; and in 100 \(\times\) 100 maps, it improves by 78.37% and 50.43%, respectively. From these data, it can be concluded that as the map size increases, the algorithm's improvement in search speed becomes more significant. However, in some cases, this improvement may lead to longer path lengths. Additionally, the improved algorithm's paths also exhibit significantly fewer turns compared to the other two algorithms. Figure 12: Schematic diagram of the dynamic circle cutting method. Table 2 compares the three algorithms in terms of the nodes traversed, path lengths, numbers of turns, and search times in grid maps of varying sizes with a consistent obstacle percentage of 70%. It shows that the improved algorithm can generally plan optimal paths, as evidenced by shorter path lengths and fewer turns compared to the other two algorithms. According to Table 2, the search time efficiency of our algorithm improves by 26.14% and 12.70% relative to the other two algorithms in 20 \(\times\) 20 maps, 39.25% and 20.80% in 40 \(\times\) 40 maps, 52.47% and 32.10% in 60 \(\times\) 60 maps, 58.21% and 39.79% in 80 \(\times\) 80 maps, and 66.58% and 48.22% in 100 \(\times\) 100 maps. It can be seen that the larger the size of the map is, the more effective the algorithm is in improving search speed. But in cases where the proportion of obstacles is higher, the improvement in search speed is not as significant as when the proportion of obstacles is lower. However, the optimal path is guaranteed to be obtained when the proportion of obstacles is higher. Figure 13: Comparison diagram of simulation results for three algorithms: (**a**) traditional A* algorithm; (**b**) traditional JPS algorithm; (**c**) improved algorithm. The simulation results indicate that the efficiency of the improved A* algorithm is influenced by the size of the environment map and the ratio of obstacles.