# Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder
## 5 Conclusions  
In this paper, we proposed a hierarchical path-planning framework called SG-RL in continuous and uncertain environments. By \"rational\", we mean (1) efficient path planning to eliminate first-move lag; (2) collision-free and smooth for agents with kinematic constraints satisfied. SG-RL plans rational paths in a two-phase manner (i.e., the first phase for global abstract path planning and the second for feasible trajectory planning). In the first phase, SG-RL uses SSG to generate subgoal sequences efficiently for eliminating first-move lag, and overcome sparse reward and local minima trap for LSPI. In the second phase, following kinematical equations, SG-RL uses LSPI to plan feasible trajectories for agents between adjacent subgoals, and handles unexpected obstacles without replanning subgoal sequences. In simulation experiments, firstly, SG-RL was evaluated on realistic and large-scale maps constructed by laser sensor data. The action-switching frequency was below 10% and the time to obtain subgoal sequences was between 195 times and 107 times faster than A* on grid maps. The path length of SG-RL was shorter than that of SSG. Secondly, evaluated on dynamic maps, SG-RL can deal with uncertainties based on original subgoal sequences without reconstructing subgoal graphs from the changed map. We demonstrated that the design of reward functions and the type of training environment are important factors for learning feasible policies. A concise reward with action-changing punishment \begin{table}
\begin{tabular}{c c c} \hline \hline
**Reward Function** & **Without Action-Changing** & **With Action-Changing** \\  & **Punishment** & **Punishment** \\ \hline concise reward & 38\% & 49\% \\ comparative value reward & 7\% & 14\% \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Effect of adding action-changing punishment. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Reward Function** & \begin{tabular}{c} **Ratio of Successful** \\ **OA Policies** \\ \end{tabular} & \begin{tabular}{c} **Ratio of Policies with Action-Switching** \\ **Frequency Below 30\%** \\ \end{tabular} & \
\begin{tabular}{c} **Average Iteration** \\ **Numbers of LSPI** \\ \end{tabular} \\ \hline
\begin{tabular}{c} simplified office map \\ map with random obstacles \\ \end{tabular} & 53\% & 48\% & 7.94 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Comparison of different types of training maps. achieved the best results in the obstacle-avoiding MDP, which means that reward functions with prior experience may bring difficulties for agents to learn effective policies. The map with random obstacles increased the accuracy of the learned transition probability function, whose ratio of getting an effective obstacle avoidance policy was 89%. SG-RL, as a hierarchical path-planning method, combines the strengths of SSG and LSPI to overcome their limitations, greatly improving the efficiency of finding rational paths. In future work, continuous action spaces can be taken into consideration. Specifically, the range of angular velocity can be [\(-0.5\), \(0.5\)], which means that robots can do more free and complex actions, such as going backward. In the second phase of SG-RL, if the number of state-action pairs is not huge, LSPI can keep the relative size of Q-value for every state-action pair to ensure the right action choice. However, since adding continuous action space will greatly increase the state-action space, it is difficult for linear basis functions to evaluate the Q-value precisely. Inspired by the idea of asynchronous advantage Actor-Critic [30], we can use an artificial neural network to approximate state-action value functions, and use another network to approximate policy functions, which can increase the accuracy of evaluating the Q-value. [PERSON] and [PERSON] conceived and designed the paper structure and the experiments; [PERSON] performed the experiments; [PERSON], [PERSON], and [PERSON] contributed with materials and analysis tools.