A Method for Coastal Global Route Planning of Unmanned Ships Based on Human-like Thinking

Abstract

Global route planning has garnered global scholarly attention as a crucial technology for ensuring the safe navigation of intelligent ships. The comprehensive influence of time-varying factors such as water depth, prohibited areas, navigational tracks, and traffic separation scheme (TSS) on ship navigation in coastal global route planning has not been fully considered in existing research, and the study of route planning method from the perspective of practical application is still needed. In this paper, a global route planning method based on human-like thinking for coastal sailing scenarios is proposed. Based on the historical route’s information, and taking into full consideration those time-varying factors, an abnormal waypoint detection and correction method is proposed to make the planned route conform to relevant regulations of coastal navigation and the common practices of seafarers as much as possible, and better meet the coastal navigation needs of unmanned ships. Taking the global route planning of “ZHIFEI”, China’s first autonomous navigation container ship, as an example, the validity and reliability of the proposed method are verified. Experimental findings demonstrate the efficacy of the proposed method in global route planning for coastal navigation ships. The method offers a solid theoretical foundation and technical guidance for global route planning research of unmanned ship.

1. Introduction

With the rapid development of science and technology, and the growing demand of the global shipping industry for ship navigation safety, efficiency, economy and ecology, ship intelligent navigation technology has increasingly become a hot spot in the field of navigation and maritime technology. Despite significant advancements, numerous obstacles and challenges persist [1]. Scholars in relevant research domains worldwide have shown significant interest in global route planning as a pivotal technology in intelligent ship navigation. There are many environmental information and influencing factors that need to be analyzed and considered in the global route planning of ships. In particular, for coastal navigation, time-varying factors such as water depth, prohibited areas, navigational tracks, TSS, sea and weather conditions will all have an impact on ship navigation, bringing great challenges to global route planning. Numerous challenges persist in the global route planning of ships to guarantee safe and autonomous navigation.

In recent years, representative research on ship global path planning can be roughly classified into three categories: research based on optimization theory, research based on a heuristic algorithm, and research based on environmental impact and risk assessment.

The research based on optimization theory mainly focuses on using mathematical theories and methods to find the optimal solution from many feasible paths and minimize the total navigation cost. This kind of research usually includes the exploration of route optimization based on meteorological data, fuel consumption model, route database or route point database, using multi-objective programming, dynamic programming and other methods. Some representative studies are as follows: In order to obtain the optimal fuel path for ocean vessels through ocean currents, Lo and McCord [2] adopted the dynamic programming method and proposed two heuristic algorithms, namely course-power (H/P) and individual course (HA) optimization methods. To improve the computational efficiency, ship and ocean current dynamics are used to limit the spatiotemporal range of the solution. Lin et al. [3] proposed a ship weather route optimization algorithm based on multiple dynamic factors, which took into account constraints such as land boundary, prohibited area, navigational track, roll response and speed loss. The experimental results show that the proposed method can reduce fuel consumption, total voyage distance and navigation time. For the common problems of insufficient efficiency of USV (Unmanned Surface Vehicles) platform, such as small size, low payload capacity, and short endurance, Liu and Bucknall [4] proposed a constrained fast marching algorithm for USV formation path planning in a dynamic environment. This algorithm has faster computation speed and lower computational complexity. The algorithm is evaluated and validated in a simulation environment. Fang and Lin [5] proposed a global route planning method based on 3D Modified Isochron (3DMI) method. In this method, two types of route planning strategies are considered, namely the ETA (estimated time of arrival) route and FUEL (fuel saving) route, and recursive forward modeling technology and floating grid system are adopted for ship track correction. By adjusting the safety threshold of ship efficiency and economy, the feasibility and robustness of the proposed method are verified under dynamic rough sea conditions. Krata and Szlapczynska [6] proposed a dynamic constrained ship meteorological path optimization method based on reliable synchronous roll prediction, and compared the wave period forecast with the actual wave period to optimize the meteorological route in real-time. Lee et al. [7] proposed a ship route planning method based on optimization technology, which considers both ship path and speed. The results of sensitivity analysis and comparison with other methods show that this method can help to effectively reduce the total fuel consumption of the planned route. Wang et al. [8] developed a dynamic optimization framework for enhancing ship energy efficiency within variable environmental conditions. By leveraging up-to-date meteorological data, tailored speed strategies were devised for distinct time segments to minimize energy usage and mitigate carbon dioxide emissions efficiently. Wang et al. [9] proposed a three-dimensional Dijkstra optimization algorithm for the global optimal planning of ship routes. The algorithm allows ships to plan waypoints and the speed of each waypoint, with the ability to save fuel consumption. Compared with other conventional route planning algorithms and measured fuel consumption data of container ships, the performance of this algorithm is verified. Experimental results show that the fuel consumption of ships can be greatly reduced by using this algorithm for route planning. The algorithm also has the advantage of parallel computation and recalculation, and can provide energy-saving route planning for voluntary deceleration or acceleration. Gkerekos and Lazakis [10] introduced a data-informed framework designed to offer ships optimal route guidance. This approach identifies the optimal route by analyzing weather data and fuel consumption across various route options. Wen et al. [11] proposed an automatic route design method for inter-port ships based on massive data from Ship Automatic Identification System (AIS). This method uses the DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm to identify key areas, and uses an artificial neural network to learn the relationship between turning areas to generate a reasonable route. At the same time, it is pointed out that there are potential risks in the course of route generation, and it is recommended to carry out safety checks before sailing, and consider adding electronic charts and the latest navigation environment information constraints to improve the quality and timeliness of results. Vagale et al. [12] analyzed and discussed the current research status of path planning for unmanned ships, and proposed a classification scheme of GNC (guidance, navigation and control) path planning algorithm and model. Wang et al. [13] utilized a multi-stage dynamic inversion approach to determine waypoint placement, diminish the impact of unfavorable weather and hydrological conditions on ship navigation, optimize navigation duration and energy use, and develop meteorological paths for unmanned ships. Gu et al. [14] proposed a PI-DP-RRT path planning algorithm. The algorithm combines the prior information of the Automatic Identification System (AIS) with the Douglas-Peucker (DP) trajectory compression algorithm. By introducing the guide region and improving the sampling strategy, the convergence speed of the algorithm is improved. Through the improved DP algorithm and path optimization method, the smoothness and practicability of the path are improved. The authors also note that in future studies, dynamic obstacles and more complex navigational environments should be considered. Aiming at distributed coordinated path planning for autonomous surface ships (MASS) at sea, Ni et al. [15] proposed a path-planning scheme based on the Three-dimensional Generalized Velocity Obstacle (TGVO) algorithm. The scheme takes into account multi-ship encounters, and combines maneuvering constraints, time dimension constraints and ship dynamic characteristics constraints to generate the actual collision-free velocity of the ship that meets the COLREGs standard. The collision type and action sequence are defined by quantitative criteria and a priority analysis model, and a multi-stage decision model is established. The simulation verifies the practicability of the method and its consistency with actual navigation, and points out that in future research, collision avoidance decision-making and emergency response collision avoidance in restricted waters, as well as unexpected course changes should be focused on.

The research based on heuristic algorithms mainly focuses on finding a set of feasible solutions to combinatorial optimization problems in acceptable time or space. This type of research usually includes improvements to one or more heuristic algorithms, combined applications, and scenario-specific applications to solve specific problems. Some representative studies are as follows: Lyu and Yin [16] introduced the Path Guided Hybrid Artificial Potential Field (PGHAPF) technique for addressing path planning and collision avoidance challenges in autonomous ship navigation. By integrating the potential field and gradient methods, this approach efficiently computes collision-free paths that adjust to changing environmental conditions, accounting for dynamic target vessels and static obstacles, as well as optimizing prior path selections and waypoint choices. Simulation results demonstrate the method’s potential utility across unmanned surface vehicles (USV), autonomous underwater vehicles (AUV), and robotics. Future research avenues may involve further quantification of multi-vessel encounters and the integration of potential field models for static obstacles into Electronic Chart Display and Information Systems (ECDIS) for validation. Xie et al. [17] proposed an improved A-Star algorithm for the global route planning of ships in wind farm waters. Chen et al. [18] proposed a path planning and ship maneuvering method based on Q-learning, which realized the generation of ship path planning and maneuvering strategies through ship modeling in simulated waterways, construction of action reward models and autonomous learning, and produced an effect closer to human maneuvering. Guo et al. [19] constructed an autonomous path planning model based on Deep Reinforcement Learning (DRL) and integrated it into the electronic chart platform for experiments to verify the effectiveness and stability of the model. Zhang et al. [20] proposed a hybrid approach for autonomous ship path planning based on global paths and local paths. The typical artificial potential field method (APF) and velocity obstacle method (VO) are improved. By integrating COLREGS and navigation techniques, the safety and maneuverability of ship collision avoidance are taken into account in global path planning and local path planning. The effectiveness of this method is verified by a case study. A route planning method for unmanned ship was proposed by Meng et al. [21], aiming to address the slow convergence issue in path planning in complex environments through the enhancement of the Grey Wolf Optimization (GWO) algorithm. Guo et al. [22] introduced a coastal navigation ship path planning model utilizing an optimized Depth Q Network (DQN) algorithm. Aiming at the path planning problem of unmanned cruise ships in the environment of unknown obstacles, Yu et al. [23] proposed a hybrid multi-objective path planning algorithm. Initially, the multi-objective planning challenge is converted into a traveling salesman problem, and the sequence for multi-objective sailing is determined through an enhanced grey Wolf optimization algorithm. Subsequently, leveraging the planned target sequence, the enhanced D* Lite algorithm is employed for inter-point path planning. Experimental validation showcases the efficacy of the proposed algorithm, amidst comparative analysis with alternative methods. The author underscored potential enhancements through parameter optimization and 3D map model construction. A route planning method considering vessel motion characteristics and Electronic Navigational Chart (ENC) vector charts was proposed by He et al. [24], aiming to reduce errors generated during the conversion of vector maps to grid maps. In order to reduce the safety hazards and carbon emissions of ships in the collision avoidance process, Gao et al. [25] proposed a potential field ant colony algorithm for ship collision avoidance path planning. In this paper, a nonlinear programming model aiming at the minimum range and carbon emission is constructed, and the ant colony algorithm is combined with the improved artificial potential field method to achieve dynamic collision avoidance. Zhang et al. [26] introduced an enhanced ant colony algorithm for ship’s global path planning, incorporating the artificial potential field method in the initial iteration phase to boost efficiency. The pseudo random state transition rule and updating pheromone method are designed to improve the convergence and security of the algorithm. By considering the factors of path length, safety and smoothness, more secure navigation path planning is realized and verified by simulation experiments. A ship route planning method for complex water areas based on Chaos Genetic Algorithm was proposed by Jia et al. [27] and validated through simulation experiments. The global path planning problem of unmanned ships in port environments was addressed by Yun et al. [28] using an improved A* algorithm combined with grid path planning, with the reliability of the method confirmed through simulation experiments.

Research based on environmental impact and risk assessment mainly focuses on in-depth analysis and assessment of various environmental and ecological factors to predict and manage possible risks. Such studies usually focus on the effects of weather, hydrology, TSS, special waters, collision risk, speed constraints and other factors on navigation safety. Some representative studies are as follows: Zaccone et al. [29] proposed a ship route dynamic optimization method based on 3D dynamic programming. Based on weather forecast information and focusing on energy consumption and comfort level, ship route optimization was carried out using a multi-stage decision-making method. Zis et al. [30] examined recent advancements in meteorological route optimization, outlining approaches to calculate wind and wave resistance with consideration for environmental factors to predict power and fuel usage. Aiming at the problem of global path planning for MASS at sea, Chen et al. [31] proposed a shortest path planning method that comprehensively considered collision risk and proximity between paths and obstacles. The concept of time-varying collision risk (TCR) is introduced in this method, considering the speed constraint and collision risk of the ship during operation, and the influence of obstacle proximity is measured by the fast forward algorithm. The International Maritime Organization (IMO) has delineated several emission control areas (ECAs) in which ships must use more expensive low-sulfur fuels. To minimize total navigation costs, Ma et al. [32] propose an improved Cell-based approach to optimize routes and speeds, which takes into account ECA regulations and weather conditions. Zhang et al. [33] introduced a dual-phase ship path planning strategy leveraging the Rapidly-exploring Random Tree (RRT) algorithm. Featuring global and local path planning components, the method targets the challenge of navigating an optimal, secure route within a fluctuating setting. Global path planning considers ship draft and keel clearance, uses the RRT algorithm to find navigable waters, and optimizes path length and waypoint by elliptical sampling and smoothing. A dynamic collision risk detection model is introduced in local path planning, taking into account ship maneuverability and COLREGS constraints. The effectiveness of the model is verified by simulation experiments. Gan et al. [34] studied the path planning problem of inland waterway ships from the perspective of navigation risk, and proposed a path planning method based on the safety potential field theory. The navigational risk causes are divided into static obstacles, dynamic obstacles and channel shore walls, and quantified by different potential field functions. In the superposition field, the minimum risk point is searched along the navigation direction and the optimal path is formed. Finally, the effectiveness of the method is verified by simulation experiments. He et al. [35] combined the quaternion ship domain and potential field to calculate ship navigation risk cost, and considered COLREGS constraints, proposed a dynamic collision avoidance path planning algorithm based on A-Star algorithm and ship navigation rules, namely dynamic collision avoidance A-Star (DAA-star) algorithm. The effectiveness of the algorithm is verified by simulation experiments. In order to improve the safety and efficiency of ship route planning, Zhen et al. [36] proposed an improved A-Star algorithm. The algorithm takes into account the influence of water flow, water depth, TSS and other factors on the navigation safety of ships, and aims to minimize the risk of collision and grounding. By introducing risk models, steering models and smoothing methods, a path that complies with TSS rules and is easy to track and control is generated. The paper also suggests that future research could consider factors such as weather to plan routes out of severe weather conditions. Aiming at the path planning problem of autonomous ships in inland river bridge areas, Zhang et al. [37] proposed a multi-vector field path planning method that could consider the influence of external environment and navigation risks. This method comprehensively considers the influence of inland water features, hydrological features and meteorological factors on navigation safety. By dividing the navigation environment factors into static vector field and dynamic vector field, and taking the synthetic vector field as the input of the algorithm, the optimal path under the influence of multiple factors is calculated. In the future, it is necessary to further combine other intelligent algorithms and real environmental data to plan the safest and most energy-efficient paths in near real-time to improve navigation safety.

In addition, in recent years, artificial intelligence technologies have developed rapidly, with some related methods, including the reinforcement learning methods mentioned earlier in the review [38], as well as deep learning, genetic algorithms, convolutional neural networks, among others, being widely applied [39]. While these methods have shown relatively good performance in handling large-scale data and complex problems, they still have many shortcomings, such as high demands for data quality and high computational complexity. Furthermore, the interpretability of models will greatly influence users’ trust in the models, consequently affecting the acceptability of these methods in practical applications.

It can be seen that the existing research on ship’s global route planning focuses more on the economy of the route, or explores the impact of various environmental or ecological factors on navigation safety. Routes planned by traditional or intelligent search algorithms are often unable to intelligently identify the waters where the ship’s routing is implemented, such as TSS and recommended routes, resulting in the planned routes failing to comply with relevant navigation rules. The knowledge, experience and common practices of seafarers involved need to be fully considered in the course of route planning. Methods such as deep learning, genetic algorithms, reinforcement learning, convolutional neural networks, etc., have demonstrated increasingly good performance in many fields, yet their lack of sufficient interpretability remains a significant issue that cannot be ignored. Therefore, it is necessary to carry out further research on global route planning from the perspective of human-like thinking.

Human-like thinking refers to applying human thought processes to machine intelligence to simulate human thinking patterns, in order to better address human needs and problem-solving. Therefore, it is necessary to determine how humans think. This is commonly achieved through introspection, psychological experiments, and brain imaging methods. In this paper, the first method is employed to explore ship global route planning from the perspective of human thought processes, aiming to achieve better interpretability.

In this paper, a global route planning method based on human-like thinking is proposed, and the detailed logic flow chart and calculation formulas of key links are given. Similar historical routes are identified through comparative analysis and used as initial routes. These routes are then adjusted based on actual sailing conditions to obtain safe and economic global routes. Alternatively, an initial path is planned using a traditional algorithm, and the global route is obtained by employing proposed methods such as abnormal waypoint detection and correction, path optimization based on navigational track constraints, path smoothing, and speed and course planning. This approach enables the realization of global route planning for unmanned ships based on human-like thinking. The validity and reliability of the method are validated using a case study involving the route planning of “ZHIFEI”.

The remainder of this paper is organized as follows: Section 2 presents the proposed global route planning method, its construction and verification method. In Section 3, the results of the verification experiments are presented. The analysis of the experimental results and the discussion of the study’s limitations are provided in Section 4. Finally, Section 5 presents the conclusion.

2. Materials and Methods

2.1. Scenarios of Ships’ Coastal Navigation

Compared with ocean navigation, the environment of coastal navigation waters is more complex, including ports, straits, islands, shoals, fishing areas and so on. At the same time, there are also narrow waterways, shallow water areas and complex terrain and other water features. In addition, it is also necessary to consider the influence of time-varying factors such as sea conditions and weather on ship navigation. Although the coastal voyage distance is generally relatively short, the factors that need to be considered in the course planning process are quite complex and changeable. Due to the complexity of the study, sea conditions and weather factors are not considered in this paper. Figure 1 is a screenshot of the Electronic Chart Display and Information System (ECDIS) for a certain coastal navigation scene. It can be seen from the figure that there are many special waters such as prohibited areas, anchorage areas, and TSS areas in the coastal waters, and the water depth is also significantly different, which has a great influence on the navigation of ships.

2.2. Route Modeling

A complete route consists of continuous route segments, each of which is a line segment with a constant course. To simplify the analysis process, the speed is assumed to be uniformly accelerated from the beginning to the end of the segment. The navigation status data at each waypoint are recorded successively as an expression of the current route.

Ship attribute parameters should include parameters used to identify the ship and some parameters that affect the result of route planning, such as parameters related to ship size. The specific parameter vectors are shown in Equation (1):

$$P_{Attribute}=(A_{MMSI},A_{Length},A_{Width},A_{Draft},A_{Displacement})$$

(1)

where, $A_{MMSI}$ represents MMSI value, $A_{Length}$ represents ship length, $A_{Width}$ represents ship width, $A_{Draft}$ represents draft value, $A_{Displacement}$ represents displacement value.

The target parameters of the route should include the position of the starting point and end point of the route and the attitude information of the ship, the specific vector is shown in Equation (2):

$$P_{Target}=(O_{Lon},O_{Lat},O_{Heading},D_{Lon},D_{Lat},D_{Heading})$$

(2)

where, $O_{Lon}$, $O_{Lat}$ and $O_{Heading}$ respectively represent longitude, latitude coordinates and ship heading value at the beginning of the course, $D_{Lon},$ $D_{Lat}$ and $D_{Heading}$ respectively represent longitude, latitude coordinates and ship heading value at the end of the course.

The waypoint model should record the time, position, attitude and motion state information of the ship at the route node, as shown in Equation (3):

$$M_{Waypt}=(V_{BDTime},V_{Lon},V_{Lat},V_{Cog},{V_{Heading},V}_{Sog})$$

(3)

where, $V_{BDTime}$ represents current time value, $V_{Lon}, V_{Lat}$,$V_{Cog}$,$V_{Heading}$ and $V_{Sog}$ respectively represents the ship’s longitude, latitude, course, heading and speed value corresponding to current time.

The waypoint set should contain the information of all waypoints on the route, which can be expressed as Equation (4).

$$S_M=\left(M_{Waypt1},M_{Waypt2},\dots ,M_{Waypti},\dots ,M_{Wayptn}\right)$$

(4)

where, $M_{Waypti}$ represents the $i-th$ waypoint (in which, $i=\mathrm{1,2},\dots ,n$).

The whole model of the route should include ship attributes, route objectives and waypoint sets, as shown in Equation (5).

$$R=\{P_{Attribute},P_{Target},S_M\}$$

(5)

Among the four kinds of shipping routes commonly used, the Parallel Route is the special case of the Rhumb Line Route, while the Composite Route is the combination of the Great Circle Route and the Parallel Route. Since this paper mainly focuses on the coastal navigation of ships, the voyage distance is generally not very long, and there is little difference between the Great Circle Route and the Rhumb Line Route, while the latter is more convenient for ship maneuvering. Therefore, this paper gives priority to Rhumb Line navigation. From the point of view of human-like thinking, in order to reduce fuel consumption as much as possible and reach the destination as soon as possible, the operator usually likes to manipulate the ship to maintain a straight line at a certain speed, which also shows that the choice of Rhumb Line Route is in line with the usual practice of seafarers.

In addition, on the Mercator Projection map, the rhumb line is a straight line, so the Mercator projection map commonly used in navigation is also adopted in this paper to plot the navigation path and calculate the route.

2.3. General Idea of Global Route Planning

To plan the global route, firstly, it is necessary to ensure that the planned route can effectively avoid all static obstacles, which can be easily realized by existing path planning algorithms. Secondly, it is necessary to ensure that the planned routes can avoid the navigation restricted waters at the same time, which requires an equivalent transformation of these waters, such as equivalent static obstacles. Finally, it is necessary to ensure that the route meets the requirements of the rules, such as the TSS, the Fixed Track System, etc., which requires the correction of the route. At the same time, the number of steering points should be reduced as much as possible to improve navigation efficiency. Ship speed planning can refer to the historical route information, or the ship’s safe speed and the speed limit regulations of the sailing waters.

In order to achieve the above objectives, according to the common practice of seafarers, when designing routes, the recommended routes given in the navigation books are mainly referred to. In addition, through the accumulation of sailing experience, or referring to historical routes of other ships or their own ship, it can also help the route planner to quickly plan the global route. In this paper, the method of ship’s global route planning based on human-like thinking makes full use of the historical route information and accords with the common practice of seafarers.

The general idea of global route planning proposed in this paper is mainly as follows: According to the requirements of route planning, similar historical routes are retrieved. If similar historical routes exist, necessary corrections are made based on similar historical routes to generate target ship routes. If there is no similar historical route, the target ship route is generated according to the route generation method. After the voyage, the actual route of the target ship is stored in the historical route model database. The overall logical flow of the proposed global route planning method is shown in Figure 2.

In this paper, the definition of similar historical routes can be roughly divided into two cases. As for the same ship, the draft depth, starting point, and endpoint position coordinate difference should be within a certain threshold range. As for different ships, the ship size, the depth of draft, and the position coordinate difference between the starting point and the endpoint should be all within a certain threshold range.

2.4. Existence Judgment of Similar Historical Routes

Firstly, according to the MMSI information of the ship, the route information is extracted from the historical route model database and stored in the referable historical route model database. By comparing the route information, the most consistent historical route is determined as the initial route of this voyage. If there is no eligible historical route in the referable historical route model database, the most consistent historical route is matched according to the ship attribute information and voyage information as the initial route. If there are still no eligible historical routes, it is determined that no similar historical routes exist. The specific logic flow chart is shown in Figure 3.

If there are similar historical routes, it will be corrected. Mainly determine whether the following conditions exist.

(1)

At least one corresponding water depth in the route does not meet the requirements of the under-keel clearance;

(2)

At least one part of the route does not comply with the latest Fixed Track System regulations;

(3)

At least one part of the route does not avoid sensitive waters, including newly prohibited areas, etc.;

(4)

There is at least one continuous unnecessary steering point on the route.

If the above problems exist, the initial route should be corrected. The correction method is to re-plan the route segment with the above problems, and the specific method is basically consistent with the global route generation method in the following content, so it will not be described in detail here.

2.5. Generation Method of Global Route

According to the general idea of the global route planning method proposed above, if there are no similar historical routes, global routes need to be generated.

2.5.1. Logical Flow of Global Route Generation

Firstly, a raster map for route planning is constructed according to electronic chart information. The raster map is mainly used to determine whether a geographical location is navigable. Therefore, the data corresponding to each grid should contain at least the water depth value, and the prohibited area and the TSS area should also be converted into equivalent static obstacles and presented in the raster map.

Then, according to the information of route starting point, terminal point, static obstacles and equivalent static obstacles on the raster map, existing path planning algorithms [40], such as A*, Dijkstra, RRT, PRM, PSO, GA and other algorithms, are adopted to generate paths. To facilitate the repetition of the research, in this paper, the most commonly used path planning algorithm of A* [41] will be taken as an example. Water depth is considered in the cost function when the path is planned. In this paper, two water depth thresholds $D_{{\theta }_M}$ and $D_{{\theta }_N}$ are set (including positive and negative signs, negative sign means below the horizontal plane, positive sign means above the horizontal plane), and $D_{{\theta }_M}>D_{{\theta }_N}$. If the water depth value of a certain point is greater than $D_{{\theta }_M}$, the cost value is set to 10,000; If the water depth of a certain point is less than $D_{{\theta }_N}$, the cost value is set to 1; A water depth value between $D_{{\theta }_N}$ and $D_{{\theta }_M}$ takes a linear value between the two specified cost values (set to 1 and 20, respectively, in this article).

In this way, there are often some continuous unnecessary steering points or redundant nodes on the obtained path. In this paper, these points are defined as abnormal nodes, which need to be corrected.

After that, the generated path is optimized according to the navigational track’s information, so that the path closer to the navigational track is navigated as close as possible to its designated waters, and the safety and efficiency of navigation are ensured to the maximum extent.

Finally, the generated path is smoothed at the steering position, so that the final planned route can conform to the law of ship movement. During the planning of speed and course, the corresponding speed of the current ship at a certain waypoint is determined mainly according to the historical route information, waterway speed regulations and the empirical formula of the relationship between water depth and ship speed [42]. If there are historical routes in current waters, the speed value of the ship at a certain waypoint is determined by the average value of speed at a similar position in historical routes. The course is determined by the vector direction of the route segment starting from the current waypoint. The specific logical flow of global route generation is shown in Figure 4.

In the above logical flow, routes and paths are tried to be distinguished according to common practice in the research field. When it contains only location information, it is called a path. When it contains information such as speed and heading, it is called a route.

2.5.2. Detection and Correction Method of Abnormal Nodes on the Path

The path obtained by traditional path planning methods often contains some abnormal nodes, as shown in Figure 5, in which, the path is indicated by a red solid line. According to the basic idea of mutation theory [43], these abnormal nodes can be regarded as a mutation phenomenon, which often means a sudden situation and is usually the result of a combination of factors. Multiple factors accumulate over time, eventually leading to the sudden emergence of path abnormal nodes, which roughly include the following categories:

Redundant Nodes: Nodes that randomly appear on both sides of the expected path and at a close distance. Such nodes are typically caused by the gridding of the map and their frequency of occurrence often depends on the resolution of the map grid.

Accidental Nodes: Local path nodes that deviate from the expected global path between two certain nodes on the path. Such nodes mainly appear on the historical path and are often caused by various accidental factors, such as dynamic obstacle avoidance, temporary refuge, mis operation, and equipment failure.

Dangerous Nodes: Nodes that cause overly small or large changes in course angle between adjacent path segments. If the change is too small, it is detrimental to ship maneuverability and course stability; and if it is too large, it requires a larger steering radius and a longer sailing distance, affecting sailing efficiency and increasing collision risk. Such nodes are typically caused by the combined effects of gridding and the aforementioned accidental factors.

The existence of these abnormal nodes hinders the planned path from effectively meeting the actual navigation requirements of the ship, necessitating the need for path correction. To address this, we propose a Path’s Abnormal Nodes Detection and Correction Method (PANDCM).

To address these types of abnormal nodes, specific detection and correction methods are proposed by analyzing their characteristics. The effectiveness of these methods is illustrated in Figure 6, in which, the path is indicated by a red solid line. The specific methods are described as follows:

Redundant Nodes: This category of nodes is primarily determined by their deviation from the expected path. A distance threshold, denoted as $D_{\theta 1}$, is set for this purpose. Typically, this threshold is set as the maximum length of a grid unit, although it can be adjusted as needed. If the distance between every node along the path between points M and N, relative to the line segment MN, is smaller than $D_{\theta 1}$, satisfying Equation (6), then all nodes between M and N are considered redundant. The path segment will be replaced by the line segment MN.

$$\forall P_i,\exists Dis\left(P_i,MN\right)<D_{\theta 1}$$

(6)

where, $P_i$ is a node between point M and point N on the path, $Dis\left(P_i,MN\right)$ indicates the distance between the node $P_i$ and the line where MN resides.

Accidental Nodes: This category of nodes is also determined by their deviation from the expected path. A distance threshold, denoted as $D_{\theta 2}$, is set for this purpose. Typically, this threshold is set as a multiple of the maximum length of a grid unit, greater than $D_{\theta 1}$, although it can be adjusted as needed. If the distance between every node along the path between points M and N, relative to the line segment MN, is greater than or equal to $D_{\theta 1}$ and less than $D_{\theta 2}$, and the line connecting points M and N does not intersect any unsuitable positions for navigation, satisfying Equations (7) and (8), then all nodes between M and N are considered accidental. The path segment will be replaced by the line segment MN.

$$\forall P_i,\exists D_{\theta 1}\le Dis\left(P_i,MN\right)<D_{\theta 2}$$

(7)

$$\forall Q_i,\exists Dep\left(Q_i\right)<D_{\theta 3}$$

(8)

where, $Q_i$ is a point on the path between point M and point N, $Dep\left(Q_i\right)$ represents the water depth of point $Q_i$, based on the water level, the water depth value is negative. $D_{\theta 3}$ is the water depth threshold suitable for ship navigation.

Dangerous Nodes: This category of nodes is mainly determined by the angle formed between adjacent path segments. Following the practice of seafarers, the angle should ideally be kept between 20° to 60°, which can also be adjusted according to special needs. For adjacent path points L, M, and N, if the angle ${\mathsf{\Delta }}_{\theta }$ between path segments LM and MN satisfies the relation ${\mathsf{\Delta }}_{\theta }<20°$ or ${\mathsf{\Delta }}_{\theta }>60°$, then the intermediate node M requires correction. If ${\mathsf{\Delta }}_{\theta }<20°$, the M node can be considered for removal, and similar methods as those applied for accidental nodes can be utilized; these methods are not discussed further. For ${\mathsf{\Delta }}_{\theta }>60°$, a path segment is added at the corner and adjusted to a suitable angle that falls within the reasonable range of 20° to 60° while ensuring navigability

2.5.3. Path Optimization Method Based on Navigational Track Constraint

To optimize the generated path, it is important to keep the path as close as possible to the navigational track, ensuring safe navigation. By traversing all path points, if distances between adjacent points $P_i$ and $P_{i+1}$ to the same navigational track $L_j$ all fall within a specified threshold $D_{\theta 4}$, satisfying Equation (9), the points $P_i$ and $P_{i+1}$ are adjusted to lie on the navigational track. It is also ensured that the adjusted path segment remains navigable, satisfying Equation (10).

$$\left\{\begin{array}{c}Dis\left(P_i,L_j\right)<D_{\theta 4}\\ Dis\left(P_{i+1},L_j\right)<D_{\theta 4}\end{array}\right.$$

(9)

$$\forall R_i,\exists Dep\left(R_i\right)<D_{\theta 3}$$

(10)

where, $R_i$ is a point on the line between points $P_i$ and $P_{i+1}$ on the path.

Furthermore, according to the study, it has been discovered that the path planning results are better when the sequence of correcting path abnormal nodes and optimizing the path is arranged according to the order illustrated in Figure 7. This process involves the correction of accidental nodes two times, with the second one aimed at inadvertently generated nodes that may arise during the correction of dangerous nodes.

2.5.4. Global Path Smoothing and Speed and Course Planning Method

The global path obtained initially consists of many line segments connected in sequence. In order to make the path more consistent with the motion law of the unmanned ship, it needs to be smoothed. At the angle where the two line segments meet, an arc with a certain radius is adopted for smooth transition. For the sake of analysis simplification, this study assumes that the ship maintains maximum speed during steering maneuvers, following an arc trajectory. The ship’s turning radius is then calculated by multiplying the longitudinal distance covered when executing a 90° turn at full rudder with a designated relaxation coefficient, as depicted in Equation (11).

$$R_T=D_V\times C_X$$

(11)

where, $R_T$ is the ship’s turning radius (unit: m), $D_V$ represents the longitudinal distance (unit: m) required for a ship to execute a 90° turn, according to IMO Resolution A.749(18) and practical sea trial data, it is estimated at 2.5 times the ship’s length, $C_X$ is the relaxation coefficient (1.2 in this paper).

The speed planning mainly refers to the historical route information. If there is no historical route information, it is calculated according to the design speed of the ship, waterway speed regulations and the empirical formula of the relationship between water depth and ship speed. The speed value of a certain waypoint on the planned route is the average speed value within the range of distance threshold specified by the current waypoint position in the historical route of the ship. Assume that the set of waypoints on the current route is $S_M=\left(M_{Waypt1},M_{Waypt2},\dots ,M_{Waypti},\dots ,M_{Wayptn}\right)$, and calculate the speed value of the waypoint $M_{Waypti}$. For example, set the distance threshold $D_{{\theta }_C}$, retrieve historical speed values of all the waypoints which have a distance to $M_{Waypti}$ within the range of $D_{{\theta }_C}$ in historical routes of the ship, and obtain the average value as the final speed value. The start and end points’ speed values are set to 0.

For the course value at a certain waypoint on a route, except the end point, the other waypoint course values are determined by the direction vector from current waypoint to the next one. For example, if the current waypoint is $M_{Waypti}$ and the next waypoint is $M_{Waypti+1}$, the course of current waypoint is in the same direction as the vector $M_{Waypti}{M}_{Waypti+1}$.

2.6. Voyage Distance Calculation

Let the mean radius of the earth be $R$, and according to the Mercator projection principle, the longitude and latitude coordinates (unit: rad) of point $A({\alpha }_1,{\beta }_1)$ are converted to the Mercator projection coordinates $A\mathrm{\prime }(x_1,y_1)$ by the Equation (12) as shown:

$$\left\{\begin{array}{c}{x}_1=R{\alpha }_1\\ y_1={\int }_0^{{\beta }_1}Rsec\theta d\theta =Rln\left|sec{\beta }_1+tan{\beta }_1\right|\end{array}\right.$$

(12)

The length of the rhumb line ($l_{AB}$) between point A and another point $B({\alpha }_2,{\beta }_2)$ is calculated as shown in Equation (13):

$$l_{AB}=R\mathrm{\ast }2\mathrm{\ast }arcsin\sqrt{{\left(\frac{{\beta }_2-{\beta }_1}{2}\right)}^2+cos{\beta }_1\mathrm{\ast }cos{\beta }_2\mathrm{\ast }{\left(\frac{{\alpha }_2-{\alpha }_1}{2}\right)}^2}$$

(13)

The course angle ($\theta$) from point A to point B is calculated as shown in Equation (14) (unit: rad):

$$\theta =arctan2(R\mathrm{\ast }ln\left|\frac{\left(1+\sin {\beta }_2\right)\cos {\beta }_1}{\left(1+\sin {\beta }_1\right)\cos {\beta }_2}\right|,R\mathrm{\ast }({\alpha }_2-{\alpha }_1))$$

(14)

where, the calculation method of $arctan2(y,x)$ is shown in Equation (15):

$$arctan2\left(y,x\right)=\left\{\begin{array}{c}arctan\frac{y}{x}, (x>0,y\ge 0)\\ arctan\frac{y}{x}+2\pi ,(x<0,y\ge 0)\\ arctan\frac{y}{x}+\pi ,(x\ne 0,y<0)\\ 0,\left(x=0,y\ge 0\right)\\ \pi ,\left(x=0,y<0\right)\end{array}\right.$$

(15)

The rhumb line route is chosen in this paper, so the ship’s voyage distance ($S$) is calculated as shown in Equation (16):

$$S=2R\sum _{i=1}^{n-1}arcsin\sqrt{{\left(\frac{{\beta }_{i+1}-{\beta }_i}{2}\right)}^2+\cos {\beta }_i\mathrm{\ast }\cos {\beta }_{i+1}\mathrm{\ast }{\left(\frac{{\alpha }_{i+1}-{\alpha }_i}{2}\right)}^2}$$

(16)

For length-related variables appearing in the equations, such as $R$, $l_{AB}$, $S$, etc., it is only necessary to ensure consistent units without specification needed.

2.7. Voyage Duration Calculation

Since in this study, it is assumed that the motion of the ship on each route segment is uniformly accelerated, the sailing time of the current route segment can be approximately calculated based on the coordinates and speed of both ends of the current route segment. This enables the derivation of the total navigation time.

Let us assume that the coordinate of an endpoint $A_i$ on the current route segment is $({\alpha }_i,{\beta }_i)$, with a speed of $v_i$. The other endpoint $A_{i+1}$, corresponds to the coordinate $\left({\alpha }_{i+1},{\beta }_{i+1}\right)$ and has a speed of $v_{i+1}$. The length of the route segment is denoted as $l_{A_i{A}_{i+1}}$. The formula for calculating the total voyage duration ($T$) is given as Equation (17). The units of each variable match each other, without the need for specific designation.

$$T=\sum _{i=1}^{n-1}\frac{2l_{A_i{A}_{i+1}}}{v_i+v_{i+1}}$$

(17)

2.8. Verification of the Proposed Method

To verify the validity and reliability of the proposed coastal global route planning method, the route planning process of China’s first autonomous navigation container ship “ZHIFEI” from Qingdao Port to Dongjiakou Port was taken as an example to carry out verification experiments. The validity of the route is verified through the analysis of the navigation rule conformity of the planned route. The reliability of the planned route is verified through the comparative analysis of the routes derived from map information and those obtained from historical route corrections.

2.8.1. Setting of the Experiment Scenario

The starting point of the route planning is set as Qingdao Port, and the longitude and latitude coordinates are set as (120.2065° E, 36.0006° N); The route planning endpoint is set at Dongjiakou Port, and the longitude and latitude coordinates are set at (119.7976° E, 35.6060° N).

The water depth data is extracted from the electronic chart to draw a raster map for route planning. To facilitate observation, the water depth threshold is set and different colors are adopted to distinguish. The generated map is shown in Figure 8. Since the grid is relatively small in the map, the grid line is not displayed for the convenience of map effect presentation. The smallest element of the grid is 0.0041°, and due to the characteristics of the Mercator projection, the grid appears as a rectangle with a longer latitude direction and a shorter longitude direction. The map covers areas ranging from longitudes [119.50° E, 121.00° E] to latitudes [35.35° N, 36.15° N]. The blue dot marks the starting point of the route, while the red dot marks the end. The pink dashed line marks the prohibited area, the black dashed line is the navigational track, and the orange dashed line is the equivalent static obstacle line in the area of traffic separation and anchorage.

2.8.2. Introduction of Experimental Ship

“ZHIFEI” (shown in Figure 9) is a container ship with autonomous navigation capabilities. The ship has three navigation modes of manual driving, remote control driving and unmanned autonomous navigation, and can realize the functions of intelligent perception and cognition of navigation situations [44], intelligent collision avoidance [45], automatic berthing and unberthing and remote-control driving. The specific parameters of the ship are shown in

Table 1. Parameters of “ZHIFEI”.

Parameter Name	Value
MMSI	413,286,730
Length (m)	117.15
Width (m)	17.32
Ship Draft (m)	9.90
Designed Speed (kn)	12
Normal Speed (kn)	8
Designed Draft (m)	4.80

.

2.8.3. Experimental Procedure Setting

In the designated experimental scenario, the proposed method was utilized to plan the global route from the specified starting point to the endpoint. Two sets of experiments were conducted, named Exp01 and Exp02, respectively. In Exp01, five historical routes traveled by “ZHIFEI” from Qingdao Port to Dongjiakou Port were respectively adopted as similar historical routes. On top of that, route corrections were made based on the map information to acquire corresponding global routes. In Exp02, no similar historical routes were set. Instead, the global route was generated on the basis of the requirements for route planning and map information, and they were identified by a code name GRoute01. The information from the five historical routes was only utilized in the process of speed planning. Historical route data are collected from the actual navigation data of “ZHIFEI” during commercial operation, which can also be obtained directly from some AIS information service websites. The corresponding numbers of different routes in Exp01 are shown in

Table 2. Route numbers in Exp01.

Historical Route Number	Departure Time	Planned Route Number
HRoute01	6 November 2023 20:12 (UTC+8)	HCRoute01
HRoute02	8 November 2023 18:46 (UTC+8)	HCRoute02
HRoute03	11 November 2023 11:28 (UTC+8)	HCRoute03
HRoute04	13 November 2023 19:20 (UTC+8)	HCRoute04
HRoute05	3 December 2023 09:20 (UTC+8)	HCRoute05

. A portion of the raw data corresponding to historical routes is shown in

Table 3. Some raw data of HRoute01.

$\mathbf{Longitude} (°)$	$\mathbf{Latitude} (°)$	Time	Speed (kn)	$\mathbf{Heading} (°)$	$\mathbf{Course} (°)$
120.1947	35.9963	6 November 2023 20:12 (UTC+8)	1.0	60	56.0
120.1971	35.9976	6 November 2023 20:14 (UTC+8)	4.6	52	53.0
120.2052	36.0038	6 November 2023 20:20 (UTC+8)	7.4	51	49.4
120.2169	36.0112	6 November 2023 20:26 (UTC+8)	7.5	53	52.8
120.2254	36.0169	6 November 2023 20:30 (UTC+8)	7.5	47	48.1
……	……	……	……	……	……
119.8019	35.5993	7 November 2023 03:46 (UTC+8)	6.1	356	357.2
119.8016	35.6030	7 November 2023 03:48 (UTC+8)	4.4	348	351.9
119.8010	35.6045	7 November 2023 03:50 (UTC+8)	2.9	325	332.7
119.7995	35.6058	7 November 2023 03:54 (UTC+8)	1.7	294	301.7
119.7984	35.6062	7 November 2023 03:56 (UTC+8)	1.6	282	282.5

(taking HRoute01 as an example).

3. Results

The experimental results are analyzed from the qualitative and quantitative perspectives. Qualitative analysis focuses on the navigation safety of the route and the conformity between the route and the navigational track. The quantitative analysis focuses on the comparative analysis of the two parameters of voyage distance and duration from perspectives of efficiency and economy.

In Exp01, the effects of different historical routes and corresponding corrected routes are shown in Figure 10, Figure 11, Figure 12, Figure 13 and Figure 14. The global route effect of Exp02 is shown in Figure 15. The green solid line from the beginning to the end of the route represents the historical route, and the red solid line represents the route based on the correction of the historical route, or the route generated based on the map information.

The voyage distance and duration of historical routes and planned routes are calculated respectively, and the results are shown in

Table 4. Statistical results of voyage distance and duration.

Route Number	Voyage Distance (nm)	Voyage Duration (s)	Route Number	Voyage Distance (nm)	Voyage Duration (s)
HRoute01	54.47	28,175	HCRoute01	54.36	28,407
HRoute02	53.53	29,299	HCRoute02	53.86	28,645
HRoute03	53.29	27,967	HCRoute03	54.26	28,135
HRoute04	54.35	30,600	HCRoute04	54.53	28,585
HRoute05	53.89	31,627	HCRoute05	54.4	28,496
GRoute01	53.51	29,259

. The deviation curves of the planned route relative to the historical route in terms of voyage distance and duration are shown in Figure 16.

To further demonstrate the reliability of the proposed global route planning method, we conducted a comparative analysis between the routes obtained by correcting each historical route and the route generated without similar historical routes. On one hand, for visual comparison, we simultaneously displayed the planned routes in the same coordinate system, as shown in Figure 17. On the other hand, for more precise comparative analysis, we employed the Longest Common Subsequence (LCSS) algorithm as a measure of route similarity and used the similarity value as an evaluation metric for the reliability of the planned routes. To facilitate the implementation of the algorithm, the same linear interpolation to all planned routes was applied to ensure that the distance between any two adjacent waypoints on the same route did not exceed 0.5 times the ship’s length (i.e., 58.575 m). In addition, a distance threshold of 7 times the ship’s length (i.e., 820.05 m) was set in the LCSS algorithm. If the distance between a planned waypoint and an actual historical waypoint was less than 7 times the ship’s length, they were considered consistent. The similarity results between the map-based planned routes and the data-corrected historical routes are presented in

Table 5. Similarity results of planned routes.

Route Number	HCRoute01	HCRoute02	HCRoute03	HCRoute04	HCRoute05
LCSS	0.7886	0.9226	0.8908	0.9502	0.8881

.

4. Discussion

4.1. Analysis of Experimental Results

Figure 8 illustrates that the experimental setup aligns with the requirements for simulating coastal navigation scenarios for the ship.

4.1.1. Analysis of Experimental Results for Method’s Validity Verification

As observed from Figure 10, Figure 11, Figure 12, Figure 13, Figure 14 and Figure 15, when planning global routes using the proposed method in this paper, if similar historical routes exist, the global routes derived from correcting the historical routes effectively avoid static obstacles and prohibited areas while considering water depth impacts. Additionally, these routes guide ships to navigate designated water areas along the navigational track according to relative rules. In the absence of similar historical routes, the global routes generated based on map information also achieve comparable results.

It can be seen that, regardless of the existence of similar historical route information, the proposed global route planning method can help to achieve routes that are both safe and compliant with navigation rules.

4.1.2. Analysis of Experimental Results for Method’s Reliability Verification

The reliability verification of the target ship’s global route planning method is mainly achieved through the comparative analysis of two indexes: voyage distance and voyage duration.

It can be seen from Figure 16 that the deviation of the corrected route’s voyage distance relative to that of the historical route does not exceed 2%, which is basically acceptable for the global route planning of ships. According to the statistical results of voyage duration, the value of the corrected route is significantly reduced compared with that of the historical route, or slightly extended but not more than 1%.

As can be seen from Figure 17, the overall trend of planned routes is basically the same, which demonstrates the stability of the proposed method to some extent. As can be seen from Table 5, the routes corrected based on historical routes’ data have a high similarity with those generated based on map information, both higher than 0.78. To a certain extent, it proves that, using the global route planning method proposed in this paper, planned routes are stable and reliable whether there are similar historical routes or not.

In general, the route voyage distance and duration obtained by using the proposed global route planning method are basically in line with the actual navigation law of ships, and the method can provide reliable global route planning results for ships in coastal navigation.

4.2. Limitations and Prospects

Due to the high costs and risks associated with real ship experiments, targeted ship trials were not conducted in this study. Instead, simulation experiments were carried out using historical voyage data of the experimental ship. Furthermore, the simulation environment map is not currently updated in real time, which may be one of the key issues to be addressed in future research.

This study primarily focuses on coastal waters, where the planning of ship speed is relatively approximate due to insufficient consideration of ship dynamic characteristics. The speed planning is mainly estimated based on speed limit regulations, empirical formulas from existing literature, and historical speed values. However, when planning actual routes, more factors such as sea conditions, weather, and the requirement of arrival time should be taken into account for more precise speed planning.

In order to simplify the analysis process and ensure the repeatability of the research as much as possible, the path generation method in this paper only takes the most commonly used A* algorithm as an example to illustrate, and a more suitable algorithm can be selected according to the needs in practical application.

Furthermore, methods such as deep learning, genetic algorithms, reinforcement learning, convolutional neural networks, and others have shown increasingly strong performance in many fields, but they lack sufficient interpretability. However, the human-like thinking method proposed in this paper, while still having some of the aforementioned shortcomings, offers good interpretability and can provide interpretive references for the global route planning of unmanned ships in nearshore waters.

In general, the proposed method for global route planning of unmanned ships in this paper effectively avoids static obstacles and considers the impact of time-varying factors such as water depth, prohibited area, navigational track, and traffic separation scheme on ship navigation. This ensures that the planned routes conform to maritime navigation regulations and common practices, guaranteeing the safety and reliability of global routes. Furthermore, the method proposed in this paper primarily revolves around human-like thinking, thus making it equally applicable to other ships that need to navigate according to nearshore navigation rules. However, adjustments to some parameters may be necessary according to specific ship. However, in this study, the influence of sea conditions and weather factors are not considered. In future research, the impact of sea conditions, weather, and other factors on human thinking during global route planning can be taken into account, leading to a more universally applicable human-like thinking-based method. This will establish a safer foundation for unmanned ship navigation.

5. Conclusions

To enhance the global route planning capability for unmanned ships in coastal navigation, in this paper, a human-like thinking-based method for global route planning is proposed. This method considers time-varying factors and regulations that affect ship navigation, such as water depth, prohibited areas, navigational track, and traffic separation scheme, from the perspective of common practices of seafarers. By extensively referencing historical route information, the proposed method plans global routes for ships engaged in coastal navigation. The effectiveness and reliability of the proposed method are validated by qualitative and quantitative analysis respectively through a case study on the global route planning of the ship “ZHIFEI”. Experimental results demonstrate that the routes constructed by the proposed method strike a balance between safety and economy while satisfying navigational rule requirements to some extent. The research results can provide interpretability references for the global route planning process of unmanned ships.