## 3 Improved A-Star Algorithm
### A-Star Algorithm Considering Risk Models
#### 3.2.3 Combined Path Generation of Vessels  
In most of path planning scenarios, the normal path and the berthing path both need to be generated. Therefore, it should be considered that how to combine the normal path and the berthing path. The main problem is that the manoeuvrability risk \(r_{m}\left[m\right]\) defined in (7) could be high, which will increase the risk of collision or stranding when the connection node of the normal path and the berthing path is inappropriate. For instance, in Figure 6, the sharp turn could not be tracked well by the vessel. The distance between two adjacent nodes, \(l_{n}\), is usually relevant to the minimum radius of the vessel, \(R_{0}\). In this article, we set \(l_{n}=R_{0}\). The combined path \(P_{c}\) consists of the normal path \(P_{n}\) and the berthing path \(P_{b}\), i.e., \(P_{c}=P_{n}+P_{b}\). To avoid a sharp turn at node \(N\left[\mathit{berth}\right]\), i.e., \(R_{0}>R_{berth}\), where \(N\left[\mathit{berth}\right]\) is the first node of \(P_{b}\), a new node can be added between \(N\left[\mathit{berth}\right]\) and the second node of \(P_{b}\). As shown in Figure 7, a node is added to eliminate the sharp turn and make the generated path smooth enough be followed. The algorithm of adding node or smoothing the combined path is denoted in Algorithm 4. ```
1: Define the last node and the last but one node of \(P_{n}=\left\{N\left[n1\right],...,N\left[ne\right],N\left[berth\right]\right\}\) as \(N\left[berth\right]\) and \(N\left[be\right]\) respectively, and define the second node of \(P_{b}=\left\{N\left[berth\right],N\left[b1\right],...\right\}\) as \(N\left[b1\right]\), which is shown in Figure 7.
2: Calculate \(r_{m}\left[berth\right]\) by (7). 3:if\(r_{m}\left[berth\right]==0\)then
4:return \"added node does not need. \"
5:endif
6:if\(r_{m}\left[berth\right]>0\)then
7: The turn of \(N\left[ne\right]\to N\left[berth\right]\to N\left[b1\right]\) is too sharp to track by the vessel. 8: Try to find a node from eight neighbourhood of \(N_{berth}\) except node \(N\left[b1\right]\) and node \(N\left[ne\right]\) that will be added to \(P_{b}\). The coordinates of \(N\left[berth\right]\) is denoted as \(\left(x_{N\left[berth\right]},y_{N\left[berth\right]}\right)\). 9:\(count=0\). 10:for\(i=-1:1\)do
11:for\(j=-1:1\)do
12: A candidate node \(N\left[c\right]\left(x_{N\left[berth\right]}+i,y_{N\left[berth\right]}+j\right)\) is selected to be verified. 13:if\(N\left[c\right]\
eq N\left[berth\right]\) and \(N\left[c\right]\
eq N\left[b1\right]\) and \(N\left[c\right]\) is not an obstacle node and \(N\left[c\right]\) is not beyond the boundary of the grid map. then
14: Calculate \(r_{m1}\left[c\right]\) of \(N\left[berth\right]\to N\left[c\right]\to N\left[b1\right]\) and \(r_{m1}\left[berth\right]\) of \(N\left[ne\right]\to N\left[berth\right]\to N\left[c\right]\) by (7). 15: Calculate \(r_{m2}\left[c\right]\) of \(N\left[c\right]\to N\left[berth\right]\to N\left[b1\right]\) and \(r_{m2}\left[berth\right]\) of \(N\left[ne\right]\to N\left[c\right]\to N\left[berth\right]\) by (7). 16:if\(r_{m1(2)}\left[c\right]==0\) and \(r_{m1(2)}\left[berth\right]==0\)then
17: Add \(N\left[c\right]\left(x_{N\left[berth\right]}+i,y_{N\left[berth\right]}+j\right)\) to \(addodelist\). 18: Calculate the danger risk \(r_{add}\left[c\right]=r_{m1(2)}\left[c\right]+r_{o1(2)}\left[c\right]\), where \(r_{o1(2)}\left[c\right]\) is calculated by (3). 19:\(f_{add}\left[c\right]=1(2)\) and add \(f_{add}\left[c\right]\) to \(flaglist\). 20:\(count=count+1\). 21:endif
22:endif
23:endif
24:endfor
25:if\(count>0\)then
26: Obtain the danger risk list \(r_{add}\left[c_{n}\right]=r_{m}\left[c_{n}\right]+r_{o}\left[c_{n}\right]\) for node list \(N\left[c_{n}\right]\left(n=1,2,...,count\right)\). 27: Select the node with the smallest value of \(r_{add}\) from \(r_{add}\left[c_{n}\right]\left(n=1,2,...,count\right)\), i.e., \(N\left[c_{\min}\right]\), and set \(N\left[add\right]=N\left[c_{\min}\right]\).