# Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder
## 1 Introduction  
In this paper, we focus on the problem of planning rational paths in continuous and uncertain environments. By \"rational\", we mean that, firstly, computational costs, mainly the time consumed, brought by the planning algorithm must be low enough, so requirements such as avoiding first-move lags and providing human users with an excellent experience can be met; secondly, resultant paths must be collision-free and smooth, and thus, feasible to follow given kinematic constraints. One typical application of this problem lies with agents who maneuver in time-sensitive scenarios (e.g., service robots working in the real world and Non-Player Characters (NPCs) engaging movement tasks in video games). Briefly, application fields such as robotics and video games strongly require time-saving path-planning methods which can quickly generate realistic paths. The problem of path planning is extensively researched in the literature [1; 2; 3; 4; 5; 6]. A* on grid maps [6] is regarded as a fundamental and standard path-planning algorithm based on search. It is completeand optimal, which means A* can find an optimal path if there is at least one from the start point to the goal point. There are at least two shortcomings of A* on grid maps: (1) path symmetry [3], i.e., the existence of symmetrical paths forces A* to generate same states multiple times along different paths, which consumes more time; (2) cell-wise expansion, i.e., since successors of a cell which are expanded are just its adjacent cells, this short-ranged expansion brings about a huge open list and a large number of operations. These two problems cause many unnecessary cell generations and expansions, and, as a result, A* is so slow that it cannot meet the first requirement for rational paths. To overcome the above disadvantages, methods for map abstraction attract many researchers' attention. Subgoal graphs (SG) [5] is an archetypical map-abstraction-based algorithm, whose preprocessing stage is responsible for building subgoal graphs. Similar to visibility graphs, its simple version--SSG--places subgoals at the corners of obstacles. SSG links cells, between which a reachability relationship called direct-h-reachability is satisfied, and all symmetrical paths are traversable. Then, over subgoal graphs, A* is used to obtain the abstract path. Finally, depth-first search is safely utilized to refine it into a ground-level path. As a result, A* on subgoal graphs works far better than that on grids and satisfies the first requirement mentioned above. As for the second requirement, however, the optimal ground-level path is constrained to grid edges (i.e., the heading changes are artificially constrained to specific angles) [7], which causes sharp turns in the generated paths, and cannot meet kinematic constrains. Moreover, it is time-consuming for SG to deal with changing environments by reconstructing subgoal graphs. To plan kinematically feasible paths, interpolating curve planners [8] construct and insert a new set of data within the range of a previously known set. For example, in Reference [9], hypocycloidal curves were used to smooth sharp turns, which can maintain a safe clearance in relation to the obstacles. However, when unexpected obstacles often appear in the detection range of robots, these kinds of planners need to recalculate a new path frequently, causing more time consumption. It is also difficult for sampling-based planners, such as Probabilistic Roadmaps (PRM) [10] and rapidly exploring Random Trees (RRT) [11], to deal with unexpected obstacles. Furthermore, the generated paths are random and suboptimal. To deal with uncertain environments and improve the path quality, Reinforcement Learning (RL) can be used to learn near-optimal policies to find paths in the real world under certain constrains. RL is learning what to do--how to map situations to actions--to maximize a numerical reward signal [12]. Specifically, RL is an agent that interacts with the environment, and learns an optimal policy by trial and error [13].