## 3 Hierarchical Path-Planning
Therefore, the SIRRT* that shows more consistent results (low SDs) is efficient for the hierarchical planning approach. The hierarchical path-planning method consists of two phases: we construct a navigable graph of the environment featuring grid map segmentation and the SIRRT*-mediated path computation among the junction nodes of each segment, then we engage in inter- and intra-regional path-planning using the graph. Table 2 shows the computational times required for the construction of navigable environmental graphs using different numbers of the SIRRT* optimization iterations. The number of such iterations is the number of ellipsoidal-informed samplings performed after obtaining an initial solution via skeletonization. For each fixed iteration number of the SIRRT* optimization, thirty experiments were performed. The environment was divided into 20 local segments, and twenty-eight junction nodes were registered. As all intra-regional paths were defined using the SIRRT*, the SIRRT* algorithm totally ran 117 times for each experiment. Therefore, the computational times in Table 2 reflect 117 SIRRT* path-plannings. The SIRRT* algorithm exploits the deterministic feature of skeletonization and the random nature of the RRT*, thus affording more stable performance than the other RRT* variants. Even after many trials, the standard deviations (SDs) were small; it is appropriate to construct the navigable graph via multiple computations of local paths in each grid map segment. Table 3 shows the hierarchical path-planning results including the inter- and intra-regional path-planning. The starts and goals are those of Table 1. The pre-constructed navigable graph featured 3000 SIRRT* iterations; we performed 100 runs for each iteration number of the SIRRT* optimization. The iteration number of the SIRRT* optimization reveals intra-regional paths from the start and goal positions to the junction nodes. Computationally, global path calculation time increased as the number of iterations increased. When sampling-based planners were used, the time required and the sample number increased as the search area increased. In the experiments of Table 1, we searched the entire environment; optimization required many samples. However, hierarchical intra-regional searches of start and goal positions were performed on environmental segments. Intra-regional searches do not require large numbers of samples. After only 100 iterations, the converged final path was apparent. Cost was reduced if the navigable graph featured over 3000 iterations. Moreover, the proposed hierarchical planning based on the SIRRT* yielded smaller SDs. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{**\# of Iterations for Optimization**} \\ \hline  & **1000** & \multicolumn{6}{c}{**2000**} & \multicolumn{6}{c}{**3000**} \\ \hline Mean & \multirow{2}{*}{Min.} & \multirow{2}{*}{Max.} & Mean & \multirow{2}{*}{Min.} & \multirow{2}{*}{Max.} & Mean & \multirow{2}{*}{(Std.)} & \multirow{2}{*}{Min.} & \multirow{2}{*}{Max.} \\ (Std.) & & & & & & & & \\ \hline
44.33 & \multirow{2}{*}{42.70} & \multirow{2}{*}{45.78} & 108.13 & \multirow{2}{*}{104.82} & \multirow{2}{*}{111.36} & 196.05 & \multirow{2}{*}{189.12} & \multirow{2}{*}{202.16} \\ (0.90) & & & & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Computational times (s) for constructing a navigable graph structure when the numbers of path optimization iterations varied. Figure 7 shows the comparison of the IRRT*, the SIRRT*, and hierarchical path-planning (the H-SIRRT*). Each graph component presents the mean, minimum, and maximum values for 100 runs. As mentioned earlier, because the results of the IRRT* have large differences for each run, it cannot be suitable for practical real-time applications. Moreover, even with the low number of optimization iterations after obtaining the initial solution, the IRRT* required too many iterations to achieve the initial solution, making the total computational time high.