# Research on Path Planning of Mobile Robot Based on Improved Theta* Algorithm
## 2 Algorithm Design
### Improvement of Heuristic Function  
The heuristic function \(h(n)\) of Theta* is mainly to estimate the cost of the robot's current position node to the target point, and different \(h(n)\) will have different effects on the operation efficiency of the algorithm. When the value of \(h(n)\) is 0, the Theta* algorithm will degenerate into Dijkstra algorithm, which can guarantee that the output path is optimal, but the number of nodes diffused in the process of calculation is large, resulting in low efficiency in path planning in a large scene environment and cannot meet the demand of real-time; when the value of \(h(n)\) is very large, Theta* can quickly plan at a path, but cannot guarantee that the path is the shortest path, so it defeats the purpose of the path planning algorithm. Therefore, in order to ensure that the path planning algorithm meets the two conditions of shortest path and low computational cost, it is necessary to choose a suitable heuristic function for the algorithm.  
The heuristic function of the improved algorithm is mainly to find the shortest path. Using the traditional method of expanding nodes will generate many useless expansion nodes and increase the computational cost. To address this problem, the following improvements are made in this paper:To get the optimal path, the predicted cost calculated by the heuristic function must be less than or equal to the actual minimum cost and the closer the two are, the more efficient the search is. In addition, the cost between two points in two-dimensional space usually refers to the Euclidean distance between the two, so this paper uses the Euclidean distance to express the distance between the current node and the end point, and its formula can be expressed as follows:  
\[d(n)=\sqrt{\left(x_{n}-x_{goal}\right)^{2}+\left(y_{n}-y_{goal}\right)^{2}} \tag{2}\]  
where \((x_{n},y_{n})\) are the coordinates of the current node \(n\) and \((x_{goal},y_{goal})\) are the coordinates of the target point.
2. If the cost function \(f(n)\) of the current node \(n\) corresponds to more than one path, all of these paths will be searched, but only one of them is actually needed. This situation occurs very frequently in maps with few obstacles. To solve this problem, in this paper, we will add additional values to the heuristic function \(h(n)\), the size of which is the vector fork product of the initial point-to-target vector and the current point-to-target vector, and then change the value of \(h(n)\) to make it more inclined to the connection from the initial point to the target point in selecting the path, to ensure uniqueness in planning the path and reduce unnecessary computation. The functional expression is: \[\mathrm{c}=\mathrm{V}_{\mathrm{c},\mathrm{c}}\times\mathrm{V}_{\mathrm{s}, \mathrm{c}}\] (3) where \(\mathrm{c}\) denotes the vector fork product of the start-point-to-target-point vector \(\mathrm{V}_{\mathrm{s},\mathrm{c}}\) and the current node-to-target-point vector \(\mathrm{V}_{\mathrm{c},\mathrm{c}}\).
3. By adding a weight \(w\) to the heuristic function \(h(n)\) and then dynamically adjusting this weight according to the progress of the algorithm, the importance of the heuristic function is reduced by decreasing the weight as the path planned by the algorithm approaches the target point, while increasing the relative importance of the true cost of the path. According to the above three improvements, the expression of the heuristic function is: \[h(n)=w\Big{[}d(n)+\frac{c}{d(s)}\Big{]}\] (4) where \(w\) is the weight and its size is set to \(w=1+\frac{d(n)}{d(s)};c\) is the crossover operator that breaks the path balance; \(d(n)\) is the distance from the current node \(n\) to the target point, expressed using the Euclidean distance; \(d(s)\) is the Euclidean distance from the starting point to the target point.