## 2 Models
### Adaptive Heuristic Function and Segment Parallel A*(SPA*)  
As discussed in the introduction, traditional path planning algorithms have found it difficult to cope with long-distance planning tasks, multi-constraint conditions, and high-resolution data requirements. Based on \"The gridded path constraint model based on the IMO\" established in 2.1, this section introduces one of the two important improvements in this paper. The path planning in this paper defaults to the 8-direction mode. It can be seen in many articles that the directional mode based on the shape of the earth has a 16-direction model and a 48-direction model of ship route planning, which are all reasonable. However, in order to facilitate the demonstration of our model ideas, we chose the classic 8-direction model. First, we improve the heuristic function in A*. A* is developed based on Dijkstra. Its total cost function takes into account not only the current distance cost but also the predicted distance cost. The total cost function of A* in path planning is described by Equation (7). \[ \begin{aligned} & f(cell_{i})=g(cell_{i})+h(cell_{i}),\\ & i=1,2,\cdots,m,\end{aligned}  \tag{7}\]where, \(cell_{i}\) denotes the grid indexed as \(i\) on the grid map. \(g(cell_{i})\) denotes the actual distance cost from the starting grid to the current grid \(cell_{i}\). A* is a path with minimum \(\sum\limits_{i}f(cell_{i})\) by establishing the objective function of Equation (7). A* algorithm is very flexible and adaptable and can be designed with specific cost functions for different search tasks. \(h(cell_{i})\) is also known as the heuristic function. A* can only select a grid with the minimum total cost over all the grids expanded by the heuristic function. It can be said that it can determine the efficiency of the A* search and the performance of the path. Generally, \(h(cell_{i})\) is estimated using Euclidean distance as the following Equation (8). \[h(cell_{i})\triangleq h(x_{i},y_{i})=w\cdot\sqrt{\left(x_{i}-x_{g}\right)^{2} +\left(y_{i}-y_{g}\right)^{2}}, \tag{8}\]  
where, \((x_{i},y_{i})\) is the row and column coordinates of grid \(cell_{i}\); \(w\) is the weight factor that regulates the value of the heuristic function; \((x_{g},y_{g})\) is the row and column coordinates of the target grid. Now assume that \(h*(cell_{i})\) is the true cost of grid \(cell_{i}\) to the end grid. But in practice, it is unknowable because it is difficult to know exactly this value until the end point is reached. We can use Table 1 to outline the laws of the heuristic function. If the \"Condition\" column is satisfied for either grid \(cell_{i}\), then the conclusion of the \"Result\" column will be obtained. Create a grid map of a real scene as shown in Figure 2. The green color on the diagram represents the island and land, the blue color represents the navigable area, and the yellow color represents the grid points expanded by the algorithm. The red and purple grids represent the starting and ending points, respectively, and the red line represents the A* planning path. Since the risk values \(f_{1}\) and \(f_{2}\) are generally normalized to 0-1, the grid-to-grid distance is calculated using great circle sailing (GCS). In this paper, the data resolution is \(1/12^{\circ}\), and the distances between grids in horizontal, vertical, and oblique directions are 4.8321 nautical miles (nm), 5.0026 nm, and 6.9552 nm. It is easy to understand that if \(h(cell_{i})\) is calculated using Eq. Therefore, this leads to scenario 4 in Table 1. In this paper, \(g(cell_{i})\) contains both scalar risk and vector risk values, so it is expressed as Equation (9). \[ \begin{array}{ll}g(cell_{i},cell_{i^{\prime}})&\triangleq g(x_{i},y_{i},x_{i^ {\prime}},y_{i^{\prime}}),\\ &=\alpha\widetilde{f_{1}}(x_{i},y_{i})+(1-\alpha)\widetilde{f_{2}}(x_{i},y_{i},x_{i^{\prime}},y_{i^{\prime}}),\alpha\in[0,1],\end{array}