# TA-RRT*: Adaptive Sampling-Based Path Planning Using Terrain Analysis
## 3 Proposed Method  
### TA-RRT* Overview  
To overcome the limitations of existing algorithms, we propose an RRT*-based path planning algorithm that incorporates adaptive sampling and a step size based on terrain analysis.  
Algorithm 2 presents the pseudocode for the proposed TA-RRT* algorithm. Here, \(V\) denotes the set of nodes, which initially contains only the starting point \(q_{\text{init}}\). \(E\) denotes the set of edges, which starts as being empty. \(K\) indicates the maximum number of iterations. \(q_{\text{rand}}\) is a randomly generated sample point, \(q_{\text{nearest}}\) is the closest node in the tree \(T\) to \(q_{\text{rand}}\), \(q_{\text{new}}\) is the new node expanded from \(q_{\text{nearest}}\) towards \(q_{\text{rand}}\), \(Q_{\text{near}}\) is the set of nodes near \(q_{\text{new}}\), and \(r\) is the radius used for searching nearby nodes.  
Algorithm 2 is similar to RRT*, with the key differences highlighted. The proposed algorithm analyzes the terrain of the operating environment to extract the terrain corners (\(C\)) and uses this information to generate a PDF (\(P\)) for node sampling (Lines 2-3). Paths that pass near obstacles can be shortened when they approach the vertices of the terrain [18; 21]. Based on this principle, a PDF is generated to increase the likelihood of node occurrence near these vertices and along the paths between them. Nodes are sampled to expand the tree. Initially, nodes are sampled based on a uniform distribution. However, once the initial path is created, nodes are sampled according to the PDF (\(P\)) generated from the terrain corners (\(C\)). To improve path length through random exploration, an \(\varepsilon\)-greedy strategy is applied [22], combining random sampling from a uniform distribution with adaptive sampling based on the PDF at a specified ratio (Lines 5, 7-9). The process of generating the terrain-based PDF and performing adaptive sampling is described in Section 3.2.  
```
1:\(V\gets q_{\text{init}}\), \(E\leftarrow\varnothing\)
2:\(C\leftarrow\text{TerrainAnalysis}()\)
3:\(P\leftarrow\text{GeneratePDF}(C)\)
4:for\(k=1\) to \(K\)do
5:if\((\varepsilon<\varepsilon_{th})\) or (not InitialPathFound) then
6:\(q_{\text{rand}}\leftarrow\text{RandomSample}()\)
7:else
8:\(q_{\text{rand}}\leftarrow\text{RandomSampleFromPDF}(P)\)
9:endif
10:\(q_{\text{nearest}}\leftarrow\text{Nearest}(T,q_{\text{rand}})\)
11:\(q_{\text{new}}\leftarrow\text{AdaptiveSteer}(q_{\text{nearest}},q_{\text{rand}},C)\)
12:if\(\text{CollisionCheck}(q_{\text{nearest}},q_{\text{new}})\)then
13:\(V\gets V\cup\{q_{\text{new}}\}\)
14:\(Q_{\text{near}}\leftarrow\text{Near}(T,q_{\text{new}},r)\)
15:\(\text{ChooseParent}(Q_{\text{near}},q_{\text{nearest}},q_{\text{new}},E)\)
16:\(\text{Rewiring}(Q_{\text{near}},q_{\text{new}},E)\)
17:endif
18:endfor
```  
**Algorithm 2** TA-RRT*(\(q_{\text{init}}\), \(V\), \(E\))  
Subsequently, the step size is adaptively adjusted according to the terrain complexity. In complex terrains, a shorter step size allows for precise path exploration, while in simpler areas, a longer step size facilitates broader exploration within the given iterations, improving the probability of generating an initial path. This adaptive step size approach, which refines the path by utilizing more nodes, is explained in Section 3.3.