# TA-RRT*: Adaptive Sampling-Based Path Planning Using Terrain Analysis
## 3 Proposed Method
### Terrain Analysis and Adaptive Sampling  
Because path exploration is influenced by the complexity of the environment, it is necessary to analyze the terrain for sampling-based path planning in order to improve search efficiency and reduce path length. In this paper, terrain corners are used to generate the PDF and to quantify the complexity of the terrain. To detect corners, various methods, such as the Harris corner detector [23], have been introduced and proven effective in image processing. The Harris corner detector is an edge detection algorithm widely used in computer vision for identifying corners in an image. It assesses local variations in intensity to determine regions with strong directional changes, which are characteristic of corners. However, due to differences in the environments and the need for computational efficiency in path planning, we utilize a simplified corner detection method based on the Harris corner detector.  
First, the environment is converted into a grid, and corners are detected by comparing the values of each cell with its neighboring cells as the grid is traversed. Figure 2 shows an example of corner detection within a grid. White and gray areas represent free space and terrain (obstacles), respectively. The star marks the point \(g(x,y)\) where corner detection is performed, and the red dashed line indicates the search range used to determine whether \(g(x,y)\) is a corner. The 'X' symbols indicate locations where the values of \(g(x,y)\) differ from those in its adjacent areas. Figure 2a-c shows three different cases of corners. In (a) and (c),\(g(x,y)\) represents a convex and concave corner, respectively [24], while (b) represents an edge that is not considered a corner. Based on these observations, corners are detected by analyzing the discrepancies between adjacent grid cells.  
Here, \(g(x,y)\) denotes the grid cell at the coordinates \((x,y)\), where a value of 0 indicates free space and 1 indicates an obstacle. The number of neighboring cells with different values from a grid \(g(x,y)\) with a value of 1, denoted as \(N_{disp}\), is calculated as follows.  
\[N_{disp}(x,y)=\sum_{\begin{subarray}{c}dy\in\{-1,0,1\},\\ dx\in\{-1,0,1\},\\ (dx,dy)\
eq(0,0)\end{subarray}}\|g(x,y)-g(x+dx,y+dy)\| \tag{1}\]  
Then, the corner \(C(x,y)\) is determined according to the value of \(N_{disp}(x,y)\) as follows:  
\[C(x,y)=\begin{cases}\text{True},&\text{if }(N_{disp}(x,y)>C_{th})\text{ or }(C_{th}==1)\\ \text{False},&\text{otherwise}\end{cases} \tag{2}\]  
where \(C_{th}\) is the threshold for corner detection, which we set to 3 in this paper.  
Next, the identified corners are connected with straight lines, and a PDF is derived using these lines. Figure 3a,b shows the corners (red points) identified using the above detection method and the PDF derived from the lines connecting these corners. In Figure 3a, the black region represents the terrain (obstacle), and the red dots indicate the identified corners. In Figure 3b, the white regions represent high probabilities, while the black regions represent low probabilities.  
Figure 2: Example of corner detection on a grid, with stars marking \(g(x,y)\) and ‘X’ symbols indicating value discrepancies with neighboring grids. (**a**) Convex corner, (**b**) edge region, and (**c**) concave corner.