## 1 Introduction
To overcome the slow convergence rate and reduce the overall processing time by quickly obtaining an initial solution, we previously developed a skeletonization-informed RRT* (SIRRT*) for mobile robots moving in 2D environments [21]. The IRRT* obtains the initial solution using the RRT* algorithm. By contrast, the SIRRT* generates an initial solution by skeletonizing a grid map and constructing a tree on the skeletonized image using [PERSON]'s algorithm [22]. As the convergence rate of the IRRT* algorithm depends on the quality of the initial solution computed by random sampling of the RRT* over the whole space, the IRRT*'s performance is unstable even when the start and goal positions do not change within the same environment. The SIRRT* utilizes the deterministic property of grid map image skeletonization to find the initial solution more robustly and rapidly than the IRRT*. The total computational time required to attain a final solution by the SIRRT* is lower and more repeatable than that required by the IRRT*. The global path-planning approaches mentioned above assume that an environmental map is available and process the entire map. Thus, path-planning is performed in a single-layer manner. When a part of the map is changed, replanning includes both the unchanged and changed regions. Moreover, we can encounter the situation when the current start and goal positions differ slightly from the start and goal positions of the previously solved problem. The conventional path-planners require sample nodes covering the entire map, although most of the two final solutions may be identical. If we can divide the map and obtain the adjacency between map segments, we can efficiently handle such situations. Sampling-based planners require ever more samples (associated with longer computational times) of larger environments to obtain optimal solutions. If we can construct a environmental graph that contains local path information for each segment and if the graph can be re-used to deal with future path-planning problems, the sampling space can be focused to compute paths more efficiently. Thus inspired, we here propose a hierarchical path-planning method using the SIRRT*. Earlier global planners have sought to guarantee optimal solutions and reduce computational times; few studies have explored hierarchical path-planning. The focused hierarchical D* (FHD*) is a grid-based,hierarchical, path-planning algorithm seeking to optimize paths by placing bridge nodes on the potential field of the grid map [23]. A three-level hierarchical structure exploiting particle swarm optimization was suggested to yield feasible, safe, and optimal paths [24]. However, its hierarchy means the algorithmic structure is composed of map decomposition and path optimization; the method does not reveal the hierarchical geometric structure of the environment. A hierarchical roadmap (HRM), similar to what we develop here, can be incrementally constructed via normalized graph-cut segmentation of a local sonar grid map [25]. Here, a two-layered, hierarchical path-planning method is developed. The combined method of the previous work, the SIRRT*, and the well-known image segmentation method, the watershed segmentation, is presented. A global path, thus a sequence of path regions from a start region to a goal region, is firstly obtained through the segmented grid map. Within each path region, the SIRRT* is applied to compute a local path between two junction nodes. An entire path from the start to the goal is generated by combining these local paths. Figure 1 illustrates the proposed hierarchical path-planning method. The local grid maps (A, B, and C) and the junction nodes (J1, J2) between adjacent local maps constitute a graph. The local paths within local grid maps, defined via intra-regional searching, are combined using the inter-regional path. The proposed approach can be applied to most mobile robots operated in 2D environments, including wheeled mobile robots and legged mobile robots.