## 3 Improved A-Star Algorithm
### A-Star Algorithm Considering Risk Models
#### 3.2.1 Normal Path Generation of Vessels  
To satisfy the requirements of considering risks for vessel path planning, model (8) needs to be modified. Here, \(g\left(N\left[i\right]\right)\) is redesigned as:  
\[g_{n}\left(N\left[i\right]\right)=g\left(N\left[i\right]\right)+\tau_{n}r_{n} \left(N\left[i\right]\right), \tag{9}\]  
where \(g_{n}\left(N\left[i\right]\right)\) is the newly defined cost of the path from \(N\left[start\right]\) to \(N\left[i\right]\). \(\tau_{n}>0\) is a constant coefficient. \(g\left(N\left[i\right]\right)\) is defined as:  
\[g\left(N\left[i\right]\right)=\sum_{k=1}^{p-1}d\left(k\right), \tag{10}\]  
where \(p\geq 1\) is the node amount from \(N\left[i\right]\) to \(N\left[start\right]\), i.e., \(N\left[i\right]\), \(N\left[i\right]\)._parent_, \(N\left[i\right]\)._parent_,..., \(N\left[start\right]\), in which \(N\)._parent_ represents the parent node of \(N\). \(d\left(k\right)\) is the Euclidean distance between \(k\)th node to \(\left(k+1\right)\)th node, where \(k\) stands for the node sequence from the start node. To be specific, assuming that the coordinates of \(k\)th node is \(\left(x_{k},y_{k}\right)\), then \(d\left(k\right)\) is as follows:  
\[d\left(k\right)=\sqrt{\left(x_{k}-x_{k+1}\right)^{2}+\left(y_{k}-y_{k+1} \right)^{2}}. \tag{11}\]  
\(r_{n}\left(N\left[i\right]\right)\) is the risk function, which is as follows:  
\[r_{n}\left(N\left[i\right]\right)=r_{o}\left[i\right]+r_{s}\left[i\right]+r_{ m}\left[i\right], \tag{12}\]  
where \(r_{o}\left[i\right]\), \(r_{s}\left[i\right]\) and \(r_{m}\left[i\right]\) are defined in Equations (3), (4) and (7), respectively. Please note that \(r_{s}=0\) if traffic separation rule is not carried out in certain waterway. A new evaluation function \(f_{n}\left(N\left[i\right]\right)\) is defined as:  
\[f_{n}\left(N\left[i\right]\right)=g_{n}\left(N\left[i\right]\right)+\beta_{n} h_{n}\left(N\left[i\right]\right), \tag{13}\]  
where \(\beta_{n}>0\) is a constant coefficient. In contrast with (8), \(\beta_{n}\) is added to balance the weight between \(g_{n}\left(N\left[i\right]\right)\) and \(h_{n}\left(N\left[i\right]\right)\). Assuming that the coordinates of \(N\left[i\right]\) are \(\left(x_{N\left[i\right]},y_{N\left[i\right]}\right)\) and the coordinates of \(N\left[dest\right]\) are \(\left(x_{N\left[dest\right]},y_{N\left[dest\right]}\right)\), then \(h_{n}\left(N\left[i\right]\right)\) is as follows:  
\[h_{n}\left(N\left[i\right]\right)=\sqrt{\left(x_{N\left[i\right]}-x_{N\left[ dest\right]}\right)^{2}+\left(y_{N\left[i\right]}-y_{N\left[dest\right]} \right)^{2}}. \tag{14}\]The proposed A-Star algorithm of the normal path generation is presented as Algorithm 2. ```
1:Mark \(N\left[start\right]\) as \(openlist\). 2:if the destination node is not the berthing one then
3:if traffic separation rule is not carried out then
4:\(r_{s}=0\) at any time. 5:endif
6:while\(openlist\
eq\varnothing\)do
7: Select the open node \(N\left[i\right]\) whose value of evaluation function \(f_{n}\left(N\left[i\right]\right)\) is smallest. 8:if\(N\left[i\right]=N\left[dest\right]\)then
9:return \"path \(P_{n}\) is found\". 10:else
11: Mark \(N\left[i\right]\) as \(closelist\). 12:if Successor \(N_{i}\left[j\right]\) of node \(N\left[i\right]\) does not belong to \(closelist\) or \(obstacle\) node then
13: Mark \(N_{i}\left[j\right]\) as \(openlist\). 14: Calculate \(r_{o}\left[j\right]\), \(r_{s}\left[j\right]\) and \(r_{m}\left[j\right]\) by (3), (4) and (7), respectively. Then, \(r_{n}\left(N_{i}\left[j\right]\right)=r_{o}\left[j\right]+r_{s}\left[j\right]+ r_{m}\left[j\right]\). 15:if\(N_{i}\left[j\right]\) belongs to \(openlist\) and \(f_{n}\left(N_{i}\left[j\right]\right)\) is smaller than \(f_{n}\left(N_{m}\left[j\right]\right)\) when \(N\left[m\right]\) was marked as \(closelist\)then
16:\(f_{n}\left(N\left[j\right]\right)=f_{n}\left(N_{i}\left[j\right]\right)\) and \(N\left[j\right].parent=N\left[i\right]\). 17:endif
18:endif
19:endif
20:endif
21:return \"path \(P_{n}\) is not found\".