## 3 Numerical Simulations
### Path Planning without Ocean Current: Comparison between the MDP and A* Algorithms  
The A* algorithm is a globally optimal algorithm widely used in robotic path planning. It uses two lists to store information, i.e., an open list, recording all the blocks that are considered to search for the shortest path, and a closed list for recording all the blocks that will not be considered again. The purpose of the A* algorithm is to find the shortest path length \(f=g+h\)[30], in which \(g\) is the distance that the robot has already traveled, and \(h\) is the distance that the robot will travel to arrive at the target. The running time and shortest path length calculated using the MDP and A* algorithms are compared and shown in Table 4. Since the ocean currents are not considered, the shortest optimal path is equivalent to the shortest travel time.  
Figure 5: The comparison of the optimal paths for different spatial resolutions. The thick black lines are the optimal paths predicted by the MDP algorithm. The triangles indicate the starting point, and the squares are the target. The grid size of 2000 m is used for the top panels, 1000 m for the middle, and 200 m for the bottom. The left, middle and right panels represent Case 1, 2, and 3, respectively.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Grid Size (m)**} & \multirow{2}{*}{**Grid Number**} & \multicolumn{2}{c}{**Case 1**} & \multicolumn{2}{c}{**Case 2**} & \multicolumn{2}{c}{**Case 3**} \\ \cline{3-8}  & & **CPU Time (s)** & **Path Length (m)** & **CPU Time (s)** & **Path Length (m)** & **CPU Time (s)** & **Path Length (m)** \\ \hline
2000 & 386 & 4.5156 & 3.4000 \(\times\) 10\({}^{4}\) & 3.5781 & 4.8770 \(\times\) 10\({}^{4}\) & 3.5000 & 4.7314 \(\times\) 10\({}^{4}\) \\
1000 & 1591 & 184.5960 & 3.4000 \(\times\) 10\({}^{4}\) & 212.7386 & 4.7598 \(\times\) 10\({}^{4}\) & 205.2193 & 4.6142 \(\times\) 10\({}^{4}\) \\
200 & 37928 & 5.3942 \(\times\) 10\({}^{4}\) & 3.4000 \(\times\) 10\({}^{4}\) & 4.6778 \(\times\) 10\({}^{4}\) & 4.6778 \(\times\) 10\({}^{4}\) & 6.7776 \(\times\) 10\({}^{4}\) & 4.4874 \(\times\) 10\({}^{4}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Algorithm performances for different spatial resolutions.  
As shown in Figure 6 and Table 4, the output of the optimal path from the A* and MDP algorithm is the same in Case 1, while they are reduced by 8.76% in Case 2 and 10.67% in Case 3 if the MDP algorithm is used compared with the A* algorithm. If an obstacle inside a grid is not in the direction of an action, this action can still be taken using the MDP algorithm, but not the A* algorithm. Therefore, the feasible domains for the AUV cruising in the MDP algorithm are actually more than the A* algorithm so that the MDP method may achieve a shorter distance. It is also noticed that the CPU time that the MDP method costs is almost 20 times of that using the A* method. It may not be a significant problem in practical deployments because it usually takes hours or even longer for the AUV to travel to the target, considering the spatial scale of the ocean. Nevertheless, a 10% path length reduction can save even more energy than the CPU energy cost in seconds.  
The MDP algorithm is more robust because it calculates the optimal paths from any point to the target, while the A* algorithm only outputs an optimal path from the starting point to the target. Even though the running time of the MDP algorithm is longer than the A* algorithm, it does not significantly affect the practical AUV path planning.