# Fast Path Planning for Autonomous Ships in Restricted Waters
## 2 Materials and Methods
### Path Planning Methods
#### 2.3.2 Online Path Planning in Dynamic Environment  
The CA decision making for autonomous ships is a complex system that is constrained by COLREGS and should cope with the dynamic environment in real time. The authors have done some work in this field [13]. By considering Rules 13\(\sim\)17 of COLREGS, the CA action scope is divided into four regions, safe zone, negotiation CA zone, emergency CA zone and prohibited zone, according to the checking criterion of collision risk and the checking range (CR) of collision risk. Based on the calculation of repulsive forces under different conditions, a real-time path planning method for static obstacles, dynamic obstacles and an emergency CA module is proposed. The detailed formulas of this algorithm can be referred to in that paper. In this paper, we first find that an emergency CA module can be improved by adding a key prerequisite. The checking criterion of collision risk (\(\theta<\theta_{m}\)) is no longer applicable once the condition \(d\leq dm\) is true. As shown in Figure 8, d is the distance between the own ship and any TS, \(d_{m}=R_{os}\)\(+\)\(d_{safe}+\)\(R_{ts}\), \(R_{os}\) and \(R_{ts}\) represent the domain radius of the own ship and TS, respectively, and \(d_{safe}\) is determined by the sea room, position sensor errors, and relative speed of the own ship and TS in one time step. The angle \(\theta_{m}\) does not exist when the own ship position O is in the circle with center T (the position of the TS) and radius \(d_{m}\). In the original algorithm, the condition of emergency CA action for close-range obstacles only has the distance limit \(d\leq d_{m}\). This condition makes the algorithm calculate the repulsive force for the TSs which have no collision risk with the own ship in this range and, therefore, take unnecessary CA actions. Taking the purple TS\({}^{\prime}\) in Figure 8 as an example, it has a smaller distance (less than \(d_{m}\)) from the own ship and is moving away from the own ship. It is obvious that there is no collision risk in this situation, and no necessary CA actions should be taken by the own ship. Figure 7: Waypoint (WPT) selection algorithm for offline path planning. Therefore, the algorithm of emergency CA is further improved by adding the judgment about collision risk in this paper. The traditional method for judging collision risk, i.e., the combination of DCPA (distance to the closest point of approach) and TCPA (time to the closest point of approach), is applied in this paper. As shown in Figure 8, DCPA = OP, TCPA = PT/ \(\rm{v_{to}}\)!, and then the prerequisites are written as DCPA \(\leq\) D\({}_{A}\) and 0 \(\leq\) TCPA \(\leq\) T\({}_{A}\), where D\({}_{A}\) and T\({}_{A}\) are the limit values determined for the particular sea area [25], which is dependent on the ship's maneuverability, scale, and visibility, and can be configured by an operator. Second, the proposed method in the authors' previous work [13] can only handle circle-shaped static obstacles. In fact, there may be many static obstacles of various shapes and characteristics surrounding the operational waters of autonomous ships. By using the static environment modeling method described in Section 2.1.1, the potential fields of restricted areas where many static obstacles coexist can be calculated. The higher the potential value (maximum 1) is, the more dangerous it is; the lower the potential value is (minimum 0), the safer it is. Autonomous ships are not allowed to cross or be too close to any static obstacle. Therefore, a minimal potential value \(\lambda\) (e.g., \(\lambda=0.001\)) may be selected according to the safety requirement, draft, maneuverability and cargo loading condition of the autonomous ship. As shown in Figure 9, the potential value at the blue boundary of a face obstacle is \(\lambda\). The potential value is more than \(\lambda\) within this boundary and less than \(\lambda\) outside this boundary.