# Intelligent Ship Scheduling and Path Planning Method for Maritime Emergency Rescue
## 2 Intelligent Ship Action Planning Method for Ocean Targets  
### Principle of Algorithm  
1. A* algorithm [5]  
Compared with the traditional Dijkstra algorithm and the best first search algorithm, the A* search algorithm can combine the actual cost from the starting point to the current goal and the total cost from the current goal to the endpoint and has higher planning accuracy and lower computational complexity. The A* algorithm determines the search direction through the evaluation function, expands from the starting point position, calculates the cost value of each surrounding node through the evaluation function, and selects the minimum cost node as the next expansion node. This process is repeated until the goal point is reached and the final path is generated. The cost function is calculated as follows:  
\[\text{f(n)}=\text{g(n)}+\text{h(n)} \tag{1}\]  
where f(n) represents the evaluation function from the starting point to the target point through any node n; g(n) represents the actual cost from the starting point to node n; and h(n)represents the estimated cost of node n to the target point. The estimated distance of h(n) is calculated by the Euclidean distance, and the formula is as follows:  
\[\text{h(n)}=\sqrt{\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2}} \tag{2}\]  
where \(\left(x_{1},y_{1}\right)\) and \(\left(x_{2},y_{2}\right)\) represent the coordinates of the two nodes \(n_{1}\) and \(n_{2}\), respectively. The process of the A* algorithm described in this paper is shown in Figure 1. The open table, close table, and path table are defined to store the expansion nodes, and the mask is initialized to 0. The optimal node is selected from the open table and stored in the close table, and its successor nodes are put into the open list. The optimal node is selected by repeated operation, and the optimal node is stopped when the target is reached or the open list is empty. 2. CCPP algorithm [22]  
Suppose that the region under test is a polygon, where \(V\) represents the set of vertices of the region under test with the origin of the regional coordinate system as a reference, and \(E\) represents the set of edges formed with vertex elements in \(V\). In the process of ship search path planning, the system first receives the task starting point coordinates \(\left(X_{0},Y_{0}\right)\) and the endpoint coordinates of the observation area v as inputs, where \(X^{o}\) and \(Y^{o}\) represent the endpoint coordinates of the detection area in the WGS84 coordinate system, respectively. If the feature of the area to be measured is mostly an irregular polygon, the regional coordinate system is set up with the nearest side of the starting coordinate and the normal line of the ship position as the axis, and the full coverage path planning algorithm is used for efficient operation. The distance \(L_{V}\) between the geometric center of the polygon in the measurement area and all endpoints in the observation area is calculated, and whether the element \(L_{V}\) in \(\left(\overline{X},\overline{Y}\right)\) is within the maximum range of the hull's omnidirectional sensing device is determined. If the distances of all endpoints are within the range of the device, the range of the omnidirectional sensing device is scheduled to cover the endpoint in the observation area that is farthest from the current position of the ship. If not, the scanning area of the task ship is determined by establishing the regional coordinate system, the hull position point is selected as the starting point, and the navigation direction is clockwise along the edge of the region. The navigation distance is based on the detection range radius of the ship-borne detection equipment to ensure the rational utilization of resources.