## 3 Hierarchical Path-Planning  
In this section, the hierarchical path-planning method using the graph-search algorithm and the SIRRT* is developed. Previously, a navigable graph of the environment consisting of local grid map segments, the adjacency matrix, and the junction nodes between all adjacent segments was constructed. We now use the SIRRT* to compute intra-regional paths among the junction nodes of each grid map segment. Figure 4 shows the SIRRT* result for Segment \"9\". The initial solution path is computed using the Harris corner nodes of the skeletonized grid map image and [PERSON]'s algorithm (Figure 4a-c). The final path is obtained via informed sampling optimization (Figure 4d). Figure 5 shows the overall procedure of the proposed method. The first layer in path-planning is an inter-regional search using the navigable graph structure of the segmented grid maps; we find a start region and a goal region (A). Then, the inter-regional path from the start region to the goal region is computed using the adjacency matrix and the graph-search algorithm (B). The Dijkstra graph-search algorithm is employed to this end; all adjacent segment pairs are equally weighted during the inter-regional search. When the inter-regional path is defined, the junction nodes are selected (C) to yield the SIRRT* paths among those nodes for each path region. At this time, several junction nodes for two adjacent segments can be selected because obstacles may lie between the segments. Thus, two adjacent segments can be connected at several nodes. To ensure that the junction node sequence from the start to the goal is efficient, we construct a cost matrix. The SIRRT* yields the intra-regional paths from the start to the junction nodes of the start region and from the goal to the junction nodes of the goal region (D). The cost matrix is calculated by the costs of the SIRRT* paths (E). By using the cost matrix and the Dijkstra graph-search algorithm, the node sequence from the start position to the goal position can be computed (F). The graph-search algorithm selects the cheapest junction nodes. Finally, a global path is achieved by combining the intra-regional paths with reference to the node sequence (G). Figure 4: \(Cont\). Algorithm 2 is the pseudocode of the hierarchical path-planning, and it describes the procedure after obtaining the inter-regional path from the start region, \(seg_{S}\), to the goal region, \(seg_{G}\). \(Seg\) is the sequence of the path regions according to the inter-regional path, and \(K\) is the number of the path regions. Algorithm 2 also requires the navigable graph structure including the junction nodes, \(Node_{JC}\), and the intra-regional paths, \(Path\), of all segments. The junction nodes, \(Node_{\text{path}}\), are selected according to the inter-regional path, \(Seg\), in Lines 2-5. The intra-regional paths, \(Path_{S}\), from the start position to the junction nodes of the start region are computed by the SIRRT* (Lines 6-10). The intra-regional paths, \(Path_{G}\), from the goal position to the junction nodes of the goal region are also computed by the SIRRT* (Lines 11-15). The cost matrix, \(Cost_{C}\), among the selected junction nodes, the start position, and the goal position is obtained in Lines 16-26. If \(M\) is the number of the selected junction nodes, \(Node_{path}\), the size of the symmetric cost matrix is \(M+2\). The cost values between the start/goal to the selected junction nodes should be added to the cost matrix. Using the cost matrix, the Dijkstra graph-search algorithm computes the node sequence, \(Node_{SG}\), from the start to the goal. Here, the indices of the start and the goal in the cost matrix are \(M+1\) and \(M+2\), respectively (Line 27). By connecting the intra-regional paths in series, we obtain the final path, \(Path_{SG}\) (Line 28). Figure 4: An example of local path-planning for Segment “9” using the skeletonization informed rapidly exploring random tree* (SIRRT*): (**a**) Skeletonization of the grid map segment.