# An Efficient RRT Algorithm for Motion Planning of Live-Line Maintenance Robots
## 3 Offline Rapid Exploring Random Tree
### Dynamic Area Sampling  
The RRT method expands the tree through random sampling. Therefore, by changing the uniformity and randomness of sampling, the tree can be controlled to grow according to the constraint conditions. Representative RRT improved algorithms based on this principle include RRT-informed and RRT-connect. In multi-DOF robot motion planning, it is not suitable to improve the algorithm by sampling in a small area because the obstacles are in a flow pattern in the planning space. The method of changing the sampling probability using the traditional greedy strategy may lead to oversearching and increase the computational effort of collision detection. As shown in Equation (6), \(x_{rand}\) is a randomly generated sample point. When a random number \(p\) is greater than \((1-\alpha)\), the random sample points are selected on the line between the nearest tree node and the target point \(p_{goal}\). \[\mathrm{x}_{\mathrm{rand}}\,=\,\left\{ \begin{array}{cl}\mathrm{ LineTo}\,\left(p_{\mathrm{goal}}\right)&\quad\text{if }p\geq\alpha\\ \mathrm{Uniform}\,\left(P\right)&\quad\text{if }p<1-\alpha\end{array} \right. \tag{6}\]  
This strategy helps the tree to find the target location quickly when there are few obstacles. However, in the case of more obstacles, it affects the efficiency of the search. As shown in Figure 5, under the influence of the greedy strategy, the tree grows towards the target. Since 6D space cannot be displayed intuitively, the algorithm is explained using a tree in a 2D space. When there is an obstacle on the line to the target, a large number of samples will be generated that do not satisfy the collision constraint. The nodes in the red area are denser, which means that the algorithm conducts many searches near the obstacle. The problem is particularly acute in robot joint spaces where flow pattern obstacles exist. To solve this problem, we proposed a dynamic sampling method using different sampling probabilities at different tree growth stages. In Equation (8), Function Rect(A,B) represents a rectangular region with vertices A \(p_{\mathrm{goal}}\) and B \(p_{\mathrm{goal}}+(1-k)p_{\mathrm{start}}\). The variable \(k\in[0,1]\) is the growth index of the tree and is expressed by the ratio of the number of nodes to the constant N in Equation (8). The greedy sampling area is controlled according to the change in \(k\). When the value of \(k\) is small, the sampling value is close to the average sampling value, the value of \(k\) increases, and the sampling area decreases. \[\mathrm{x}_{\mathrm{rand}}\,=\,\left\{ \begin{array}{cl}\mathrm{Uniform}( \mathrm{dynarea})&\quad\text{if }p\geq\alpha\\ \mathrm{Uniform}\,\left(\Phi_{I}\right)&\quad\text{if }p<\alpha\end{array} \right. \tag{7}\]\[\text{dynarea }=\text{Rect}\Big{(}p_{\text{goal}}\,,\quad k\cdot p_{\text{goal}} +(1-k)p_{\text{start}}\,\Big{)} \tag{8}\]  
\[k=\text{ size(tree) /N} \tag{9}\]  
Figure 6 shows the planning results of dynamic area sampling. Compared with the traditional greedy algorithm, the sampling density near the obstacle is lower, and there is no oversampling phenomenon. Close to the target area, the branches and leaves of the tree become denser. This can help trees grow quickly towards the target location. In motion planning, some paths are not expected. Reducing the sampling frequency for a specific area can reduce the growth of trees in that area. As a result, the probability of generating undesired paths is greatly reduced. In Equation (10), \(\beta\in(0,\alpha)\) is a small constant, and the region is sampled only when \(p<\beta\). \[\text{x}_{\text{rand}}\,=\,\left\{ \begin{array}{cc}\text{Uniform}(rect)&p\geq \alpha\\ \text{Uniform}(\text{C }_{p}P_{\text{bor}}\,)&\beta\leq p<\alpha\\ \text{Uniform }(P_{\text{bor}}\,)&p<\beta\end{array} \right.