## 3 Improved A-Star Algorithm
### A-Star Algorithm Considering Risk Models
#### 3.2.3 Combined Path Generation of Vessels
28:if\(f_{add}\left[c_{\min}\right]==1\)then
29: Change \(P_{b}\) to \(P_{b}^{\prime}=\left\{N\left[berth\right],N\left[add\right],N\left[b1\right],...\right\}\) and \(P_{c}=P_{n}+P_{b}^{\prime}\). 30:else
31: Change \(P_{n}\) to \(P_{n}^{\prime}=\left\{N\left[n1\right],...,N\left[add\right],N\left[berth \right]\right\}\) and \(P_{c}=P_{n}^{\prime}+P_{b}\). 32:endif
33:return \"added node is found. \"
34:else
35:return \"added node cannot be found. \"
36:endif
37:endif

## 4 Case Study

To verify the effectiveness of the proposed improved A-Star path planning method, simulation experiments are conducted in this section. Firstly, a normal path is generated by the proposed A-Star algorithm in consideration of obstacle, traffic separation and manoeuvrability risk, and the performance of path planning is compared between the proposed A-Star method and traditional A-Star method. Then, the berthing path planning is realized by the proposed A-Star algorithm, and the berthing path is evaluated. The combination of the normal path and the berthing path is conducted by the proposed A-Star algorithm and the performance of the combined path is compared with the uncombined path. Finally, the proposed improved A-Star method is used to generate the path in a real scenario in Yangtze waterway. ### Case 1: Normal Path Planning

During the normal path planning, the obstacle risk and the manoeuvrability restriction risk are always considered, and it depends on the traffic rule that whether the traffic separation risk is considered or not. In this case, all these types of risks are all taken into consideration. #### 4.1.1 Setup

To model the obstacle risk, related model parameters need to be determined. It is known that the current velocity near the shore is smaller than one far away from the shore. Hence, \(v_{m}\left(\mathrm{m}/\mathrm{s}\right)\) at node \(N\left[m\right]\) is set as:

\[v_{m}= \begin{cases}0.4d_{s},d_{s}\leq 4l_{n}\\ 2,d_{s}>4l_{n}\end{cases} , \tag{19}\]

where \(d_{s}\left(\mathrm{m}\right)\) is the vertical distance from node \(N\left[m\right]\) to the nearest shore node. Other parameters are shown in Table 1. The vessel starts from the start node \(N\left[start\right]\left(3,3\right)\) to the destination node \(\left(32,21\right)\). Figure 6: The combined path with a sharp turn

Figure 7: The combined path to deal with a sharp turn. #### 4.1.2 Results

The normal path generation performance with a traditional A-Star algorithm and an improved A-Star algorithm for vessels is shown in Figure 8. From Figure 8, it can be seen that the traditional A-Star algorithm generates the optimal path only by taking the shortest path length as the standard. On the contrary, the improved A-Star algorithm considers the path length, obstacle risk, the traffic separation rule and manoeuvrability restriction simultaneously. Specifically, the path length of the traditional A-Star algorithm and the improved A-Star algorithm is 34.0 and 38.1, respectively. Generally, the improved A-Star algorithm will generate a longer path than the traditional A-Star algorithm. The sum of path node obstacle risk for the traditional A-Star algorithm and the improved A-Star algorithm is 150 and 22, respectively. The path generated by the traditional A-Star algorithm has much higher risk to collide with obstacles. For instance, the vessel is too close to the bridge piers and other vessels, which could increase the collision risks enormously in Figure 8.

The path generated by the improved A-Star algorithm has taken into account the traffic separation rule, which decreases the risk of collision with other navigating vessels. Moreover, the manoeuvrability risk is also considered in the improved A-Star algorithm to avoid the vessel failing to track the generated path. In summary, the improved A-Star algorithm can improve the navigating safety with slightly increasing the path length.