# Research on Path Planning of Mobile Robot Based on Improved Theta* Algorithm
## 3 Simulation
### W-Theta* Algorithm Stability Test Experiment  
This part of the experiment was designed with 3 groups of maps, each with dimensions of 40 \(\times\) 40 m, 80 \(\times\) 80 m, and 100 \(\times\) 100 m, respectively, where each group of the same size map has an obstacle coverage of 10, 30, and 50%. As shown in Figure 5, the green point is the starting point, the red point is the ending point, and the black grid is the obstacle. The solid blue line is the path planned by Theta* algorithm, and the dashed orange line is the path planned by W-Theta* algorithm.  
The data of the W-Theta* algorithm and Theta* algorithm run on each map are shown in Table 1. The data in the table shows that the pathfinding time of the W-Theta* algorithm is shorter than that of the Theta* algorithm for maps of different sizes and obstacle densities, and the W-Theta* algorithm reduces the pathfinding time compared with the Theta* algorithm for maps of 40 \(\times\) 40 m, 80 \(\times\) 80 m, and 120 \(\times\) 120 m by 47.12%, 84.77%, and 92.56%, respectively. The difference is more obvious for larger maps. Usually, the time spent by an algorithm can visually reflect the time complexity of the algorithm, and it can be concluded that the time complexity of the W-Theta* algorithm is less than that of the original Theta* algorithm. In this paper, the heuristic function was optimized to achieve the control algorithm in planning the path to traverse the path nodes. This reduced the computation time and computation cost of the algorithm. Through this experiment, it can be seen that the W-Theta* algorithm calculates a different number of traversed map nodes than the Theta* algorithm; in the same size of the map, the greater the density of obstacles, the greater the gap between the two in the map size of the larger the gap. The larger the map size, the greater the difference between the W-Theta* algorithm and Theta* algorithm. In the maps of 40 \(\times\) 40 m, 80 \(\times\) 80 m and 120 \(\times\) 120 m, respectively, the number of traversed nodes is reduced by 36.32, 72.58, and 82.83%. W-Theta* in these three groups of experiments calculates the number of traversed map nodes to remain below 600, while the Theta* algorithm calculates that the the highest number of nodes is 3658. In terms of path length, the difference in the length of the paths planned by the two algorithms is not significant, and the paths planned by the Theta* algorithm are on average 1.60% shorter than those planned by the W-Theta* algorithm in the three groups of maps, and the Theta* algorithm has a slight advantage in the path length. Theta* algorithm is better than the W-Theta* algorithm in terms of spatial complexity. The memory consumed by W-Theta* algorithm is reduced by 15.02, 32.32, and 35.96% compared with Theta* algorithm in maps of 40 \(\times\) 40 m, 80 \(\times\) 80 m, and 120 \(\times\) 120 m, respectively. It can be seen that the difference between the performance of W-Theta* algorithm and Theta* algorithm is more obvious in the larger size of the map environment.  
Figure 5: Comparison between W-Theta* algorithm and Theta* algorithm for maps with three sizes and different obstacle densities.