# Research on Path Planning of Mobile Robot Based on Improved Theta* Algorithm
## 1 Introduction
### Related Work  
The current mainstream path planning algorithms are broadly classified into three main categories: population intelligence-based algorithms, random sampling-based, and graph search-based. The idea of cluster-based optimization is inspired by the process of population evolution, and its typical algorithms include the genetic algorithm proposed by [PERSON] [1; 2], the ant colony algorithm proposed by [PERSON] [3; 4], and the particle swarm algorithm proposed by [PERSON] and [PERSON] [5], etc. The random sampling-based path planning method gradually obtains the connectivity information between different states in the state space by random sampling and then gradually finds the feasible solution, which greatly reduces the search complexity and improves the search efficiency, but these methods have the problem of poor stability of the solution quality and cannot guarantee  
Figure 1: Path planning diagram. the optimal solution. The most studied methods are the Probabilistic Roadmap (PRM) [6] algorithm and the Rapidly expanding Random Tree (RRT) algorithm [7]. The graph search-based path planning method first requires the construction of graphs, i.e., the state space of the mobile robot system is partitioned into discrete spaces (considered as graphs) according to a certain criterion, after which graph search algorithms are applied to search for paths in these graphs, and the commonly used algorithms are [PERSON]'s algorithm [8; 9], A* algorithm [10; 11], and Theta* algorithm [12; 13; 14; 15]. A* algorithm based on graph search technique has a wide range of applications in path planning for robots. The advantage of A* algorithm is that it is better in real time and easy to implement, but the disadvantage is that the uncertainty of the heuristic function affects the quality of path planning [16], and the search direction of A* algorithm is limited by the shape of the grid in the map in the process of path planning, so the planned path is not the shortest path in the actual map shortest path in the actual map. To address this problem, [PERSON] et al. proposed the Theta* algorithm [14]. This algorithm is an improved branch based on the A* algorithm, which combines the respective features of the A* algorithm and the visual map method, and searches along the grid on the grid map during path planning, but the path is not restricted to the edges of the grid, which achieves the arbitrary turning angle and effectively reduces the length of the path and the number of turning points. The difference between the Theta* algorithm and the A* algorithm is that the Theta* algorithm allows the parent of the current node to be any other node, while in the A* algorithm, the parent of the current node can only be a visible neighbor of the node. Since the Theta* algorithm is derived from the A* algorithm, it is still limited in operational efficiency by the excessive number of nodes traversed in the path search process. The optimal path proposed by path planning is not only the shortest passable path, but also the continuous and smooth transition of the robot's position, velocity, and acceleration during the movement, which requires the optimization of the planned path. Many scholars have proposed different path optimization schemes in previous studies. The most commonly used methods for path smoothing optimization are Bezier curves [17; 18] and B-sample curve optimization [19]. The Bezier curve approach allows curve fitting of the generated path points during path planning and thus achieves the role of smoothing the path. Usually, the number of initial path points obtained by the global path planning algorithm is small, resulting in a low fit, and therefore the smoothed path may collide with the obstacle. In order to increase the curve fit, the path points are usually increased. However, if the number of path points is increased excessively, it increases the computational effort of the algorithm thus leading to a decrease in the efficiency of the algorithm [20].