1   Introduction

Research on intelligent ship route planning technologies has long been the focus of experts and researchers in the field of navigation, and route planning problems have been examined from different perspectives. The melting of Arctic sea ice due to climate change has expedited the opening of new shipping routes through the Arctic Ocean. Lee et al. (2021) proposed the Polar Ice Routing and Risk Assessment System (POLARIS), which is based on risk index calculation that reflects the impact of sea ice on ships. To address the large amount of floating ice and icebergs in the Arctic route, researchers have used the Dijkstra algorithm combined with an ice resistance estimation formula considering the ship scale parameter's impact to establish a multi-objective ship route planning method in polar regions (Wang et al., 2022a; Lv et al., 2022). This method is of great significance for the optimization of navigation routes, saving navigation time and reducing fuel consumption. However, the Dijkstra algorithm has low efficiency and requires excessive memory.

Owing to the influence of special water areas, such as shallow water areas, ships are at high risk of grounding, and current research on grounding accidents still focuses on grounding probability. Liu and Hu (2023) used the artificial fish swarm algorithm (Wei et al., 2022) to plan navigation routes in shallow water areas and combined it with empirical summaries based on ships' navigation patterns to further optimize and adjust the algorithm to enable it to prevent grounding (Chen et al., 2019). However, this algorithm requires rasterization of sea map environments in advance and is thus cumbersome and computationally intensive. Research on autonomous ground vehicles and intelligent ships is closely related. Kim (2022) proposed a fast route planning algorithm that considers T-shaped terrain information and validated its effectiveness by comparing it with the RRT* algorithm; they found that the time efficiency of suboptimal routes is high when terrain information is considered.

To address the ship's route planning problem in complex routes, Wang et al. (2020) considered the maneuvering characteristics of ships and established a ship turning and deceleration model; they then proposed a dual-cycle genetic algorithm for detecting irregular polygon boundaries; it was based on the quad-tree method and considered ship maneuvering constraints; the algorithm achieved efficient and feasible solutions for the dynamic programming of ship routes. Han et al. (2023) proposed a solution based on the multiscale A* algorithm, Reeds-Shepp curves (RSC), and online double-s trajectory planning, considering factors such as ship position, heading, and speed for easy integration with control algorithms. Liu et al. (2022) proposed a ship route planning algorithm based on the field theory ‒ improved PE-A* algorithm, which uses potential energy fields to address nonlinear constraints, such as obstacle restrictions and safety depth limits, and enhances route planning effects. Zhang et al. (2022) proposed a two-stage pathplanning algorithm based on rapid search random trees that consider ship maneuvering constraints and Convention on the International Regulations for Preventing Collisions at Sea (COLREG) restrictions to find satisfactory paths, but there is still room for improvement.

To further optimize the Rapidly-exploring Random Trees (RRT) algorithm, Ning et al. (2022) designed an improved RRT algorithm that embeds Dijkstra's algorithm; the algorithm resulted in shorter flight paths than the traditional RRT algorithm but required a longer path planning time. Cao et al. (2022) proposed a method to improve the RRT algorithm for inland waterway navigation and used cutting, smoothing, and safety reservation methods; the method achieved a higher fitting degree than the minimum residual error method. To accelerate the node generation speed of the RRT algorithm and reduce the path planning time, a bidirectional sampling RRT-Connect algorithm was proposed, which gradually constructed two fast-searching random trees based on starting and target configurations and explored the space until it found a feasible flight path (Kuffner and LaValle, 2000; Jhong and Chen, 2022). Jang and Kim (2022) proposed the RRT* algorithm that used a specified space to shorten flight paths and planning time. Wang et al. (2022b) proposed the RRT-FN path-planning algorithm that improved the Bézier interpolation method based on target – bias extension; the algorithm randomly selected target‒bias with a certain probability when an initial path was not found; after determining the initial path, the algorithm used heuristic sampling to improve the guidance of path planning and solve problems, such as path distortion, weak directionality, slow convergence speed, and poor smoothness (Wang et al., 2022b; Tan et al., 2021). Qiu et al. (2022) proposed an F-RRT algorithm based on the target– bias strategy and angle restriction to address high randomness, poor directionality, slow convergence speed, poor smoothness of path twisting, and tracking problems.

In recent years, some studies on path optimization have extremely focused on offline planning and overlooked the real-time nature of ships. Zaccone (2021) studied the problems in optimal ship path planning from the perspective of real-time applications and proposed an RRT* based optimal path planning algorithm; navigation collision avoidance, path feasibility, and optimality issues were discussed, and the algorithm needs to be improved in terms of route planning efficiency. Although the technology of route planning has become increasingly mature and sophisticated over time, new algorithms have emerged in the direction of intelligent ship route planning in recent years, such as route planning algorithms that simultaneously determine trajectory and speed, multi-objective weather routing algorithms based on hybrid particle swarm optimization, genetic algorithms with improved particle swarm optimization, multiscale Visibility Graph (VG) algorithms, and RA-RRT* algorithm (Lee et al., 2018; Zhao et al., 2022; Zhao et al., 2021; Wu et al., 2021; Muhammad and Zhou, 2023).

Although the above algorithms can complete route planning tasks, they still have some shortcomings in planning efficiency. Intelligent ships urgently need an algorithm that can significantly improve the speed and efficiency of route planning and enable the ships to cope with planning requirements. This paper proposes an adaptive step size InformedRRT* algorithm, which can restrict the sampling space according to known information during the random tree exploration after a simple, feasible path is obtained. Additionally, it can increase the probability of sampling points that have a positive effect on the search tree by utilizing the special properties of elliptical geometry. The improved sampling function greatly enhances the expansion efficiency of the search tree. When a ship encounters complex waterways with concave-convex or narrow straits and multiple obstacles, a unique adaptive step size mechanism enables this algorithm to offset the limitations of search tree expansion in complex environments. In complex environments, the improved algorithm has a strong search ability and is robust.

This article is organized as follows: Section 2 introduces the expansion of a search tree and the principle of the dynamic optimization of known routes. Section 3 describes the principle of the Informed-RRT* algorithm's restriction of the sampling space and the mechanism for selecting adaptive step sizes. Section 4 discusses the simulation experiments to simulate ship route planning and validate the algorithm's performance. Section 5 discusses the advantages, limitations, and prospects of the algorithm. Section 6 summarizes the contributions and conclusions of this article.

2   Principle and improvement of the RRT algorithm

2.1   Sampling and exploration principle of the RRT algorithm

The RRT algorithm is a path planning algorithm based on sampling and incremental growth and was first proposed by Lavalle and Kuffner (1999). It has high coverage and wide search space and does not require system modeling. Through continuous sampling and node expansion, the algorithm can gradually search unknown areas and approach a target node until a feasible route is found.

The steps involved in the RRT algorithm can be summarized as follows: First, the random tree T, start position x_start, goal position x_goal, step length step, and other initial data are defined. Second, a random sampling point x_rand is generated. Third, xrand is considered the target point, and all the leaf nodes in the tree are traversed. The distance between x_rand and the leaf node is calculated, and the node with the minimum distance is selected as x_near. Then, a new node x_new is added to the tree, connecting x_near and x_rand with a branch of step length step. The position of the new node x_new is determined by the step length step, the nearest node x_nearest, and the random sampling point x_rand. The calculation method for inserting a new node into the tree is defined in Equation (1).

In the fourth step, the path between node x_near and node x_new is checked. If no obstacle is present, node x_new is added to the random tree T. Otherwise, node x_new is discarded, and the search process starts over. The expansion of the tree continues in a loop, following the above procedure until the new node x_new reaches the target position x_goal within a certain range and is successfully connected to the target position, generating a feasible path. The process of expanding the tree is shown in Figure 1 (Zhong et al., 2022).

Figure  1  RRT node expansion process

Download: Full-Size Img

Given that the RRT algorithm does not perform any optimization or evaluate any cost function, it only generates trajectories that satisfy constraints. Therefore, it can produce convoluted and illogical paths. Additionally, the resulting path is often only feasible and not necessarily optimal because of the random nature of sampling in RRT. However, this feature enables the RRT to run quickly. The RRT algorithm is extremely useful when path feasibility and computational speed are the only two important concerns.

2.2   Asymptotically optimal and improved RRT* algorithm

In practical ship route planning, the requirements often go beyond having a feasible route. Intelligent ships prioritize several factors, such as route length and safety, when selecting a route. Thus, a simple RRT algorithm, which only generates feasible paths, cannot fully meet the needs of ship route planning. Comparatively, the RRT* algorithm, which can find an optimal feasible route and generate an asymptotically optimal route, is more suitable for ship route planning. Its main feature is that it quickly finds an initial path. The number of sampled points and coverage range of random numbers increase as the algorithm iterates. The algorithm continuously optimizes a current route until a satisfactory route is obtained, and the longer the iteration time is, the more satisfactory the path will be (Zaccone and Martelli, 2019). The key processes that upgrade the basic RRT algorithm to the asymptotically optimal RRT* algorithm are the two re-computation processes for the new node x_new: the re-selection of a parent node process and the rewiring process of the random tree.

The selection of a new parent node for x_new proceeds as follows: All nodes whose distances to a new node x_new are shorter than a certain threshold are obtained by traversing the entire tree. These nodes are added to a list, which is no longer used to store the distance to the starting point. The list stores the distance from x_new to a starting point when a node is set as the parent of x_new. Finally, the node with the smallest distance in the list is selected, and its corresponding node is set as the parent of x_new. This process is illustrated in Figure 2.

Figure  2  Rewrite of a random tree

Download: Full-Size Img

The process of rewiring the random tree proceeds as follows: after a new parent node for x_new is selected, the random tree is further optimized by rerouting the tree, and the cost of connecting nodes in the tree is minimized. In this rerouting process, if a change in the parent node of a neighboring node to x_new can reduce the path length, then the change is implemented. The purpose of this process is to check whether the path cost of some nodes can be reduced by rerouting after a new node is generated. From a global perspective, not every rerouted node appears in the final generated path. However, in the generation of a random tree, each rerouting attempt maximizes the chance of reducing the path cost. The rerouting of a random tree is illustrated in Figure 3.

Figure  3  Rerouting of a random tree

Download: Full-Size Img

By continuously evaluating and adjusting the distances among nodes on the random tree, the RRT* algorithm can further optimize the known optimal route as the number of iterations increases. Node expansion and the principles of the RRT* algorithm are shown in Figure 4 (Chen, 2021).

Figure  4  RRT* node expansion

Download: Full-Size Img

Node x_start represents the starting point of ship route planning and the initial node of the random tree. Node x_rand is the sampled node obtained by the algorithm through random sampling, and node x_near is the nearest node to the random sample point in the random tree obtained from the last iteration. Moreover, Ɛ is the fixed step length of the expansion of the tree. Node x_new is the new expanded node of the algorithm, where p (p > 0) is the radius of the exploration range of the algorithm's neighboring nodes. Nodes x_neighbor1 and x_neighbor2 are the neighboring nodes within the circle centered on x_new with a radius of p. After collision detection, the algorithm grows a new node x_new toward the direction of sampled point x_rand with a step size of Ɛ and checks nearby points within the circle with a radius of p. Whether a new parent node is selected, or the random tree is rewired is determined. Afterward, a new node (x_new) is added to the nodes of the random tree, and the next round of sampling work begins.

3   Optimization of the algorithm by sampling and step setting

3.1   Introduction of the informed-RRT* algorithm

Owing to the special properties of the RRT* algorithm, its sampling function continues to perform uniform sampling in the entire map space after a feasible path is found. During the operation, some sampling points have no positive effects on path planning. Especially in a large path planning environment, extensive sampling imposes a computational burden on the computer and increases the solution time, thereby reducing the efficiency of the algorithm.

To address redundant sampling caused by traditional algorithms, the Informed-RRT* algorithm improves the sampling process for seeking an optimal path, considerably reducing the time and space waste caused by unnecessary sampling (Gammell and Srinvivasa, 2014). Informed-RRT* is an improved version of the RRT* algorithm and maintains the same completeness and optimal probability as RRT* while being superior to RRT* in terms of convergence speed, final solution cost, and ability to discover difficult passages. This algorithm is not fully dependent on the state dimension and range of planning problems and is suitable for various cases of route planning problems (Gammell et al., 2018).

The basic idea of the Informed-RRT* algorithm is to avoid the use of the traditional sampling function for sampling work after the first feasible path is obtained. Instead, an elliptical sampling region is constructed according to the positions of the start and goal points and the length of the current shortest path. The sampling range of the sampling function is then restricted within this region. As the search tree continuously prunes paths, the restricted elliptical sampling region gradually shrinks, and the probability of sampling points with a positive effect on path planning increases. This approach substantially reduces the time cost of path planning while balancing path quality and planning efficiency.

3.2   Optimization of the algorithm by limiting the sampling space

The principle used in limiting the sampling space is based on the starting position, target position, theoretical optimal path length under unobstructed conditions, and current optimal path length. The range of the sampling space is determined. The restricted elliptical sampling area is defined by Equation (3).

The specific restriction process is to define an ellipse by using the starting position x_start and goal position x_goal as the two foci, the theoretical minimum length of the optimal path c_min as the focal length, and the current optimal path length as the length of the major axis of the ellipse. The length of the minor axis is defined by Equation (4).

According to the properties of the ellipse, the sum of the distances from any point on the ellipse to the two foci is equal to the length of the ellipse's major axis, c_best. Let f (x) be the sum of the distance costs from a new node c_new added to the random tree to nodes x_start and x_goal, and let X be the set of sampling points outside the ellipse. Whenever a sampling point appears outside the ellipse, it must satisfy the following condition:

Sampling and expanding new nodes outside the elliptical range are meaningless when short flight paths are used. By restricting the sampling range of sampling points, the time cost of calculating invalid sampling points can be directly reduced, and the wastage of computing resources is prevented. When no feasible path is found in the initial state, the Informed-RRT* algorithm that restricts the sampling space has the same operating process as the traditional RRT* algorithm. If any feasible path from the starting position x_start to the goal position x_goal is found, the sampling space will be restricted to the elliptical region shown in Figure 5 (Jin et al., 2023).

Figure  5  Schematic diagram of an ellipse sampling space

Download: Full-Size Img

The sampling principle is to first randomly sample from a standard equation and then rotate and translate the obtained sample point to the actual sampling region by using two parameters: a translation vector and a rotation matrix. The transformed coordinates can be expressed as follows:

where [x, y]^T is the coordinate in the standard equation, [x', y']^T is the transformed actual coordinate obtained by rotating and translating the sample point using two parameters, the rotation matrix R that represents the angle between the line connecting the start and goal points and the x-axis, and the translation vector T.

As the algorithm iterates, whenever a short path is found, the value of the optimal path length c best is updated, which in turn affects the length of the major axis of the ellipse. The sampling range is then restricted to the new ellipseshaped sampling space, and sampling is performed in the new sampling area. The complete process of converting the coordinates of the sampling points can be expressed using Equation (8).

According to the algorithmic characteristics of InformedRRT*, the shorter the length of the optimal route c_best obtained as the algorithm iterates is, the further the elliptical sampling space is restricted and narrowed until the iteration stops and the optimal route is found.

In an environment without obstacles, the path between x_start and x_goal continues to decrease until it becomes a straight line between the two points as the algorithm iterates a certain number of times. The sampling space then approximates to a line. The change in the sampling space after iteration in an obstacle-free environment is shown in Figure 6.

Figure  6  Iteration process of Informed-RRT* algorithm

Download: Full-Size Img

During the sampling process, the algorithm separates the elliptical sampling space S_ellipse from the planning space S according to the current information.

The sampling function returns independent and identically distributed samples from the defined sampling state space S_ellipse, attempting to reduce the cost of the shortest path from node x_start to node x_goal that includes x_new to less than the current shortest path cost c_max, thus further reducing the sampling space.

3.3   Optimization of algorithm by adaptive step size

The marine environment is complex, and ships are easily affected by prohibited zones, shallow areas, and harsh weather when sailing on the high seas. Thus, they hardly avoid encountering relatively complex waters. Owing to the randomness of the RRT algorithm, its ability to handle narrow waterways is relatively weak. A long step size inhib‐its the algorithm from allowing a ship to pass through narrow waterways during the growth and exploration of a random tree, whereas a short step size will make the ship's growth extremely slow in a vast sea, wasting a substantial amount of time and computational cost for route planning. Traditional RRT algorithms encounter some problems when applied to complex water environments. Dynamic selection and the adjustment of an algorithm's step size can solve these problems, and adaptive step size can be introduced, which effectively addresses the special requirements of different environments for the algorithm's step size (Zhang et al., 2019).

The key processes for determining an adaptive step size are selecting an initial step size according to the characteristics of an environment for route planning and using the defined initial step size during the growth and exploration of a random tree. Then, the step size is continuously adjusted until an ideal route is found during expansion. The selection of the initial step size during the growth of the RRT algorithm is often influenced by factors such as the distance between the initial and target points, number of obstacles, and ratio of the obstacle area to the total area. By integrating multiple influencing factors through comprehensive analysis, the impact of the initial step size selection on the algorithm can be reflected in the comprehensive weight parameter w₁, as shown in Equation (10).

Msize represents the total area of the navigation environment, w₁ is a comprehensive impact parameter, and $\left\lfloor M_{\text {size }} \times w_1\right\rfloor$ indicates rounding down the value of M_size×w₁. The initial step length of the algorithm, stepinit, is calculated using the above method.

The w₂ in the equation is the step size adjustment coefficient. The extension step size, step, is dynamically adjusted during the growth process of the RRT until the optimal route is found and the algorithm terminates. As the algorithm extends toward the goal, it adapts the step size according to the size of the sampling range, increasing the efficiency of the sampling process (Yu et al., 2022).

4   Simulation experiment and result

4.1   Experimental pretreatment

To validate the feasibility of the improved InformedRRT* algorithm with adaptive step size and to demonstrate the planning effect of ship route planning more intuitively, an experiment was designed to verify the planning effect of the algorithm on ship route planning. The experiment was conducted in a sea area located at 29°50ʹN and 120°10ʹE. The experimental environment is shown in Figure 7.

Figure  7  Schematic diagram of the sea area (120°1ʹE, 29°5ʹN)

Download: Full-Size Img

The simulation experiment selected a part of the sea chart in the target sea area as the environment background for the route planning experiment. The experimental environment contains many islands and pieces of land that can thus be used in verifying the obstacle-avoidance effect and route reliability of the algorithm. In the first step, a sea area of 1 000 nautical miles×1 000 nautical miles was selected as the experimental environment and a relative coordinate system was established on the chart. An image recognition technology is needed to preprocess sea chart data and convert it into a grayscale image. These processes facilitate route planning. Using grayscale values helps to distinguish among land, islands, and shallow water areas with shallow depths and to determine a ship's navigable area. The search tree is expanded in the navigable area.

4.2   Verification experiment simulation and analysis

The feasibility of the Informed-RRT* algorithm with adaptive step size in intelligent ship route planning is verified. The relative coordinates of the starting and destination points are defined as (100, 100) and (500, 500), respectively. The adaptive step size Informed-RRT* algorithm is used for ship route planning experiments. The experimental results are shown in Figure 8.

Figure  8  Planning results of adaptive step size Informed-RRT* algorithm

Download: Full-Size Img

The experimental results show that the Informed-RRT* algorithm successfully planned a navigable path for a ship for the first time after 331 iterations. The optimal path length is 767.902 7 nautical miles (Figure 8(a)). Once the algorithm finds any navigable path, it restricts the sampling function to the ellipse defined by the known information (Figures 8(b)‒8(f)).

As the algorithm iterates, the coverage and exploration range of the random tree gradually increase, and the instantaneous optimal path is shortened. Thus, the sampling space is restricted to a small ellipse range. The positive effect probability of the sampling points increases and improves the efficiency of the algorithm. As the algorithm iterates, the search tree gradually covers the entire ellipse sampling area until the optimal path is obtained. The resulting optimal path obtained by the algorithm is shown in Figure 9.

Figure  9  Optimal result of route planning

Download: Full-Size Img

The optimal path obtained by the proposed algorithm is shown in Figure 9. After avoiding obstacles such as islands, land, and shallow water areas, a smooth and shortest path is obtained. It can be concluded that the optimal path achieves the expected effect of intelligent ship route planning. The relationship between the number of algorithm iterations and the length of the optimal path is shown in Figure 10.

Figure  10  Relationship between the number of iterations and the course length

Download: Full-Size Img

The length of the planned route gradually decreases with the increasing number of iterations (Figure 10). The optimization effect is particularly large before 400 iterations, and a good optimization effect is found between 400 and 800 iterations. After 800 iterations, the length of the route gradually stabilizes to its optimal value. The experimental results demonstrate that the length of the route planned by the adaptive step Informed-RRT* algorithm gradually converges to an optimal value as the exploration range and coverage of the search tree gradually increase.

5   Discussion

5.1   Comparative experimental simulation

In route planning for an intelligent ship, a route planning algorithm is often evaluated from the perspectives of route length, planning time, route safety, and computational resources required for the calculation to show the differences among different algorithms. To accurately reflect the actual situation of route planning, this study selected a complex sea area as the experimental environment for the comparative experiment. Traditional sample-based route planning algorithms were selected for result comparison. As the RRT family of algorithms is a sample-based algorithm, route planning is more random than traditional intelligent and traversal search algorithms, and the processing speed increases. Thus, it is unsuitable for comparison. Therefore, RRT, RRT*, and Informed-RRT* algorithms were mainly selected for comparative experiments. The sea area of 750 nautical miles×1 000 nautical miles was selected as the experimental environment with a relative coordinate system, and the relative coordinates of the route planning starting point were defined as (300, 300). The relative coordinates of the destination were defined as (500, 500). RRT, RRT*, and other algorithms were used to plan the ship's route, and the evaluation of various indicators of the experimental results was used in the assessment of the advantages and disadvantages of the improved algorithm. In the current experimental environment, the effect of random tree expansion affected by the environmental boundary range decreases, thereby reflecting the characteristics of the algorithm.

In this experiment, the RRT algorithm was used for path planning with a step size of 40 nautical miles and a detection range of 80 nautical miles near the target. The algorithm took 2.539 4 s to run, expanded 74 nodes, and iterated 287 times, resulting in a path length of 508.245 6 nautical miles. The experimental results of the RRT algorithm are shown in Figure 11.

Figure  11  Simulation results of RRT algorithm

Download: Full-Size Img

In the experiment of intelligent ship route planning using the RRT* algorithm, the step size is set at 40 nautical miles, and the detection range near the target is set at 80 units in length. The maximum iteration number of the program is set at 3 000. The algorithm running time for route planning is 27.602 2 s, and the number of expanded nodes is 566. The optimal route is obtained after 2 358 iterations, and the length of the optimal route is 343.631 1 nautical miles. The simulation results of the RRT* algorithm are shown in Figure 12.

Figure  12  Simulation results of RRT* algorithm

Download: Full-Size Img

When the Informed-RRT* algorithm is used for intelligent ship route planning, the step size is 40 nautical miles, and the detection range is 80 units around the target. The program is set at a maximum of 2 000 iterations for route planning. The runtime of the algorithm is 25.692 27 s, the number of expanded nodes is 395, the optimal route is obtained at 1 857 iterations, and the optimal route length is 340.220 5 nautical miles. The simulation result of the Informed-RRT* algorithm is shown in Figure 13.

Figure  13  Simulation results of Informed-RRT* algorithm

Download: Full-Size Img

Figure 13(a) shows the state of the algorithm after 735 iterations when the algorithm found a feasible route for the first time. The route is 423.181 8 nautical miles long. Figures 13(b)-13(d) show the iterative process of the algorithm as the coverage of the search tree expands and the optimal route shortens. Figures 13(e) and 13(f) show how the step size of the search tree is continuously adjusted to cover narrow straits in the map with a short step size after 1 415 iterations. This process results in a new optimal route that is approximately 12% shorter than the original route and passes through the strait.

The Informed-RRT* algorithm with adaptive step size was used for the ship route planning experiment, and the maximum iteration was 2 000. The experimental result is shown in Figure 14. The algorithms used in the planning of a dynamically optimal route are RRT*, Informed-RRT*, and Informed-RRT* with adaptive step size. The comparison of the optimal route results obtained by route planning is shown in Figure 15.

Figure  14  Simulation results of Adaptive step size Informed-RRT* algorithm

Download: Full-Size Img

Figure  15  Comparison of optimal route planning results

Download: Full-Size Img

To demonstrate the superiority or inferiority of the proposed algorithm to the other algorithms, important indicators for evaluating the quality of the algorithm, such as planned course length, number of iterations, number of convergent iterations, and run time, were summarized from all the comparative experiments above. The experimental data are shown in Table 1.

Compared with the RRT algorithm, RRT* algorithm, and Informed-RRT* algorithm, the adaptive step size InformedRRT* algorithm can find the optimal path with fewer iterations under the same computational scale and is thus more suitable for ship route planning technologies for intelligent ships.

5.2   Shortcomings and prospects

When ships navigate in complex ocean environments, they are subject to many interfering factors that often result in poor maneuverability. The optimal route for a ship must consider the economic feasibility of a route. Thus, the smoothness of a route and the maximum steering angle should be considered when planning routes for intelligent ships. Frequent steering to pursue the shortest route increases fuel consumption and is thus counterproductive to route planning. Therefore, researchers often try to use methods to keep planned routes as straight as possible. However, the shortcoming of this research is that it focuses mainly on planning short route lengths without comprehensively considering the economic feasibility of the route.

As intelligent ships continue to develop at an increasing pace, unmanned ships will become common in various waters. To meet the needs of route planning for unmanned ships, the development of dynamic programming technology is imperative. The algorithm proposed in this research can produce optimal routes after a few iterations. If applied in the field of dynamic route planning, it may have good planning effects, and it has a certain reference value for experts and researchers in the shipping industry.

6   Conclusions

In intelligent ship route planning, the traditional RRT algorithm produces routes with poor quality, whereas the improved RRT* algorithm sacrifices algorithm speed for high-quality routes. The improved Informed-RRT* algorithm reduces the time cost of algorithm sampling and increases solution speed, but improvements are still needed. This paper discusses the route planning problem for intelligent ships navigating ocean environments and proposes an efficient and suitable route planning algorithm, the adaptive step size Informed-RRT* algorithm, which optimizes step size selection based on the regular Informed-RRT* algorithm.

By comparing and analyzing the results of traditional route planning algorithms, the improved algorithm not only ensures a short planned route length but also reduces the number of sampling points and the time required for planning. Compared with the fixed-step Informed-RRT* algorithm, the adaptive-step Informed-RRT* algorithm reduces the optimal route length by approximately 13.05%, speeds up the planning algorithm by approximately 4.64%, and avoids approximately 23.64% of the sampling nodes, achieving fast route planning while planning a short route. Additionally, the unique adaptive-step mechanism solves the problem of search tree expansion limitations when intelligent ships encounter complex waterways with multiple obstacles. The research results indicate that this algorithm is suitable for intelligent ship route planning work, and it is beneficial to the development of intelligent navigation in the field of intelligent ships. It has a certain reference value for the dynamic route planning of unmanned ships and promotes research in the field of intelligent ship route planning.