## 2 Path Planning Algorithm Based on the Markov Decision Process (MDP)
### Markov Reward Function  
Except for the terrains, as usually considered for land-based robots, the ocean current is an important factor for underwater navigation because its magnitude is in the same order as the cruising speed of the AUV. In this paper, we assume that the AUV moves at a constant cruising speed \(v_{1}\) = 0.5 m/s (1 knot). If the ocean current is \(\mathbf{v_{2}}\), the absolute velocity of AUV is the vector sum of \(\mathbf{v_{1}}+\mathbf{v_{2}}\). The actual trajectory is along the direction of action \(a\). If \(\mathbf{n^{a}}\) is used to represent the unit vector along the direction of action \(a\), the \begin{table}
\begin{tabular}{c c} \hline \hline
**Action Number** & **Action** \\ \hline
1 & 15\(\rightarrow\)17 \\
2 & 15\(\rightarrow\)14 \\
3 & 15\(\rightarrow\)11 \\
4 & 15\(\rightarrow\)18 \\
5 & 15\(\rightarrow\)15 \\
6 & 15\(\rightarrow\)12 \\
7 & 15\(\rightarrow\)19 \\
8 & 15\(\rightarrow\)16 \\
9 & 15\(\rightarrow\)13 \\
10 & 15\(\rightarrow\)5 \\
11 & 15\(\rightarrow\)25 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The action set partitioning in the 3D space. Figure 1: The numbers in each grid indicate the different states, and the vectors represent the actions for the 2D case. Figure 2: Same as Figure 1, but for the 3D case. absolute speed of AUV is \((\mathbf{v_{1}}+\mathbf{v_{2}})\cdot\mathbf{n}^{a}\). In the 2D case, the distance \(L\) for the AUV to travel from the present to successor grid is:  
\[L=\left\{ \begin{array}{l}0.5d\text{ if }a=\text{ action }5\\ d\text{ if }a=\text{ action }2,4,6,8.\\ 1.4d\text{ if }a=\text{ action }1,3,7,9\end{array} \right. \tag{8}\]  
Here, \(d\) is the grid size. In the 3D case:  
\[L=\left\{ \begin{array}{l}0.5d\text{ if }a=\text{ action }5\\ d\text{ if }a=\text{ action }2,4,6,8\\ 1.4d\text{ if }a=\text{ action }1,3,7,9\\ 0.02d\text{ if }a=\text{ action }10,11\end{array} \right. \tag{9}\]  
Thus, it takes \(L/(\mathbf{v_{1}}+\mathbf{v_{2}})\cdot\mathbf{n}^{a}\) for the AUV to move from one grid to its adjacent grid through taking the action \(a\). The goal of the MDP algorithm is to find the optimal path to maximize the total reward expectation. Here, we focus on time-optimal path planning, so we set the reward function as a function of travel time. The principle of the reward function is that the shorter the travel time between grids, the larger the corresponding reward function. A parameter \(R_{S}\) is then defined. To make sure that the reward function decreases with each step, \(R_{S}\) is \(-1\) in each grid except for when the grid is the target or includes an obstacle. In order to obtain the maximum reward in the target grid, \(R_{S}\) is set to be a large positive number, whose magnitude is in the same order as the total grid number, for instance, \(R_{S}=+1000\) in our case. In this way, the algorithm can make the AUV reach the target as soon as possible and also avoid detours around the target. While in the obstacle grid, \(R_{S}\)= \(-1000\) to prevent the AUV from reaching this grid. The reward function is designed as:  
\[R_{S}^{ac}=\left[\frac{wL}{(\mathbf{v_{1}}+\mathbf{v_{2}})\cdot\mathbf{n}^{a}} \right]R_{S}, \tag{10}\]  
which represents the reward for the AUV to take an action \(a\) in the present state \(s\). Here, \(w\) is the weight coefficient. The superscript \(ac\) represents considering the influence of ocean currents. \(R_{S}^{a}\) will be used to represent the reward function without ocean currents. The reward function (10) is always greater for the AUV moving along the current than against it, so the AUV prefers to move along the current to achieve an optimal path. However, it is not necessary to require the optimal path to be along the ocean current because the MDP only requires the total reward function (3) to reach its maximum. Since the vertical current is usually too weak to affect the AUV's speed, the reward function \(R_{S}^{ac}\) is the same for both 2D and 3D cases. The cruising velocity \(\mathbf{v_{1}}\) of the AUV is assumed to be constant.