# Path Planning of a Mobile Robot Based on the Improved RRT Algorithm
## 3 Methods
### Optimizer
#### 3.2.1 Dijkstra Pruning  
The quality of the path generated by the RRT algorithm is poor; this is mainly reflected in the fact that there are many redundant nodes in the path and the path is relatively tortuous. Generally, this kind of path cannot be directly used in practical applications. In [12], an optimization concept based on triangle inequality is proposed. This method can eliminate redundant nodes and shorten the path length, but it does not find the shortest path based on the current results and there may be issues related to detours, as shown in Figure 4b. Because this method only considers the relationship between three nodes (the child node, the parent node, and the ancestor node) each time, it does not take into account the distance relationship between all the nodes in the path. The Dijkstra algorithm is an effective means of finding the shortest path. In each iteration of the Dijkstra algorithm, the node that is closest to the initial state and has not been visited is chosen to perform the relaxation operation. Finally, the shortest path from the initial state to the target state is determined. The specific method for applying the Dijkstra algorithm to the path optimization is as follows. First, an adjacency matrix _Value_ is used to record the distance between each state and the other states in the path. If there are obstacles blocking the connection between two states, the distance is set to infinity (line 1 in Algorithm 6). Then, three arrays, _Visit_, _Path_, and _Dis_, are set. _Visit_ is used to record the visibility of each state. _Path_ is used to record the predecessor node of each state. _Dis_ is used to record the distance value from the initial state to each other state (line 1 in Algorithm 7). In each round, the minimum value is selected  
Figure 3: Illustration of the adjustable sampling area strategy. The nodes added to the tree are marked with blue, and the nodes marked with purple are added to the tree using the FailSample function. The final path is marked with an orange outline. from _Dis_, and the corresponding state \(i\) in _Visit_ is set to true (line 3-4 in Algorithm 7). Then, the relaxation operation is performed, such that:  
\[Dis[j]>Dis[i]+Value(i,j) \tag{7}\]  
If the distance from the initial state to state \(j\) can be improved by state \(i\), state \(i\) is set as the predecessor node of state \(j\) (line 6-9 in Algorithm 7). The above operations are repeated until all states in _Visit_ are visited. Finally, the shortest path is traced from the target state to the initial state via the array _Path_ (line 12 in Algorithm 7). ```
Input: \(\eta_{init}\),Value Output: an optimized path \(\eta^{\star}\)
1:Visit:init, Path.init, Dis.init
2:for\(k=1\) to \(n-1\) do
3:\(i\gets min(Dis)\)
4:\(Visit[i]\leftarrow\) True
5:for\(j=1\) to \(n\) do
6:ifDis[j] \(>\)Dis[i] +Value(i,j) then
7:\(Dis[j]\gets Dis[i]+Value(i,j)\)
8:\(Path[j]\gets i\)
9:end
10:end
11:end
12:\(\eta^{\star}\leftarrow\)Path
```  
**Algorithm 7**_Dijkstra Pruning_  
An example of a utilization of the Dijkstra pruning strategy is shown in Figure 4. Let obstacles be denoted by _obs_. As shown in Figure 4a, the initial path is as follows: \(x_{init}\)-\(x_{1}\)-\(x_{2}\)-\(x_{3}\)-\(x_{4}\)-\(x_{5}\)-\(x_{goal}\). As shown in Figure 4b, starting from the initial state, three waypoints \(x_{init}\), \(x_{1}\), and \(x_{2}\) are chosen in order. Note that the edge {\(x_{init}\), \(x_{2}\)} is free of collisions and the distance is shorter than the original route from \(x_{init}\) to \(x_{2}\). Therefore, the state \(x_{1}\) is considered to be a redundant node and the original route is replaced by the edge {\(x_{init}\), \(x_{2}\)}. Then, consider the relationship between the three waypoints \(x_{init}\), \(x_{2}\), and \(x_{3}\), where the edge {\(x_{init}\), \(x_{3}\)} is not free of collisions. Therefore, the state \(x_{init}\) is traversed; starting from the next state \(x_{2}\), the same operation is executed until the target state is traversed.