# Fast Path Planning for Autonomous Ships in Restricted Waters
## 1 Introduction  
Planning with multiple target ships (TSs) is complicated by the need for constant adjustments of plans to consider the moving TSs and collision avoidance (CA) under the rules of the International Regulations for Preventing Collisions at Sea (COLREGS). Additionally, it is important to produce trajectories that avoid all static and dynamic obstacles in real time in order to comply with highly dynamic maritime environments. Therefore, a very fast and effective path-planning method is required to apply these requirements for autonomous ships. Some methods show great potential in solving multiship CA and path optimization, but they may be more time-consuming. For example, the computation time is at least a few seconds for the cooperative path planning (CPP) method [1, 2] and a trajectory base algorithm (TBA) [3] but over 200 s for the evolutionary algorithm (EA)-based approach [4] and the fuzzy logic (FL) method [5], and the computation time of these methods is significantly increased with the number of obstacles, which makes it difficult to achieve real-time navigation, especially for high-speed ships. Some studies assume that all TSs keep course and speed [3, 6, 7, 8] or take COLREGS-compliant maneuvers [4] during the path planning process. Once any TS performs changes of speed and/orcourse, even with a nonprotocol action, the original solution based on these algorithms might be invalid. A model predictive control (MPC) method can be used to handle multiple dynamic obstacles with random motions [9]. However, this method does not consider static obstacles and might take longer. The artificial potential field (APF) is a powerful method for path planning that is easy to construct, suitably fast for online planning, easily handles static and dynamic constraints, and applicable in the fields of mobile robots and unmanned surface vehicles (USVs) [10]. However, the main drawback of this method is the possibility of becoming trapped in local minima, including no passage through closely spaced obstacles, oscillations in narrow passages, trap situations in U-shaped obstacles, and the GNRON (goals non-reachable with obstacles nearby) problem [11]. APF-based methods [6; 12] can plan a collision-free path with static and/or dynamic obstacles and consider some key rules of COLREGS. However, [PERSON]'s method incorporates more than 200 fuzzy rules even for simple ship-to-ship encounter situations, which leads to overload in computation time. The CA action for this method is fixed to a right-hand turn regardless of the obstacle's mobility. [PERSON]'s algorithm addresses a complicated multiship encounter situation in the presence of some static obstacles, but local minima limitations do exist in this method. The own ship is obstructed by the obstacle and cannot reach the destination when the own ship, the destination, and the obstacle lie on the same line as the obstacle in the middle. Additionally, this method assumes that all TSs perform COLREGS-compliant behavior. No emergency scenarios or unforeseen circumstances are considered. [PERSON]'s method solves the above problems, but it is limited to avoiding point obstacles and cannot deal with irregular linear and surface obstacles [13]. [PERSON] et al. [14] achieved CA with static obstacles by constructing an adaptive artificial repulsive force field in a self-organizing map (SOM). This method needs to be improved by adding dynamic obstacle avoidance and considering COLREGS. Other APF-based methods for mobile robots path planning are valuable for autonomous ships, although they do not consider COLREGS. [PERSON] et al. [15] proposed a bacterial potential field (BPF) method, which combines the advantages of the APF and bacterial evolutionary algorithm (BEA) methods to ensure a feasible, optimal and safe path in a dynamic complex environment. However, the static and dynamic obstacles are both circle or point shapes, and the computation time is several seconds even in a very simple condition with only 2-3 static obstacles. [PERSON] et al.