## 3 Improved A-Star Algorithm
### A-Star Algorithm Considering Risk Models
#### 3.2.2 Berthing Path Generation of Vessels  
As previously mentioned, when the destination node is the berthing one, a specific path planning rule should be obeyed in order to guarantee the safety of vessels. The algorithm of generating berthing path \(P_{b}\) described in Section 2.3 is presented in Algorithm 3, in which \(N\left[berth\right]\) is the starting node of \(P_{b}\).  
The evaluation function for berthing path generation, \(f_{b}\left(N\left[i\right]\right)\), is defined as:  
\[f_{b}\left(N\left[i\right]\right)=g_{b}\left(N\left[i\right]\right)+\beta_{b} h_{b}\left(N\left[i\right]\right), \tag{15}\]  
where \(\beta_{b}>0\) is a constant coefficient. \(h_{b}\left(N\left[i\right]\right)=0\) at any time since the destination node is not known before the berthing path generation finishes. \(g_{b}\left(N\left[i\right]\right)\) is as follows:  
\[g_{b}\left(N\left[i\right]\right)=g\left(N\left[i\right]\right)+\tau_{b}r_{b} \left(N\left[i\right]\right), \tag{16}\]  
where \(g\left(N\left[i\right]\right)=0\) at any time, \(\tau_{b}>0\) is a constant coefficient. \(r_{b}\left(N\left[i\right]\right)\) is as follows:  
\[r_{b}\left(N\left[i\right]\right)=r_{o}\left[i\right]+r_{be}\left[i\right]+r_{ m}\left[i\right]. \tag{17}\]  
Please note that the traffic separation rule is not considered for the berthing path generation, i.e., \(r_{s}=0\) at any time, because a vessel in the berthing process always finds the path that is against the current ignoring the traffic separation rule temporarily.  
Combining (15), (16) and (17), \(f_{b}\left(N\left[i\right]\right)\) can be denoted as:  
\[f_{b}\left(N\left[i\right]\right)=r_{o}\left[i\right]+r_{be}\left[i\right]+r_{m} \left[i\right]. \tag{18}\]  
Please note that \(\tau_{b}=1\) and \(\beta_{b}=1\) are both eliminated in (18) since \(g\left(N\left[i\right]\right)\) and \(h_{b}\left(N\left[i\right]\right)\) are constant to 0.  
```
1:Mark \(N\left[dest\right]\) as \(\mathit{openlist}\).
2:if the destination node is the berthing one then
3: Set the predefined number of berthing path nodes as \(q_{0}\).
4:while\(\mathit{openlist}\
eq\varnothing\)do
5: Select the open node \(N\left[i\right]\) whose value of evaluation function \(f_{b}\left(N\left[i\right]\right)\) is smallest.
6: Set \(N\left[i\right]\) as the berth node and \(N\left[i\right]\to N\left[dest\right]\) as the berth path \(P_{b}\). Count the number of the path \(P_{b}\) nodes, which is denoted as \(q_{b}\).
7:if\(q_{b}>=q_{0}\)then
8: \"path \(P_{b}\) is found\".
9:else
10: Mark \(N\left[i\right]\) as \(\mathit{closelist}\).
11:if Successor \(N_{i}\left[j\right]\) of node \(N\left[i\right]\) does not belong to \(\mathit{closelist}\) or \(\mathit{obstacle}\) node then
12: Mark \(N_{i}\left[j\right]\) as \(\mathit{openlist}\).
13: Calculate \(r_{o}\left[j\right]\), \(r_{be}\left[j\right]\) and \(r_{m}\left[j\right]\) by (3), (4) and (7), respectively. Then, \(r_{b}\left(N_{i}\left[j\right]\right)=r_{o}\left[j\right]+r_{be}\left[j\right] +r_{m}\left[j\right]\).
14:if\(N_{i}\left[j\right]\) belongs to \(\mathit{openlist}\) and \(f_{b}\left(N_{i}\left[j\right]\right)\) is smaller than \(f_{b}\left(N_{m}\left[j\right]\right)\) when \(N\left[m\right]\) was marked as \(\mathit{closelist}\)then
15:\(f_{b}\left(N\left[j\right]\right)=f_{b}\left(N_{i}\left[j\right]\right)\) and \(N\left[j\right].\mathit{parent}=N\left[i\right]\).
16:endif
17:endif
18:endif
19:endwhile
20:return \"path \(P_{b}\) is not found\".
21:endif
```  
**Algorithm 3** Berthing path generation algorithm (\(N\left[\mathit{berth}\right]\to N\left[dest\right]\))