## 1 Introduction  
Autonomous underwater vehicles (AUVs) are deployed in the ocean to carry out specific missions, such as ocean observations, target identification, etc., due to their excellent advantages in maneuverability. In order to complete the mission, the AUV is often required to move to a target location under some constraints, such as the shortest time, shortest distance, and least energy consumption. Avoiding risks or obstacles in the ocean is also required. Aiming at different constraints, relevant path planning algorithms are developed. In this paper, the time-optimal is prioritized. The path planning algorithms for mobile robots can be divided into two categories: discrete-grid-based and sampling-based planning algorithms [1]. The former one is established on a gridded map. For example, the A* algorithm is transformed from the Dijkstra algorithm by adding a heuristic cost to enhance the computational efficiency. The A* algorithm can be modified, aiming at speeding the convergence of the A* algorithm, such as with iterative deepening A*, lifelong planning A*, and bidirectional A* algorithms [2, 3], [PERSON] et al. [4] introduced an improved A* algorithm for generating the procedure of the normal path and berthing path when considering obstacles with currents and marine traffic. The sampling-based planning algorithm does not directly calculate global optimization on a gridded map. It uses the random scattering of particles on the map to extract map-assisted planning. The probabilistic roadmap [5] and rapidly-exploring random tree algorithms [6] are two typical examples. Recently, some clustering algorithms are also applied to path planning, for instance, the ant colony algorithm, genetic algorithm, etc. [7]. The level-set method is also an important branch of robotic path planning [8]. With the rapid development of artificial intelligence, reinforcement learning is applied to robotic path planning. [PERSON] et al. [9] presented an MDP-based planning method for a robot with wheels. In order to resolve the impact of their surrounding environment, [PERSON] et al. [10] modeled the robotic motion as a Markov process and proposed a probabilistic-model-checking method to seek the optimal path. [PERSON] [11] applied the object-oriented Markov decision process for indoor robots, which greatly simplifies the problem of the so-called \"curse of dimensionality\". It reduces the state spaces by making the MDP properties as objects. [PERSON] et al. [12] used a minimum expected risk planner and a risk-aware Markov decision process to improve the reliability and safety of AUV operation in coastal regions. Different from the land or air based robots, the AUVs have their special characters due to the underwater environment. 1. Low positioning accuracy and high positioning cost  
Land robots can directly acquire real-time positions through the global positioning system (GPS) with relatively high positioning accuracy (about 0.5 m [13]). Because of the absorption of electromagnetic waves by seawater, satellite signals cannot be directly received underwater by AUVs. Alternatively, the inertial navigation system (INS) is commonly used for underwater positioning. However, it is expensive while providing low positioning accuracy, which produces about 100 m errors after traveling by 1 km [14]. Its positioning error accumulates over time, which must be frequently calibrated for long-term underwater deployment. 2. Low cruising speed and high fault tolerance  
Compared with land or air based robots, the maximum speed of underwater robots is much slower, which ranges from about 3 to 10 knots [15]. Except in the harbors, marine traffic is limited. The marine morphology, such as the coastline, islands, and seamounts, is relatively fixed. Therefore, more tolerance is allowed for AUVs to tip or roll over in the ocean. 3. High impacts by the marine environment  
In the ocean, the current velocity, and the speed of AUVs are usually in the same order of magnitude.