# Fast Path Planning for Autonomous Ships in Restricted Waters
## 2 Materials and Methods
### Path Planning Methods
#### 2.3.1 Offline Path Planning for Static Obstacles  
In the offline phase, any artificial intelligence (AI) and soft computation method can be utilized to generate a safe and optimal path to the goal in the presence of only static obstacles. [PERSON]'s algorithm [PERSON] (1986), the fast marching method (FMM) [PERSON] (1986), and the line-of-sight (LOS) method have been used to produce a collision-free and optimal path in a complex environment. However, how to get the path is beyond the content of this paper. It is supposed that the optimal path in the static environment has been obtained. As a prior path, it generally includes a sequence of subgoals or waypoints (WPTs), which is the same as the passage planning on charts undertaken by the bridge team of a vessel. Then, the offline prior path is applied during the online decision-making phase by computing the attractive forces with successive subgoals (WPTs) to guide the USV to the destination unless there is a dynamic obstacle.  
Due to the dynamic environment, it is difficult and impractical for a vessel to sail exactly along the prior path and reach every waypoint. At present, one of the most commonly used methods is to set a circle-of-acceptance (COA) around each waypoint that flags the arrival of the ship at each one [PERSON] (1986); [PERSON] (1986), except the start and end points. As shown in Figure 7, for example, the prior path is composed of 3 WPTs (WPT\({}_{\text{k}-1-\text{k}+1}\)) and two legs (L\({}_{\text{k}-1}\) and L\({}_{\text{k}}\)), and the radius of the COA for WPT\({}_{\text{k}}\) is \(r_{k}\). When the distance between the own ship and WPT\({}_{\text{k}}\) (\(d_{k}\)) _is_ less than or equal to \(r_{k}\), i.e., the own ship enters the COA of this waypoint (see positions D, E and H), the mission planner selects the next waypoint WPT\({}_{\text{k}+1}\), and the own ship is guided toward it. However, if the own ship (e.g., at position F) deviates largely near the WPT due to CA actions with other vessels, the \(d_{k}\) is always larger than \(r_{k}\), which leads to the failure to complete the leg switch automatically.  
In this paper, as a supplementary term to the COA method, a criterion regarding the angular bisector of the angle (\(\alpha\)) between the consecutive legs (abbreviated to angular bisector method) is introduced to complete the path leg switch automatically. Before the own ship crosses the angular bisector or the COA (see Figure 7 at positions A, B, and C), the path planning calculations are carried out with reference to leg L\({}_{\text{k}-1}\) and subgoal (WPT\({}_{\text{k}}\)), i.e., the end point of L\({}_{\text{k}-1}\). When the own ship is passing or has passed the angular bisector (at positions F and G), or enters the COA of the WPT\({}_{\text{k}}\) (at positions D, E and H), the current path leg becomes L\({}_{\text{k}}\), and the path planning calculations should be based on WPT\({}_{\text{k}+1}\) instead of WPT\({}_{\text{k}}\).  
Figure 6: Typical encounters illustration: (**a**) overtaking, (**b**) Head-on, (**c**) crossing A and (**d**) crossing B and the corresponding Rules in COLREGS.  
It should be noted that judging whether the own ship has reached the goal or not is still based on the range between the goal and the own ship position; if \(d_{g}\leq r_{g}\) is true, the own ship is considered to have reached the goal.  
The prior path-guided process and the automatic selection of waypoints can reduce the risk of trapping the potential function in local minima, optimize the path globally, and extend the application of the APF method to long-distance navigation with many waypoints.