# Research on Path Planning of Mobile Robot Based on Improved Theta* Algorithm
## 3 Simulation
### Experiment of Comparing W-Theta\({}^{\star}\) Algorithm with Other Algorithms

Table 3: Experimental data sheet for various algorithms on Baldurs Gate II map. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Map Name**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{2}{c}{**Pathfinding**} & \multicolumn{2}{c}{**Number of**} & \multirow{2}{*}{**Path**} & \multirow{2}{*}{**Memory**} & \multirow{2}{*}{**Total Path**} \\  & & & **Time/s** & & **Nodes** & **Length/m** & **Consumption/Bit** \\ \hline \multirow{4}{*}{Harvest moon} & A* & 49.332874 & 18,542 & 506.6194 & 8,333,752 & 2205.00 \\ \cline{2-7}  & Dijkstra & 350.203546 & 111,916 & 515.7321 & 15,813,992 & 810.00 \\ \cline{2-7}  & Theta* & 50.735335 & 18,542 & 498.0176 & 10,988,924 & 383.65 \\ \cline{2-7}  & W-Theta* & 6.665620 & 1812 & 500.4910 & 6,990,296 & 223.22 \\ \hline  
The data in Tables 3-5 gives the following information: the pathfinding time W-Theta* algorithm is the shortest, while the longest time consuming algorithm is Dijkstra algorithm. In Baldurs Gate II, W-Theta* reduces the pathfinding time by an average of 55.96% compared to the A* algorithm, 61.78% compared to the Theta* algorithm, and 79.70% compared to the Dijkstra algorithm; in City maps, W-Theta* reduces the pathfinding time by an average of 94.81%, 94.91% compared to Theta* and 98.24% compared to Dijkstra; in Warcraft III, W-Theta* reduced the pathfinding time by 88.13%, 88.39% compared to Theta* and 97.97% compared to Dijkstra. The number of nodes traversed by the W-Theta* algorithm is also the lowest, because Theta* is based on the A* algorithm, so both algorithms traverse the same number of nodes, and the highest number of nodes traversed by the Dijkstra algorithm, and the number of nodes traversed by the W-Theta* algorithm relative to the A* algorithm and the original Theta* algorithm is the highest. The nodes traversed by the W-Theta* algorithm are reduced by 62.49%, 91.41%, and 91.31% in Baldurs Gate II, City maps, and Warcaft III maps, respectively; compared to the original Theta* algorithm, the nodes traversed by the W-Theta* algorithm are reduced by 82.99, 97.13, and 97.13% in Baldurs Gate II, City maps, and Warcaft III maps, respectively, and 82.99%, 97.13%, and 97.92%, respectively. In terms of the length of the planned paths, the Theta* algorithm plans the shortest paths, but the path lengths planned by the W-theta* algorithm do not differ much from those planned by the Theta* algorithm, and the path lengths planned by the W-theta* algorithm relative to the Theta* algorithm increase by 1 in Baldurs Gate II, City maps, and Warcaft The path lengths planned by the W-Theta* algorithm compared to the Theta* algorithm increased by 1.98%, 0.81%, and 0.96% in Baldurs Gate II, City maps, and Warcaft III maps, respectively, which shows that the difference between the two algorithms is smaller in the larger environment; the path lengths planned by the W-Theta* algorithm compared to the A* algorithm decreased by 2.48 and 3.09%. The path lengths planned by the W-Theta* algorithm compared to the Dijkstra algorithm are reduced by 14.83, 7.35, and 6.09% for Baldurs Gate II, City maps, and Warcaft III maps, respectively. In terms of memory consumption, the least memory resources are used by the W-Theta* algorithm. Memory resources used by the W-Theta* algorithm compared to the A* algorithm are reduced by 17.80, 49.90, and 20.30% for the maps of Baldurs Gate II, City maps, and Warcaft III, respectively. Memory resources usage by the W-Theta* algorithm compared to the Theta* algorithm is reduced by 37.39, 56.63, and 38.90% for Baldurs Gate II, City maps, and Warcaft III maps, respectively. The W-Theta* algorithm is compared to the Dijkstra algorithm, and memory resource usage is reduced by 17.80, 49.90, and 20.30% for Baldurs Gate II, City maps, and Warcaft III maps, respectively. Maps and Warcaft III by 29.82%, 75.41%, and 52.85%, respectively. In the three sets of maps, the paths planned by the W-Theta* algorithm have the smallest turning angles, and the paths planned by the A* algorithm have the largest turning angles.