# Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder
## 3 Materials and Methods
### The LSPI-Based Feasible Trajectory Planner
#### 3.4.2 Definitions of Subgoal-Approaching (SA) and Obstacle-Avoiding (OA) MDPs  
In the feasible-trajectory-planning phase, to increase training efficiency, we decomposed the problem of finding feasible trajectories between subgoals into two sub-problems--approaching subgoals and avoiding obstacles. Since LSPI is used to find a solution to discrete-time MDPs with continuous state spaces, given as a tuple of states, action, rewards, and next states, \((s,a,r,s^{\prime})\), we separately built two MDPs via abstracting key information from the two sub-problems, to formally describe environments for LSPI. One MDP, named Subgoal-Approaching (SA), describes the process of approaching subgoals with kinematic constraints satisfied. The other MDP, named Obstacle-Avoiding (OA), describes the process of preventing collisions with obstacles. Definitions of SA and OA are described in Table 1. In these two MDPs, we used kinematic equations to update trajectories of the robot, so that the trajectories could preserve G1 continuity. Figure 5 shows the process of planning feasible trajectories. At first, we check the sensor data, and then decide which MDP to execute. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Type of MDP** & **SA MDP** & **OA MDP** \\ \hline States & \((d_{g},a_{g})\) & \((S_{1},S_{2},S_{3},S_{4},S_{5},S_{6})\) \\ \hline \multirow{3}{*}{Actions} & move forward: (0.5, 0.5) & move forward: (0.5, 0.5) \\  & turn left: (0.5, 0) & turn left: (0.5, 0) \\  & turn right: (0, 0.5) & turn right: (0, 0.5) \\ \hline \multirow{3}{*}{Reward} & +10 & if \(d_{g}<d_{n}\) \\  & \(-\tilde{a}_{g}\) & if \(\tilde{a}_{g}>0\) \\ \cline{1-1}  & \(1-\tilde{d}_{g}-\tilde{a}_{g}\) & else \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Definitions of Subgoal-Approaching (SA) and Obstacle-Avoiding (OA) Markov Decision Processes (MDPs). In the SA MDP, state \(d_{g}\) denotes the distance between the robot and the goal, state \(a_{g}\) denotes the angle between the robot's orientation and the direction from the robot heading to the goal, and the range of \(a_{g}\) is \([-\pi,\,\pi]\). When the goal is on the left side of the robot's orientation, the value of \(a_{g}\) is positive. Otherwise, the value is negative. There are three actions (i.e., going forward, turning left, and turning right) that the robot can execute. Each action corresponds to values of \(\omega_{l}\) and \(\omega_{r}\). For example, the action of going forward is equal to setting \(\omega_{l}\) and \(\omega_{r}\) to 0.5. And the action's execution is through the use of kinematic equations to calculate the next positions of the robot via inputting \(\omega_{l}\) and \(\omega_{r}\) (i.e., the angular velocity of left and right tracks). The definition of reward plays an important role in MDP, which is directly related to the training speed and the validity of the resulting policy. When arriving into the predefined acceptable area of subgoals, the robot gets a +10 scalar reward; \(d_{n}\) is the goal tolerance. If \(\widetilde{a}_{g}\) is more than 0, the reward function is \(-\widetilde{a}_{g}\), where \(\widetilde{a}_{g}\) is the absolute value of normalization of \(a_{g}\). Otherwise, the reward function is \(1-\widetilde{d}_{g}-\widetilde{a}_{g}\), where \(\widetilde{d}_{g}\) is the normalization of \(d_{g}\). In the OA MDP, state \(S_{i}\) (\(i\in(1,2,3\ldots,6)\)) denotes the reading of sensor \(i\). The range of \(S_{i}\) is \([0,5]\). The first three sensors belong to left-side sensors and the others belong to right-side sensors. The setting of action is the same as the SA MDP's. Because of complexities of the obstacle-avoiding process, in general, it is tempting to add prior experience into reward functions, but it may not improve the training effect, which is discussed in Section 3.4.3. To explore the effects of adding prior experience into reward functions, we designed two kinds of reward functions--concise reward and comparative value reward. The first is a simple reward function (i.e., colliding with obstacles means receiving \(-4\), otherwise 0).