Intelligent Ship Scheduling and Path Planning Method for Maritime Emergency Rescue

Abstract

Intelligent ship navigation scheduling and planning is of great significance for ensuring the safety of maritime production and life and promoting the development of the marine economy. In this paper, an intelligent ship scheduling and path planning method is proposed for a practical application scenario wherein the emergency rescue center receives rescue messages and dispatches emergency rescue ships to the incident area for rescue. Firstly, the large-scale sailing route of the task ship is pre-planned in the voyage planning stage by using the improved A* algorithm. Secondly, the full-coverage path planning algorithm is used to plan the ship’s search route in the regional search stage by updating the ship’s navigation route in real time. In order to verify the effectiveness of the proposed algorithm, comparative experiments were carried out with the conventional algorithm in the two operation stages of rushing to the incident sea area and regional search and rescue. The experimental results show that the proposed algorithm can adapt to emergency search and rescue tasks in the complex setting of the sea area and can effectively improve the efficiency of the operation, ensure the safety of the operation process, and provide a more intelligent and efficient solution for the planning of maritime emergency rescue tasks.

1. Introduction

Ship navigation scheduling and planning have broad application prospects in maritime emergency rescue, maritime safety governance, maritime shipping control, and other fields [1]. Specifically, in the field of emergency rescue, after receiving the maritime rescue news alert, the search and rescue center needs to immediately dispatch rescue vessels to the incident area and carry out search and rescue operations. However, due to the opaque information and inflexibility of the information of ships, facilities, and operators, there will be inaccurate intelligent scheduling and low efficiency. The application of intelligent ship navigation scheduling and planning can make the search and rescue command center more flexible and allow it to have a more reasonable allocation of search and rescue resources, which is conducive to improving the efficiency of maritime search and rescue operations.

The existing studies on ship navigation scheduling and planning are mainly based on traditional planning algorithms and intelligent bionic path planning algorithms [2]. The traditional planning algorithms mainly include the depth-first search algorithm [3], Dijkstra algorithm [4], A* algorithm [5], and the artificial potential field algorithm [6]. The authors of [7] designed a global path planning algorithm with a mandatory point constraint by integrating an improved A* algorithm and simulated annealing algorithm for the problem of non-point to point global path planning. The authors of [8] improved the hybrid path planning algorithm based on a static environmental potential field and dynamic environmental attraction and repulsion, combined with the typical mariner ship type and proportional differential control, which was suitable for local minimum problems in restricted waters such as narrow waters. The D* algorithm is a dynamic programming algorithm based on the A* algorithm which can adapt to dynamic programming in complex environments and has a good [9,10] effect in real-time planning and scheduling. The intelligent bionic algorithm [11,12,13] is a kind of random search algorithm that operates by simulating biological evolution or population behavior; it is widely used in path planning. In reference, a static path planning method based on a simulated annealing algorithm is proposed, which uses neighborhood search and probabilistic jumping strategies to find a feasible and optimal observation path. The authors of [14] proposed a dynamic path planning method based on game theory. By establishing a game model and designing a reasonable negotiation mechanism, the problem of resource competition and conflict was solved, and the overall observation efficiency was improved. The ant colony search algorithm does not rely on a lot of prior knowledge; the structure of the algorithm is simple and easy to understand and implement, and it has strong adaptability for optimizing solutions to complex problems. However, the iteration speed of the algorithm [15,16,17] is slow, and it is easy to fall into local optimum. In reference [18], a particle swarm optimization (PSO) algorithm was proposed, which used the idea of genetic mutation for reference to increase the population diversity of particles and effectively improve the convergence speed of the algorithm. The authors of [19] proposed a path planning with dynamic obstacle avoidance method of the manipulator based on a deep reinforcement learning algorithm soft actor-critic (SAC). A comprehensive reward function of dynamic obstacle avoidance and target approach is designed to avoid the moving obstacle in the environment and make real-time planning. In addition, some studies related to trajectory planning and trajectory analysis have been conducted by using AIS and SOS data. The authors of [20] propose a multi-regime vessel trajectory reconstruction model based on a large AIS dataset. Through the removal of outliers, ship navigational state estimation, and vessel trajectory fitting, the proposed trajectory can eliminate the noise in the raw AIS data quite well. Ref. [21] quantified the operational risk management strategies of shipping companies using AIS data, providing a new research direction regarding AIS in the field of shipping risk management.

The above methods still cannot fully meet the actual needs in ship mission planning for maritime search and rescue. On the one hand, the development of danger is difficult to predict. Although the current maritime SOS alarm system has been widely used, it takes time for the rescue force to rush to the incident area. The vessels and personnel in distress may be affected by environmental and human factors, and when the rescue force arrives, it may not be in the position of the news report. And sometimes the actual situation may be more complex and severe; for example, the hull may have capsized, disintegration and/or drift with the current may have occurred, or some people may have rescued themselves from the initial position, making it necessary to search the surrounding area of the incident. On the other hand, the complexity and uncertainty of the maritime environment bring greater challenges to mission planning, which needs to consider multiple constraints and risk factors, such as weather changes, sea state fluctuations, and obstacle avoidance at sea. In addition, real-time and computational efficiency are also important factors which need to considered to provide a fast response while ensuring the accuracy of planning results.

In order to improve the efficiency and safety of the execution of maritime rescue tasks and to intelligently manage and schedule maritime ships and operating facilities, this paper proposes an intelligent planning method for ship action for the whole process of maritime search and rescue. The algorithm uses the A* algorithm with added constraints for large-scale route pre-planning; then, a complete coverage path planning algorithm (CCPP) [22] is used to search the target area for full coverage. The experimental results show that the intelligent ship scheduling and path planning method proposed in this paper can adapt to search and rescue missions in the complex setting of the sea and provide a more intelligent and efficient solution for the planning of maritime emergency rescue missions. Regarding the structure of this paper, firstly, the intelligent action planning method for maritime emergency rescue is described, including three parts: algorithm principle, experimental strategy, and evaluation index. Section 2 analyzes the experimental data, and Section 3 compares the experimental results of the algorithm with a conventional algorithm, including the ship navigation planning stage and the conventional A* algorithm for comparison. In the region search stage, a differential evolution algorithm is used for comparison experiments. Finally, the experimental results are discussed and analyzed.

2. Intelligent Ship Action Planning Method for Ocean Targets

2.1. Principle of Algorithm

• 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:

f(n) = g(n) + h(n)

(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:

$$\mathrm{h}(\mathrm{n})=\sqrt{{\left(x_2-x_1\right)}^2+{\left(y_2-y_1\right)}^2}$$

(2)

where $(x_1,y_1) \mathrm{and} (x_2,y_2)$ represent the coordinates of the two nodes $n_1 \mathrm{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. When an endpoint is completely covered, the direction will be converted, and the conversion Angle formula is as follows:

$${\theta }^r={\tan }^{-1}\left(\frac{Y_B^r}{\left|X_B^r-X_A^r\right|}\right)$$

(3)

where ${\theta }^r$ represents the conversion Angle under the regional coordinate system; $Y_B^r$ represents the ordinate of region endpoint B in the regional coordinate system. $X_A^r$ and $X_B^r$ represent the horizontal coordinates of the region endpoints A and B in the regional coordinate system, respectively.

2.2. Experimental Strategy

An intelligent ship action planning method for maritime emergency rescue is the impetus that allows for maritime rescue forces to carry out actions. According to the task requirements, an intelligent action planning model algorithm is constructed to plan the sailing route and action steps of maritime rescue vessels, continuously track the ongoing action tasks, and feed back the task execution in real time. As shown in Figure 2, intelligent ship action planning for maritime emergency rescue is mainly divided into two stages: the navigation planning and regional search stages. In the navigation planning stage, according to the pre-planning of the navigation route in the maritime rescue area, it is ensured that the ship can quickly and safely reach the incident area from the starting point. After the ship reaches the incident area, it enters the regional search phase. In the regional search stage, the ship delimits the search area and carries out search route planning according to the reported location of the incident, searches for the target that needs to be rescued along the way, and continues the regional search after the rescue is completed.

In the ship navigation planning stage, the optimal navigation route from the starting point to the emergency rescue area is planned based on the A* algorithm, which takes the longitude and latitude coordinates of the observation area and the longitude and latitude coordinates of the ship’s starting point as inputs and combines the ship archives, power duration parameters, sea and land rasterization data, and related constraints. At the same time, a variety of constraints need to be considered, as shown in

Table 1. Constraints of navigation route planning.

Categories of Constraints	Constraints	Constraint Meaning
Time constraint	Sailing path start time	The ship’s departure time cannot be later than the start time of the mission
	Sailing path duration	The sailing time cannot exceed the mission duration
	Starting point of the navigation path	The starting point of the A* route planning algorithm
Spatial constraint	Sailing path target point	The end point of the A* route planning algorithm
	Navigable area	The planned route can only pass through navigable areas
Task conflict constraint	Task time window	Task time window conflict solution
	Task priority	Tasks considered priorities are executed first
Ship performance constraint	Ship speed constraint	The estimated sailing time refers to the maximum speed and average speed of the ship
	Ship range constraints	The distance of the planned navigation route shall not exceed the maximum sailing mileage of the ship

. The first is the time constraint, which requires that the start time and duration of the navigation path must meet the time requirements of the mission; the second is the space constraint, which specifies the starting and ending points of the navigation path and requires that the navigation path should only pass through the navigable area and avoid the non-navigable areas such as land and islands. Secondly, the task conflict constraint solves the problem of time window conflict under multi-task processing and determines the execution order according to the priority of the task. Finally, there is the ship performance constraints, including ship sailing speed constraints, ship cruising range constraints, etc.

After the ship arrives at the emergency rescue area, it enters the regional search and rescue route planning stage. It uses the full coverage path planning algorithm to establish the survey area coordinate system with the ship as the reference point, iteratively updates the travel distance and turning Angle, and searches the observation area in an all-directional way. After the rescue operation is completed, the scope of the unsearched area is recalculated, and the full coverage path planning is carried out again until the entire emergency search area has been searched.

2.3. Evaluation Metrics

In order to effectively evaluate the planning effect of the two stages of navigation planning and regional search, the evaluation indicators shown in

Table 2. Evaluation indicators of the algorithm proposed in this article.

Running Stage	Algorithm Name	Evaluation Metrics
Navigation Planning	Regular A* algorithm, algorithm in this paper	Path length, number of turns, average turn Angle
Regional Search	Differential evolution algorithm, algorithm in this paper	Path length, regional coverage rate, point arrival rate, trajectory prediction accuracy

are used. The ship’s voyage planning stage involves pre-planning the path from the large scale of space. Therefore, compared with other stages, only the path economic benefit and trip safety are considered, that is, the path length, the number of turns, and the average turning Angle. In the area search stage, it needs to search the area of interest in an all-round way, so it needs to consider the area search coverage rate and task completion rate and other indicators. The ship target observation stage needs to take into account the real-time planning of sensors and the detailed and comprehensive exploration of the area of interest, so it is also the stage with the most considerations in the whole navigation process, which needs to take into account both timeliness and task completion.

3. Experimental Data

The intelligent planning of the ship’s navigation route mainly needs to consider the time and space relationship between the current position of the ship and the position of the area to be observed, as well as the start time of the mission. The planning parameters of the algorithm are shown in

Table 3. Table of parameters of intelligent planning algorithm for ship navigation routes.

Types	Parameter Name	Symbol Name	Unit	Precision	Range of Values
Ship’s current position	Vessel longitude	Loncp	°	10−6	[−180°, 180°]
	Vessel latitude	Latcp	°		[−90°, 90°]
Position coordinates of the area to be observed	Longitude 1	Lonul	°		[−180°, 180°]
	Latitude 1	Latul	°		[−90°, 90°]
	Longitude 2	Lonbr	°		[−180°, 180°]
	Latitude 2	Latbr	°		[−90°, 90°]
Time	Mission start	starTime	ms	1	[0, 2554372347000]

. The current latitude and longitude of the ship is automatically captured through the ship positioning system, and the position coordinates of the observation area and the start time of the task are obtained through the human–computer interaction interface configuration.

The data used for the creation of this paper were sourced from the raster data of sea and land maps provided by Natural Earth [23] This dataset uses the WGS-84 (World Geodetic System 1984) coordinate system, with a total of about 900 million pixels, each pixel representing a spatial area of 500 m × 500 m on the Earth’s surface. The rasterized map data are intercepted according to the coordinate values of the starting point and the target point in the exploration mission and inputted into the algorithm to correct the coordinates. A large number of rosters are simplified, and the electronic chart is appropriately trimmed according to the regional scope required by the mission planning, as shown in Figure 3.

Horizontal and vertical grid lines are used to divide the task area delivery into grid cells of the same size. According to the selected task area, the human–computer interaction simulation platform extracts the sea, land, and water depth information in the task area by traversing and sets the land, islands, and areas with shallow water depth as obstacle areas. After determining the position of the obstacle area, the grid map of the obstacle grid, the free grid (navigable area), and the initial position grid (the initial position of the ship) are established. According to the tiff files of different precision, they are converted into the corresponding rasterized data, as shown in Figure 4.

4. Experiment and Analysis

4.1. Route Pre-Planning in the Navigation Planning Stage

In order to verify the performance of the route pre-planning model in the ship’s voyage planning stage, it was compared with the conventional A*algorithm. Taking Sanya Port of China as the planning starting point, the target maritime rescue position of 109°15.4′ E and 18°12.5′ N was selected, and the experiment was carried out in the period when the weather and sea conditions are relatively stable.

The results are shown in

Table 4. Experimental results of conventional A * algorithm and algorithm proposed in this paper.

Algorithm	Path Length/Nautical Mails	Number of Turns/Times	Average Turn Angle/(°)
Regular A* algorithm	35.4	6	30.7
Algorithm of this article	29.6	4	29.3

. The path length of the proposed algorithm is shorter than that of the A* algorithm, which indicates that the navigation route planned by the proposed algorithm can reduce the navigation time and energy consumption and improve the efficiency and economy of navigation. In terms of the number of turns, the proposed algorithm has fewer than the A* algorithm, indicating that the navigation route planned by the algorithm can reduce the difficulty and risk of ship control and improve the stability and safety of navigation. In terms of the average turning Angle, the average turning Angle of the algorithm proposed in this paper is smaller, and the sailing route is smoother. The algorithm has a smaller turning radius and ship inertia, which improves the flexibility and stability of navigation.

4.2. Search Route Planning for the Regional Search Stage

We conducted another experiment in order to verify the performance of the ship search route planning model in the regional search stage. Taking the rescue location as the starting point, a search and rescue area of 109°13.4′ E~109°19.2′ E, 18°9.9′ N~18°14.3′ N (about 130 square kilometers) was selected, the average speed of the search and rescue ship was set to 11 knots, the visual range was 6 km, and the effective search and rescue time was 30 min. The differential evolution algorithm [24] and the algorithm proposed in this paper were used for comparison experiments, and the experimental results are shown in

Table 5. Experimental results of differential evolution algorithm and algorithm proposed in this paper.

Algorithm	Path Length/Nautical Mails	Area Coverage/%
Differential evolution algorithm	47.8	82.1
Algorithm of this article	43.2	93.4

. From the perspective of path length, when the regional search task is carried out within the same time limit, the path planned by the proposed algorithm is shorter, and the regional coverage rate is higher, which provides obvious advantages in terms of planning efficiency.

4.3. Discussion of Analysis

The core problem of route planning is how to minimize the distance and time from the departure location to the mission location under the influence of external conditions such as weather and obstacles so as to maximize the utilization of resources. According to the location of the incident area and the constraints of each stage of the mission planning, the path is reasonably planned to help to comprehensively reduced consumption and achieve the greatest benefit.

The experimental results show that the performance of the improved A* algorithm presented in this paper is better than that of the traditional algorithm in terms of path length, number of turns, and average turn Angle, indicating that the algorithm is more efficient, economical, safe, and flexible in planning the navigation route and is more suitable for the actual needs of maritime navigation. Compared with the differential evolution algorithm, the full coverage path planning algorithm has a shorter planned path and greater regional coverage rate within the specified time, which provides obvious advantages in terms of path planning efficiency.

5. Conclusions

Aimed at the practical application scenario of an emergency rescue center receiving rescue messages and dispatching emergency rescue vessels to the incident area for rescue, this paper proposes an intelligent ship scheduling and path planning method for the whole process of maritime emergency rescue operation. The work of this paper is summarized below:

• For the task planning stage in the process of maritime emergency rescue, through the improved A* algorithm, taking the longitude and latitude coordinates of the observation area as inputs and considering the ship’s own performance, current status, and external environmental constraints, the large-scale navigation route of the search and rescue vessels is planned in advance to meet the needs of the search and rescue vessels to allow them to rush to the incident area quickly and safely. The experimental results show that the proposed algorithm can generate large-scale measurement action plans that meet the task requirements. Compared with the traditional A* algorithm, the proposed algorithm can reduce the sailing distance and turning frequency and improve the navigation efficiency and safety.
• For the regional search and rescue stage in the process of maritime emergency rescue, the full coverage path planning algorithm is used to plan the search route with the goal of reaching the full coverage of the search area as soon as possible. By updating the route and Angle of the ship’s navigation in real time, the needs of the search and rescue vessels, which need to search the incident area efficiently and without going missing, are met. The experimental results show that compared with the differential evolution algorithm, the proposed algorithm has shorter path plans and greater regional coverage, which provides obvious advantages in terms of path planning efficiency.

In summary, intelligent ship scheduling and path planning for maritime emergency rescue tasks is an effective method which is helpful for improving the efficiency and safety of ships in maritime search and rescue activities. Future research could further optimize and improve this method to ensure it can adapt to more complex maritime environments and mission requirements and provide more intelligent and efficient solutions for the planning of maritime emergency rescue missions.