# Path Planning of a Mobile Robot Based on the Improved RRT Algorithm
## 3 Methods
### Optimizer
#### 3.2.2 Interpolation  
The path optimization method based on the Dijkstra pruning strategy can find the shortest path given the current results. However, the problem remains that overly small angles remain in the path; these are called sharp nodes. A path with large turning angles can affect the stability of the motion planning; meanwhile, a path with gentle turning angles can better meet the requirements of practical applications. Therefore, it is necessary to remove sharp nodes. To solve this problem, the interpolation optimization method is utilized. In simple terms, two states are inserted into the path instead of the original corner node.  
Specifically, if the angle \(\theta_{1}\) between the two adjacent vectors \(\{x_{1}\), \(x_{2}\}\) and \(\{x_{2}\), \(x_{3}\}\) is smaller than the _threshold_, then the middle nodes \(a\) and \(b\) of the two vectors \(\{x_{1}\), \(x_{2}\}\) and \(\{x_{2}\), \(x_{3}\}\) are calculated (line 2-4 in Algorithm 8). If there is no collision between the vector \(\{a,b\}\), and the angle \(\theta_{2}\) between \(\{x_{1}\), \(a\}\) and \(\{a,b\}\) and the angle \(\theta_{3}\) between \(\{b,x_{3}\}\) and \(\{a,b\}\) are greater than the _threshold_, then the two states, \(a\) and \(b\), are added into the path instead of the original corner node \(x_{2}\) (line 5-8 in Algorithm 8). As shown in Figure 5a, two states, \(a\) and \(b\), are inserted into the path instead of the original corner node \(x_{2}\). The modified path is as follows: \(x_{1}\)-\(a\)-\(b\)-\(x_{3}\). If the angle \(\theta_{2}\) or \(\theta_{3}\) is still smaller than the _threshold_, the corner node with the larger angle and the middle node of the vector with the smaller angle are calculated; if this connection between the two states satisfies the conditions for insertion into the path, these two states are inserted into the path instead of the original corner node (line 9-14 in Algorithm 8). As shown in Figure 5b, the angle \(\theta_{3}\) is still smaller than the _threshold_ after the first interpolation operation, then the two states, \(a\) and \(c\), are inserted into the path instead of the original corner node \(x_{2}\). The modified path is as follows: \(x_{1}\)-\(a\)-\(c\)-\(x_{3}\). If the vector \(\{a,b\}\) is not free of collisions after the first interpolation operation, the middle nodes of the vectors \(\{a,x_{2}\}\) and \(\{x_{2},b\}\) are used to modify the path (line 15-17 in Algorithm 8). As shown in Figure 5c, the connection between \(a\) and \(b\) is not free of collisions after the first interpolation operation, then the two states, \(c\) and \(d\), are inserted into the path instead of the original corner node \(x_{2}\). The modified path is as follows: \(x_{1}\)-\(c\)-\(d\)-\(x_{3}\). This method not only eliminates sharp nodes in the path, but also shortens the path according to the principle of triangle inequality.  
Figure 5: Illustration of interpolation optimization. The blue dotted lines represent the cut and add operations. The modified path is marked with an orange outline. (**a**) An edge can be directly inserted into the path; (**b**) a sharp node still exists after inserting an edge; and (**c**) the inserted edge is not free of collisions.