# Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder
## 3 Materials and Methods
### The SG-Based Global Abstract Path Planner  
Figure 3 shows the offline work concerning building alert areas and constructing subgoals. Since paths found by SSG over the original map are close to obstacles, they are not safe for robots to follow. To tackle this problem, we added alert areas into original-map-based distance maps. Figure 3: _Cont._  
During the phase of building alert areas, the dynamic brushfire algorithm [29] was used to build the Euclidean distance map (Figure 3b) based on the original map (Figure 3a). Then, the map with alert areas was constructed based on the Euclidean distance map. The size of alert areas was determined by the sizes of the robot and user-defined safety distance. One distinctive advantage of using a distance map to build alert areas is that one distance map can be used to construct various sizes of alert areas. Then, we used the SG algorithm to find abstract paths on maps with alert areas and provide subgoal sequences for the feasible trajectory planner. There are three kinds of SG algorithm, namely simple, two-level, and n-level subgoal graphs [5,20]. We chose SSG as the method at this phase because, in SSG, all symmetrical paths between adjacent subgoals are not blocked by obstacles, which can provide better subgoal sequences for the trajectory planner. First of all, in Reference [5], there are some key definitions. Heuristic \(h(s,s^{\prime})\) is the octile distance between cells \(s\) and \(s^{\prime}\). **Definition 1**. : _An unblocked cellsis a subgoal iff there are two perpendicular cardinal directions \(c_{1}\) and \(c_{2}\) such that \(s+c_{1}+c_{2}\) is blocked and \(s+c_{1}\) and \(s+c_{2}\) are not blocked._  
**Definition 2**. : _Two cellssand \(s^{\prime}\) are h-reachable iff there is a path of length \(h(s,s^{\prime})\) between them. Two h-reachable cells are safe-h-reachable iff all shortest paths between them are not blocked by obstacles. Two h-reachable cells \(s\) and \(s^{\prime}\) are direct-h-reachable iff none of the shortest paths between them contains a subgoal \(s^{\prime}\
otin\{s,s^{\prime}\}\)._  
**Definition 3**. : _A subgoal graph\(G_{S}=(V_{S},E_{S})\) is an undirected graph where \(V_{S}\) is the set of subgoals and \(E_{S}\) is the set of edges connecting direct-h-reachable subgoals. The lengths of edges are the octile distances between subgoals they connect._  
In SSG, there are two steps to find the shortest paths from a start cell to a goal cell. The preprocessing stage abstracts subgoal graphs from the underlying grid maps with alert areas, by identifying subgoals and checking direct-h-reachability. This sparse space representation can eliminate the path symmetry with the strict reachability check and generate subgoals which are not close to each other, as successors. As for the online phase, given the start and goal point, it applies a connect-search-refine approach to return ground-level paths. For our scenarios, the refinement was  
Figure 3: (**a**)This is the original map. (**b**) The Euclidean distance map. Black represents occupied cells. The brightness of cells increases with distance. (**c**) The map with alert areas. The light-yellow cells denote the alert areas. (**d**) The subgoal graph. The light-blue cells represent subgoals, and the red lines signify the direct-h-reachability of adjacent subgoals. replaced by LSPI to obtain a smooth and collision-free path. Thus, a connect-search method remained, as shown in Algorithm 1. Algorithm 1 shows how to find the shortest paths over subgoal graphs. Firstly, the start cell and the goal cell are regarded as subgoals and are connected to subgoal graphs. Then, A* is used to search global abstract paths over modified subgoal graphs. As proven in Reference [5], SSG is a complete and optimal global search algorithm. In Figure 3d, the grid map with alert areas is 12 \(\times\) 12. However, the size of \(V_{S}\) of the subgoal graph is 7, and the size of \(E_{S}\) is 7. Obviously, the search space of the subgoal graph is smaller than the grid map's.