## 3 Improved A-Star Algorithm
### A-Star Algorithm Considering Risk Models
#### 3.2.3 Combined Path Generation of Vessels
\begin{table}
\begin{tabular}{l l} \hline \hline
**Parameters** & **Value** \\ \hline node range of \(x\) axis & \([1,38]\) \\ node range of \(y\) axis & \([1,25]\) \\ grid length \(l_{\pi}\) & 30 m \\ minimum radius of vessel \(R_{0}\) & 27 m \\ \(\alpha\) & 100 \\ \(\tau\) & 0.2 \\ \(\beta\) & 0.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Parameter initialization. Figure 8: Normal path generation with a traditional A-Star algorithm and an improved A-Star algorithm for vessels (The definition of the graphic symbols in this figure is the same as the definition in Figure 7). ### Case 2: Berthing Path Planning

#### 4.2.1 Setup

As previously mentioned, a vessel should berth into the current when the vessel needs to anchor or berth at a port. In this case, the vessel starts from the node of \(N\left[start\right]\left(6,3\right)\) to the port whose node is \(N\left[dest\right]\left(32,21\right)\). The node number of berthing path \(P_{b}\) is set to 6. The other parameters are the same as Table 1. The performance of the berthing path planning is presented as Figure 9.

#### 4.2.2 Results

In Figure 9, the path generated by the A-Star algorithm without considering the berthing path is hard to berth to the port because the vessel cannot be manipulated well if the current direction is consistent with the vessel sailing direction. When the berthing procedure is taken into account, the berthing path \(P_{b}\) and the berthing node \(N\left[berth\right]\) are obtained firstly according to Algorithm 3, specifically, the coordinates of \(N\left[berth\right]\) are \(\left(37,18\right)\). Then, the normal path \(P_{n}\) can be generated with the destination node \(N\left[dest\right]=N\left[berth\right]\). Finally, \(P_{n}\) and \(P_{b}\) are combined to become the complete path \(P_{c}\). ### Case 3: Combined Path Planning

#### 4.3.1 Setup

When combining normal path \(P_{n}\) and berthing path \(P_{b}\), a sharp turn could encounter in the combination node, which will result in that the vessel cannot track the path because of the restriction of vessel's manoeuvrability. In this case, the vessel needs to berth in an anchorage from node \(\left(10.11\right)\) to node \(\left(17,13\right)\). The parameters are the same as Table 1 except the node range of \(x\) axis changes to 28. The comparison of path planning with considering smoothing the path or without considering smoothing the path is presented in Figure 10.

Figure 9: Berthing path generation with an improved A-Star algorithm considering berthing and an A-Star algorithm not considering berthing for vessels (The definition of the graphic symbols in this figure is the same as the definition in Figure 7). #### 4.3.2 Results

As shown in Figure 10, a sharp turn appears when smoothing the path is not considered. The sharp turn is eliminated when the smoothing strategy denoted by Algorithm 4 is applied. When the number of candidates for the added node are more than one, a candidate node with the least risk \(r_{\mathit{add}}\) defined in Algorithm 4 is selected. ### Case 4: Path Planning in Real Scenario

A real scenario, Wuhan waterway in Yangtze River, is selected to verify the effectiveness of the improved A-Star method in this case. In this scenario, a vessel is planned to navigate from one side of the river to the other side of the river in a bridge zone, which is shown in Figure 11. The navigable area for crossing bridge is indicated by the two beacon vessels, i.e., the middle area between the beacon vessel is navigable. To apply the proposed path planning method, the grid length, \(ln\), is set as 50 m, and the minimum radius of vessel, \(R_{0}\), is set as 45 m. The latitude and longitude coordinates of the start point is (\(30\lx@math@degree 36\lx@math@degree 02.6\lx@math@degree 7\lx@math@degree\)N, \(114\lx@math@degree 19\lx@degree 23.4\lx@math@degree\)E), and the latitude and longitude coordinates of the destination point is (\(30\lx@math@degree 37\lx@degree 35.9\lx@math@degree 7\lx@degree\)N, \(114\lx@degree 19\lx@degree 36.0\lx@degree\)E).