Research on Path Planning of Mobile Robot Based on Improved Theta* Algorithm

Abstract

The Theta* algorithm is a path planning algorithm based on graph search, which gives the optimal path with more flexibility than A* algorithm in terms of routes. The traditional Theta* algorithm is difficult to take into account with the global and details in path planning and traverses more nodes, which leads to a large amount of computation and is not suitable for path planning in large scenarios directly by the Theta* algorithm. To address this problem, this paper proposes an improved Theta* algorithm, namely the W-Theta* algorithm. The heuristic function of Theta* is improved by introducing a weighting strategy, while the default Euclidean distance calculation formula of Theta* is changed to a diagonal distance calculation formula, which finally achieves a reduction in computation time while ensuring a shorter global path; the trajectory optimization is achieved by curve fitting of the generated path points to make the motion trajectory of the mobile robot smoother. Simulation results show that the improved algorithm can quickly plan paths in large scenarios. Compared with other path planning algorithms, the algorithm has better performance in terms of time and computational cost. In different scenarios, the W-Theta* algorithm reduces the computation time of path planning by 81.65% compared with the Theta* algorithm and 79.59% compared with the A* algorithm; the W-Theta* algorithm reduces the memory occupation during computation by 44.31% compared with the Theta* algorithm and 29.33% compared with the A* algorithm.