Path Planning of Unmanned Surface Vehicle Based on Improved Sparrow Search Algorithm

Abstract

In order to solve the problem of many constraints and a complex navigation environment in the path planning of unmanned surface vehicles (USV), an improved sparrow search algorithm combining cubic chaotic map and Gaussian random walk strategy was proposed to plan it. Firstly, in the population initialisation stage, cubic chaotic map was used to replace the random generation method of the traditional sparrow search algorithm to optimise the uneven initial distribution of the population and improve the global search ability of the population. Secondly, in the late iteration of the algorithm, the standard deviation of fitness is introduced to determine whether the population is trapped in the local optimum. If true, the Gaussian random walk strategy is used to perturb the optimal individual and assist the algorithm to escape the local optimum. Thirdly, the chosen water environment is modelled, and the navigation information of the original inland electronic navigation chart (ENC) is preprocessed, gridised, and the obstacle swelling is processed. Finally, the path planning experiments of USV are carried out in an inland ENC grid environment. The experimental results show that, compared with the traditional sparrow search algorithm, the average fitness value of the path planned by improved sparrow search algorithm is reduced by 14.8% and the variance is reduced by 49.9%. The path planned by the algorithm is of good quality and high stability and, combined with ENC, it can provide a reliable path for USV.

1. Introduction

The application of unmanned ships in water transportation, environmental monitoring, life saving, cluster investigation, and other fields is gaining popularity [1]. The key to research in unmanned ship technology lies in the three dimensions of navigation, control, and perception. Navigation is the technology used to approach or avoid obstacle targets [2], and the path planning link in the navigation section is especially crucial. Unmanned ship path planning refers to the planning of a path for an unmanned ship to reach a target point in accordance with a provided map and target points [3].

Existing algorithms for the study of the unmanned ship path planning problem include the A* algorithm, artificial potential field method, reinforcement learning method, and bionic class algorithm [4]. Each of these algorithms has its own advantages for solving the unmanned ship path planning problem and, by improving the traditional algorithms, researchers have achieved good application results under specific conditions [5], expanded the A* algorithm node search from 8 neighbourhoods to 24 and 48 neighbourhoods to obtain the global optimal solution in a larger optimisation space and make the path smoother [6], proposed a new artificial potential field function and added the escape force factor based on Krogh’s research, which solved the problems of local minima and unreachability of the target in the traditional artificial potential field method [7], solved the problem of local minima and unreachability of the target by improving the gain parameter of the potential field of Q-Learning reinforcement learning algorithm, improving the problem of high sensitivity of the parameter to the algorithm and enhancing the algorithm path planning performance [8] based on the traditional ant colony algorithm considered the uneven distribution of initial pheromone, introduced the weight factor, and improved the ant colony information update rule and other methods to solve the problem that the algorithm easily falls into the deadlocked path. The previously mentioned ant colony algorithm is a type of bionic algorithm, and scholars have proposed a number of similar group intelligence algorithms by analysing the behaviour of biological communities in nature, including the grey wolf algorithm, the ant colony algorithm, the whale optimisation algorithm [9,10,11], and the sparrow search algorithm.

The sparrow search algorithm is a new population intelligence algorithm proposed by [12] in 2020. It was discovered that the algorithm outperformed the grey wolf algorithm and its equivalent type of algorithms in terms of finding accuracy, robustness, and convergence speed, and the standard test function finding results demonstrated the algorithm’s superior performance [13]. Currently, the algorithm has been effectively applied to the 3D UAV trajectory optimisation problem [14], but no research has been conducted on the unmanned ship path planning problem, so a method based on the improved sparrow search algorithm is proposed: first, cubic chaotic mapping is used to initialise the population instead of the traditional algorithm’s random generation method; then, the fitness standard deviation is introduced in the final iteration of the algorithm to determine if the population is stable. Then, in the final iteration of the algorithm, the standard deviation of fitness is introduced to determine whether the population is trapped in the local optimum, and a Gaussian random wandering strategy is used to perturb the optimal individuals to aid the algorithm in escaping the local optimum; then, the selected water environment is modelled and the original electronic route map is preprocessed, gridised, and obstacle expansion processed; finally, the enhanced algo is implemented. Compared with the traditional sparrow search algorithm, the optimal fitness value is reduced by 11.49%, the number of inflection points is reduced by 72.7%, and the average fitness value is reduced by 7.92%.

The sparrow search algorithm is an intelligent algorithm based on the foraging and antipredation characteristics of the sparrow population, which classifies sparrows into three categories: discoverers, followers, and observers. The explorers seek sustenance for the populace and direct the foraging efforts of the followers. The following is the iterative formula for the discoverers:

(1)$X_{i,j}^{t+1}=\left\{\begin{array}{c}{X}_{i,j}^t\cdot \exp \left(\frac{-i}{\alpha \cdot {\mathit{iter}}_{\max }}\right),\hspace{1em}{R}_2<s_f\\ X_{i,j}^t\cdot R\times \mathit{\lambda },\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} R_2\ge s_f\end{array}\right.$

where t is the current iteration number, X_i,j is the position information of the first sparrow population in the first dimension, $\alpha \in rand(0, 1)$, iter_max is the maximum number of iterations, R is a random number obeying a normal distribution, $\mathit{\lambda }$ is a 1 × d matrix with all elements equal to 1, d is the dimension of the unmanned boat path planning problem, $R_2\in (0, 1)$ is the warning value of the sparrow population position, and $s_f\in (0.5, 1)$ is the safety value of the sparrow population position.

When $R_2<s_f$, it indicates that there is no danger in the current foraging environment; when $R_2\ge s_f$, it indicates that there is danger in the current foraging environment that needs to be signalled and all sparrows must leave their current position and fly to a secure area. During the foraging process, the followers act in accordance with the seeker, and, when the finder discovers a superior food source, the followers compete with it; if successful, they receive the finder’s food. Followers update their position based on the following equation:

(2)$X_{i,j}^{t+1}=\{\begin{array}{c}R\cdot \exp \left(\frac{X_{\mathrm{worst}}^t-X_{i,j}^t}{i^2}\right),\hspace{1em}\hspace{1em}i>n/2\hfill \\ X_p^{t+1}+|X_{i,j}^t-X_p^{t+1}|\cdot {\mathit{A}}^{+}\cdot \mathit{\lambda },\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\hfill \end{array}$

where X_p is the optimal population position, X_worst is the worst population position, A is 1 × d matrix, each matrix cell is random-1 or 1, and A⁺ = A^T(AA^T)⁻¹. When $i>n/2$, the i-th follower cannot find sustenance and must seek it elsewhere by flying. The function of scouts in sparrow populations is to be aware of danger and lead the population to a secure area, accounting for 10–20% of the total population. The iterative formula for generating the random locations of spies within the population is shown in the following equation.

(3)$X_{i,j}^{t+1}=\{\begin{array}{c}{X}_{\mathrm{best}}^t+\beta \cdot |X_{i,j}^t-X_{\mathrm{best}}^t|,f_i>f_g\\ X_{i,j}^t+k\cdot \left(\frac{|X_{i,j}^t-X_{\mathrm{worst}}^t|}{(f_i-f_w)+\xi }\right),f_i\le f_g\end{array}$

where X_best is the current global optimal position, β is a step control parameter that follows the standard normal distribution, $k\in [-1, 1]$ indicates the direction of individual movement, f_i is the current sparrow fitness value, f_g is the global optimal fitness value, f_w is the global worst fitness value, and $\xi$ is a constant to prevent the denominator from being zero. $f_i>f_g$ demonstrates that the sparrow is at the edge of the population and vulnerable to external attack; $f_i\le f_g$ demonstrates that the scout is aware of the threat and must abandon the current location.

2. Improved Sparrow Search Algorithm

2.1. Cubic Chaotic Map

In comparison to other swarm intelligence algorithms, the sparrow search algorithm has superior performance. However, when solving complex optimisation problems such as unmanned ship paths, there are still issues such as slow convergence speed, reduced population diversity in the late iteration period, and a tendency to converge to local optimal solutions [15]. Taking into account the stochastic and ergodic characteristics of chaos, when the sparrow population is initialised, the majority of scholars use logistic mapping to ensure the population distribution is uniform [16]. This paper proposes replacing the stochastic generation of the sparrow search algorithm with cubic chaotic mapping to improve the algorithm’s global search performance and avoid premature convergence. The formula for cubic chaotic mapping is as follows:

(4)$c_{n+1}={\rho }_{c_n}(1-c_n^2)$

where −1 < c_n < 1, c_n ≠ 0, n = 0,1,2, …, n; $\rho$ is a control parameter. To analyse the effect of the value of $\rho$ taking on the chaotic value c_n, the simulation is conducted, and the empirical initial value c₀ = 0.315 with a step size of 0.01 is used to acquire the chaotic results shown in Figure 1.

Based on Figure 1, when $2.595\le \rho \le 3$, the chaotic value c_n has a reasonable random distribution effect, taking the extreme value $\rho$=2.595, 0 < c_n < 1, and the number of iterations is 2000; Figure 2 displays the results of the sequence distribution of cubic chaotic mapping. Figure 2 demonstrates that the cubic chaotic mapping possesses excellent uniform distribution characteristics.

The cubic chaotic mapping establishes the sparrow population in the manner described below. The sparrow population consists of N d-dimensional sparrows and generates N d-dimensional vectors C_d before applying Equation (5) to map C_d to individual sparrows:

(5)$X_d^{\mathrm{new}}={\min }_d+\left({\max }_d-{\min }_d\right)\cdot C_d$

where max_d and min_d are the maximum and minimum values of dth dimensional variable $X_d^{\mathrm{new}}$. The results of $X_d^{\mathrm{new}}$ obtained from cubic chaotic mapping are used as the initial population sequence of the sparrow search algorithm, which improves the initial global search capability of the algorithm.

2.2. Gaussian Random Wandering Strategy

The sparrow search algorithm will exist in the late iteration of the local optimum; for this problem, this paper proposes the use of a Gaussian random wandering strategy. First, the concept of fitness standard deviation is introduced to determine whether the sparrow population falls into the local optimum.

(6)$\sigma =\sqrt{\frac{{\displaystyle \sum _{i=1}^N{\left(f_i-f_a\right)}^2}}{f}}$

where f_a is the mean of the overall fitness of the sparrow population, f is the control parameter of the standard deviation $\sigma$, and the value of f is as follows:

(7)$f=\{\begin{array}{c}\max \left\{\left|f_i-f_a\right|\right\},\hspace{1em}\max \left\{\left|f_i-f_a\right|\right\}>1\\ \hspace{1em}\hspace{1em} 1\hspace{1em}\hspace{1em} ,\hspace{1em}\max \left\{\left|f_i-f_a\right|\right\}\le 1 \end{array}$

If the difference between the standard deviation of fitness $\sigma$ before and after is less than the specified value of 10⁻³, the population is considered to have fallen into a local optimum during the iterative process. The Gaussian random walk strategy is then used to perturb the best individual of fitness f_i in the sparrow population in order to help the algorithm jump out of the local optimum. The equation for the generation of new sparrow individuals is shown in the following equation:

(8)$X_i^{t+1}=Gauss\left(X_i^t,\left(-{\left(\frac{t}{ite{r}_{\max }}\right)}^2+1\right)\cdot \left(X_i^t-X_r^{\mathrm{new}}\left(t\right)\right)\right)$

where $X_r^{\mathrm{new}}$ is the random individuals in the new sparrow population and iter_max is the maximum number of iterations and uses the property that the convex function decreases in the first quadrant: as the number of iterations t increases, the perturbation is gradually reduced. The coarse search and fine search capabilities of the algorithm are balanced.

2.3. Improved Sparrow Search Algorithm Implementation Process

The flow of the improved sparrow search algorithm is shown in Figure 3.

According to the implementation flow chart of the improved algorithm, the pseudo-code implementation is as follows (see Algorithm 1):

Algorithm 1 Modified Sparrow Algorithm

int main(void) { %cubic chaotic map initializes N sparrows and their related parameters; N,itermax,d,Xi,j$,{\mathrm{s}}_{\mathrm{f}},\mathrm{A},\beta$$,\xi$,fw,… do (set the basic parameters to be determined) While(when the maximum number of iterations is not exceeded itermax) calculate Formulas (1)–(3) and (8); % Calculate and sort fitness values to identify the current best and worst individuals If(calculate Formulas (6) and (7), the standard deviation is less than the specified value 10−3?) { % decide to fall into local optima use gaussian walk strategy to perturb the optimal individual; calculate Formula (8) to obtain the perturbed new sparrow population $X_i^{t+1}$; } else { calculate Formula (1) to obtain the location of the sparrow-finder population; calculate Formula (2) to obtain the location of the sparrow-follower population; calculate Formula (3) to obtain the location of the sparrow-scouter population; } while(when the maximum number of iterations is exceeded itermax) output the optimal individual Xbest, the optimal fitness fg; return 0; }

2.4. Kinematic Physical Model of USV

USV has six degrees of freedom: roll, roll, pitch, yaw, heave motion, translation motion, and forward and backward motion. In order to reduce the complexity of the motion control algorithm of the unmanned ship, the control algorithm of the unmanned ship is usually studied in the horizontal plane. At the initial stage of the research, the unmanned ship is regarded as a particle and only two degrees of freedom of motion are given, namely the translation motion of X and Y axes.

3. Environment Modelling

Unmanned ships need to carry out environment modelling before path planning, with the purpose of representing the unmanned ship information, navigation information, and obstacle information in the navigation environment. Accurate modelling of the map environment is a prerequisite for autonomous path planning of unmanned ships. An important factor to be considered in establishing an environmental model is the structure of the environmental model. If the structure is relatively simple, less data will be occupied and important environmental information may be lost. If the complexity of the modelling structure is high, the modelling time is long and it is difficult to reflect the real-time change information of the environment. Therefore, it is particularly important to determine the model method suitable for the path planning of unmanned ships. At present, domestic and foreign research on unmanned ship environment modelling mainly includes the grid method, Voronoi diagram method, topological diagram method, etc., [17]. Considering that the subsequent environment modelling will be based on an electronic route map, in order to fit the electronic route map environment, this paper adopts grid method modelling.

3.1. Preprocessing of Navigational Information

The electronic route map is a digital map that provides necessary geographic information and route information for ships during navigation. The environmental information of the section from Zhenjiang Port to Yangzhou Port is selected for study. The electronic channel map of Zhenjiang Port–Yangzhou Port section is shown in Figure 4.

For the studied route planning problem, the channel information provided by the electronic channel chart is too comprehensive (e.g., virtual beacons, passing ships, meteorology, isobaths, etc.) to be used directly as a map for route planning; therefore, it is necessary to extract navigational feature information from the electronic channel chart, analyse the navigational information, and save it. In this paper, the fuzzy C-mean clustering algorithm is used to process the navigational information: first, the navigational information of the electronic route map is characterised and the information applicable to unmanned vessel path planning is recorded, such as navigable water, land, etc.; segmentation is performed based on the characteristics and the segmented fields are stored in the node graphic container; and, finally, the segmented fields are stored in the node graphic container. Figure 5 is a flowchart of the extraction and analysis of electronic route information and Figure 6 depicts the electronic route map after the aforementioned procedure has been applied.

3.2. Grid Method and Obstacle Swelling Treatment

After the preprocessed electronic channel map is obtained, the next step is to calibrate the location information of the map environment. In this paper, the grid method is used to process the map. The raster map has the advantages of easy construction, clear description of the environment, unique location, etc. After the raster map data are processed, the map information is transformed from a geoinformation system to information that can be solved by programming.

The environment modelling based on the grid method first needs to determine the co-ordinates of the map in the grid environment to facilitate the positioning. The grid co-ordinates are specified to increase from left to right and from bottom to top and the grid number of the m × n grid is set as i and the grid area as 1. The co-ordinates of the grid centre point can be obtained from the following equation:

(9)$\left\{\begin{array}{c}x=\mathrm{mod}(i,m)-1/2\hfill \\ y=\mathrm{int}(i,n)+1/2\hfill \end{array}\right.$

where x and y represent the centre point’s co-ordinates in the grid environment; Figure 7a depicts the information of each point in the 1010 grid environment. Due to the small size of the unmanned ship in comparison to the surface navigation environment, the process of the unmanned ship performing the autonomous navigation task in the grid environment can be compared to the motion of a mass point in a two-dimensional plane for the sake of algorithm study. However, the grid size setting has a direct influence on the construction of the environment model and the effect of path planning during the actual grid processing procedure. When the determined grid is small, the grid map can clearly represent the navigation environment characteristics of the unmanned ship, but it also occupies a large amount of storage space, affecting the real-time algorithm solution, resulting in a decrease in the speed of unmanned ship path planning, thereby reducing the manoeuvrability and flexibility of the unmanned ship; when the determined grid is large, the navigation environment characteristics of the unmanned ship are less clear. Consequently, it is essential to determine an appropriate grid size. The side length of a single grid is determined by 1.5 times the ship’s length using this method.

To ensure that the unmanned ship does not collide with obstacles while sailing, this paper adopts expansion processing for obstacles, stipulating that, in the modelling process, when the unnavigable area occupies less than one cell grid, the default expansion is one cell, stipulating that the unmanned ship is prohibited from sailing along the edge of the obstacles, and the reserved safety distance is 0.5 grid; when there is no collision between the path and the obstacle, the individual fitness value of the sparrow is equal to the sum of the length of the path and the turning energy consumption, the consumption of right-angle turning is 0.4, and the consumption of obtuse corner turning is 0.2. Figure 7b simulates the situation of irregular obstacles, and the raster map environment after expansion treatment is shown in Figure 7c.

In order to save the map information into the computer as Boolean form, it is necessary to obtain the black and white map before the grid method is used to model the electronic channel chart. OSTU image segmentation method is used to process Figure 6 [18]. OSTU image segmentation method has the advantages of easy implementation, small size, and good stability and has become the most widely used segmentation technology in image segmentation, especially in the range of images with different grey levels of the target and background. The principle of OSTU image segmentation is, first, determine whether the feature attributes of each pixel in the map meet the preset threshold requirements; then, determine whether the pixel in the map belongs to the target region or the background region and, finally, convert the series of colour images into a binary map. The segmentation threshold set by this method is 100, and the obtained binary electronic channel diagram is shown in Figure 8.

Then, the above grid method and obstacle expansion treatment are applied to Figure 8, and the binarized map is saved in the form of a grid array. The grid environment model of the electronic channel chart of Zhenjiang Port and Yangzhou Port is finally obtained, as shown in Figure 9. After the grid environment model suitable for path planning of an unmanned ship is obtained, the relative position information of an unmanned ship during sailing (location information of individual sparrows in the population) and the horizontal and vertical co-ordinates of the grid map are mapped, so as to prepare for the subsequent simulation test of unmanned ship path planning.

4. Experimental Simulation and Evaluation

To verify the feasibility and efficacy of the constructed electronic route map grid environment model and the improved sparrow search algorithm, simulation experiments are performed on the MATLAB R2019b platform for the traditional sparrow search algorithm and the improved sparrow search algorithm. In order to demonstrate the superiority of the enhanced sparrow search algorithm over other heuristic intelligent search algorithms, the simulation portion of this paper introduces the particle swarm search algorithm as a comparison algorithm.

In order to reflect the distinctions between the traditional sparrow search algorithm and the improved sparrow search algorithm in this paper, the sparrow search algorithm’s fundamental parameter settings are kept the same, as shown in Table 1.

The particle swarm search algorithm is an evolutionary computational method whose fundamental concept is to discover the optimal solution through collaboration and information sharing among a population’s individuals. Each particle in the swarm possesses two types of characteristic information: velocity characteristic information and position characteristic information. Each particle autonomously investigates the local optimal solution in the search space and stores it as the extreme value of the current individual and positional details. In this investigation, the control variable concept is utilised and Table 2 displays the parameter settings of the particle swarm algorithm.

In order to compare the results of the improved sparrow search algorithm, the traditional sparrow search algorithm, and the particle swarm search algorithm, 50 simulation experiments are conducted using the 2020 grid environment model for the traditional sparrow search algorithm, the improved sparrow search algorithm, and the particle swarm search algorithm, with the same experimental starting point, end point, path evaluation method, etc. The starting point of the path is (1, 1) and the ending point is (20, 20). The path adaptation value equals the path length plus right angle turns minus 0.4 and obtuse angle turns minus 0.2. One of the simulation outcomes is depicted in Figure 10, where the optimal traditional sparrow search algorithm adaptation value is 33.17, the enhanced sparrow search algorithm adaptation value is 29.81, and the particle swarm optimisation algorithm adaptation value is 0.00. Table 3 displays a comparison of the comprehensive experimental data.

Figure 10 and Table 3 demonstrate that the improved sparrow search algorithm achieves smaller fitness values than the traditional sparrow search algorithm, as evidenced by the 10.13 percent decrease in the optimal fitness value, the 70 percent decrease in the number of turns, and the 6.3 percent decrease in the average fitness value. Specifically, the enhanced sparrow search algorithm is more stable, as demonstrated by a comparison of variance data.

The enhanced sparrow search algorithm obtained smaller fitness values than the particle swarm search algorithm, as evidenced by the 11.49% reduction in the optimal fitness value, 72.7% reduction in the number of cycles, and 7.92% reduction in the average fitness value.

In the initialisation phase of the population, the cubic chaos mapping improves the algorithm’s global search capability, while the introduction of the Gaussian random walk strategy reduces the algorithm’s likelihood of achieving a local optimum. Moreover, the average time spent is only 0.27 s slower than the traditional sparrow search algorithm and 0.34 s slower than the particle swarm algorithm, demonstrating that the introduction of cubic chaos mapping to initialise the population and the Gaussian random walk strategy do not significantly increase the computation time of the improved sparrow search algorithm and meet the real-time requirement for the path planning of unmanned ships.

In order to validate the efficacy of the enhanced sparrow search algorithm in path planning under the electronic route map grid environment, simulation experiments are conducted to validate the algorithm’s practicability. The results of the improved algorithm in the electronic route map grid environment are depicted in Figure 11, where the planned path begins at Zhenjiang Port and ends at Yangzhou Port, whose corresponding co-ordinates begin at (2, 2) and end at (50, 50) in Figure 11.

Figure 11 depicts the enhanced sparrow search algorithm with an adaptation value of 63.97 and an iteration time of 2.99 s. The fact that planning from Zhenjiang Port to Yangzhou Port requires only three instances of ruddering and the waypoints are reasonably distributed demonstrates the efficacy of the proposed algorithm for unmanned ship path planning in a channel chart grid environment.

The figure depicts an enhanced sparrow search algorithm with an adaptation value of 63.97 and an iteration time of 2.99 s. The fact that only three turns are required to plan from Zhenjiang Port to Yangzhou Port and that the navigation points are reasonably distributed demonstrates the efficacy and applicability of the proposed algorithm for unmanned vessel path planning in a channel map grid environment.

After optimizing the optimal path based on the improved sparrow search algorithm, the path is discretised into latitude and longitude data. For the most important latitude and longitude co-ordinate information, we cannot directly see the navigation position of the unmanned ship from the latitude and longitude information, so the distance between the longitude and latitude points of GPS needs to be calculated. The two formulas commonly used in geodesy to calculate the distance between two points on the Earth’s surface are the Vincenty formula and the spherical cosine formula. The Vincenty formula is slower to calculate but more accurate. The spherical cosine formula can be obtained quickly, but the result of the solution is poor and the error is large. Considering that the unmanned ship used for the verification experiment is small and the offline analysis does not require high calculation time, this paper adopts the Vincenty formula to transform the distance and establish the relative co-ordinate system. The distance transformation of longitude and latitude co-ordinates is shown in Figure 12.

In this section, practical engineering applications are carried out based on YL-2500 unmanned ship with specific functions. YL-2500 unmanned ship can replace manual surface garbage cleaning operations. The verification experiment in one of the R&D processes is selected to make a brief explanation. The main technical parameters of YL-2500 unmanned ship are shown in Table 4.

Figure 13 and Figure 14 show the built internal control box system, and Figure 15 shows the overall appearance of the unmanned ship. YL-2500 unmanned ship mainly realises surface garbage cleaning in municipal rivers, lakes, and other waters, so the unmanned ship needs to have the ability to track the set target path. YL-2500 unmanned ship is equipped with the control system designed in this paper to carry out the path tracking experiment and carry out the surface garbage cleaning operation while carrying out the path tracking operation, so as to realise the independent cleaning of the surface garbage.

A water area near Jiaoshan Lake, Jingkou District, Zhenjiang City, was selected for the experiment. First, the unmanned boat was hoisted into the water, as shown in Figure 16. After launching, it was checked on the shore to see if the equipment was damaged in the process of hoisting and lowering. Subsequently, the unmanned ship is manually controlled for sea trials to check whether the internal and external environment has the conditions for autonomous navigation, and then to conduct autonomous navigation. The scene navigation picture is shown in Figure 17.

At the end of the ground station, an electronic fence is designed to delimit the navigation area, as shown in Figure 18. The electronic fence limits the maximum navigation area of the unmanned ship and avoids collision with the non-navigable area. A carpet cleaning path with a waypoint radius of two meters is set, as shown in Figure 19. The target path is sent to the end of the ship and instructions are sent to start the unmanned ship to clean up. At this time, the unmanned ship will clean up while sailing according to the designed path tracking algorithm.

After the garbage cleared by the unmanned ship reaches 50 kg, a full warehouse alarm is issued to remind the ship to return to the sea and replace the nylon net. The garbage collected in the experiment is recorded once, as shown in Figure 20. It can be seen that the garbage on the selected waters is mainly plastic bottles, plastic foam, residual building materials, trees, etc.

The above analysis shows that the unmanned ship can track the target path and clean the target path at the same time. It also directly reflects that the designed path tracking algorithm and embedded control system can enable YL-2500 unmanned ship to track the target path efficiently.

In order to verify the feasibility of the path tracking algorithm designed above in the actual embedded system, an unmanned ship path tracking system is built and a real ship experiment of motion control is carried out. The effective path tracking of YL-2500 unmanned ship verifies the feasibility of the path tracking algorithm. The practical cleaning results of YL-2500 unmanned ship verify the feasibility of the engineering application of the algorithm and the system.

5. Conclusions

In order to solve the path planning problem of unmanned ships, an improved sparrow search algorithm is proposed in this paper. In the population initialisation stage, cubic chaotic mapping is adopted instead of the random generation mode of the traditional sparrow search algorithm to optimise the problem of uneven population distribution in the initial stage. In the late iteration of the algorithm, fitness standard deviation is introduced to judge whether the population is in the local optimal, and Gaussian random walk strategy is used to disturb the optimal individuals, which can effectively assist the algorithm to jump out of the local optimal. Since the original electronic route map cannot be directly used for route planning, the route information of Zhenjiang Port to Yangzhou Port is selected for navigation information preprocessing, rasterisation, and obstacle expansion processing, so as to meet the experimental requirements. The simulation results show that the improved sparrow search algorithm has better global search ability and can avoid falling into local optimal, and can obtain a stable and reliable navigation path combined with an electronic route map.

Through the comparison and analysis between the calculation results of three different algorithms, the following conclusions are drawn:

• By optimising the algorithm in the population initialisation stage of the traditional sparrow search algorithm, the global search ability can be improved and the Gaussian random walk strategy can avoid the algorithm falling into the local optimal;

• Compared with the traditional algorithm, the total path planning time of the optimised sparrow search algorithm is increased by about 10% but the optimal fitness value is reduced by 10.13%, which slightly improves the adaptability of the algorithm;

• The improved sparrow search algorithm can reduce the inflection point of the track, which is very good for the driving habits of the real ship. The intelligent ship can reduce the use of the rudder and have a good energy-saving effect, so this part is worth applying and recommending;

• Compared with the results of mean variance, the robustness of the algorithm is improved and the routes obtained are more stable.

It is an important part of the research that the unmanned ship can obtain a stable and reliable path but, in order to realise the true navigation in the project, it is necessary to consider the external environmental interference, the manoeuvring performance of the unmanned ship itself, fuel economy, and other factors. The research in this paper is only a discussion of theoretical algorithms in the field of path planning for unmanned ships. In the future, external environmental factors such as wind, waves, and dynamic obstacles will be further taken into account to find a suitable global path planning algorithm.

Author Contributions

Conceptualization, S.Z.; Methodology, S.Z.; Validation, G.M.; Formal analysis, S.Z.; Investigation, S.Z.; Writing—original draft, S.Z.; Writing—review & editing, G.L.; Visualization, Y.P.; Supervision, G.L. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

No new data were created or analyzed in this study. Data sharing is not applicable to this article.

Conflicts of Interest

The authors declare no conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. Chaos fork.

Figure 2. Result of cubic chaotic map.

Figure 3. Flow chart of improved algorithm implementation.

Figure 4. ENC chart of Zhenjiang port–Yangzhou port (Green is the water area, purple is the dotted line area is the channel).

Figure 5. Flow chart of electronic channel information analysis.

Figure 6. Preprocessed ENC.

Figure 7. Grid method and obstacle swelling treatment. (a) Grid environment; (b) Obstacles schematic; (c) Swelling treatment.

Figure 8. ENC after OSTU segmentation.

Figure 9. ENC grid environment model.

Figure 10. Both algorithms result in a grid environment. (a) Result of traditional algorithm; (b) Particle swarm search algorithm results; (c) Improved algorithm result.

Figure 11. Result of the improved algorithm in ENC grid environment.

Figure 12. Distance transformation of latitude and longitude co-ordinates.

Figure 13. Unmanned ship ground station.

Figure 14. Control box system.

Figure 15. Physical picture of YL-2500 unmanned ship.

Figure 16. Drop the water screen.

Figure 17. Procedure of YL-2500 experiment.

Figure 18. Electronic fencing.

Figure 19. Sweeping paths.

Figure 20. Garbage collected after trajectory tracking operations by unmanned ship.

Table 1

Basic parameter settings for sparrow search algorithm.

Parameters	Value
Number of populations N	100
Number of iterations itermax	500
Warning value R2	0.8
Percentage of discoverers	0.3
Percentage of followers	0.2
Proportion of scouts	0.15
Solution space dimension	20

Table 2

Parameter settings for particle swarm optimisation.

Parameters	Value
Number of populations N	100
Number of iterations itermax	500
$\mathrm{Learning} \mathrm{factor} c_1$	2.5
$\mathrm{Learning} \mathrm{factor} c_2$	2.5
Inertia weights	1

Table 3

Data comparison of 50 simulation experiments.

Path Metrics	Particle Swarm Search Algorithm	Traditional Sparrow Search Algorithm	Improved Sparrow Search Algorithm
Optimum fitness value	33.68	33.17	29.81
Number of Turns	11	10	3
Mean value	35.96	35.34	30.11
Mean time	0.60	0.67	0.94
Variance	17.03	18.62	9.33

Table 4

Main technical parameters of YL-2500 unmanned ship.

Parameter	Value	Parameter	Value
length/M	2.5	Propulsion mode	Two engines and two OARS
width/M	1.5	speed/KN	6
Mean value	0.6	Unilateral propulsion power/W	750
Connecting steel frame length/M	1.6	Garbage full load capacity/L	50
Connecting steel frame width/M	0.7	Maximum total displacement/KG	400

References

1. Li, S.Y. Start a New Voyage and Create a New Future for Shipping; China Communications Press: Beijing, China, 2021.

2. Yu, Y.L.; Su, R.B.; Feng, X. Tracking control of backstepping adaptive path of unmanned surface vessels based on surge-varying LOS. Chin. J. Ship Res.; 2019; 14, pp. 163-171.

3. Hossain, M.A.; Ferdous, I. Autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique. Robot. Auton. Syst.; 2015; 64, pp. 136-141. [DOI: https://dx.doi.org/10.1016/j.robot.2014.07.002]

4. Polvara, R.; Sharma, S.; Wan, J.; Manning, A.; Sutton, R. Obstacle avoidance approaches for autonomous navigation of unmanned surface vehicles. J. Navig.; 2018; 71, pp. 240-256. [DOI: https://dx.doi.org/10.1017/S0373463317000753]

5. Gao, F.; Zhou, H.; Yang, Z.Y. Global path planning of surface unmanned ship based on improved A* algorithm. Appl. Res. Comput.; 2020; 37, 125.

6. Zhang, Q.; Tian, T.; Luan, T.Y. Research on path planning of unmanned boat routes based on improved artificial potential field algorithm. Ship Sci. Technol.; 2022; 44, 78.

7. Guo, R.X. Research on the Path Planning for USV Based on Reinforcement Learning. Ph.D. Thesis; Harbin Engineering University: Harbin, China, 2020.

8. Wang, C.; Ren, J.; Zhang, Y. Unmanned surface vessel path planning based on improved ant colony algorithm. Nat. Sci. J. Hainan Univ.; 2021; 39, pp. 242-250.

9. Liu, C.A.; Wang, X.P.; Liu, C.Y. Three-dimensional route planning for unmanned aerial vehicle based on improved grey wolf optimizer algotithm. Huazhong Univ. Sci. Tech. Nat. Sci. Ed.; 2017; 45, pp. 38-42.

10. Wang, S.R. Research on Stanley Algorithm Based on Improved Whale Optimization Algorithm. Ph.D. Thesis; Jilin University: Changchun, China, 2022.

11. Liu, J.H.; Yang, J.G.; Liu, H.P.; Tian, X.; Gao, M. An improved ant colony algorithm for robot path planning. Soft Comput.; 2017; 21, pp. 5829-5839. [DOI: https://dx.doi.org/10.1007/s00500-016-2161-7]

12. Xue, J.K.; Shen, B. A novel swarm intelligence optimization approach: Sparrow search algorithm. Syst. Sci. Control. Eng.; 2020; 8, pp. 22-34. [DOI: https://dx.doi.org/10.1080/21642583.2019.1708830]

13. Lyu, X.; Mu, X.D.; Zhang, J.; Zhen, W. Chaos sparrow search optimization algorithm. J. Beijing Univ. Aeronaut. Astronaut.; 2021; 47, pp. 1712-1720.

14. Ouyang, C.T.; Zhu, D.L.; Wang, F.Q. UAV path planning based on refracted sparrow search algorithm. Electron. Opt. Control.; 2022; 29, pp. 25-31.

15. Ge, C.; Qian, S.Q. Path planning of unmanned vehicle based on improved sparrow search algorithm. J. Navig. Position.; 2022; pp. 1-5.

16. Li, P.; Chen, S.J.; Yang, S.S. Otsu image segmentation method optimized by fruit fly optimization algorithm based on Logistic mapping. Foreign Electron. Meas. Technol.; 2022; 41, pp. 9-17.

17. Li, Q.F.; Yuan, Z.J.; Tang, G.Y. Map environment modeling and path planning of unmanned boats. Proceedings of the 2021 Academic Conference of Test Technology Group, Ship Mechanics Academic Committee; Kunming, China, 11–24 October 2021; pp. 490-496.

18. Li, P.; Ding, Q.W. OSTU segmentation algorithm based on sparrow algorithm optimization. Electron. Meas. Technol.; 2021; 44, pp. 148-154. (In Chinese)