# An Efficient RRT Algorithm for Motion Planning of Live-Line Maintenance Robots
## 3 Offline Rapid Exploring Random Tree
### Expansion  
Algorithm 1 introduces the expansion method of the random tree. Unlike the traditional expansion method, we add the withering operation to the expansion process. The expansion process stops the growth whenever n new nodes are generated. Then, Algorithm 2 is used to wither the tree, removing small branches on the random tree and keeping the main trunk. Through the cycle of growth and withering, tree \(T_{offline}\) will eventually fill the planning space. During the expansion process, only the fixed barrier constraint \(P_{StaticObs}\) is calculated. Figure 8: The twisting of a drainage line during installation. Figure 7: Tool restrictions on robot movement. ((a) The unfixed parts need to be kept open for cable entry. (b) Cable with uncertain twist). Figure 9: Tree expansion influenced by the change in regional sampling frequency (sampling times = 500/1000/2000, \(\alpha=0.5\), and \(\beta=0.05\)). ```
0:\(\Phi_{j}\), \(P_{StaticObs}\), \(p_{start}\), \(p_{goal}\),\(n\),\(N\)
0:\(T_{offline}\)
1: Create \(T_{offline}\) with root node \(p_{start}\);
2:loop
3: // Make the tree grow;
4:\(cnt\) = \(n\);
5:while cnt >0 do
6: Expand \(T_{offline}\) using RRT*;
7:\(cnt\) = cnt -1;
8:endwhile
9: //ither the tree
10: Remove the small branches of \(T_{offline}\) using Algorithm 3;
11:\(num\) = sizeof(\(T_{offline}\));
12:if\(num\geq N\)then
13: Break;
14:endif
15:endloop
```  
**Algorithm 1** Expand the tree by growing and withering. ```
0:\(T\), len
0:\(T_{withered}\)
1:\(cnt\) = size(\(T_{offline}\));
2:while cnt >0 do
3:\(parent\_index\) = GetParentIndex(\(T\)(cnt));
4:while parent\(\_index\) >0 do
5:if\(T(parent\_index)\) is not retrieved then
6:\(branch\) = [\(T(parent\_index)\);branch];
7: Mark \(T(parent\_index)\) as retrieved
8:\(parent\_index\) = GetParentIndex(\(T(parent\_index)\));
9:else
10:\(parent\_index\) = 0;
11:endif
12:endwhile
13:if size(branch) >\(len\)then
14: Merge the branch into \(T_{withered}\);
15:endif
16:\(cnt\) = cnt-1;
17:endwhile
```  
**Algorithm 2** Wither the tree. The purpose of withering is to remove the short branches on the tree and reduce the number of nodes. Starting from the point with the largest index, the branches are constructed by retrieving the parent node. The retrieved nodes are marked to prevent repeated retrieval. A long branch (>len) is added to tree \((T_{withered})\). Since nodes with larger indices are newly added, starting from the largest index point can ensure the integrity of the branch. In addition, this also prevents new nodes at the ends of the branches from being pruned, ensuring that the branches are continuously expanded. The withering process is shown in Figure 10.  
```
0:\(\Phi_{j}\), \(\mathbf{P}_{StaticObs}\), \(\mathbf{P}_{DynObs}\), \(\mathbf{p}_{start}\), \(\mathbf{p}_{end}\)
0:\(\Theta_{Path}\)
1: Create \(T_{offline}\) with \(\mathbf{p}_{start}\) in \(\Phi_{j}\);
2: Expand \(T_{offline}\) using Algorithm 1 offline under the constraints of \(\mathbf{P}_{StaticObs}\);
3: Create \(T_{goal}\) with \(\mathbf{p}_{start}\);
4:while new node \(P_{new}\) cannot be connected to \(T_{offline}\)do
5: Expand \(T_{goal}\) using Algorithm 4;
6:endwhile
7: Plan \(Path(\theta_{0},\theta_{1},...\theta_{n})\) from \(\mathbf{p}_{start}\) to \(\mathbf{p}_{end}\) through point \(p_{new}\);
8:if Path collides with \(\mathbf{P}_{DynObs}\)then
9: Replan using Algorithm 5;
10:endif
```  
**Algorithm 4** Rewiring for the dynamic obstacle. ```
0:\(p_{dyn,obs}\), \(T_{offline}\), Path
0:\(Path_{dyn}\)
1:[\(p_{s}\), \(p_{e}\)]=FindCollisionofPath(\(Path,p_{dyn\_obs}\));
2:\(T_{cut}\) = CutTreeCrownFromNode(\(p_{s}\));
3: Inital \(T_{dyn}\) with Path(\(p_{e}:\) end);
4:loop
5: Expand \(T_{dyn}\) using Algorithm 4 (line 4-11);
6: Find the \(Path_{dyn}\) through the joint node
7:if collision(\(Path_{dyn}\), \(p_{dyn\_obs}\)) == false then
8: break;
9:endif
10:endif
11:endloop
```  
**Algorithm 5** Expand the tree from the goal.