# Fast Path Planning for Autonomous Ships in Restricted Waters
## 2 Materials and Methods
### Environment Modeling
#### 2.1.1 Static Environment Modeling  
For an isolated point obstacle in the 2D plane, the artificial potential field at any location \(p(x,y)\) can be written as:  
\[f_{point}(p_{i})=\mathrm{e}^{-\beta_{i}\cdot[(x-x_{i})^{2}+(y-y_{i})^{2}]}, \tag{1}\]  
where \(f_{point}(p_{i})\) is the potential field function of the \(i\)-th point object in position \(p_{i}(x_{i},y_{i})\), \(\beta_{i}\) is a positive scalar, and \(f_{point}(p_{i})\) is a decreasing function of \(\beta_{i}\). The larger the value of \(\beta_{i}\) is, the faster vanishing and tighter \(f_{point}(p_{i})\). When \(p=p_{i}\), the potential will reach the maximum value 1. The larger the distance between the own ship and the point obstacle is, the smaller the effect of the obstacle. This effect approaches 0 at places far away from the obstacle. If there are M (M \(\in\) N+) point obstacles, the total potential field \(f_{point}(p)\) can be found by:  
\[f_{point}(p)=\sum_{i=1}^{\mathrm{M}}f_{point}(p_{i}), \tag{2}\]  
Figure 1 shows the total potential field for the two point obstacles \(p_{1}\)(1, 5) and \(p_{2}\)(3, 3) with different values of parameter \(\beta\) (\(\beta_{1}=10\) and \(\beta_{2}=1\)). For an obstacle in the form of a curve or line \(c=\phi(p)\), the potential field is expressed by the generalized Sigmoid function of \(c\)[18]:  
\[f_{\mathrm{curve}}(c)=\frac{1}{1+\mathrm{e}^{-\gamma f(c)}}, \tag{3}\]  
where \(\gamma\) is a positive parameter that is used to adjust the range of influence for the curve obstacle. A small \(\gamma\) leads to a large influence range of an obstacle, but a larger \(\gamma\) makes the influence range of an obstacle smaller. The potential value is 0.5 when the point \(p(x,y)\) is exactly on the curve, i.e., \(c=0\). When \(c>0\), the potential value is larger, and the maximum is 1. If \(c<0\), the potential value is smaller, and the minimum value is 0 (far enough from the curve that \(c=0\)). As shown in Figure 2a, based on the coding direction of the curve, the left face of the curve has high potential due to condition \(c>0\), and the right face is a low potential area due to condition \(c<0\). The potential field surface for a curve \(c\) of \(-5x^{3}+10x^{2}+x+10y-7=0\) when \(\gamma=0.5\) is presented in Figure 2b. \begin{table}
\begin{tabular}{c c} \hline \hline
**Vector Format** & **Represented Obstacles (Including but not Limited to)** \\ \hline point & isolated reefs, wrecks, navigational aids, etc. \\ curve (line) & safety contours, channel limits, etc. \\ surface (face) & boundaries of bigger obstacles, other natural and cultural areas, etc. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Spatial vector data in the electronic navigational chart (ENC). The potential is larger when \(p(x\),\(y)\) is on the left face of the curve (\(c>0\)), and it is smaller when \(p(x\),\(y)\) is on the right face of the curve (\(c<0\)) based on the coding direction of the curve. The area with a very low potential value is navigable for ships. A face (or surface) obstacle consists of \(n\) (n \(\in\) N+) curves that are connected at adjacent nodes and expressed by some implicit functions. The \(j\)-th curve is represented by \(c=\phi_{j}\) (\(p\)). The potential field of the face obstacle \(f_{face}(p)\) can be expressed as the product of the Sigmoid function of these curves. \[f_{face}(p)=\prod_{j=1}^{n}f_{curve}(\phi_{j}(p)), \tag{4}\]  
Because any shape can be associated with an implicit function, the selected potential model can make a general representation of obstacles with arbitrary shapes. As shown in Figure 3, according to the counterclockwise coding direction of adjacent nodes, the left faces of the \(n\) lines (including curves) have high potential, which constructs a face-shaped obstacle. It should be noted that formula (4) cannot deal with concave polygons that are totally composed of straight lines. However, we can construct concave polygons in the following ways:  
First, the two straight lines forming a concave shape, are replaced by a curve (see Figure 3).