# TA-RRT*: Adaptive Sampling-Based Path Planning Using Terrain Analysis
## 2 Related Works  
### Motivation  
The RRT algorithm generates random sample points to expand a tree and explores paths that allow a vehicle to reach its target point [13]. While it has the advantage of quickly exploring complex high-dimensional spaces, it does not guarantee the optimality of the generated path. RRT is a fundamental algorithm that has served as the basis for many studies and improvements in the efficiency of path exploration. The RRT* algorithm was designed to improve the optimality of paths while maintaining the exploration efficiency of RRT [15]. RRT* reduces the path length by reorganizing the existing tree structure each time a new node is added during the exploration process. However, this restructuring process incurs additional computational costs. RRT* consists of the following key steps:  
* Random Sampling: randomly generates sample points to expand the exploration space. * Node Expansion: finds the nearest node to the sample point and generates a new node in that direction. * Collision Check: verifies that the path between the new node and the existing nodes does not collide with any obstacles. * Rewiring: after adding a new node, the connections with surrounding nodes are restructured to improve the optimality of the path. The pseudocode of RRT* is shown in Algorithm 1. ```
1:\(V\gets q_{\text{init}}\), \(E\leftarrow\emptyset\)
2:for\(k=1\) to \(K\)do
3:\(q_{\text{rand}}\leftarrow\text{RandomSample}()\)
4:\(q_{\text{nearest}}\leftarrow\text{Nearest}(T,q_{\text{rand}})\)
5:\(q_{\text{new}}\leftarrow\text{Steer}(q_{\text{nearest}},q_{\text{rand}})\)
6:if CollisionCheck(\(q_{\text{nearest}},q_{\text{new}}\)) then
7:\(V\gets V\cup\{q_{\text{new}}\}\)
8:\(Q_{\text{near}}\leftarrow\text{Near}(T,q_{\text{new}},r)\)
9: ChooseParent(\(Q_{\text{near}},q_{\text{nearest}},q_{\text{new}},E\))
10: Rewiring(\(Q_{\text{near}},q_{\text{new}},E\))
11:endif
12:endfor
```  
**Algorithm 1** RRT*(\(q_{init}\), \(V\), \(E\))  
Here, \(V\) represents the set of nodes, which initially contains only the starting point \(q_{\text{init}}\). \(E\) represents the set of edges, which is initially empty. \(K\) denotes the maximum number of iterations of the algorithm. \(q_{\text{rand}}\) is a randomly generated sample point, \(q_{\text{nearest}}\) is the node in the tree \(T\) closest to \(q_{\text{rand}}\), \(q_{\text{new}}\) is the new node expanded from \(q_{\text{nearest}}\) in the direction of \(q_{\text{rand}}\), \(Q_{\text{near}}\) is the set of nodes near \(q_{\text{new}}\), and \(r\) is the radius used to search for nearby nodes. The RRT* algorithm can find a path that connects the starting point to the goal by expanding the tree. However, as shown in Figure 1, the resulting path (purple line) may not be the shortest path between the two points. Figure 1: Example of RRT* path planning results. To overcome these limitations and derive more efficient paths, algorithms such as Informed-RRT* and RRT*-Smart have been proposed [17; 18]. These algorithms build upon RRT* by enhancing path efficiency through node sampling in a limited region after generating the initial path. Informed-RRT* first generates an initial path, then defines an ellipse using the start and goal points, along with the path length, as parameters [17]. Additional nodes are sampled within this ellipse to improve the initial path, with the ellipse being reconfigured iteratively to further enhance path efficiency. RRT*-Smart also generates an initial path, then improves it by designating key points in the environment, such as terrain corners, as beacons [18]. Additional nodes are sampled near these beacons to update and improve the path. These algorithms propose additional node sampling regions based on an intuitive analysis of the environment. As a result, they can improve paths in certain conditions, but their effectiveness is limited in other scenarios, particularly in complex terrains.