# A Decision-Making Method for Ship Collision Avoidance Based on Improved Cultural Particle Swarm

Authors: Yisong Zheng; Xiuguo Zhang; Zijing Shang; Siyu Guo; Yiquan Du
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

In the process of ship collision avoidance decision making, steering collision avoidance is the most frequently adopted collision avoidance method. In order to obtain an effective and reasonable steering angle, this paper proposes a decision-making method for ship collision avoidance based on improved cultural particle swarm. Firstly, the ship steering angle direction is to be determined. In this stage, the Kalman filter is used to predict the ship’s trajectory. According to the prediction parameters, the collision risk index of the ship is calculated and the situation with the most dangerous ship is judged. Then, the steering angle direction of the ship is determined by considering the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs). Secondly, the ship steering angle is to be calculated. In this stage, the cultural particle swarm optimization algorithm is improved by introducing the index of population premature convergence degree to adaptively adjust the inertia weight of the cultural particle swarm so as to avoid the algorithm falling into premature convergence state. The improved cultural particle swarm optimization algorithm is used to find the optimal steering angle within the range of the steering angle direction. Compared with other evolutionary algorithms, the improved cultural particle swarm optimization algorithm has better global convergence. The convergence speed and stability are also significantly improved. Thirdly, the ship steering angle direction decision method in the first stage and the ship steering angle decision method in the second stage are integrated into the electronic chart platform to verify the effectiveness of the decision-making method of ship collision avoidance presented in this paper. Results show that the proposed approach can automatically realize collision avoidance from all other ships and it has an important practical application value.


---

## Body

## 1. Introduction

The increasing density of ship traffic flow leads to the frequent occurrence of ship collision accidents. More than 90% of ship collision accidents are related to human factors, of which at least 60% are directly caused by human errors [1]. At present, a large number of advanced auxiliary systems such as Global Positioning System (GPS), Automatic Radar Mapping Assistant (ARPA), Automatic Identification System (AIS), and Electronic Chart Display and Information System (ECDIS) have brought great help to the acquisition of ships during navigation [2]. However, the progress of information acquisition has not reduced the collision probability of ships to the ideal level [3]. On the other hand, due to the increasingly complex collision avoidance environment faced by ships, it is difficult to describe all possible conditions with rules, which requires ships to have the ability to autonomously analyze the surrounding environment so as to make accurate collision avoidance decisions.Autonomous ship navigation can be divided into two main research areas: collision avoidance and track keeping [4]. Among them, collision avoidance is the core of autonomous ship navigation. The realization of ship collision avoidance first needs to divide the encounter situation of the target ship on the basis of the known environment, quantify the collision risk of the ship, determine the key avoiding ships, then establish the mathematical model of steering, and finally calculate the avoidance decision of own ship in the situation [5]. However, apart from the general rules outlined in the International Regulations for Preventing Collisions at Sea (COLREGs) and the traditional operating specifications, there are no special rules to guide the ship’s navigation system for avoidance manipulation in situations involving multiple ships, and there is no guidance. When multiple ships meet, the collision avoidance decision to avoid collision depends on many factors, such as ship speed, heading, relative position, and maneuverability of the ship [6]. Changing the course of a ship can achieve better collision avoidance than changing the speed. At the same time, it is easier for the surrounding ships to observe the change of the ship’s course on vision and radar [7]. Therefore, finding the optimal steering angle of a ship is currently the most frequently adopted collision avoidance decision-making method.Finding the optimal steering angle is an objective optimization problem. At present, objective optimization problems are divided into linear optimization and nonlinear optimization. Linear optimization problems include the simplex method, interior point method, and polynomial method. The Newton method and conjugate gradient method are commonly used in nonlinear optimization problems. In essence, these optimization problems can be summarized into two steps: the first step is to build a mathematical model based on the actual problem according to its description; The second step is to use a certain method to find the optimal solution within its limited range [8]. The optimal solution of a single-objective optimization problem is generally a solution that can be clearly defined, and the optimal solution of a multiobjective optimization problem is generally an optimal solution set containing multiple optimal solutions [9]. In the objective optimization problem, there are currently two optimization algorithms: deterministic and random algorithms. Deterministic algorithms are mainly based on gradient search methods [10]. The shortcomings of this method are as follows: on the one hand, it has high requirements for the initial value points and gradient information, and on the other hand, it is difficult to optimize the nonderivable and feasible region disconnection. Random algorithms mainly include simulated annealing algorithm (SA) [11], tabu search algorithm (TS) [12], and evolutionary algorithms [13]. The evolutionary algorithm is more robust than SA and TS [14] and also has strong search efficiency; compared with deterministic algorithms, evolutionary algorithms have fewer constraints and are easier to implement when solving constrained optimization problems. With the successful application of evolutionary algorithms in many fields, people’s research efforts have also been strengthened, which has also promoted the rapid development of evolutionary algorithms.Particle swarm optimization (PSO) was proposed by Kennedy and Eberhart in 1995 based on the predatory behavior of birds [15], which belongs to an evolutionary algorithm. This algorithm has the following advantages: simple calculation and good robustness. However, there are still some weaknesses in solving the problem of objective optimization, such as easy to fall into local optimum, poor global convergence, and so on. In order to overcome the defects and improve the local optimization ability of PSO algorithm, scholars at home and abroad have proposed many improvement methods for the inertia weight of particles. For example, in [16], a nonlinear decreasing algorithm of inertia weight is proposed. Based on the basic idea of linearly decreasing inertial weight values, three nonlinear decreasing strategies are proposed. In [17], the problem of adaptive change of inertial weight is studied. In [18], the inertia weight change according to the exponential law is proposed. In [19], stochastic inertia weighting strategies are proposed. Compared with the standard PSO algorithm, these methods can improve the convergence speed and optimization accuracy.However, in these previous improvement studies, the linearly decreasing inertial weight method is usually used, which cannot adapt to complex nonlinear optimization problems, such as finding the optimal steering angle of a ship. Besides, only the optimization and improvement of inertial weights are improved. The algorithm still has the possibility of falling into a local optimum.In view of the above problems, this paper proposes an improved cultural particle swarm optimization algorithm, which can dynamically and nonlinearly change the inertia weights, and solves the problem of falling into a local optimum. The cultural particle swarm optimization algorithm (CPSO) [20, 21] integrates the PSO algorithm into the framework of cultural algorithms and composes the main group space (lower space) and the knowledge space (upper space) based on PSO. Both levels have their groups and evolve independently and in parallel. The lower space regularly provides excellent individuals to the upper space. After the upper space has evolved, it regularly guides the evolution of the lower space; therefore, a “double evolution and double promotion” mechanism is formed so as to increase the population diversity of PSO and avoid “prematurity” to improve the calculation accuracy and computational efficiency. This article introduces the index of the premature convergence degree of the particle swarm, which is calculated to determine the spatial state of the population, and the inertia weight is dynamically and nonlinearly changed, to improve the optimization efficiency of the cultural particle swarm algorithm. Simulation results prove that in terms of the steering angle of a multitarget ship, the algorithm can effectively avoid the defect of being easily trapped into a local optimum, and the convergence speed and optimization accuracy are far better than the single PSO and CPSO algorithms.The rest of the paper is organized as follows. The related works are introduced inSection 2. Section 3 gives a ship collision avoidance decision framework based on improved cultural particle swarms. Section 4 presents the steering angle direction decision method based on ship collision risk. Section 5 presents the optimal steering angle decision algorithm based on improved cultural particle swarms. Section 6 integrates the method of this paper with the electronic chart platform and performs experimental analysis. Finally, the summary and conclusions are given in Section 7.


## 2. Related Research

At present, in the practice of ship collision avoidance, it is still inseparable from the subjective decision of the driver, that is, to manually complete the collision avoidance task based on experience. In the early stage of the shipping industry, the density of traffic flow is small, and the ship speed is low. The method of subjective judgment and manual operation for collision avoidance decision is still competent. However, as the density of ships traffic increases, it becomes more and more difficult to manually complete the collision avoidance decision task of ships. So far, there has been no effective method to satisfy mariners in the area of ship automation collision avoidance decision, and it has become an urgent problem that needs to be solved. The problem of collision avoidance decision is essential to find the optimal steering angle of the ship without collision. At present, many solutions to this problem have been proposed. The mainstream methods include traditional methods such as ship optimal control theory [22], speed obstacle method [23], distributed tabu search algorithm [24], including evolutionary algorithms [25], and other related methods.In terms of traditional methods, Johansen et al. [22] proposed a ship collision avoidance model based on the optimal control theory. By changing the offset to the autopilot’s heading angle, a limited set of alternative control behaviors can be obtained, and then whether these alternative control behaviors meet the COLREGs or not is determined and the relevant collision risk is evaluated to find the best control behavior. But this method mainly considers the situation of one-to-one ships and does not include the treatment of priority avoidance of the most dangerous target ship in case of multiple target ships (two or more). Kuwata et al. [23] proposed a ship autonomous motion model based on the speed obstacle method. This model combines COLREGs to generate a cone-shaped obstacle in the ship’s speed space. It dynamically jumps out of the obstacle range by changing the course of the ship to ensure that the ship’s speed vector is not within the range of the cone obstacle. The advantage of this method is that it can check ship collisions along arbitrary trajectories. However, since collision checking needs to be performed on many time slices, it is computationally expensive and time-consuming. Kim et al. [24] used distributed taboo search algorithm (DTSA) to find the best course for the ship. When multiple ships meet, it is assumed that the highest priority of selecting the next course will be given to the ship, which can minimize the risk of collision by changing the course. This method calculates the collision risk from the information of the current heading received by neighboring ships. This process is repeated until the collision risk disappears. Although these works consider a distributed coordination structure involving multiple ships, they ignore the AIS (automatic identification system). The problem that the data cannot be updated on time causes the ship to be unable to change the course according to the prescribed time.In recent years, the rapid development of intelligent technologies and methods has overcome the difficulties of abstract factors and quantification difficulties encountered in the early use of deterministic methods to solve collision avoidance decision problems [26]. For example, the impact of these parameters on ship collisions estimated only based on existing experiments and expert experience will make the collision avoidance decision unreliable. The fuzzy distribution usually needs to find a function similar to the ship collision within a given fuzzy distribution function range. The actual parameters are determined through prior knowledge or experimental data to obtain the specific membership function and realize the quantification of the collision risk of ships. Therefore, the application of evolutionary algorithms in ship collision avoidance has gradually become a new research direction. For example, Lazarowska et al. [25] applied the ant colony (ACO) algorithm to the unmanned surface vehicle (USV) control system and realized the decision of USV optimal steering angle included in the high seas and restricted waters. The system converts the problem of finding the optimal rudder angle into an optimization problem, takes collision risk and voyage loss as the objective function, and uses the ACO algorithm to solve the optimal solution. However, the convergence speed of the ACO algorithm is slow and it is prone to appear stagnation, and the ship information acquisition error is not considered. Tam et al. [27] thought of all ships as moving points and used the genetic algorithm (GA) to analyze the relevant information of the ships that meet in close range to find the optimal steering angle of the ship. Although the GA has a good global search capability, the operation of the algorithm requires more training time.In summary, the current mainstream ship collision avoidance methods still have various problems, which are prominently manifested in the following aspects:(1)
Most of the methods of steering and collision avoidance do not consider the problems of delayed data update, equipment operation errors, and other problems leading to untimely data updates and inaccurate ship trajectory, which affects the decision of steering angle.(2)
Most studies focus on the collision avoidance behavior of one-to-one ships and do not analyze the situation of the ship’s encounter with the most dangerous target ships, in the case of encounters with multitarget ships (two and more), resulting in the ship’s steering angle direction decisions not satisfying COLREGs.(3)
Although the evolutionary algorithm has a good performance in finding the optimal steering angle of the ship without collision, the related evolutionary algorithm is liable to fall into a local optimum or the training time is too long.Aiming at the above problems, this paper proposes a collision avoidance decision method based on improved cultural particle swarm optimization, which combines Kalman filtering algorithm, fuzzy distribution algorithm, CPSO algorithm, and COLREGs. The main contributions of the method in this paper are as follows:(1)
This method firstly uses the advantages of the Kalman filter algorithm in target tracking and prediction and smoothing and prediction of ship motion trajectory through AIS ship observation node data; the error caused by the AIS data transmission is reduced, the accuracy of the data is improved, and the accuracy of the collision avoidance decision is further improved. The problem that the AIS data are not updated in time is solved, the accuracy of the data is improved, and the accuracy of collision avoidance decision is further improved.(2)
Using the advantage of fuzzy distribution algorithm in dealing with uncertain mathematical models, this paper establishes the corresponding membership function for several factors that mainly affect the ship’s risk degree, solves the ship’s collision risk degree, and finds out the most dangerous target ship. Combined with COLREGs, the problem of steering angle direction is solved by analyzing the encounter situation between the ship and the most dangerous target ship when meeting with two or more target ships.(3)
In the calculation of the optimal steering angle, the index to evaluate the premature convergence degree of particle swarm is introduced to dynamically change the inertia weight of particles, and the advantage of cultural particle swarm algorithm in finding the global optimal solution is higher than that of GA, PSO, and other common evolutionary algorithms in calculation accuracy and efficiency, which improves the convergence speed and optimization accuracy of the algorithm and solves the problem that the evolutionary algorithm is easy to fall into local optimum and training time is too long.


## 3. Ship Collision Avoidance Decision Framework Based on Improved Cultural Particle Swarm

The ship collision avoidance decision framework based on the improved cultural particle swarm is shown in Figure1. The framework is mainly composed of three stages of functions. In the first stage, the collision risk between the ship and the surrounding target ships is analyzed and the optimal steering angle direction is determined according to COLREGs. In the second stage, the ship’s steering angle is calculated based on the steering angle direction determined in the first stage, and the obtained steering angle is input to the ship control module to realize the ship collision avoidance operation. In the third stage, the method of the ship steering angle direction decision in the first stage and the method of the ship steering angle decision in the second stage are integrated into the electronic chart platform, and the validity of the collision avoidance decision method studied in this paper is verified.Figure 1
A ship collision avoidance decision framework based on cultural particle swarm.


### 3.1. Ship Steering Angle Direction Decision

In this stage, the direction of ship steering angle is determined. Since the ship is on the high seas and the waters connected with it that can be navigable, in addition to the implementation of local rules in ports and rivers, COLREGs will be followed first, that is, before calculating the optimal steering angle of the ship, the direction of ship steering angle needs to be determined according to COLREGs. This stage includes 4 steps: ship trajectory prediction, collision risk calculation, judgment of the situation with the most dangerous ship, and judgment of the steering angle direction.First, the Kalman filter algorithm is used to smooth and predict the ship’s motion trajectory to solve the problem of untimely updating of AIS data. Then, the fuzzy distribution algorithm is used to solve the collision risk of the ship and find the most dangerous target ship. Finally, according to the influence parameters of own ship and the most dangerous target ship, it is divided into 16 kinds of ship encounter situations according to literature [28], and the meeting situation of own ship and the most dangerous target ship is judged. By consulting the captain and crew having practical navigation experience and according to the collision avoidance rules and the encounter situation between the own ship and target ship, the rudder angle direction of the ship is determined.


### 3.2. Optimal Steering Angle Decision

At this stage, the optimal steering angle of the ship is calculated based on the improved cultural particle swarm algorithm.First, an index that evaluates the degree of premature convergence of the particle swarm is introduced to determine the state of the particles in the population space to determine the degree of convergence of the population, and then the inertial weight is adaptively changed according to the result of the judgment to ensure the diversity of the particles in the population space. Then, the optimal steering angle is calculated based on the improved cultural particle swarm algorithm. The fitness function is constructed with the help of the collision risk of the ship, and the main group space (lower space) and knowledge space (upper space) of the algorithm are established. The interaction between them improves the evolution efficiency to find the optimal steering angle of the ship more effectively. Finally, the obtained optimal steering angle is input to the ship control module to achieve collision avoidance of the ship.


### 3.3. Electronic Chart Platform Integration and Display

This paper uses electronic charts as a display and verification platform and integrates the steering angle decision method based on ship collision risk and the optimal steering angle decision method based on improved cultural particle swarm algorithm into the electronic chart platform. The platform can dynamically display the status and trajectory of all ships in real time, which can easily show the experimental results of collision avoidance between own ship and target ship and verify the feasibility of the method.


## 3.1. Ship Steering Angle Direction Decision

In this stage, the direction of ship steering angle is determined. Since the ship is on the high seas and the waters connected with it that can be navigable, in addition to the implementation of local rules in ports and rivers, COLREGs will be followed first, that is, before calculating the optimal steering angle of the ship, the direction of ship steering angle needs to be determined according to COLREGs. This stage includes 4 steps: ship trajectory prediction, collision risk calculation, judgment of the situation with the most dangerous ship, and judgment of the steering angle direction.First, the Kalman filter algorithm is used to smooth and predict the ship’s motion trajectory to solve the problem of untimely updating of AIS data. Then, the fuzzy distribution algorithm is used to solve the collision risk of the ship and find the most dangerous target ship. Finally, according to the influence parameters of own ship and the most dangerous target ship, it is divided into 16 kinds of ship encounter situations according to literature [28], and the meeting situation of own ship and the most dangerous target ship is judged. By consulting the captain and crew having practical navigation experience and according to the collision avoidance rules and the encounter situation between the own ship and target ship, the rudder angle direction of the ship is determined.


## 3.2. Optimal Steering Angle Decision

At this stage, the optimal steering angle of the ship is calculated based on the improved cultural particle swarm algorithm.First, an index that evaluates the degree of premature convergence of the particle swarm is introduced to determine the state of the particles in the population space to determine the degree of convergence of the population, and then the inertial weight is adaptively changed according to the result of the judgment to ensure the diversity of the particles in the population space. Then, the optimal steering angle is calculated based on the improved cultural particle swarm algorithm. The fitness function is constructed with the help of the collision risk of the ship, and the main group space (lower space) and knowledge space (upper space) of the algorithm are established. The interaction between them improves the evolution efficiency to find the optimal steering angle of the ship more effectively. Finally, the obtained optimal steering angle is input to the ship control module to achieve collision avoidance of the ship.


## 3.3. Electronic Chart Platform Integration and Display

This paper uses electronic charts as a display and verification platform and integrates the steering angle decision method based on ship collision risk and the optimal steering angle decision method based on improved cultural particle swarm algorithm into the electronic chart platform. The platform can dynamically display the status and trajectory of all ships in real time, which can easily show the experimental results of collision avoidance between own ship and target ship and verify the feasibility of the method.


## 4. Direction Decision Method of Steering Angle Based on Ship Collision Risk

### 4.1. Optimal Steering Angle Decision

The real-time acquisition of accurate ship AIS information is the database of ship collision avoidance decision making. Only the real-time acquisition of ship AIS data can effectively monitor the navigation status of the water area and timely find the ship information with collision risk in the navigation water area. At present, although a large number of AIS instruments have been installed in ship and shore-based management, due to various subjective and objective reasons, as well as congestion and network transmission of AIS ship stations and shore stations, such as improper AIS operation and data broadcast by AIS equipment due to ships, the distance from the AIS base station, the abnormal operation of the AIS device itself, or the artificial shutdown of the AIS device caused the AIS data received by the shore-based AIS to be incorrect and the data location report to be updated in a timely manner.In order to compensate for the delayed data update caused by AIS data blockage and other reasons, resulting in inaccurate or large errors in the ship’s trajectory, this paper uses the Kalman filter algorithm and considers the measurement noise caused by the AIS data transmission. Smoothing and predicting the ship’s motion trajectory can reduce the error caused by the AIS data transmission, improve the accuracy of the data, and further improve the accuracy of collision avoidance decisions.


#### 4.1.1. Basic Concepts

(1)
AIS Data. AIS (automatic ship identification system) is a new navigation aid system for shore-to-ship, ship-to-shore, and ship-to-ship communication [29]. AIS equipment can send own ship information such as latitude and longitude, speed, heading, ship name, and other information to the target ship via VHF channel after processing by the processor and automatically obtain the position of other ships with similar equipment in real time, speed, heading, etc.(2)
Mercator Projection. Mercator projection is a map projection technology that uses an equiangular projection method. The principle is to assume that the Earth is enclosed in a hollow cylinder, whose datum of latitude (equator) is tangent to the cylinder, and then imagine a lamp in the center of the Earth, project the figure on the sphere onto the cylinder, and expand the cylinder to get a map drawn by the “Mercator projection” on the selected datum line [30].The experimental model needs to convert the WGS84 latitude and longitude coordinates in the AIS data to Mercatorx, y coordinates to predict the ship’s trajectory. According to the principle of Mercator projection, the projection of the equator is X axis, the projection of the prime meridian is Y axis, and the projection of the intersection of the two is the origin of the coordinate, which is positive toward east and north and negative toward west and south, forming the Mercator plane rectangular coordinate system. Let the long axis of the Earth be a and the short axis be b. The longitude of a point on the Earth is θ∈−π,+π with latitude α∈−π/2,+π/2; according to the equiangular principle, the coordinate conversion formula is as follows:(1)x=a∗θ,y=a∗lntanπ4+α2+e2ln1−e∗sinα1+e∗sinα,wheree=a2−b2/a2 is the first eccentricity of the Earth’s ellipsoid, and formula (1) θ,α translates to plane coordinates x,y.(3)
Trajectory Vector Set. Modeling the two-dimensional plane X axis and Y axis of Euclidean space, using vectors in the directions of the two coordinate axes to represent trajectory data, and let T be the trajectory vector set. T=Trj1,Trj2,…,Trjn=px1,py1,px2,py2,…pxn,pyn=px,1px2,…,pxnT,py1,py2,…,pynT, where pxi=xi1,xi2,…,xidTrepresents the projection vector set of the ith trajectory in the X axis direction, pyi=yi1,yi2,…,yidTrepresents the projection vector set of the ith trajectory in the Y axis direction, andpxi,pyi is called the vector set of the trajectory Trji.(4)
Kalman Filtering. The core is to use recursive algorithms to estimate the optimal system state and realize the prediction of target motion behavior [31]. The Kalman filtering system of state equations and observation equations is as follows:(2)Xk+1=AkXk+ΓkUk+TkWk,Zk=HkXk+Vk,whereXk+1 represents k+1 state value at the moment, Ak is the state transition matrix, Γk is the control matrix, Uk is the control input vector, Tk is the interference transfer matrix, Wk is the system state noise of the motion model, Zk is the observation vector, Hk is the observation matrix, and Vk is the observation noise.(5)
Prediction Error. For the geometric spatial error between the predicted trajectory point and the actual trajectory point, the root mean square error is shown as follows:(3)RMSE=∑i=1kxi′−xi2+yi′−yi2k,wherexi,yi represents the position of the actual trajectory point, xi′,yi′ position information represents predicted trajectory points, and k represents the number of predicted trajectory points.


#### 4.1.2. Ship Trajectory Prediction

In this paper, the AIS observation data transmitted by the VHF channel are used to optimally estimate the system state such as the ship position and speed to make real-time prediction of the ship trajectory.(1) Ship Trajectory Modeling. The latitude and longitude of the ship are transformed into coordinates x,y in the Cartesian coordinate system through Mercator projection. Wxk and Wyk are the two orthogonal components of Gaussian white noise W(k) with zero mean and variance σW2, Wxk and Wyk are independent of each other at any time. The values are related to factors such as actual sea wind, waves, and weather. Vxk and Vyk are two orthogonal components of Gaussian white noise V(k) with zero mean and variance σV2, Vxk and Vyk are independent of each other at any time. The value is related to the error of the actual AIS information in the detection and transmission process. Wk and Vk are independent Gaussian white noises, which the corresponding covariances are Q and R.The model obtains the optimal state estimateX′k of the system at time k based on the number of observations transmitted by AIS in the first kt times. There are two different update processes in the process of the stochastic linear discrete Kalman filtering cycle, which are the time update process and the observation update process. The time update process is to predict the state at the current moment according to the optimal state estimation at the previous moment (see equation (4)). The observation update process is that after predicting the ship’s trajectory point at k+1 time, the observed value of the ship’s trajectory point at the actual k+1 time is used for linear fitting to find out the optimal estimated position of the trajectory point. That is to say, according to the observed value and the predicted value, the optimal estimation point of the ship’s trajectory at k+1 time is derived through the observation update equation, as shown in equation (5).(4)xk+1,k=xk,k+vktcosθk,yk+1,k=yk,k+vktsinθk,(5)xk+1,k+1=xk+1,k+Kk+1∗xzk+1−xk+1,k,yk+1,k+1=yk+1,k+Kk+1∗yzk+1−yk+1,k,where xk+1,k is the predicted x coordinate of the ship at time k+1. yk+1,k is the predicted y coordinate of the ship at time k+1. xk,k is the optimal estimate of the x coordinate of the ship at time k. yk,k is the optimal estimate of the y coordinate of the ship at time k. vk is the ship’s speed at time k, the θk is the heading of the ship at time k, and t is the time interval. Kk+1 is the filter gain matrix at time k+1. For the value and the update formula of the covariance Pk+1,k+1 of the optimal state estimation at time, see formula (6).(6)Pk+1,k=AkPk,kAkT+TkQkTkT,Sk+1=Hk+1Pk+1,kHk+1T+Rk+1,Kk+1=Pk+1,kHk+1TSk+1−1,Pk+1,k+1=Pk+1,k−Kk+1Sk+1Kk+1T.WhereQk is the system noise of the ship at node k, Rk is the observed noise, Pk,k is the error variance matrix, Ak is the ship state transition matrix, Pk+1,k is the error variance matrix of the predictive state xk+1,k and yk+1,k, and Kk is the filter gain matrix. Besides that, Wxk and Wyk have zero mean. Gaussian white noise with variance σW2 and the time update equation of equation (5), we can get Tk and Ak as the identity matrix. Furthermore, the coordinates do not undergo unit conversion. The observation matrix Hk is also the identity matrix. According to the above formula, the optimal position prediction value of the ship at a single step is obtained. If the ship nt position is predicted, the ship trajectory prediction can be completed iteratively.The ship trajectory prediction algorithm based on Kalman filtering is shown in Algorithm1. The detailed steps are as follows.Algorithm 1: Ship trajectory prediction algorithm based on Kalman filter.
Input: trajectory dynamic AIS dataset of moving shipsT=Trj1,Trj2,…,TrjnOutput: mean value of ship trajectory error RMSE(1)
D = trajectPretreatment (T)(2)
initParameters ()(3)
state = getCurrentState (D)(4)
fori = 1 to k:(5)
p = KalmanPredict (D)(6)
e[i] = getRMSE (p, p’)(7)
end for(8)
RMSE=∑i=1kei/k(9)
Output RMSEIn Algorithm1, the function trajectory predictionT is used to collect and decode ship AIS data and perform x,y preprocessing operations such as coordinate transformation. The function initParameters is used to determine the parameters of the ship’s motion model according to the state equation and observation equation of the system; besides, this function is also used to initialize the ship’s A, U, and Q with R and other parameters. The function getCurrentStateD is based on the optimal state estimate at the initial moment X0,0 and estimates error variance matrix P0,0, predicting the ship trajectory value at the next moment according to the system state equation X1,0 and obtaining the covariance matrix of the estimation error at the same time P1,0. According to the observed value Z1 of the ship trajectory at the next moment, theoptimal state estimation value X1,1 and the covariance matrix P1,1 of the optimal estimation error are obtained to complete the single-step filtering process of the ship trajectory. Then iteratively obtain the optimal state estimate X(n − 1, n − 1) at the time of n−1 to complete the filtering process. The function of Kalman  PredictD is to estimate the position of the ship's trajectory point at time n+1 based on the optimal state estimation Xn−1,n−1 at time n-1 and the observed value of current time n. The function of getRMSEp,p′ is to compare the predicted point p′ with real trajectory point p to calculate the filtering prediction error. Finally, repeat the operation k times to complete the prediction of the future k steps of ship trajectory points. Then, calculate and output the average prediction error.(2) Simulation Experiment Verification. Experimental model using sk indicates that the ship’s real location is at the sampling time kt.yk means observations of AIS data transmission at the moment kt, where yk=sk+vk, and vk represents observation noise. s′k means speed of ship at the moment kt, acceleration ak is a combination of maneuvering acceleration uk and random acceleration wk. The uniform acceleration motion and acceleration formula of the ship is as follows:(7)sk+1=sk+s′kt+0.5t2ak,s′k+1=s′k+tak,ak=uk+wk,where uk are the control signals of the ship’s power system; define the system status xk at the sampling time kt for the position and speed of the ship; the equations of motion and observation of the ship are shown as follows:(8)sk+1s′k+1=1T001sks′k+0.5T02T0uk+0.5T02T0wk,yk=10sks′k+vk.This experiment does not consider the ship’s own dynamic factorsuk=0 and state vector Xk generalized to four dimensions; its expression and system equations are shown in equation (9), and the initial position is set as −100m,200m, X shaft speed is set as 2m/s, and Y shaft speed is set as 20m/s. The experimental record of the ship trajectory formed at 20 time points is shown in Figure 2, and the error analysis diagram is shown in Figure 3.(9)xkxk−ykyk−=1,T,0,00,1,0,00,0,1,T0,0,0,1xk−1xk−1−yk−1yk−1−+0.5T2,0T,00,0.5T20,Twk,Zk=1,0,0,00,0,1,0xkxk−ykyk−+vk,Xk=xk,xk−,yk,yk−.Figure 2
Ship tracking trajectory.Figure 3
Ship tracking error.The observed ship trajectory obviously oscillates in Figure2, indicating that the measurement noise has a great impact, and after Kalman filtering, the filtering estimation is relatively close to the true trajectory of the ship. Figure 3 shows that the observed noise of the ship displacement is close to 32 m, and the experiment is only simulation; the actual ship AIS measurement error will not be so large. After Kalman filter processing, the ship’s displacement deviation is reduced to less than 12 m. Experiments show that Kalman filter can limit the impact of noise to the greatest extent and better predict the position after the ship.


### 4.2. Calculation of Ship Collision Risk

The membership function of different factors determines the value of ship collision risk. The collision risk of ships plays a key role in measuring the collision risk of ships and is an important basis for ship collision avoidance decision making [32]. The crew can decide the timing and order of avoidance according to the collision risk. There are many factors that affect the collision risk of ships. From the statistical research on the crew’s collision avoidance behavior at sea by experts and scholars [33] and the research on the decision-making process, it can be seen that the main factors for judging the collision risk are intership distance, azimuth, DCPA, TCPA, and speed ratio. These factors can fully reflect the encounter situation with the target, so the membership function of these factors is used as input to infer the collision risk of the ship.


#### 4.2.1. Calculation of Influence Parameters

Kalman filtering prediction is used to obtain the shipX axis position coordinate x0, the Y axis position coordinate y0, the own ship’s speed on the X axis component xv0 and the Yaxis component yv0, other ship X axis position coordinate x1, Y axis position coordinate y1, the component xv1 on the X axis, and the component xv1 on the yv1 axis. Then, the longitude Aj, latitude Aw, heading Ah, and speed AS of the own ship and the longitude Bjm, latitude Bvm, heading Bhm, and speed BSm of other ships are obtained through the reverse solution of the Mercator projection equation. By substituting the above information into equation (10), the relevant influencing factor values can be solved.(10)D=2∗R∗arcsinsin2Bwm−Aw2+cosAw∗cosBwm∗sinBjm−Aj2,TB=arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈first quardrant,360+arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈second quardrant,180−arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈third and fourth quardrants,B=Ah−TB,RSH=arctanBsm∗cosBhm−As∗cosAhBsm∗sinBhm−As∗sinAh,RS=Bsm2+As2−2∗Bsm∗As∗cosAh−Bhm,DCPA=D∗sinRSH−RA−180∘,TCPA=D∗cosRSH−RA−180∘,where D, TB, B, RSH, and RS are the distance, azimuth, relative azimuth, relative speed course, and relative speed between ships.


#### 4.2.2. Establishment of Collision Risk Model

The collision risk calculation method used in this paper is calculated through fuzzy sets. Fuzzy set is a set used to express the concept of fuzziness. It is defined as a given research rangeU; then a mapping from U to the unit interval [0, 1] is called a fuzzy set on U or a set of U fuzzy subset. Fuzzy set is described by membership function. The membership function occupies an extremely important position in fuzzy set theory. It is defined as if any element x in the research range U has a number Ax∈0,1 corresponding to it, then A is called the fuzzy set on U, and Ax is called the membership degree of x to A. When x changes in U, Ax is a function called A’s membership function. In the fuzzy set, the value range of its characteristic function is [0, 1] interval; this characteristic function is also called membership function. Membership function is an important basis of fuzzy set theory, so how to determine the membership function is a key issue. However, the object is “fuzzy” and empirical, so it is unrealistic to find a unified calculation method for membership. The fuzzy distribution method currently used is used to construct the membership function of each influencing factor to realize the calculation of ship collision risk. The membership function formula ((11)–(17)) used in this paper refers to the relevant formula in reference [33].(1) DCPA Membership FunctiontDCPA. DCPA is the distance that the ship will meet recently. Statistics show that when the distance between the two ships is less than the distance between the two ships, the possibility of collision between the ships is extremely large. According to the empirical data of collision avoidance in open waters, when DCPA≤0.6nmile, it is dangerous, tVDDCPA=1; when 0.6nmile<DCPA≤1.8nmile, it is considered very dangerous, tVDDCPA; when 0.6nmile<DCPA≤1.2nmile, it is considered dangerous, tDDCPA; when 1.0nmile<DCPA≤1.6nmile, it is considered fair, tNDCPA; when 1.4nmile<DCPA≤2.5nmile, it is considered safer, tSDCPA; when DCPA>2.5nmile, it is considered very safe, tVSDCPA. The membership function is shown in equation (11), and the corresponding function image is shown in Figure 4.(11)tVDDCPA=1,DCPA≤0.6nmile,0.5−0.5sinπ0.2x−0.7,0.6nmile<DCPA<0.8nmile,0,0.8nmile≤DCPA,tDDCPA=0,DCPA≤0.6nmile,0.5+0.5sinπ0.2x−0.7,0.6nmile<DCPA<0.8nmile,1,0.8nmile≤DCPA≤1nmile,0.5−0.5sinπ0.2x−1.1,1nmile<DCPA<1.2nmile,0,1.2nmile≤DCPA,tNDCPA=0,DCPA≤1nmile,0.5+0.5sinπ0.2x−1.1,1nmile<DCPA<1.2nmile,1,1.2nmile≤DCPA≤1.4nmile,0.5−0.5sinπ0.2x−1.5,1.4nmile<DCPA<1.6nmile,0,1.6nmile≤DCPA,tSDCPA=0,DCPA≤1.4nmile,0.5+0.5sinπ0.3x−1.55,1.4nmile<DCPA<1.7nmile,1,1.7nmile≤DCPA≤2nmile,0.5−0.5sinπ0.5x−2.25,2nmile<DCPA<2.5nmile,0,2.5nmile≤DCPA,tVSDCPA=0,DCPA≤2.0nmile,0.5+0.5sinπ0.5x−2.25,2.0nmile<DCPA<2.5nmile,1,2.5nmile≤DCPA.Figure 4
DCPA membership function image.(2) TCPA Membership FunctiontTCPA. TCPA is the recent meeting time of the ship, which reflects the urgency of the meeting situation between the two ships. Statistics and empirical data show that TCPA≤6min Time, tVDTCPA=1; when 8min≤TCPA≤9min Time, tDTCPA=1; when 11min≤TCPA≤12min Time, tNTCPA=1; when 14min≤TCPA≤15min Time, tSTCPA=1; when TCPA≥17minTime, tVSTCPA=1. The membership function is shown in equation (12), and the corresponding function image is shown in Figure 5.(12)tVDTCPA=1,TCAP≤6min,0.5−0.5sinπ2x−7,6min<TCPA<8min,0,8min≤TCPA,tDTCPA=0,TCAP≤6min,0.5+0.5sinπ2x−7,6min<TCPA<8min,1,8min≤TCPA≤9min,0.5−0.5sinπ2x−10,9min<TCPA<11min,0,11min≤TCPA,tNTCPA=0,TCAP≤9min,0.5+0.5sinπ2x−10,9min<TCPA<11min,1,11min≤TCPA≤12min,0.5−0.5sinπ2x−13,12min<TCPA<14min,0,14min≤TCPA,tSTCPA=0,TCAP≤12min,0.5+0.5sinπ2x−13,12min<TCPA<14min,114min≤TCPA≤15min,0.5−0.5sinπ2x−16,15min<TCPA<17min,0,17min≤TCPA,tVSTCPA=0,TCAP≤15min0.5+0.5sinπ2x−16,15min<TCPA<17min,1,17min≤TCPA.Figure 5
TCPA membership function image.(3) D Membership FunctiontD. D It is the distance between ships; the smaller the value is, the closer the target ship is and the greater the collision risk of the ship is. Statistical empirical data show that when D≤1.5nmile, tVDD=1; when 1.7nmile≤D≤2nmile, tDD=1; when 2.2nmile<D<2.5nmile, tND=1; when 2.7nmile<D<3nmile, tSD=1; when D>=3.2nmile, tVSD=1. The membership function is shown in equation (13), and the corresponding function image is shown in Figure 6.(13)tVDD=1,D≤1.5nmile,0.5−0.5sinπ0.2x−1.6,1.5nmile<D<1.7nmile,0,1.7nmile≤D,tDD=0,D≤1.5nmile,0.5+0.5sinπ0.2x−1.6,1.5nmile<D<1.7nmile,1,1.7nmile≤D≤2nmile,0.5−0.5sinπ0.2x−2.1,2nmile<D<2.2nmile,0,2.2nmile≤D,tND=0,D≤2nmile,0.5+0.5sinπ0.2x−2.1,2nmile<D<2.2nmile,1,2.2nmile≤D≤2.5nmile,0.5−0.5sinπ0.2x−2.6,2.5nmile<D<2.7nmile,0,2.7nmile≤D,tSD=0,D≤2.5nmile,0.5+0.5sinπ0.2x−2.6,2.5nmile<D<2.7nmile,1,2.7nmile≤D≤3nmile,0.5−0.5sinπ0.2x−3.1,3nmile<D<3.2nmile,0,3.2nmile≤D,tVSD=0,D≤3nmile,0.5+0.5sinπ0.2x−3.1,3nmile<D<3.2nmile,1,3.2nmile≤D.Figure 6
D membership function image.(4) B Membership FunctiontB. B is the relative position between ships, and the danger of coming ships with different relative positions is different from their own ships. Statistical empirical data show that the safety of each area is ranked as E, A, B, C, D. E area arrival range is 335°∼5°, and the meeting situation between the coming ship and own ship in this area is the most dangerous meeting situation. A area arrival range is 5°∼67.5°, and the meeting situation between the coming ship and own ship in this area is a starboard small angle crossing meeting situation, which is more dangerous. B area arrival range is 67.5°∼122.5°, and the meeting situation between the coming ship and own ship in this area is a starboard high-angle crossing meeting situation, and the danger is average. C area arrival range is122.5°∼210.5°, and the meeting situation between the coming ship and own ship in this area is safer. D area arrival range is 247.5°∼355°, and the meeting situation between the incoming ship and own ship in this area is safe. The membership function is shown in equation (14), and the corresponding function image is shown in Figure 7.(14)tVDB=1−B360°0°≤B≤5°,B360°355°≤B≤0°,tDB=1−B−36.25°360°5°<B<67.5°,tNB=1−B−90°360°67.5°≤B≤122.5°,tSB=1−B−180°360°122.5°<B<247.5°,tVSB=1−B−301.75°360°247.5°≤B<355°.Figure 7
B membership function image.(5) Ship Speed Ratio Membership FunctiontK. Define the speed ratio K of the own ship and the targetship m as As/Bsm. The statistical research on collision avoidance shows that when the own ship is a low-speed ship, collision avoidance actions must be taken as soon as possible and it needs to turn a large angle. Take tK=0.5 as the boundary point between safety and danger. The larger the value of tK, the higher the risk of collision. The membership function is shown in equation (15), and the corresponding function image is shown in Figure 8.(15)tK=11+1/K2.Figure 8
Ship speed ratio membership function image.(6) Calculation of Ship Collision Risk. Drawing on the research results at home and abroad and the experience of collision avoidance in open waters at sea, this paper establishes the evaluation criteria for the danger avoidance of each factor as shown in Table 1. The importance of the factor set DCPA,TCPA,D,B,Kthat affects the collision risk of ships is in order of DCPA>TCPA>D>B>K. According to the investigation in the literature [34], during the course of crew training bridge resource management, the corresponding weight of the factor set is W=0.4,0.367,0.167,0.033,0.033. The final risk vector R can be obtained through the evaluation matrix formed by the weight vector W and membership function of each factor (see equation (16)).(16)R=WDCPA,WTCPA,WD,WB,WKtVDDCPAtDDCPAtNDCPAtSDCPAtVSDCPAtVDTCPAtDTCPAtNTCPAtSTCPAtVSTCPAtVDDtDDtNDtSDtVSDtVDBtDBtNBtSBtVSBtVDKtDKtNKtSKtVSK=WDCPAtVDDCPA⊕WTCPAtVDTCPA⊕WDtVDD⊕WBtVDB⊕WKtVDKWDCPAtDDCPA⊕WTCPAtDTCPA⊕WDtDD⊕WBtDB⊕WKtDKWDCPAtNDCPA⊕WTCPAtNTCPA⊕WDtND⊕WBtNB⊕WKtNKWDCPAtSDCPA⊕WTCPAtSTCPA⊕WDtSD⊕WBtSB⊕WKtSKWDCPAtVSDCPA⊕WTCPAtVSTCPA⊕WDtVSD⊕WBtVSB⊕WKtVSK.Table 1
Criteria for risk evaluation of various factors.
FactorLow riskLow riskAverage riskHigh riskHigh riskDCPAnmile2.5∼4.01.2∼2.51.0∼1.60.6∼1.20.6∼0.8TCPAmin18151296Dnmile4.03.02.52.01.5B°301.75。180。90。36.25。0。K<0.50.5∼0.80.8∼1.21.2∼2>2Here,⊕ is a hazard synthesis operator. According to the actual operation requirements of collision avoidance at sea, the synthesis operator is regulated as follows:(17)α⊕β=min1,α+β.


#### 4.2.3. Calculation of Ship Collision Risk

Literature [34] sets the size of the collision risk of the target ship relative to the own ship as a set −2,−1,0,1,2. It is divided into five dangers: low danger, low danger, normal danger, high danger, and high danger, calculated by weighting the vector R by its weight value. Table 2 shows the relevant data and the influencing factors (the first is the own ship data) of the own ship and the 4 experimental ships at that moment. Figure 4 shows the hazard curves of the ship and the four experimental ships when the steering angle of the ship is limited within the range −35,35. The horizontal axis is the number of steering angles of the ship. Negative values represent counterclockwise steering.Table 2
Related data of own ship and other ships.
LongitudeLatitudeCourseSpeedBearingRelative bearingDistanceRelative speed headingRelativeDCPATCPACollision risk2330050————————23.0730.022206071.7271.724.33201.89103.42−3.311.62−0.07722.8830.0131060275.52275.527.23256.0347.362.418.630.05723.0529.9826060114.78114.783.18224.3684.51−2.990.750.2822.8729.974060255.11255.117.9795.9838.782.8411.521.17From Figure9 and Table 2, it can be seen that when own ship is at the initial heading (the horizontal axis of the image is 0), the danger is first ship > second ship > third ship > fourth ship, and as the ship’s clockwise steering angle increases, the danger of the second ship becomes higher, making it more prone to collision risks.Figure 9
Curve of ship collision risk.


### 4.3. Ship Steering Angle Decision

By analyzing the collision risk curve of the ship in Figure4 and following the rule that the ship will always avoid the most dangerous ship each time when avoiding a collision, the lower the collision risk of the ship in the curve, the more likely it is to collide. We analyze the collision risk curve of the ship, take the lowest value of the ship’s danger degree corresponding to each steering angle, and record the name (serial number) of the ship with the lowest collision danger when the steering angle is zero so as to analyze the current situation of the ship corresponding to the most dangerous target ship situation and determine the direction of the ship’s steering angle.The encounter situation of ships is determined in accordance with the applicable provisions of the rules for avoiding collisions. The rules for avoiding collisions are the basic guidelines for the safe navigation of ships at sea, and they are also an important legal basis for regulating ship avoidance actions. The rules clearly stipulate the methods of avoidance of ships in various situations and play an important role in guiding the safe navigation and avoidance of ships. The encounter situation is mainly divided into two types: first, under the provisions of the collision avoidance rules, the meeting situation is divided according to the possible collision avoidance actions of the crew and the degree of collision avoidance difficulty. The second is from the angle of collision avoidance action (left and right collision avoidance) and according to the relative azimuth (side angle) of the target ship [34]. Reference [28] divides three kinds of ship encounter situations, including 16 kinds of ship encounter situations, based on the relative position relationship between the own ship and the target ship, the avoidance responsibility, and the steering avoidance action method and good visibility. In this paper, by collecting the actual control experience of the master and crew and combining with the provisions of the International Regulations for Preventing Collisions at Sea in 1972, the specific directions of the ship’s steering angles for the overtaking ship, the giving way ship, and the ship in the encounter are given.Rule 13 of the Collision Avoidance Rule: “when a ship is catching up with other ships from a certain direction that is more than 22.5 degrees behind the other ship, that is, the position of the ship it is chasing, it can only see the taillight of the overtaken ship at night, but not the other. Any of its side lights should be considered to be overtaking.” According to the rules of collision avoidance and actual navigational experience, when the ship is an overtaking ship, the crew usually practices the rudder to the left. Regardless of any change in the orientation between the two ships, until the responsibility of the overtaken ship is relieved and the ship passes by to clear it, the situation is shown in Figures10 and 11, where Figure 10 is a direct ship and Figure 11 is an overpass. In the following picture, the blue solid line is the main ship and the yellow dotted line is the target ship.Figure 10
Overtaking situation (own ship is a direct ship).
(a)(b)(c)(d)Figure 11
Overtaking situation (own ship is overtaking ship).
(a)(b)(c)(d)Rule 14 of the Collision Avoidance Rule: “when two motor ships meet in opposite or near opposite headings and there is a danger of collision, they each turn to the right so that they each pass through the port side of other ships”; according to collision avoidance, the crew members should normally steer the rudder to the right, and the situation is shown in Figure12.Figure 12
Meeting situation.
(a)(b)Rule 15 of the Collision Avoidance Rule: “when two motor boats cross each other and there is a danger of collision, a ship with other ships on the starboard side of the ship should make way for other ships. If the environment permits at the time, they should also avoid crossing the front of other ships.” According to the rules of collision avoidance and actual navigational experience, when the ship is a yielding ship, the crew usually practices the rudder to the right until the responsibility of the yielding ship is relieved. The situation is shown in Figures13 and 14. Among them, the first two small pictures in Figures 13 and 14 limit the speed ratio of own ship to the target ship.Figure 13
Crossing situation (own ship is a give way ship).
(a)(b)(c)Figure 14
Cross situation (own ship is a direct ship).
(a)(b)(c)According to the literature [35], the ship’s danger is divided into 5 levels. The minimum value of the collision danger corresponding to the ship at the current moment is obtained through the curve in Figure 5. When the value is less than −0.4, the collision risk of the ship is more likely to require a collision avoidance decision. At the moment, the meeting situation of the ship with the lowest collision risk is determined. According to the above conclusions, the determination of the ship rudder angle direction is completed.


## 4.1. Optimal Steering Angle Decision

The real-time acquisition of accurate ship AIS information is the database of ship collision avoidance decision making. Only the real-time acquisition of ship AIS data can effectively monitor the navigation status of the water area and timely find the ship information with collision risk in the navigation water area. At present, although a large number of AIS instruments have been installed in ship and shore-based management, due to various subjective and objective reasons, as well as congestion and network transmission of AIS ship stations and shore stations, such as improper AIS operation and data broadcast by AIS equipment due to ships, the distance from the AIS base station, the abnormal operation of the AIS device itself, or the artificial shutdown of the AIS device caused the AIS data received by the shore-based AIS to be incorrect and the data location report to be updated in a timely manner.In order to compensate for the delayed data update caused by AIS data blockage and other reasons, resulting in inaccurate or large errors in the ship’s trajectory, this paper uses the Kalman filter algorithm and considers the measurement noise caused by the AIS data transmission. Smoothing and predicting the ship’s motion trajectory can reduce the error caused by the AIS data transmission, improve the accuracy of the data, and further improve the accuracy of collision avoidance decisions.


### 4.1.1. Basic Concepts

(1)
AIS Data. AIS (automatic ship identification system) is a new navigation aid system for shore-to-ship, ship-to-shore, and ship-to-ship communication [29]. AIS equipment can send own ship information such as latitude and longitude, speed, heading, ship name, and other information to the target ship via VHF channel after processing by the processor and automatically obtain the position of other ships with similar equipment in real time, speed, heading, etc.(2)
Mercator Projection. Mercator projection is a map projection technology that uses an equiangular projection method. The principle is to assume that the Earth is enclosed in a hollow cylinder, whose datum of latitude (equator) is tangent to the cylinder, and then imagine a lamp in the center of the Earth, project the figure on the sphere onto the cylinder, and expand the cylinder to get a map drawn by the “Mercator projection” on the selected datum line [30].The experimental model needs to convert the WGS84 latitude and longitude coordinates in the AIS data to Mercatorx, y coordinates to predict the ship’s trajectory. According to the principle of Mercator projection, the projection of the equator is X axis, the projection of the prime meridian is Y axis, and the projection of the intersection of the two is the origin of the coordinate, which is positive toward east and north and negative toward west and south, forming the Mercator plane rectangular coordinate system. Let the long axis of the Earth be a and the short axis be b. The longitude of a point on the Earth is θ∈−π,+π with latitude α∈−π/2,+π/2; according to the equiangular principle, the coordinate conversion formula is as follows:(1)x=a∗θ,y=a∗lntanπ4+α2+e2ln1−e∗sinα1+e∗sinα,wheree=a2−b2/a2 is the first eccentricity of the Earth’s ellipsoid, and formula (1) θ,α translates to plane coordinates x,y.(3)
Trajectory Vector Set. Modeling the two-dimensional plane X axis and Y axis of Euclidean space, using vectors in the directions of the two coordinate axes to represent trajectory data, and let T be the trajectory vector set. T=Trj1,Trj2,…,Trjn=px1,py1,px2,py2,…pxn,pyn=px,1px2,…,pxnT,py1,py2,…,pynT, where pxi=xi1,xi2,…,xidTrepresents the projection vector set of the ith trajectory in the X axis direction, pyi=yi1,yi2,…,yidTrepresents the projection vector set of the ith trajectory in the Y axis direction, andpxi,pyi is called the vector set of the trajectory Trji.(4)
Kalman Filtering. The core is to use recursive algorithms to estimate the optimal system state and realize the prediction of target motion behavior [31]. The Kalman filtering system of state equations and observation equations is as follows:(2)Xk+1=AkXk+ΓkUk+TkWk,Zk=HkXk+Vk,whereXk+1 represents k+1 state value at the moment, Ak is the state transition matrix, Γk is the control matrix, Uk is the control input vector, Tk is the interference transfer matrix, Wk is the system state noise of the motion model, Zk is the observation vector, Hk is the observation matrix, and Vk is the observation noise.(5)
Prediction Error. For the geometric spatial error between the predicted trajectory point and the actual trajectory point, the root mean square error is shown as follows:(3)RMSE=∑i=1kxi′−xi2+yi′−yi2k,wherexi,yi represents the position of the actual trajectory point, xi′,yi′ position information represents predicted trajectory points, and k represents the number of predicted trajectory points.


### 4.1.2. Ship Trajectory Prediction

In this paper, the AIS observation data transmitted by the VHF channel are used to optimally estimate the system state such as the ship position and speed to make real-time prediction of the ship trajectory.(1) Ship Trajectory Modeling. The latitude and longitude of the ship are transformed into coordinates x,y in the Cartesian coordinate system through Mercator projection. Wxk and Wyk are the two orthogonal components of Gaussian white noise W(k) with zero mean and variance σW2, Wxk and Wyk are independent of each other at any time. The values are related to factors such as actual sea wind, waves, and weather. Vxk and Vyk are two orthogonal components of Gaussian white noise V(k) with zero mean and variance σV2, Vxk and Vyk are independent of each other at any time. The value is related to the error of the actual AIS information in the detection and transmission process. Wk and Vk are independent Gaussian white noises, which the corresponding covariances are Q and R.The model obtains the optimal state estimateX′k of the system at time k based on the number of observations transmitted by AIS in the first kt times. There are two different update processes in the process of the stochastic linear discrete Kalman filtering cycle, which are the time update process and the observation update process. The time update process is to predict the state at the current moment according to the optimal state estimation at the previous moment (see equation (4)). The observation update process is that after predicting the ship’s trajectory point at k+1 time, the observed value of the ship’s trajectory point at the actual k+1 time is used for linear fitting to find out the optimal estimated position of the trajectory point. That is to say, according to the observed value and the predicted value, the optimal estimation point of the ship’s trajectory at k+1 time is derived through the observation update equation, as shown in equation (5).(4)xk+1,k=xk,k+vktcosθk,yk+1,k=yk,k+vktsinθk,(5)xk+1,k+1=xk+1,k+Kk+1∗xzk+1−xk+1,k,yk+1,k+1=yk+1,k+Kk+1∗yzk+1−yk+1,k,where xk+1,k is the predicted x coordinate of the ship at time k+1. yk+1,k is the predicted y coordinate of the ship at time k+1. xk,k is the optimal estimate of the x coordinate of the ship at time k. yk,k is the optimal estimate of the y coordinate of the ship at time k. vk is the ship’s speed at time k, the θk is the heading of the ship at time k, and t is the time interval. Kk+1 is the filter gain matrix at time k+1. For the value and the update formula of the covariance Pk+1,k+1 of the optimal state estimation at time, see formula (6).(6)Pk+1,k=AkPk,kAkT+TkQkTkT,Sk+1=Hk+1Pk+1,kHk+1T+Rk+1,Kk+1=Pk+1,kHk+1TSk+1−1,Pk+1,k+1=Pk+1,k−Kk+1Sk+1Kk+1T.WhereQk is the system noise of the ship at node k, Rk is the observed noise, Pk,k is the error variance matrix, Ak is the ship state transition matrix, Pk+1,k is the error variance matrix of the predictive state xk+1,k and yk+1,k, and Kk is the filter gain matrix. Besides that, Wxk and Wyk have zero mean. Gaussian white noise with variance σW2 and the time update equation of equation (5), we can get Tk and Ak as the identity matrix. Furthermore, the coordinates do not undergo unit conversion. The observation matrix Hk is also the identity matrix. According to the above formula, the optimal position prediction value of the ship at a single step is obtained. If the ship nt position is predicted, the ship trajectory prediction can be completed iteratively.The ship trajectory prediction algorithm based on Kalman filtering is shown in Algorithm1. The detailed steps are as follows.Algorithm 1: Ship trajectory prediction algorithm based on Kalman filter.
Input: trajectory dynamic AIS dataset of moving shipsT=Trj1,Trj2,…,TrjnOutput: mean value of ship trajectory error RMSE(1)
D = trajectPretreatment (T)(2)
initParameters ()(3)
state = getCurrentState (D)(4)
fori = 1 to k:(5)
p = KalmanPredict (D)(6)
e[i] = getRMSE (p, p’)(7)
end for(8)
RMSE=∑i=1kei/k(9)
Output RMSEIn Algorithm1, the function trajectory predictionT is used to collect and decode ship AIS data and perform x,y preprocessing operations such as coordinate transformation. The function initParameters is used to determine the parameters of the ship’s motion model according to the state equation and observation equation of the system; besides, this function is also used to initialize the ship’s A, U, and Q with R and other parameters. The function getCurrentStateD is based on the optimal state estimate at the initial moment X0,0 and estimates error variance matrix P0,0, predicting the ship trajectory value at the next moment according to the system state equation X1,0 and obtaining the covariance matrix of the estimation error at the same time P1,0. According to the observed value Z1 of the ship trajectory at the next moment, theoptimal state estimation value X1,1 and the covariance matrix P1,1 of the optimal estimation error are obtained to complete the single-step filtering process of the ship trajectory. Then iteratively obtain the optimal state estimate X(n − 1, n − 1) at the time of n−1 to complete the filtering process. The function of Kalman  PredictD is to estimate the position of the ship's trajectory point at time n+1 based on the optimal state estimation Xn−1,n−1 at time n-1 and the observed value of current time n. The function of getRMSEp,p′ is to compare the predicted point p′ with real trajectory point p to calculate the filtering prediction error. Finally, repeat the operation k times to complete the prediction of the future k steps of ship trajectory points. Then, calculate and output the average prediction error.(2) Simulation Experiment Verification. Experimental model using sk indicates that the ship’s real location is at the sampling time kt.yk means observations of AIS data transmission at the moment kt, where yk=sk+vk, and vk represents observation noise. s′k means speed of ship at the moment kt, acceleration ak is a combination of maneuvering acceleration uk and random acceleration wk. The uniform acceleration motion and acceleration formula of the ship is as follows:(7)sk+1=sk+s′kt+0.5t2ak,s′k+1=s′k+tak,ak=uk+wk,where uk are the control signals of the ship’s power system; define the system status xk at the sampling time kt for the position and speed of the ship; the equations of motion and observation of the ship are shown as follows:(8)sk+1s′k+1=1T001sks′k+0.5T02T0uk+0.5T02T0wk,yk=10sks′k+vk.This experiment does not consider the ship’s own dynamic factorsuk=0 and state vector Xk generalized to four dimensions; its expression and system equations are shown in equation (9), and the initial position is set as −100m,200m, X shaft speed is set as 2m/s, and Y shaft speed is set as 20m/s. The experimental record of the ship trajectory formed at 20 time points is shown in Figure 2, and the error analysis diagram is shown in Figure 3.(9)xkxk−ykyk−=1,T,0,00,1,0,00,0,1,T0,0,0,1xk−1xk−1−yk−1yk−1−+0.5T2,0T,00,0.5T20,Twk,Zk=1,0,0,00,0,1,0xkxk−ykyk−+vk,Xk=xk,xk−,yk,yk−.Figure 2
Ship tracking trajectory.Figure 3
Ship tracking error.The observed ship trajectory obviously oscillates in Figure2, indicating that the measurement noise has a great impact, and after Kalman filtering, the filtering estimation is relatively close to the true trajectory of the ship. Figure 3 shows that the observed noise of the ship displacement is close to 32 m, and the experiment is only simulation; the actual ship AIS measurement error will not be so large. After Kalman filter processing, the ship’s displacement deviation is reduced to less than 12 m. Experiments show that Kalman filter can limit the impact of noise to the greatest extent and better predict the position after the ship.


## 4.1.1. Basic Concepts

(1)
AIS Data. AIS (automatic ship identification system) is a new navigation aid system for shore-to-ship, ship-to-shore, and ship-to-ship communication [29]. AIS equipment can send own ship information such as latitude and longitude, speed, heading, ship name, and other information to the target ship via VHF channel after processing by the processor and automatically obtain the position of other ships with similar equipment in real time, speed, heading, etc.(2)
Mercator Projection. Mercator projection is a map projection technology that uses an equiangular projection method. The principle is to assume that the Earth is enclosed in a hollow cylinder, whose datum of latitude (equator) is tangent to the cylinder, and then imagine a lamp in the center of the Earth, project the figure on the sphere onto the cylinder, and expand the cylinder to get a map drawn by the “Mercator projection” on the selected datum line [30].The experimental model needs to convert the WGS84 latitude and longitude coordinates in the AIS data to Mercatorx, y coordinates to predict the ship’s trajectory. According to the principle of Mercator projection, the projection of the equator is X axis, the projection of the prime meridian is Y axis, and the projection of the intersection of the two is the origin of the coordinate, which is positive toward east and north and negative toward west and south, forming the Mercator plane rectangular coordinate system. Let the long axis of the Earth be a and the short axis be b. The longitude of a point on the Earth is θ∈−π,+π with latitude α∈−π/2,+π/2; according to the equiangular principle, the coordinate conversion formula is as follows:(1)x=a∗θ,y=a∗lntanπ4+α2+e2ln1−e∗sinα1+e∗sinα,wheree=a2−b2/a2 is the first eccentricity of the Earth’s ellipsoid, and formula (1) θ,α translates to plane coordinates x,y.(3)
Trajectory Vector Set. Modeling the two-dimensional plane X axis and Y axis of Euclidean space, using vectors in the directions of the two coordinate axes to represent trajectory data, and let T be the trajectory vector set. T=Trj1,Trj2,…,Trjn=px1,py1,px2,py2,…pxn,pyn=px,1px2,…,pxnT,py1,py2,…,pynT, where pxi=xi1,xi2,…,xidTrepresents the projection vector set of the ith trajectory in the X axis direction, pyi=yi1,yi2,…,yidTrepresents the projection vector set of the ith trajectory in the Y axis direction, andpxi,pyi is called the vector set of the trajectory Trji.(4)
Kalman Filtering. The core is to use recursive algorithms to estimate the optimal system state and realize the prediction of target motion behavior [31]. The Kalman filtering system of state equations and observation equations is as follows:(2)Xk+1=AkXk+ΓkUk+TkWk,Zk=HkXk+Vk,whereXk+1 represents k+1 state value at the moment, Ak is the state transition matrix, Γk is the control matrix, Uk is the control input vector, Tk is the interference transfer matrix, Wk is the system state noise of the motion model, Zk is the observation vector, Hk is the observation matrix, and Vk is the observation noise.(5)
Prediction Error. For the geometric spatial error between the predicted trajectory point and the actual trajectory point, the root mean square error is shown as follows:(3)RMSE=∑i=1kxi′−xi2+yi′−yi2k,wherexi,yi represents the position of the actual trajectory point, xi′,yi′ position information represents predicted trajectory points, and k represents the number of predicted trajectory points.


## 4.1.2. Ship Trajectory Prediction

In this paper, the AIS observation data transmitted by the VHF channel are used to optimally estimate the system state such as the ship position and speed to make real-time prediction of the ship trajectory.(1) Ship Trajectory Modeling. The latitude and longitude of the ship are transformed into coordinates x,y in the Cartesian coordinate system through Mercator projection. Wxk and Wyk are the two orthogonal components of Gaussian white noise W(k) with zero mean and variance σW2, Wxk and Wyk are independent of each other at any time. The values are related to factors such as actual sea wind, waves, and weather. Vxk and Vyk are two orthogonal components of Gaussian white noise V(k) with zero mean and variance σV2, Vxk and Vyk are independent of each other at any time. The value is related to the error of the actual AIS information in the detection and transmission process. Wk and Vk are independent Gaussian white noises, which the corresponding covariances are Q and R.The model obtains the optimal state estimateX′k of the system at time k based on the number of observations transmitted by AIS in the first kt times. There are two different update processes in the process of the stochastic linear discrete Kalman filtering cycle, which are the time update process and the observation update process. The time update process is to predict the state at the current moment according to the optimal state estimation at the previous moment (see equation (4)). The observation update process is that after predicting the ship’s trajectory point at k+1 time, the observed value of the ship’s trajectory point at the actual k+1 time is used for linear fitting to find out the optimal estimated position of the trajectory point. That is to say, according to the observed value and the predicted value, the optimal estimation point of the ship’s trajectory at k+1 time is derived through the observation update equation, as shown in equation (5).(4)xk+1,k=xk,k+vktcosθk,yk+1,k=yk,k+vktsinθk,(5)xk+1,k+1=xk+1,k+Kk+1∗xzk+1−xk+1,k,yk+1,k+1=yk+1,k+Kk+1∗yzk+1−yk+1,k,where xk+1,k is the predicted x coordinate of the ship at time k+1. yk+1,k is the predicted y coordinate of the ship at time k+1. xk,k is the optimal estimate of the x coordinate of the ship at time k. yk,k is the optimal estimate of the y coordinate of the ship at time k. vk is the ship’s speed at time k, the θk is the heading of the ship at time k, and t is the time interval. Kk+1 is the filter gain matrix at time k+1. For the value and the update formula of the covariance Pk+1,k+1 of the optimal state estimation at time, see formula (6).(6)Pk+1,k=AkPk,kAkT+TkQkTkT,Sk+1=Hk+1Pk+1,kHk+1T+Rk+1,Kk+1=Pk+1,kHk+1TSk+1−1,Pk+1,k+1=Pk+1,k−Kk+1Sk+1Kk+1T.WhereQk is the system noise of the ship at node k, Rk is the observed noise, Pk,k is the error variance matrix, Ak is the ship state transition matrix, Pk+1,k is the error variance matrix of the predictive state xk+1,k and yk+1,k, and Kk is the filter gain matrix. Besides that, Wxk and Wyk have zero mean. Gaussian white noise with variance σW2 and the time update equation of equation (5), we can get Tk and Ak as the identity matrix. Furthermore, the coordinates do not undergo unit conversion. The observation matrix Hk is also the identity matrix. According to the above formula, the optimal position prediction value of the ship at a single step is obtained. If the ship nt position is predicted, the ship trajectory prediction can be completed iteratively.The ship trajectory prediction algorithm based on Kalman filtering is shown in Algorithm1. The detailed steps are as follows.Algorithm 1: Ship trajectory prediction algorithm based on Kalman filter.
Input: trajectory dynamic AIS dataset of moving shipsT=Trj1,Trj2,…,TrjnOutput: mean value of ship trajectory error RMSE(1)
D = trajectPretreatment (T)(2)
initParameters ()(3)
state = getCurrentState (D)(4)
fori = 1 to k:(5)
p = KalmanPredict (D)(6)
e[i] = getRMSE (p, p’)(7)
end for(8)
RMSE=∑i=1kei/k(9)
Output RMSEIn Algorithm1, the function trajectory predictionT is used to collect and decode ship AIS data and perform x,y preprocessing operations such as coordinate transformation. The function initParameters is used to determine the parameters of the ship’s motion model according to the state equation and observation equation of the system; besides, this function is also used to initialize the ship’s A, U, and Q with R and other parameters. The function getCurrentStateD is based on the optimal state estimate at the initial moment X0,0 and estimates error variance matrix P0,0, predicting the ship trajectory value at the next moment according to the system state equation X1,0 and obtaining the covariance matrix of the estimation error at the same time P1,0. According to the observed value Z1 of the ship trajectory at the next moment, theoptimal state estimation value X1,1 and the covariance matrix P1,1 of the optimal estimation error are obtained to complete the single-step filtering process of the ship trajectory. Then iteratively obtain the optimal state estimate X(n − 1, n − 1) at the time of n−1 to complete the filtering process. The function of Kalman  PredictD is to estimate the position of the ship's trajectory point at time n+1 based on the optimal state estimation Xn−1,n−1 at time n-1 and the observed value of current time n. The function of getRMSEp,p′ is to compare the predicted point p′ with real trajectory point p to calculate the filtering prediction error. Finally, repeat the operation k times to complete the prediction of the future k steps of ship trajectory points. Then, calculate and output the average prediction error.(2) Simulation Experiment Verification. Experimental model using sk indicates that the ship’s real location is at the sampling time kt.yk means observations of AIS data transmission at the moment kt, where yk=sk+vk, and vk represents observation noise. s′k means speed of ship at the moment kt, acceleration ak is a combination of maneuvering acceleration uk and random acceleration wk. The uniform acceleration motion and acceleration formula of the ship is as follows:(7)sk+1=sk+s′kt+0.5t2ak,s′k+1=s′k+tak,ak=uk+wk,where uk are the control signals of the ship’s power system; define the system status xk at the sampling time kt for the position and speed of the ship; the equations of motion and observation of the ship are shown as follows:(8)sk+1s′k+1=1T001sks′k+0.5T02T0uk+0.5T02T0wk,yk=10sks′k+vk.This experiment does not consider the ship’s own dynamic factorsuk=0 and state vector Xk generalized to four dimensions; its expression and system equations are shown in equation (9), and the initial position is set as −100m,200m, X shaft speed is set as 2m/s, and Y shaft speed is set as 20m/s. The experimental record of the ship trajectory formed at 20 time points is shown in Figure 2, and the error analysis diagram is shown in Figure 3.(9)xkxk−ykyk−=1,T,0,00,1,0,00,0,1,T0,0,0,1xk−1xk−1−yk−1yk−1−+0.5T2,0T,00,0.5T20,Twk,Zk=1,0,0,00,0,1,0xkxk−ykyk−+vk,Xk=xk,xk−,yk,yk−.Figure 2
Ship tracking trajectory.Figure 3
Ship tracking error.The observed ship trajectory obviously oscillates in Figure2, indicating that the measurement noise has a great impact, and after Kalman filtering, the filtering estimation is relatively close to the true trajectory of the ship. Figure 3 shows that the observed noise of the ship displacement is close to 32 m, and the experiment is only simulation; the actual ship AIS measurement error will not be so large. After Kalman filter processing, the ship’s displacement deviation is reduced to less than 12 m. Experiments show that Kalman filter can limit the impact of noise to the greatest extent and better predict the position after the ship.


## 4.2. Calculation of Ship Collision Risk

The membership function of different factors determines the value of ship collision risk. The collision risk of ships plays a key role in measuring the collision risk of ships and is an important basis for ship collision avoidance decision making [32]. The crew can decide the timing and order of avoidance according to the collision risk. There are many factors that affect the collision risk of ships. From the statistical research on the crew’s collision avoidance behavior at sea by experts and scholars [33] and the research on the decision-making process, it can be seen that the main factors for judging the collision risk are intership distance, azimuth, DCPA, TCPA, and speed ratio. These factors can fully reflect the encounter situation with the target, so the membership function of these factors is used as input to infer the collision risk of the ship.


### 4.2.1. Calculation of Influence Parameters

Kalman filtering prediction is used to obtain the shipX axis position coordinate x0, the Y axis position coordinate y0, the own ship’s speed on the X axis component xv0 and the Yaxis component yv0, other ship X axis position coordinate x1, Y axis position coordinate y1, the component xv1 on the X axis, and the component xv1 on the yv1 axis. Then, the longitude Aj, latitude Aw, heading Ah, and speed AS of the own ship and the longitude Bjm, latitude Bvm, heading Bhm, and speed BSm of other ships are obtained through the reverse solution of the Mercator projection equation. By substituting the above information into equation (10), the relevant influencing factor values can be solved.(10)D=2∗R∗arcsinsin2Bwm−Aw2+cosAw∗cosBwm∗sinBjm−Aj2,TB=arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈first quardrant,360+arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈second quardrant,180−arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈third and fourth quardrants,B=Ah−TB,RSH=arctanBsm∗cosBhm−As∗cosAhBsm∗sinBhm−As∗sinAh,RS=Bsm2+As2−2∗Bsm∗As∗cosAh−Bhm,DCPA=D∗sinRSH−RA−180∘,TCPA=D∗cosRSH−RA−180∘,where D, TB, B, RSH, and RS are the distance, azimuth, relative azimuth, relative speed course, and relative speed between ships.


### 4.2.2. Establishment of Collision Risk Model

The collision risk calculation method used in this paper is calculated through fuzzy sets. Fuzzy set is a set used to express the concept of fuzziness. It is defined as a given research rangeU; then a mapping from U to the unit interval [0, 1] is called a fuzzy set on U or a set of U fuzzy subset. Fuzzy set is described by membership function. The membership function occupies an extremely important position in fuzzy set theory. It is defined as if any element x in the research range U has a number Ax∈0,1 corresponding to it, then A is called the fuzzy set on U, and Ax is called the membership degree of x to A. When x changes in U, Ax is a function called A’s membership function. In the fuzzy set, the value range of its characteristic function is [0, 1] interval; this characteristic function is also called membership function. Membership function is an important basis of fuzzy set theory, so how to determine the membership function is a key issue. However, the object is “fuzzy” and empirical, so it is unrealistic to find a unified calculation method for membership. The fuzzy distribution method currently used is used to construct the membership function of each influencing factor to realize the calculation of ship collision risk. The membership function formula ((11)–(17)) used in this paper refers to the relevant formula in reference [33].(1) DCPA Membership FunctiontDCPA. DCPA is the distance that the ship will meet recently. Statistics show that when the distance between the two ships is less than the distance between the two ships, the possibility of collision between the ships is extremely large. According to the empirical data of collision avoidance in open waters, when DCPA≤0.6nmile, it is dangerous, tVDDCPA=1; when 0.6nmile<DCPA≤1.8nmile, it is considered very dangerous, tVDDCPA; when 0.6nmile<DCPA≤1.2nmile, it is considered dangerous, tDDCPA; when 1.0nmile<DCPA≤1.6nmile, it is considered fair, tNDCPA; when 1.4nmile<DCPA≤2.5nmile, it is considered safer, tSDCPA; when DCPA>2.5nmile, it is considered very safe, tVSDCPA. The membership function is shown in equation (11), and the corresponding function image is shown in Figure 4.(11)tVDDCPA=1,DCPA≤0.6nmile,0.5−0.5sinπ0.2x−0.7,0.6nmile<DCPA<0.8nmile,0,0.8nmile≤DCPA,tDDCPA=0,DCPA≤0.6nmile,0.5+0.5sinπ0.2x−0.7,0.6nmile<DCPA<0.8nmile,1,0.8nmile≤DCPA≤1nmile,0.5−0.5sinπ0.2x−1.1,1nmile<DCPA<1.2nmile,0,1.2nmile≤DCPA,tNDCPA=0,DCPA≤1nmile,0.5+0.5sinπ0.2x−1.1,1nmile<DCPA<1.2nmile,1,1.2nmile≤DCPA≤1.4nmile,0.5−0.5sinπ0.2x−1.5,1.4nmile<DCPA<1.6nmile,0,1.6nmile≤DCPA,tSDCPA=0,DCPA≤1.4nmile,0.5+0.5sinπ0.3x−1.55,1.4nmile<DCPA<1.7nmile,1,1.7nmile≤DCPA≤2nmile,0.5−0.5sinπ0.5x−2.25,2nmile<DCPA<2.5nmile,0,2.5nmile≤DCPA,tVSDCPA=0,DCPA≤2.0nmile,0.5+0.5sinπ0.5x−2.25,2.0nmile<DCPA<2.5nmile,1,2.5nmile≤DCPA.Figure 4
DCPA membership function image.(2) TCPA Membership FunctiontTCPA. TCPA is the recent meeting time of the ship, which reflects the urgency of the meeting situation between the two ships. Statistics and empirical data show that TCPA≤6min Time, tVDTCPA=1; when 8min≤TCPA≤9min Time, tDTCPA=1; when 11min≤TCPA≤12min Time, tNTCPA=1; when 14min≤TCPA≤15min Time, tSTCPA=1; when TCPA≥17minTime, tVSTCPA=1. The membership function is shown in equation (12), and the corresponding function image is shown in Figure 5.(12)tVDTCPA=1,TCAP≤6min,0.5−0.5sinπ2x−7,6min<TCPA<8min,0,8min≤TCPA,tDTCPA=0,TCAP≤6min,0.5+0.5sinπ2x−7,6min<TCPA<8min,1,8min≤TCPA≤9min,0.5−0.5sinπ2x−10,9min<TCPA<11min,0,11min≤TCPA,tNTCPA=0,TCAP≤9min,0.5+0.5sinπ2x−10,9min<TCPA<11min,1,11min≤TCPA≤12min,0.5−0.5sinπ2x−13,12min<TCPA<14min,0,14min≤TCPA,tSTCPA=0,TCAP≤12min,0.5+0.5sinπ2x−13,12min<TCPA<14min,114min≤TCPA≤15min,0.5−0.5sinπ2x−16,15min<TCPA<17min,0,17min≤TCPA,tVSTCPA=0,TCAP≤15min0.5+0.5sinπ2x−16,15min<TCPA<17min,1,17min≤TCPA.Figure 5
TCPA membership function image.(3) D Membership FunctiontD. D It is the distance between ships; the smaller the value is, the closer the target ship is and the greater the collision risk of the ship is. Statistical empirical data show that when D≤1.5nmile, tVDD=1; when 1.7nmile≤D≤2nmile, tDD=1; when 2.2nmile<D<2.5nmile, tND=1; when 2.7nmile<D<3nmile, tSD=1; when D>=3.2nmile, tVSD=1. The membership function is shown in equation (13), and the corresponding function image is shown in Figure 6.(13)tVDD=1,D≤1.5nmile,0.5−0.5sinπ0.2x−1.6,1.5nmile<D<1.7nmile,0,1.7nmile≤D,tDD=0,D≤1.5nmile,0.5+0.5sinπ0.2x−1.6,1.5nmile<D<1.7nmile,1,1.7nmile≤D≤2nmile,0.5−0.5sinπ0.2x−2.1,2nmile<D<2.2nmile,0,2.2nmile≤D,tND=0,D≤2nmile,0.5+0.5sinπ0.2x−2.1,2nmile<D<2.2nmile,1,2.2nmile≤D≤2.5nmile,0.5−0.5sinπ0.2x−2.6,2.5nmile<D<2.7nmile,0,2.7nmile≤D,tSD=0,D≤2.5nmile,0.5+0.5sinπ0.2x−2.6,2.5nmile<D<2.7nmile,1,2.7nmile≤D≤3nmile,0.5−0.5sinπ0.2x−3.1,3nmile<D<3.2nmile,0,3.2nmile≤D,tVSD=0,D≤3nmile,0.5+0.5sinπ0.2x−3.1,3nmile<D<3.2nmile,1,3.2nmile≤D.Figure 6
D membership function image.(4) B Membership FunctiontB. B is the relative position between ships, and the danger of coming ships with different relative positions is different from their own ships. Statistical empirical data show that the safety of each area is ranked as E, A, B, C, D. E area arrival range is 335°∼5°, and the meeting situation between the coming ship and own ship in this area is the most dangerous meeting situation. A area arrival range is 5°∼67.5°, and the meeting situation between the coming ship and own ship in this area is a starboard small angle crossing meeting situation, which is more dangerous. B area arrival range is 67.5°∼122.5°, and the meeting situation between the coming ship and own ship in this area is a starboard high-angle crossing meeting situation, and the danger is average. C area arrival range is122.5°∼210.5°, and the meeting situation between the coming ship and own ship in this area is safer. D area arrival range is 247.5°∼355°, and the meeting situation between the incoming ship and own ship in this area is safe. The membership function is shown in equation (14), and the corresponding function image is shown in Figure 7.(14)tVDB=1−B360°0°≤B≤5°,B360°355°≤B≤0°,tDB=1−B−36.25°360°5°<B<67.5°,tNB=1−B−90°360°67.5°≤B≤122.5°,tSB=1−B−180°360°122.5°<B<247.5°,tVSB=1−B−301.75°360°247.5°≤B<355°.Figure 7
B membership function image.(5) Ship Speed Ratio Membership FunctiontK. Define the speed ratio K of the own ship and the targetship m as As/Bsm. The statistical research on collision avoidance shows that when the own ship is a low-speed ship, collision avoidance actions must be taken as soon as possible and it needs to turn a large angle. Take tK=0.5 as the boundary point between safety and danger. The larger the value of tK, the higher the risk of collision. The membership function is shown in equation (15), and the corresponding function image is shown in Figure 8.(15)tK=11+1/K2.Figure 8
Ship speed ratio membership function image.(6) Calculation of Ship Collision Risk. Drawing on the research results at home and abroad and the experience of collision avoidance in open waters at sea, this paper establishes the evaluation criteria for the danger avoidance of each factor as shown in Table 1. The importance of the factor set DCPA,TCPA,D,B,Kthat affects the collision risk of ships is in order of DCPA>TCPA>D>B>K. According to the investigation in the literature [34], during the course of crew training bridge resource management, the corresponding weight of the factor set is W=0.4,0.367,0.167,0.033,0.033. The final risk vector R can be obtained through the evaluation matrix formed by the weight vector W and membership function of each factor (see equation (16)).(16)R=WDCPA,WTCPA,WD,WB,WKtVDDCPAtDDCPAtNDCPAtSDCPAtVSDCPAtVDTCPAtDTCPAtNTCPAtSTCPAtVSTCPAtVDDtDDtNDtSDtVSDtVDBtDBtNBtSBtVSBtVDKtDKtNKtSKtVSK=WDCPAtVDDCPA⊕WTCPAtVDTCPA⊕WDtVDD⊕WBtVDB⊕WKtVDKWDCPAtDDCPA⊕WTCPAtDTCPA⊕WDtDD⊕WBtDB⊕WKtDKWDCPAtNDCPA⊕WTCPAtNTCPA⊕WDtND⊕WBtNB⊕WKtNKWDCPAtSDCPA⊕WTCPAtSTCPA⊕WDtSD⊕WBtSB⊕WKtSKWDCPAtVSDCPA⊕WTCPAtVSTCPA⊕WDtVSD⊕WBtVSB⊕WKtVSK.Table 1
Criteria for risk evaluation of various factors.
FactorLow riskLow riskAverage riskHigh riskHigh riskDCPAnmile2.5∼4.01.2∼2.51.0∼1.60.6∼1.20.6∼0.8TCPAmin18151296Dnmile4.03.02.52.01.5B°301.75。180。90。36.25。0。K<0.50.5∼0.80.8∼1.21.2∼2>2Here,⊕ is a hazard synthesis operator. According to the actual operation requirements of collision avoidance at sea, the synthesis operator is regulated as follows:(17)α⊕β=min1,α+β.


### 4.2.3. Calculation of Ship Collision Risk

Literature [34] sets the size of the collision risk of the target ship relative to the own ship as a set −2,−1,0,1,2. It is divided into five dangers: low danger, low danger, normal danger, high danger, and high danger, calculated by weighting the vector R by its weight value. Table 2 shows the relevant data and the influencing factors (the first is the own ship data) of the own ship and the 4 experimental ships at that moment. Figure 4 shows the hazard curves of the ship and the four experimental ships when the steering angle of the ship is limited within the range −35,35. The horizontal axis is the number of steering angles of the ship. Negative values represent counterclockwise steering.Table 2
Related data of own ship and other ships.
LongitudeLatitudeCourseSpeedBearingRelative bearingDistanceRelative speed headingRelativeDCPATCPACollision risk2330050————————23.0730.022206071.7271.724.33201.89103.42−3.311.62−0.07722.8830.0131060275.52275.527.23256.0347.362.418.630.05723.0529.9826060114.78114.783.18224.3684.51−2.990.750.2822.8729.974060255.11255.117.9795.9838.782.8411.521.17From Figure9 and Table 2, it can be seen that when own ship is at the initial heading (the horizontal axis of the image is 0), the danger is first ship > second ship > third ship > fourth ship, and as the ship’s clockwise steering angle increases, the danger of the second ship becomes higher, making it more prone to collision risks.Figure 9
Curve of ship collision risk.


## 4.2.1. Calculation of Influence Parameters

Kalman filtering prediction is used to obtain the shipX axis position coordinate x0, the Y axis position coordinate y0, the own ship’s speed on the X axis component xv0 and the Yaxis component yv0, other ship X axis position coordinate x1, Y axis position coordinate y1, the component xv1 on the X axis, and the component xv1 on the yv1 axis. Then, the longitude Aj, latitude Aw, heading Ah, and speed AS of the own ship and the longitude Bjm, latitude Bvm, heading Bhm, and speed BSm of other ships are obtained through the reverse solution of the Mercator projection equation. By substituting the above information into equation (10), the relevant influencing factor values can be solved.(10)D=2∗R∗arcsinsin2Bwm−Aw2+cosAw∗cosBwm∗sinBjm−Aj2,TB=arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈first quardrant,360+arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈second quardrant,180−arctanBjm−Aj∗cosBwmBwm−Aw;arctanBjm−Aj∗cosBwmBwm−Aw∈third and fourth quardrants,B=Ah−TB,RSH=arctanBsm∗cosBhm−As∗cosAhBsm∗sinBhm−As∗sinAh,RS=Bsm2+As2−2∗Bsm∗As∗cosAh−Bhm,DCPA=D∗sinRSH−RA−180∘,TCPA=D∗cosRSH−RA−180∘,where D, TB, B, RSH, and RS are the distance, azimuth, relative azimuth, relative speed course, and relative speed between ships.


## 4.2.2. Establishment of Collision Risk Model

The collision risk calculation method used in this paper is calculated through fuzzy sets. Fuzzy set is a set used to express the concept of fuzziness. It is defined as a given research rangeU; then a mapping from U to the unit interval [0, 1] is called a fuzzy set on U or a set of U fuzzy subset. Fuzzy set is described by membership function. The membership function occupies an extremely important position in fuzzy set theory. It is defined as if any element x in the research range U has a number Ax∈0,1 corresponding to it, then A is called the fuzzy set on U, and Ax is called the membership degree of x to A. When x changes in U, Ax is a function called A’s membership function. In the fuzzy set, the value range of its characteristic function is [0, 1] interval; this characteristic function is also called membership function. Membership function is an important basis of fuzzy set theory, so how to determine the membership function is a key issue. However, the object is “fuzzy” and empirical, so it is unrealistic to find a unified calculation method for membership. The fuzzy distribution method currently used is used to construct the membership function of each influencing factor to realize the calculation of ship collision risk. The membership function formula ((11)–(17)) used in this paper refers to the relevant formula in reference [33].(1) DCPA Membership FunctiontDCPA. DCPA is the distance that the ship will meet recently. Statistics show that when the distance between the two ships is less than the distance between the two ships, the possibility of collision between the ships is extremely large. According to the empirical data of collision avoidance in open waters, when DCPA≤0.6nmile, it is dangerous, tVDDCPA=1; when 0.6nmile<DCPA≤1.8nmile, it is considered very dangerous, tVDDCPA; when 0.6nmile<DCPA≤1.2nmile, it is considered dangerous, tDDCPA; when 1.0nmile<DCPA≤1.6nmile, it is considered fair, tNDCPA; when 1.4nmile<DCPA≤2.5nmile, it is considered safer, tSDCPA; when DCPA>2.5nmile, it is considered very safe, tVSDCPA. The membership function is shown in equation (11), and the corresponding function image is shown in Figure 4.(11)tVDDCPA=1,DCPA≤0.6nmile,0.5−0.5sinπ0.2x−0.7,0.6nmile<DCPA<0.8nmile,0,0.8nmile≤DCPA,tDDCPA=0,DCPA≤0.6nmile,0.5+0.5sinπ0.2x−0.7,0.6nmile<DCPA<0.8nmile,1,0.8nmile≤DCPA≤1nmile,0.5−0.5sinπ0.2x−1.1,1nmile<DCPA<1.2nmile,0,1.2nmile≤DCPA,tNDCPA=0,DCPA≤1nmile,0.5+0.5sinπ0.2x−1.1,1nmile<DCPA<1.2nmile,1,1.2nmile≤DCPA≤1.4nmile,0.5−0.5sinπ0.2x−1.5,1.4nmile<DCPA<1.6nmile,0,1.6nmile≤DCPA,tSDCPA=0,DCPA≤1.4nmile,0.5+0.5sinπ0.3x−1.55,1.4nmile<DCPA<1.7nmile,1,1.7nmile≤DCPA≤2nmile,0.5−0.5sinπ0.5x−2.25,2nmile<DCPA<2.5nmile,0,2.5nmile≤DCPA,tVSDCPA=0,DCPA≤2.0nmile,0.5+0.5sinπ0.5x−2.25,2.0nmile<DCPA<2.5nmile,1,2.5nmile≤DCPA.Figure 4
DCPA membership function image.(2) TCPA Membership FunctiontTCPA. TCPA is the recent meeting time of the ship, which reflects the urgency of the meeting situation between the two ships. Statistics and empirical data show that TCPA≤6min Time, tVDTCPA=1; when 8min≤TCPA≤9min Time, tDTCPA=1; when 11min≤TCPA≤12min Time, tNTCPA=1; when 14min≤TCPA≤15min Time, tSTCPA=1; when TCPA≥17minTime, tVSTCPA=1. The membership function is shown in equation (12), and the corresponding function image is shown in Figure 5.(12)tVDTCPA=1,TCAP≤6min,0.5−0.5sinπ2x−7,6min<TCPA<8min,0,8min≤TCPA,tDTCPA=0,TCAP≤6min,0.5+0.5sinπ2x−7,6min<TCPA<8min,1,8min≤TCPA≤9min,0.5−0.5sinπ2x−10,9min<TCPA<11min,0,11min≤TCPA,tNTCPA=0,TCAP≤9min,0.5+0.5sinπ2x−10,9min<TCPA<11min,1,11min≤TCPA≤12min,0.5−0.5sinπ2x−13,12min<TCPA<14min,0,14min≤TCPA,tSTCPA=0,TCAP≤12min,0.5+0.5sinπ2x−13,12min<TCPA<14min,114min≤TCPA≤15min,0.5−0.5sinπ2x−16,15min<TCPA<17min,0,17min≤TCPA,tVSTCPA=0,TCAP≤15min0.5+0.5sinπ2x−16,15min<TCPA<17min,1,17min≤TCPA.Figure 5
TCPA membership function image.(3) D Membership FunctiontD. D It is the distance between ships; the smaller the value is, the closer the target ship is and the greater the collision risk of the ship is. Statistical empirical data show that when D≤1.5nmile, tVDD=1; when 1.7nmile≤D≤2nmile, tDD=1; when 2.2nmile<D<2.5nmile, tND=1; when 2.7nmile<D<3nmile, tSD=1; when D>=3.2nmile, tVSD=1. The membership function is shown in equation (13), and the corresponding function image is shown in Figure 6.(13)tVDD=1,D≤1.5nmile,0.5−0.5sinπ0.2x−1.6,1.5nmile<D<1.7nmile,0,1.7nmile≤D,tDD=0,D≤1.5nmile,0.5+0.5sinπ0.2x−1.6,1.5nmile<D<1.7nmile,1,1.7nmile≤D≤2nmile,0.5−0.5sinπ0.2x−2.1,2nmile<D<2.2nmile,0,2.2nmile≤D,tND=0,D≤2nmile,0.5+0.5sinπ0.2x−2.1,2nmile<D<2.2nmile,1,2.2nmile≤D≤2.5nmile,0.5−0.5sinπ0.2x−2.6,2.5nmile<D<2.7nmile,0,2.7nmile≤D,tSD=0,D≤2.5nmile,0.5+0.5sinπ0.2x−2.6,2.5nmile<D<2.7nmile,1,2.7nmile≤D≤3nmile,0.5−0.5sinπ0.2x−3.1,3nmile<D<3.2nmile,0,3.2nmile≤D,tVSD=0,D≤3nmile,0.5+0.5sinπ0.2x−3.1,3nmile<D<3.2nmile,1,3.2nmile≤D.Figure 6
D membership function image.(4) B Membership FunctiontB. B is the relative position between ships, and the danger of coming ships with different relative positions is different from their own ships. Statistical empirical data show that the safety of each area is ranked as E, A, B, C, D. E area arrival range is 335°∼5°, and the meeting situation between the coming ship and own ship in this area is the most dangerous meeting situation. A area arrival range is 5°∼67.5°, and the meeting situation between the coming ship and own ship in this area is a starboard small angle crossing meeting situation, which is more dangerous. B area arrival range is 67.5°∼122.5°, and the meeting situation between the coming ship and own ship in this area is a starboard high-angle crossing meeting situation, and the danger is average. C area arrival range is122.5°∼210.5°, and the meeting situation between the coming ship and own ship in this area is safer. D area arrival range is 247.5°∼355°, and the meeting situation between the incoming ship and own ship in this area is safe. The membership function is shown in equation (14), and the corresponding function image is shown in Figure 7.(14)tVDB=1−B360°0°≤B≤5°,B360°355°≤B≤0°,tDB=1−B−36.25°360°5°<B<67.5°,tNB=1−B−90°360°67.5°≤B≤122.5°,tSB=1−B−180°360°122.5°<B<247.5°,tVSB=1−B−301.75°360°247.5°≤B<355°.Figure 7
B membership function image.(5) Ship Speed Ratio Membership FunctiontK. Define the speed ratio K of the own ship and the targetship m as As/Bsm. The statistical research on collision avoidance shows that when the own ship is a low-speed ship, collision avoidance actions must be taken as soon as possible and it needs to turn a large angle. Take tK=0.5 as the boundary point between safety and danger. The larger the value of tK, the higher the risk of collision. The membership function is shown in equation (15), and the corresponding function image is shown in Figure 8.(15)tK=11+1/K2.Figure 8
Ship speed ratio membership function image.(6) Calculation of Ship Collision Risk. Drawing on the research results at home and abroad and the experience of collision avoidance in open waters at sea, this paper establishes the evaluation criteria for the danger avoidance of each factor as shown in Table 1. The importance of the factor set DCPA,TCPA,D,B,Kthat affects the collision risk of ships is in order of DCPA>TCPA>D>B>K. According to the investigation in the literature [34], during the course of crew training bridge resource management, the corresponding weight of the factor set is W=0.4,0.367,0.167,0.033,0.033. The final risk vector R can be obtained through the evaluation matrix formed by the weight vector W and membership function of each factor (see equation (16)).(16)R=WDCPA,WTCPA,WD,WB,WKtVDDCPAtDDCPAtNDCPAtSDCPAtVSDCPAtVDTCPAtDTCPAtNTCPAtSTCPAtVSTCPAtVDDtDDtNDtSDtVSDtVDBtDBtNBtSBtVSBtVDKtDKtNKtSKtVSK=WDCPAtVDDCPA⊕WTCPAtVDTCPA⊕WDtVDD⊕WBtVDB⊕WKtVDKWDCPAtDDCPA⊕WTCPAtDTCPA⊕WDtDD⊕WBtDB⊕WKtDKWDCPAtNDCPA⊕WTCPAtNTCPA⊕WDtND⊕WBtNB⊕WKtNKWDCPAtSDCPA⊕WTCPAtSTCPA⊕WDtSD⊕WBtSB⊕WKtSKWDCPAtVSDCPA⊕WTCPAtVSTCPA⊕WDtVSD⊕WBtVSB⊕WKtVSK.Table 1
Criteria for risk evaluation of various factors.
FactorLow riskLow riskAverage riskHigh riskHigh riskDCPAnmile2.5∼4.01.2∼2.51.0∼1.60.6∼1.20.6∼0.8TCPAmin18151296Dnmile4.03.02.52.01.5B°301.75。180。90。36.25。0。K<0.50.5∼0.80.8∼1.21.2∼2>2Here,⊕ is a hazard synthesis operator. According to the actual operation requirements of collision avoidance at sea, the synthesis operator is regulated as follows:(17)α⊕β=min1,α+β.


## 4.2.3. Calculation of Ship Collision Risk

Literature [34] sets the size of the collision risk of the target ship relative to the own ship as a set −2,−1,0,1,2. It is divided into five dangers: low danger, low danger, normal danger, high danger, and high danger, calculated by weighting the vector R by its weight value. Table 2 shows the relevant data and the influencing factors (the first is the own ship data) of the own ship and the 4 experimental ships at that moment. Figure 4 shows the hazard curves of the ship and the four experimental ships when the steering angle of the ship is limited within the range −35,35. The horizontal axis is the number of steering angles of the ship. Negative values represent counterclockwise steering.Table 2
Related data of own ship and other ships.
LongitudeLatitudeCourseSpeedBearingRelative bearingDistanceRelative speed headingRelativeDCPATCPACollision risk2330050————————23.0730.022206071.7271.724.33201.89103.42−3.311.62−0.07722.8830.0131060275.52275.527.23256.0347.362.418.630.05723.0529.9826060114.78114.783.18224.3684.51−2.990.750.2822.8729.974060255.11255.117.9795.9838.782.8411.521.17From Figure9 and Table 2, it can be seen that when own ship is at the initial heading (the horizontal axis of the image is 0), the danger is first ship > second ship > third ship > fourth ship, and as the ship’s clockwise steering angle increases, the danger of the second ship becomes higher, making it more prone to collision risks.Figure 9
Curve of ship collision risk.


## 4.3. Ship Steering Angle Decision

By analyzing the collision risk curve of the ship in Figure4 and following the rule that the ship will always avoid the most dangerous ship each time when avoiding a collision, the lower the collision risk of the ship in the curve, the more likely it is to collide. We analyze the collision risk curve of the ship, take the lowest value of the ship’s danger degree corresponding to each steering angle, and record the name (serial number) of the ship with the lowest collision danger when the steering angle is zero so as to analyze the current situation of the ship corresponding to the most dangerous target ship situation and determine the direction of the ship’s steering angle.The encounter situation of ships is determined in accordance with the applicable provisions of the rules for avoiding collisions. The rules for avoiding collisions are the basic guidelines for the safe navigation of ships at sea, and they are also an important legal basis for regulating ship avoidance actions. The rules clearly stipulate the methods of avoidance of ships in various situations and play an important role in guiding the safe navigation and avoidance of ships. The encounter situation is mainly divided into two types: first, under the provisions of the collision avoidance rules, the meeting situation is divided according to the possible collision avoidance actions of the crew and the degree of collision avoidance difficulty. The second is from the angle of collision avoidance action (left and right collision avoidance) and according to the relative azimuth (side angle) of the target ship [34]. Reference [28] divides three kinds of ship encounter situations, including 16 kinds of ship encounter situations, based on the relative position relationship between the own ship and the target ship, the avoidance responsibility, and the steering avoidance action method and good visibility. In this paper, by collecting the actual control experience of the master and crew and combining with the provisions of the International Regulations for Preventing Collisions at Sea in 1972, the specific directions of the ship’s steering angles for the overtaking ship, the giving way ship, and the ship in the encounter are given.Rule 13 of the Collision Avoidance Rule: “when a ship is catching up with other ships from a certain direction that is more than 22.5 degrees behind the other ship, that is, the position of the ship it is chasing, it can only see the taillight of the overtaken ship at night, but not the other. Any of its side lights should be considered to be overtaking.” According to the rules of collision avoidance and actual navigational experience, when the ship is an overtaking ship, the crew usually practices the rudder to the left. Regardless of any change in the orientation between the two ships, until the responsibility of the overtaken ship is relieved and the ship passes by to clear it, the situation is shown in Figures10 and 11, where Figure 10 is a direct ship and Figure 11 is an overpass. In the following picture, the blue solid line is the main ship and the yellow dotted line is the target ship.Figure 10
Overtaking situation (own ship is a direct ship).
(a)(b)(c)(d)Figure 11
Overtaking situation (own ship is overtaking ship).
(a)(b)(c)(d)Rule 14 of the Collision Avoidance Rule: “when two motor ships meet in opposite or near opposite headings and there is a danger of collision, they each turn to the right so that they each pass through the port side of other ships”; according to collision avoidance, the crew members should normally steer the rudder to the right, and the situation is shown in Figure12.Figure 12
Meeting situation.
(a)(b)Rule 15 of the Collision Avoidance Rule: “when two motor boats cross each other and there is a danger of collision, a ship with other ships on the starboard side of the ship should make way for other ships. If the environment permits at the time, they should also avoid crossing the front of other ships.” According to the rules of collision avoidance and actual navigational experience, when the ship is a yielding ship, the crew usually practices the rudder to the right until the responsibility of the yielding ship is relieved. The situation is shown in Figures13 and 14. Among them, the first two small pictures in Figures 13 and 14 limit the speed ratio of own ship to the target ship.Figure 13
Crossing situation (own ship is a give way ship).
(a)(b)(c)Figure 14
Cross situation (own ship is a direct ship).
(a)(b)(c)According to the literature [35], the ship’s danger is divided into 5 levels. The minimum value of the collision danger corresponding to the ship at the current moment is obtained through the curve in Figure 5. When the value is less than −0.4, the collision risk of the ship is more likely to require a collision avoidance decision. At the moment, the meeting situation of the ship with the lowest collision risk is determined. According to the above conclusions, the determination of the ship rudder angle direction is completed.


## 5. Decision Method of Optimal Steering Angle Based on Improved Cultural Particle Swarm

After finding the direction of ship’s steering angle under the collision avoidance rules inSection 3, this section will find the optimal steering angle of the ship under this direction to achieve ship collision avoidance. In order to be more in line with the actual sailing environment of marine vessels and obtain more accurate results, this paper uses the CPSO (cultural particle swarm optimization) algorithm to establish the main swarm space (lower space) and knowledge space (upper space) of the particle swarm and improve the evolution efficiency through the interaction between the two levels so as to find the optimal steering angle of the ship more effectively.


### 5.1. Cultural Particle Swarm Algorithm

#### 5.1.1. Cultural Algorithm

Cultural algorithm (CA) is a new global optimization search algorithm created by Reynolds et al. to solve complex calculations in 1994. Researchers [36] see culture as a carrier of information that potentially affects all members of society and is useful in guiding the evolutionary process of contemporaries and offspring. Cultural algorithm is a two-layer evolution system based on knowledge which contains two evolution spaces: one is a belief space composed of experience and knowledge acquired during the evolution process and the other one is the population space composed of specific individuals, which is solved iteratively through evolutionary operations and performance evaluation. The basic framework of the cultural algorithm is shown in Figure 15.Figure 15
Graphical representation of the cultural algorithm.As shown in Figure15, population space and belief space are two relatively independent evolutionary processes. The two spaces are linked by a set of communication protocols consisting of acceptor function Accept and influence function Influence. During the evolution process of individuals in the population space, individual experiences are formed, and the individual experiences are transferred to the belief space through Accept functions. Belief space compares and optimizes individual experience according to certain behavior rules to form population experience. Belief space is updated with Update functions based on existing population experience and new individual experience; the Influence function can use the empirical knowledge of the problem to be solved in the belief space to guide the evolution of the population space so that the population space can obtain higher evolution efficiency. In a cultural system, there are many kinds of knowledge, among which normative knowledge and situational knowledge are regarded as the most important knowledge. Normative knowledge provides behavioral norms and guiding principles for individuals, and situational knowledge provides examples for individuals. They can provide guidance information for the evolution of populations. objective function is the objective function (fitness function). Its function is to evaluate the fitness value of individuals in the population space. generate function generates the next generation of individuals based on the rules of individual behavior and the parameters of the parents. The select function selects a part of the newly generated individuals as the parents of the next generation of individuals according to the rules (see Algorithm 2).Algorithm 2: Cultural algorithm pseudocode.
(1)
begin(2)
t = 0;(3)
POP(t); //Initialize the population space(4)
BLF(t); //Initialize the belief space(5)
repeat(6)
POP(t); //Assessing population space(7)
update (BLF(t), accept (POP(t)));(8)
generate (POP(t), influence (BLF(t)));(9)
t = t + 1;(10)
select POP(t) from POP(t−1);(11)
until Termination condition(12)
end


#### 5.1.2. Particle Swarm Algorithm

The term “group intelligence” was first coined by Beni et al. [37]. It was proposed in the research of cellular robot systems. Typical swarm intelligence consists of a group of simple agents with local influence and their environment. Although there is no centralized control structure in the swarm intelligence system to guide the behavior of these agents, local influences can often generate global behavior. Particle swarm optimization, as a typical swarm intelligence optimization algorithm, originates from the research on the simplified social model of bird swarms and the simulation of behaviors [38].Suppose each particle in the particle swarm algorithm is flying at a certain speed in then-dimensional search space; Xi=xi1,xi2,…,xin is particles i’s position, Vi=vi1,vi2,…,vin is particles i’s speed, and pbesti=pbesti1,pbesti2,…,pbestin is optimal position experienced by particles i. The current optimal position, global optimal position, particle moving speed, and position update formula are shown in the following equation:(18)pbestit+1=pbestit,iffXit+1≥fpbestit,Xit+1,iffXit+1<fpbestit,gbestt=minfpbest1t,fpbest2t,…,fpbestNt,vijt+1=wvijt+c1r1pbestijt−xijt+c2r2gbestjt−xijt,xijt+1=xijt+vijt+1,where gbestt is the global optimal position, w is the inertia weight, i is the first i particles, j is particle dimension, c1, c2 are the acceleration factors, and r1, r2 are random numbers among 0,1. Particle swarm algorithm speed update equation consists of three parts: the first part is the previous speed of the particle; the second part is called the “cognitive” part, which comes from the experience and thinking of the particle itself; the acceleration factor c1 can adjust the flight step size of the particle’s best position; the third part is the “social” part of the particle, indicating information sharing and interaction between particles and acceleration factors c2. You can adjust the particle’s flight step to the optimal position of the group.


#### 5.1.3. Cultural Particle Swarm Algorithm

The CA algorithm framework provides a computational model of multiple evolutionary processes, so from the perspective of the computational model, any evolutionary algorithm that meets the requirements of a cultural algorithm can be embedded in the cultural algorithm framework as an evolutionary process of population space. The current research studies mainly focus on the group intelligence algorithms such as GA, POS, and ACO. Unlike the existing evolutionary algorithms, CA provides a dual evolution mechanism. Based on the group space evolutionary algorithm, through the acquisition, preservation, analysis, and integration of the empirical knowledge generated by individual evolution, the evolution process of the population space is further guided so that the evolution speed of the population surpasses the evolution speed solely relying on ordinary evolution algorithms and has good global optimization performance.The essence of cultural particle swarm optimization algorithm is a combination of cultural algorithm model and particle swarm optimization. During the PSO evolution process, particles track two “extreme values”: one is the individual historical optimal solution, the other is the global historical optimal solution, and the global historical optimal solution is passed from generation to generation, which naturally forms the trajectory of the global optimal solution. These optimal solutions are regarded as the global knowledge information of iterative search which is kept continuously, and the knowledge space is updated; the knowledge solution is evolved. At the same time, the further solution of PSO group is guided. Through the dual evolution and mutual influence of PSO space (main group space) and knowledge space, the solution has better global search ability.


### 5.2. Improvements to the Cultural Particle Swarm Algorithm

#### 5.2.1. Premature Convergence Judgment

The diversity of the particle swarm population is a prerequisite for the effective operation of the algorithm, and the greater the population diversity, the more likely it is to produce better offspring individuals. However, due to the solution process of the particle swarm algorithm, the diversity will be gradually lost, and the individuals will converge with each other. The particle with the optimal current position will guide other particles to approach it quickly. If the position of the current optimal particle is a local optimal solution, the entire group cannot search again and can fall into a precocious convergence state. Generally, the fitness of different distributed particles in the population space is different. The degree of diversity of particles can be expressed by the degree of dispersion of fitness distribution of particles. When the PSO algorithm is in the state of premature convergence or global convergence, particles will gather in one place or in several specific places. Therefore, the state of the particle swarm can be judged by studying the change of the particle fitness value in the population space, thereby determining whether the algorithm converges.This paper introduces the index proposed in [34] to evaluate the premature convergence of the particle swarm, which is defined as: Let the size of the particle swarm ben. In the k-th iteration, the fitness value of the particle is fik and the average fitness value of the particle swarm is favgk; favgk¯ is obtained by averaging the fitness values of particles whose fitness value is better than favgk, which is defined as follows:(19)ρ=fmk−favgk¯fmk−1−favgk−1¯,where ρ evaluates the degree of convergence of the particle swarm algorithm; the smaller ρ is, the more the particle swarm tends to converge.


#### 5.2.2. Dynamic Adjustment of Inertia Weight

The standard particle swarm algorithm uses linearly decreasing inertial weights because the linearly decreasing inertial weight changes are too singular, and the process of searching the optimal steering angle of a ship by the particle swarm algorithm is very complicated and nonlinear; it is suitable for complex problems. Both ability and regulation ability are very limited. Aiming at the above problems, this paper proposes a strategy for dynamically adjusting the inertia weights, combining the changes of the inertia weights with indicators to evaluate the degree of premature convergence of the particle swarm:(20)wit=1−1+e−ρ−1.It can be seen from the above formula that the particle’s inertia weight value changes within (0, 1),wit describes the effect of the inertia of the i-th particle on the t-th velocity, and the value can adjust the global optimization ability of the PSO and local optimization capabilities. When the PSO is in a state of convergence, a large inertia weight is required to increase the search step size, thereby enhancing the global optimization capability of the PSO. When the PSO is in the global search state, a small inertia weight is required to reduce the search step size, thereby enhancing the local optimization capability of the PSO. When the index for evaluating the degree of premature convergence of the particle swarm decreases, wit increases accordingly, which enhances the global search ability; when ρ increases, the value of wit decreases accordingly, increasing the local search ability.Figure 16
Fitness function curve.


### 5.3. Optimal Steering Angle Decision Algorithm

#### 5.3.1. Particle Swarm Space Design and Iteration Rules

(1)
Coding Scheme. The particle swarm in the population space encodes the particle swarm according to the Michigan coding scheme, that is, each particle represents a ship collision avoidance strategy, and all the collision avoidance strategies correspond to a certain particle swarm, the particles are composed of different dimensions, and the dimensions of the particles are correspondingly related to the feature term; this article only searches for the ship’s collision avoidance steering angle and does not involve other feature items such as ship speed. Therefore, the steering angle is expressed as coordinates xi,i=1,2,…,N; then, this particle swarm individual is encoded as x1x2x3…xN.(2)
Fitness Function. Determine the fitness function of the individual particle swarm based on the collision risk of the ship and set the number of ships that need to be avoided at present as M; the ship collision risk function is CollisionRisk, and the value of the fitness function is mainly related to the collision risk of the currently most dangerous ships, so its fitness function is expressed as(21)objectiveθ=MinCollisionRiski,θ,i∈M.Among them,θ represents the size of the steering angle, positive represents the clockwise direction, and negative represents the counterclockwise direction. According to the collision risk curve of the ship in Figure 9 of this paper, the fitness function curve at that point in time is obtained, as shown in Figure 16.


#### 5.3.2. Design and Update Rules of Belief Space

The structure of the belief space uses the structure pairS,N proposed in article [39], where S=s1t,s2t,…,smt is situational knowledge, which represents the optimal individual set, sit represents the i-th optimal individual in the t generation population, and m represents the scale of the optimal individual set. This article only takes the current best individual st to update the situation knowledge S in belief space, which is S=st, and searching for the optimal steering angle of the ship is to find the maximum value Maxfitnessθ of the fitness function, so the update formula is as follows:(22)st+1=xbestt,objectivexbestt>objectivest,st,otherwise.Among them,xbestt represents the optimal particle in the t generation. In the current population, if the optimal particle xbest is better than the existing one st, then the knowledge of the belief space situation is adjusted and updated by replacing xbest and st.N=<X1,X2,…,Xn> is standardized knowledge; it represents the value interval information of each variable. n is the number of variables, and Xi is I,L,U, where I is defined as(23)I=l,u=x|l≤x≤u.Among them,l and u represent the lower and upper boundaries of the particle steering angle decision, respectively, and L and U represent the fitness values corresponding to these two boundaries. In t-th iterations of the particle swarm, it is assumed that the steering angle parameter of i-th particle affects its lower boundary lit and its fitness value Lit. Similarly, the steering angle parameter of the k-th particle affects its upper boundary ukt and its fitness value Ukt. For the parameter update, see equation (24).(24)lit+1=xit,xit≤litor objectivexit>Lit,lit,otherwise,Lit+1=objectivexi,xit≤litor objectivexit>Lit,Lit,otherwise,ukt+1=xkt,xkt≥uktor objectivexkt>Ukt,ukt,otherwise,Ukt+1=objectivexkt,xkt≥uktor objectivexkt>Ukt,Ukt,otherwise.


#### 5.3.3. Acceptance Function and Influence Function

This article uses a dynamic acceptance function, which introduces evolutionary algebra as a dynamic factor and adjusts the acceptance ratio. The expression is(25)ηaccept=p%+p%t∗n.Among them,n is the size of the population, t is the current evolutionary algebra, and p% is a predetermined fixed ratio. The belief space can affect the mutation operator in the population space in two ways: firstly, changing the step size of the variable change, and secondly, changing the direction of the variable. In this section, normative knowledge is used to adjust the variable step size, and situational knowledge is used to adjust its forward direction. The specific expression is as follows:(26)xit+1=xit+sizeIit∗N−1,1,xit<sit,xit−sizeIit∗N−1,1,xit>sit,xit+sizeIit∗N−1,1,xit=sit,where N−1,1 is a random number that follows a normal distribution and sizeIit is the difference between the upper and lower bounds of the normative knowledge of the particle swarm at the t iteration. Through normative knowledge and situational knowledge, offspring individuals move as far as possible to a given interval (see Algorithm 3).Algorithm 3: Optimal steering angle decision algorithm based on cultural particle swarm.
(1)
Initialize particle population sizeN, dimension 1, iterations item, steering angle search space −xmax,xmax, particle maximum velocity vmax.(2)
Initialize the population space, particle initial positionx, initial velocity v, initial <S, N>.(3)
Calculate the objective value of population space particles, particle’ current optimal positionpbesti, global optimal position gbest.(4)
Update inertia weights according to formula (21), and equation (19) updates particle velocity and position, by xi update pbesti, gbest.(5)
Replace the least fit particles in the belief space with the best fit particles in the population space based on acceptance function and update the position of the population space particles by the influence function.(6)
Determine whether the maximum number of iterations item has been reached; if not, go to step 4; otherwise, go to step 7.(7)
Outputgbest, algorithm ends.


### 5.4. Experimental Verification

The experiment uses the data of own ship and related ships in Table2 of Section 4, taking the total number of particles n = 30, the maximum number of iterations I = 1000, acceleration factor c1=c2=2, ship steering angle whose range is [−35,35], the fitness function which is objectiveθ=MinCollisionRiski,θ, where i is the number of vessels to avoid, and acceptance ratio = 1.5; the data of the first 40 iterations of the experiment are shown in Figure 17.Figure 17
Cultural particle swarm curve.Figure17 shows that in the cultural particle swarm curve, according to the situational knowledge and normative knowledge, the rate of particles toward the global optimal solution is gradually increased with the increase of the number of population iterations. At the 9-th iteration, the global optimal particle position is found, and the fitness value is 0.268394533746147 (see Figure 18). When the particle iterates to the 8-th time, the particle position exceeds the global optimal solution, but according to the knowledge and particle swarm velocity update formula, the particle quickly returns to the global optimal solution position again, which indicates that this algorithm has good global search capabilities.Figure 18
Algorithm’s three-dimensional figure (7–9 generations).In order to analyze the global search ability and convergence performance of the cultural particle swarm algorithm in this section, a comparison experiment is performed between the algorithm in this paper and the standard PSO, that is, the PSO algorithm, GA (genetic) algorithm, and AFSA (fish school) algorithm. The results are shown in Figure19.Figure 19
Comparative experiment chart.Figure19 shows the display of the four algorithms for finding the optimal steering angle of the ship. It can be seen from the figure that after 40 iterations, the CPSO (cultural particle swarm optimization) algorithm adopted in this paper is better than the standard PSO, GA, and AFSA algorithms. This is because the belief space of the cultural particle swarm algorithm uses the influence function to guide the population space, enhances the diversity of particles in the population space, and uses a dynamic inertia weight adjustment strategy to adaptively adjust weight according to the degree of population convergence, making the algorithm have a strong global optimizing ability.The standard PSO algorithm reached the optimal solution the 24-th iteration, but because the linearly decreasing inertial weight is used, the inertial weight change is too single, and the process of finding the optimal steering angle of the ship is nonlinear and does not consider the population iteration information. The adjustment ability of the standard PSO algorithm is limited, so the algorithm has decreased compared with the cultural particle swarm algorithm. The GA and AFSA algorithms reached the optimal solution in the 26-th and 16-th generations, respectively, but because there is no influence function to guide the population space and it has a certain degree of blindness to the population iteration, the convergence speed has decreased compared to the cultural particle swarm algorithm.


## 5.1. Cultural Particle Swarm Algorithm

### 5.1.1. Cultural Algorithm

Cultural algorithm (CA) is a new global optimization search algorithm created by Reynolds et al. to solve complex calculations in 1994. Researchers [36] see culture as a carrier of information that potentially affects all members of society and is useful in guiding the evolutionary process of contemporaries and offspring. Cultural algorithm is a two-layer evolution system based on knowledge which contains two evolution spaces: one is a belief space composed of experience and knowledge acquired during the evolution process and the other one is the population space composed of specific individuals, which is solved iteratively through evolutionary operations and performance evaluation. The basic framework of the cultural algorithm is shown in Figure 15.Figure 15
Graphical representation of the cultural algorithm.As shown in Figure15, population space and belief space are two relatively independent evolutionary processes. The two spaces are linked by a set of communication protocols consisting of acceptor function Accept and influence function Influence. During the evolution process of individuals in the population space, individual experiences are formed, and the individual experiences are transferred to the belief space through Accept functions. Belief space compares and optimizes individual experience according to certain behavior rules to form population experience. Belief space is updated with Update functions based on existing population experience and new individual experience; the Influence function can use the empirical knowledge of the problem to be solved in the belief space to guide the evolution of the population space so that the population space can obtain higher evolution efficiency. In a cultural system, there are many kinds of knowledge, among which normative knowledge and situational knowledge are regarded as the most important knowledge. Normative knowledge provides behavioral norms and guiding principles for individuals, and situational knowledge provides examples for individuals. They can provide guidance information for the evolution of populations. objective function is the objective function (fitness function). Its function is to evaluate the fitness value of individuals in the population space. generate function generates the next generation of individuals based on the rules of individual behavior and the parameters of the parents. The select function selects a part of the newly generated individuals as the parents of the next generation of individuals according to the rules (see Algorithm 2).Algorithm 2: Cultural algorithm pseudocode.
(1)
begin(2)
t = 0;(3)
POP(t); //Initialize the population space(4)
BLF(t); //Initialize the belief space(5)
repeat(6)
POP(t); //Assessing population space(7)
update (BLF(t), accept (POP(t)));(8)
generate (POP(t), influence (BLF(t)));(9)
t = t + 1;(10)
select POP(t) from POP(t−1);(11)
until Termination condition(12)
end


### 5.1.2. Particle Swarm Algorithm

The term “group intelligence” was first coined by Beni et al. [37]. It was proposed in the research of cellular robot systems. Typical swarm intelligence consists of a group of simple agents with local influence and their environment. Although there is no centralized control structure in the swarm intelligence system to guide the behavior of these agents, local influences can often generate global behavior. Particle swarm optimization, as a typical swarm intelligence optimization algorithm, originates from the research on the simplified social model of bird swarms and the simulation of behaviors [38].Suppose each particle in the particle swarm algorithm is flying at a certain speed in then-dimensional search space; Xi=xi1,xi2,…,xin is particles i’s position, Vi=vi1,vi2,…,vin is particles i’s speed, and pbesti=pbesti1,pbesti2,…,pbestin is optimal position experienced by particles i. The current optimal position, global optimal position, particle moving speed, and position update formula are shown in the following equation:(18)pbestit+1=pbestit,iffXit+1≥fpbestit,Xit+1,iffXit+1<fpbestit,gbestt=minfpbest1t,fpbest2t,…,fpbestNt,vijt+1=wvijt+c1r1pbestijt−xijt+c2r2gbestjt−xijt,xijt+1=xijt+vijt+1,where gbestt is the global optimal position, w is the inertia weight, i is the first i particles, j is particle dimension, c1, c2 are the acceleration factors, and r1, r2 are random numbers among 0,1. Particle swarm algorithm speed update equation consists of three parts: the first part is the previous speed of the particle; the second part is called the “cognitive” part, which comes from the experience and thinking of the particle itself; the acceleration factor c1 can adjust the flight step size of the particle’s best position; the third part is the “social” part of the particle, indicating information sharing and interaction between particles and acceleration factors c2. You can adjust the particle’s flight step to the optimal position of the group.


### 5.1.3. Cultural Particle Swarm Algorithm

The CA algorithm framework provides a computational model of multiple evolutionary processes, so from the perspective of the computational model, any evolutionary algorithm that meets the requirements of a cultural algorithm can be embedded in the cultural algorithm framework as an evolutionary process of population space. The current research studies mainly focus on the group intelligence algorithms such as GA, POS, and ACO. Unlike the existing evolutionary algorithms, CA provides a dual evolution mechanism. Based on the group space evolutionary algorithm, through the acquisition, preservation, analysis, and integration of the empirical knowledge generated by individual evolution, the evolution process of the population space is further guided so that the evolution speed of the population surpasses the evolution speed solely relying on ordinary evolution algorithms and has good global optimization performance.The essence of cultural particle swarm optimization algorithm is a combination of cultural algorithm model and particle swarm optimization. During the PSO evolution process, particles track two “extreme values”: one is the individual historical optimal solution, the other is the global historical optimal solution, and the global historical optimal solution is passed from generation to generation, which naturally forms the trajectory of the global optimal solution. These optimal solutions are regarded as the global knowledge information of iterative search which is kept continuously, and the knowledge space is updated; the knowledge solution is evolved. At the same time, the further solution of PSO group is guided. Through the dual evolution and mutual influence of PSO space (main group space) and knowledge space, the solution has better global search ability.


## 5.1.1. Cultural Algorithm

Cultural algorithm (CA) is a new global optimization search algorithm created by Reynolds et al. to solve complex calculations in 1994. Researchers [36] see culture as a carrier of information that potentially affects all members of society and is useful in guiding the evolutionary process of contemporaries and offspring. Cultural algorithm is a two-layer evolution system based on knowledge which contains two evolution spaces: one is a belief space composed of experience and knowledge acquired during the evolution process and the other one is the population space composed of specific individuals, which is solved iteratively through evolutionary operations and performance evaluation. The basic framework of the cultural algorithm is shown in Figure 15.Figure 15
Graphical representation of the cultural algorithm.As shown in Figure15, population space and belief space are two relatively independent evolutionary processes. The two spaces are linked by a set of communication protocols consisting of acceptor function Accept and influence function Influence. During the evolution process of individuals in the population space, individual experiences are formed, and the individual experiences are transferred to the belief space through Accept functions. Belief space compares and optimizes individual experience according to certain behavior rules to form population experience. Belief space is updated with Update functions based on existing population experience and new individual experience; the Influence function can use the empirical knowledge of the problem to be solved in the belief space to guide the evolution of the population space so that the population space can obtain higher evolution efficiency. In a cultural system, there are many kinds of knowledge, among which normative knowledge and situational knowledge are regarded as the most important knowledge. Normative knowledge provides behavioral norms and guiding principles for individuals, and situational knowledge provides examples for individuals. They can provide guidance information for the evolution of populations. objective function is the objective function (fitness function). Its function is to evaluate the fitness value of individuals in the population space. generate function generates the next generation of individuals based on the rules of individual behavior and the parameters of the parents. The select function selects a part of the newly generated individuals as the parents of the next generation of individuals according to the rules (see Algorithm 2).Algorithm 2: Cultural algorithm pseudocode.
(1)
begin(2)
t = 0;(3)
POP(t); //Initialize the population space(4)
BLF(t); //Initialize the belief space(5)
repeat(6)
POP(t); //Assessing population space(7)
update (BLF(t), accept (POP(t)));(8)
generate (POP(t), influence (BLF(t)));(9)
t = t + 1;(10)
select POP(t) from POP(t−1);(11)
until Termination condition(12)
end


## 5.1.2. Particle Swarm Algorithm

The term “group intelligence” was first coined by Beni et al. [37]. It was proposed in the research of cellular robot systems. Typical swarm intelligence consists of a group of simple agents with local influence and their environment. Although there is no centralized control structure in the swarm intelligence system to guide the behavior of these agents, local influences can often generate global behavior. Particle swarm optimization, as a typical swarm intelligence optimization algorithm, originates from the research on the simplified social model of bird swarms and the simulation of behaviors [38].Suppose each particle in the particle swarm algorithm is flying at a certain speed in then-dimensional search space; Xi=xi1,xi2,…,xin is particles i’s position, Vi=vi1,vi2,…,vin is particles i’s speed, and pbesti=pbesti1,pbesti2,…,pbestin is optimal position experienced by particles i. The current optimal position, global optimal position, particle moving speed, and position update formula are shown in the following equation:(18)pbestit+1=pbestit,iffXit+1≥fpbestit,Xit+1,iffXit+1<fpbestit,gbestt=minfpbest1t,fpbest2t,…,fpbestNt,vijt+1=wvijt+c1r1pbestijt−xijt+c2r2gbestjt−xijt,xijt+1=xijt+vijt+1,where gbestt is the global optimal position, w is the inertia weight, i is the first i particles, j is particle dimension, c1, c2 are the acceleration factors, and r1, r2 are random numbers among 0,1. Particle swarm algorithm speed update equation consists of three parts: the first part is the previous speed of the particle; the second part is called the “cognitive” part, which comes from the experience and thinking of the particle itself; the acceleration factor c1 can adjust the flight step size of the particle’s best position; the third part is the “social” part of the particle, indicating information sharing and interaction between particles and acceleration factors c2. You can adjust the particle’s flight step to the optimal position of the group.


## 5.1.3. Cultural Particle Swarm Algorithm

The CA algorithm framework provides a computational model of multiple evolutionary processes, so from the perspective of the computational model, any evolutionary algorithm that meets the requirements of a cultural algorithm can be embedded in the cultural algorithm framework as an evolutionary process of population space. The current research studies mainly focus on the group intelligence algorithms such as GA, POS, and ACO. Unlike the existing evolutionary algorithms, CA provides a dual evolution mechanism. Based on the group space evolutionary algorithm, through the acquisition, preservation, analysis, and integration of the empirical knowledge generated by individual evolution, the evolution process of the population space is further guided so that the evolution speed of the population surpasses the evolution speed solely relying on ordinary evolution algorithms and has good global optimization performance.The essence of cultural particle swarm optimization algorithm is a combination of cultural algorithm model and particle swarm optimization. During the PSO evolution process, particles track two “extreme values”: one is the individual historical optimal solution, the other is the global historical optimal solution, and the global historical optimal solution is passed from generation to generation, which naturally forms the trajectory of the global optimal solution. These optimal solutions are regarded as the global knowledge information of iterative search which is kept continuously, and the knowledge space is updated; the knowledge solution is evolved. At the same time, the further solution of PSO group is guided. Through the dual evolution and mutual influence of PSO space (main group space) and knowledge space, the solution has better global search ability.


## 5.2. Improvements to the Cultural Particle Swarm Algorithm

### 5.2.1. Premature Convergence Judgment

The diversity of the particle swarm population is a prerequisite for the effective operation of the algorithm, and the greater the population diversity, the more likely it is to produce better offspring individuals. However, due to the solution process of the particle swarm algorithm, the diversity will be gradually lost, and the individuals will converge with each other. The particle with the optimal current position will guide other particles to approach it quickly. If the position of the current optimal particle is a local optimal solution, the entire group cannot search again and can fall into a precocious convergence state. Generally, the fitness of different distributed particles in the population space is different. The degree of diversity of particles can be expressed by the degree of dispersion of fitness distribution of particles. When the PSO algorithm is in the state of premature convergence or global convergence, particles will gather in one place or in several specific places. Therefore, the state of the particle swarm can be judged by studying the change of the particle fitness value in the population space, thereby determining whether the algorithm converges.This paper introduces the index proposed in [34] to evaluate the premature convergence of the particle swarm, which is defined as: Let the size of the particle swarm ben. In the k-th iteration, the fitness value of the particle is fik and the average fitness value of the particle swarm is favgk; favgk¯ is obtained by averaging the fitness values of particles whose fitness value is better than favgk, which is defined as follows:(19)ρ=fmk−favgk¯fmk−1−favgk−1¯,where ρ evaluates the degree of convergence of the particle swarm algorithm; the smaller ρ is, the more the particle swarm tends to converge.


### 5.2.2. Dynamic Adjustment of Inertia Weight

The standard particle swarm algorithm uses linearly decreasing inertial weights because the linearly decreasing inertial weight changes are too singular, and the process of searching the optimal steering angle of a ship by the particle swarm algorithm is very complicated and nonlinear; it is suitable for complex problems. Both ability and regulation ability are very limited. Aiming at the above problems, this paper proposes a strategy for dynamically adjusting the inertia weights, combining the changes of the inertia weights with indicators to evaluate the degree of premature convergence of the particle swarm:(20)wit=1−1+e−ρ−1.It can be seen from the above formula that the particle’s inertia weight value changes within (0, 1),wit describes the effect of the inertia of the i-th particle on the t-th velocity, and the value can adjust the global optimization ability of the PSO and local optimization capabilities. When the PSO is in a state of convergence, a large inertia weight is required to increase the search step size, thereby enhancing the global optimization capability of the PSO. When the PSO is in the global search state, a small inertia weight is required to reduce the search step size, thereby enhancing the local optimization capability of the PSO. When the index for evaluating the degree of premature convergence of the particle swarm decreases, wit increases accordingly, which enhances the global search ability; when ρ increases, the value of wit decreases accordingly, increasing the local search ability.Figure 16
Fitness function curve.


## 5.2.1. Premature Convergence Judgment

The diversity of the particle swarm population is a prerequisite for the effective operation of the algorithm, and the greater the population diversity, the more likely it is to produce better offspring individuals. However, due to the solution process of the particle swarm algorithm, the diversity will be gradually lost, and the individuals will converge with each other. The particle with the optimal current position will guide other particles to approach it quickly. If the position of the current optimal particle is a local optimal solution, the entire group cannot search again and can fall into a precocious convergence state. Generally, the fitness of different distributed particles in the population space is different. The degree of diversity of particles can be expressed by the degree of dispersion of fitness distribution of particles. When the PSO algorithm is in the state of premature convergence or global convergence, particles will gather in one place or in several specific places. Therefore, the state of the particle swarm can be judged by studying the change of the particle fitness value in the population space, thereby determining whether the algorithm converges.This paper introduces the index proposed in [34] to evaluate the premature convergence of the particle swarm, which is defined as: Let the size of the particle swarm ben. In the k-th iteration, the fitness value of the particle is fik and the average fitness value of the particle swarm is favgk; favgk¯ is obtained by averaging the fitness values of particles whose fitness value is better than favgk, which is defined as follows:(19)ρ=fmk−favgk¯fmk−1−favgk−1¯,where ρ evaluates the degree of convergence of the particle swarm algorithm; the smaller ρ is, the more the particle swarm tends to converge.


## 5.2.2. Dynamic Adjustment of Inertia Weight

The standard particle swarm algorithm uses linearly decreasing inertial weights because the linearly decreasing inertial weight changes are too singular, and the process of searching the optimal steering angle of a ship by the particle swarm algorithm is very complicated and nonlinear; it is suitable for complex problems. Both ability and regulation ability are very limited. Aiming at the above problems, this paper proposes a strategy for dynamically adjusting the inertia weights, combining the changes of the inertia weights with indicators to evaluate the degree of premature convergence of the particle swarm:(20)wit=1−1+e−ρ−1.It can be seen from the above formula that the particle’s inertia weight value changes within (0, 1),wit describes the effect of the inertia of the i-th particle on the t-th velocity, and the value can adjust the global optimization ability of the PSO and local optimization capabilities. When the PSO is in a state of convergence, a large inertia weight is required to increase the search step size, thereby enhancing the global optimization capability of the PSO. When the PSO is in the global search state, a small inertia weight is required to reduce the search step size, thereby enhancing the local optimization capability of the PSO. When the index for evaluating the degree of premature convergence of the particle swarm decreases, wit increases accordingly, which enhances the global search ability; when ρ increases, the value of wit decreases accordingly, increasing the local search ability.Figure 16
Fitness function curve.


## 5.3. Optimal Steering Angle Decision Algorithm

### 5.3.1. Particle Swarm Space Design and Iteration Rules

(1)
Coding Scheme. The particle swarm in the population space encodes the particle swarm according to the Michigan coding scheme, that is, each particle represents a ship collision avoidance strategy, and all the collision avoidance strategies correspond to a certain particle swarm, the particles are composed of different dimensions, and the dimensions of the particles are correspondingly related to the feature term; this article only searches for the ship’s collision avoidance steering angle and does not involve other feature items such as ship speed. Therefore, the steering angle is expressed as coordinates xi,i=1,2,…,N; then, this particle swarm individual is encoded as x1x2x3…xN.(2)
Fitness Function. Determine the fitness function of the individual particle swarm based on the collision risk of the ship and set the number of ships that need to be avoided at present as M; the ship collision risk function is CollisionRisk, and the value of the fitness function is mainly related to the collision risk of the currently most dangerous ships, so its fitness function is expressed as(21)objectiveθ=MinCollisionRiski,θ,i∈M.Among them,θ represents the size of the steering angle, positive represents the clockwise direction, and negative represents the counterclockwise direction. According to the collision risk curve of the ship in Figure 9 of this paper, the fitness function curve at that point in time is obtained, as shown in Figure 16.


### 5.3.2. Design and Update Rules of Belief Space

The structure of the belief space uses the structure pairS,N proposed in article [39], where S=s1t,s2t,…,smt is situational knowledge, which represents the optimal individual set, sit represents the i-th optimal individual in the t generation population, and m represents the scale of the optimal individual set. This article only takes the current best individual st to update the situation knowledge S in belief space, which is S=st, and searching for the optimal steering angle of the ship is to find the maximum value Maxfitnessθ of the fitness function, so the update formula is as follows:(22)st+1=xbestt,objectivexbestt>objectivest,st,otherwise.Among them,xbestt represents the optimal particle in the t generation. In the current population, if the optimal particle xbest is better than the existing one st, then the knowledge of the belief space situation is adjusted and updated by replacing xbest and st.N=<X1,X2,…,Xn> is standardized knowledge; it represents the value interval information of each variable. n is the number of variables, and Xi is I,L,U, where I is defined as(23)I=l,u=x|l≤x≤u.Among them,l and u represent the lower and upper boundaries of the particle steering angle decision, respectively, and L and U represent the fitness values corresponding to these two boundaries. In t-th iterations of the particle swarm, it is assumed that the steering angle parameter of i-th particle affects its lower boundary lit and its fitness value Lit. Similarly, the steering angle parameter of the k-th particle affects its upper boundary ukt and its fitness value Ukt. For the parameter update, see equation (24).(24)lit+1=xit,xit≤litor objectivexit>Lit,lit,otherwise,Lit+1=objectivexi,xit≤litor objectivexit>Lit,Lit,otherwise,ukt+1=xkt,xkt≥uktor objectivexkt>Ukt,ukt,otherwise,Ukt+1=objectivexkt,xkt≥uktor objectivexkt>Ukt,Ukt,otherwise.


### 5.3.3. Acceptance Function and Influence Function

This article uses a dynamic acceptance function, which introduces evolutionary algebra as a dynamic factor and adjusts the acceptance ratio. The expression is(25)ηaccept=p%+p%t∗n.Among them,n is the size of the population, t is the current evolutionary algebra, and p% is a predetermined fixed ratio. The belief space can affect the mutation operator in the population space in two ways: firstly, changing the step size of the variable change, and secondly, changing the direction of the variable. In this section, normative knowledge is used to adjust the variable step size, and situational knowledge is used to adjust its forward direction. The specific expression is as follows:(26)xit+1=xit+sizeIit∗N−1,1,xit<sit,xit−sizeIit∗N−1,1,xit>sit,xit+sizeIit∗N−1,1,xit=sit,where N−1,1 is a random number that follows a normal distribution and sizeIit is the difference between the upper and lower bounds of the normative knowledge of the particle swarm at the t iteration. Through normative knowledge and situational knowledge, offspring individuals move as far as possible to a given interval (see Algorithm 3).Algorithm 3: Optimal steering angle decision algorithm based on cultural particle swarm.
(1)
Initialize particle population sizeN, dimension 1, iterations item, steering angle search space −xmax,xmax, particle maximum velocity vmax.(2)
Initialize the population space, particle initial positionx, initial velocity v, initial <S, N>.(3)
Calculate the objective value of population space particles, particle’ current optimal positionpbesti, global optimal position gbest.(4)
Update inertia weights according to formula (21), and equation (19) updates particle velocity and position, by xi update pbesti, gbest.(5)
Replace the least fit particles in the belief space with the best fit particles in the population space based on acceptance function and update the position of the population space particles by the influence function.(6)
Determine whether the maximum number of iterations item has been reached; if not, go to step 4; otherwise, go to step 7.(7)
Outputgbest, algorithm ends.


## 5.3.1. Particle Swarm Space Design and Iteration Rules

(1)
Coding Scheme. The particle swarm in the population space encodes the particle swarm according to the Michigan coding scheme, that is, each particle represents a ship collision avoidance strategy, and all the collision avoidance strategies correspond to a certain particle swarm, the particles are composed of different dimensions, and the dimensions of the particles are correspondingly related to the feature term; this article only searches for the ship’s collision avoidance steering angle and does not involve other feature items such as ship speed. Therefore, the steering angle is expressed as coordinates xi,i=1,2,…,N; then, this particle swarm individual is encoded as x1x2x3…xN.(2)
Fitness Function. Determine the fitness function of the individual particle swarm based on the collision risk of the ship and set the number of ships that need to be avoided at present as M; the ship collision risk function is CollisionRisk, and the value of the fitness function is mainly related to the collision risk of the currently most dangerous ships, so its fitness function is expressed as(21)objectiveθ=MinCollisionRiski,θ,i∈M.Among them,θ represents the size of the steering angle, positive represents the clockwise direction, and negative represents the counterclockwise direction. According to the collision risk curve of the ship in Figure 9 of this paper, the fitness function curve at that point in time is obtained, as shown in Figure 16.


## 5.3.2. Design and Update Rules of Belief Space

The structure of the belief space uses the structure pairS,N proposed in article [39], where S=s1t,s2t,…,smt is situational knowledge, which represents the optimal individual set, sit represents the i-th optimal individual in the t generation population, and m represents the scale of the optimal individual set. This article only takes the current best individual st to update the situation knowledge S in belief space, which is S=st, and searching for the optimal steering angle of the ship is to find the maximum value Maxfitnessθ of the fitness function, so the update formula is as follows:(22)st+1=xbestt,objectivexbestt>objectivest,st,otherwise.Among them,xbestt represents the optimal particle in the t generation. In the current population, if the optimal particle xbest is better than the existing one st, then the knowledge of the belief space situation is adjusted and updated by replacing xbest and st.N=<X1,X2,…,Xn> is standardized knowledge; it represents the value interval information of each variable. n is the number of variables, and Xi is I,L,U, where I is defined as(23)I=l,u=x|l≤x≤u.Among them,l and u represent the lower and upper boundaries of the particle steering angle decision, respectively, and L and U represent the fitness values corresponding to these two boundaries. In t-th iterations of the particle swarm, it is assumed that the steering angle parameter of i-th particle affects its lower boundary lit and its fitness value Lit. Similarly, the steering angle parameter of the k-th particle affects its upper boundary ukt and its fitness value Ukt. For the parameter update, see equation (24).(24)lit+1=xit,xit≤litor objectivexit>Lit,lit,otherwise,Lit+1=objectivexi,xit≤litor objectivexit>Lit,Lit,otherwise,ukt+1=xkt,xkt≥uktor objectivexkt>Ukt,ukt,otherwise,Ukt+1=objectivexkt,xkt≥uktor objectivexkt>Ukt,Ukt,otherwise.


## 5.3.3. Acceptance Function and Influence Function

This article uses a dynamic acceptance function, which introduces evolutionary algebra as a dynamic factor and adjusts the acceptance ratio. The expression is(25)ηaccept=p%+p%t∗n.Among them,n is the size of the population, t is the current evolutionary algebra, and p% is a predetermined fixed ratio. The belief space can affect the mutation operator in the population space in two ways: firstly, changing the step size of the variable change, and secondly, changing the direction of the variable. In this section, normative knowledge is used to adjust the variable step size, and situational knowledge is used to adjust its forward direction. The specific expression is as follows:(26)xit+1=xit+sizeIit∗N−1,1,xit<sit,xit−sizeIit∗N−1,1,xit>sit,xit+sizeIit∗N−1,1,xit=sit,where N−1,1 is a random number that follows a normal distribution and sizeIit is the difference between the upper and lower bounds of the normative knowledge of the particle swarm at the t iteration. Through normative knowledge and situational knowledge, offspring individuals move as far as possible to a given interval (see Algorithm 3).Algorithm 3: Optimal steering angle decision algorithm based on cultural particle swarm.
(1)
Initialize particle population sizeN, dimension 1, iterations item, steering angle search space −xmax,xmax, particle maximum velocity vmax.(2)
Initialize the population space, particle initial positionx, initial velocity v, initial <S, N>.(3)
Calculate the objective value of population space particles, particle’ current optimal positionpbesti, global optimal position gbest.(4)
Update inertia weights according to formula (21), and equation (19) updates particle velocity and position, by xi update pbesti, gbest.(5)
Replace the least fit particles in the belief space with the best fit particles in the population space based on acceptance function and update the position of the population space particles by the influence function.(6)
Determine whether the maximum number of iterations item has been reached; if not, go to step 4; otherwise, go to step 7.(7)
Outputgbest, algorithm ends.


## 5.4. Experimental Verification

The experiment uses the data of own ship and related ships in Table2 of Section 4, taking the total number of particles n = 30, the maximum number of iterations I = 1000, acceleration factor c1=c2=2, ship steering angle whose range is [−35,35], the fitness function which is objectiveθ=MinCollisionRiski,θ, where i is the number of vessels to avoid, and acceptance ratio = 1.5; the data of the first 40 iterations of the experiment are shown in Figure 17.Figure 17
Cultural particle swarm curve.Figure17 shows that in the cultural particle swarm curve, according to the situational knowledge and normative knowledge, the rate of particles toward the global optimal solution is gradually increased with the increase of the number of population iterations. At the 9-th iteration, the global optimal particle position is found, and the fitness value is 0.268394533746147 (see Figure 18). When the particle iterates to the 8-th time, the particle position exceeds the global optimal solution, but according to the knowledge and particle swarm velocity update formula, the particle quickly returns to the global optimal solution position again, which indicates that this algorithm has good global search capabilities.Figure 18
Algorithm’s three-dimensional figure (7–9 generations).In order to analyze the global search ability and convergence performance of the cultural particle swarm algorithm in this section, a comparison experiment is performed between the algorithm in this paper and the standard PSO, that is, the PSO algorithm, GA (genetic) algorithm, and AFSA (fish school) algorithm. The results are shown in Figure19.Figure 19
Comparative experiment chart.Figure19 shows the display of the four algorithms for finding the optimal steering angle of the ship. It can be seen from the figure that after 40 iterations, the CPSO (cultural particle swarm optimization) algorithm adopted in this paper is better than the standard PSO, GA, and AFSA algorithms. This is because the belief space of the cultural particle swarm algorithm uses the influence function to guide the population space, enhances the diversity of particles in the population space, and uses a dynamic inertia weight adjustment strategy to adaptively adjust weight according to the degree of population convergence, making the algorithm have a strong global optimizing ability.The standard PSO algorithm reached the optimal solution the 24-th iteration, but because the linearly decreasing inertial weight is used, the inertial weight change is too single, and the process of finding the optimal steering angle of the ship is nonlinear and does not consider the population iteration information. The adjustment ability of the standard PSO algorithm is limited, so the algorithm has decreased compared with the cultural particle swarm algorithm. The GA and AFSA algorithms reached the optimal solution in the 26-th and 16-th generations, respectively, but because there is no influence function to guide the population space and it has a certain degree of blindness to the population iteration, the convergence speed has decreased compared to the cultural particle swarm algorithm.


## 6. Electronic Chart Platform Integration and Experimental Analysis

We integrate the method proposed in this paper into the electronic chart platform. The electronic chart platform is used as the verification environment of the method. At the same time, the AIS data of the ship are displayed on the electronic chart platform and provided to the related algorithm. Electronic chart platform is an important navigation tool chart for ships and other marine vehicles, which can provide true and complete environmental information required during navigation, mainly including land, ocean, water depth, obstacles, and islands. So, it is widely used in ocean path planning and other aspects.In this paper, the international standard electronic chart platform developed in C ++ language is used as the experimental verification environment, as shown in Figure20. The system has the following characteristics:(1)
The system uses international standards to display chart information, and we can zoom and observe the chart interface at any scale.(2)
The system uses the MFC (Microsoft Foundation Class) framework to generate a dynamic link library of related algorithms, providing a flexible and convenient interface design.(3)
The system provides operations for autonomously setting the movement information of the current ship and other ships, including information such as longitude, latitude, heading, and speed, and all ship models in the system use bulk carriers.(4)
It can dynamically display the movement tracks of all ships in the chart, which is convenient to observe the simulation results of real environment. The interface is shown in Figure20.Figure 20
Electronic chart simulation environment.


### 6.1. Steering Angle Direction Decision Verification

Figures21–29 show the ship encounter scenarios, verifying whether the model meets the rules of collision avoidance. Figures 21 and 22 are the scenes of own ship as overtaking ship. The own ship speed is 15 knots and the target ship speed is 8 knots. Besides that, the specific parameters of the ship are shown in Table 3.Figure 21
Own ship is overtaking ship.Figure 22
Right-steering collision avoidance.Figure 23
The hazard curve of ship collision avoidance described in this scene.Figure 24
Own ship is facing the ship.Figure 25
Right-steering collision avoidance.Figure 26
The hazard curve of ship collision avoidance described in this scene.Figure 27
Own ship is a give way ship.Figure 28
Right-steering collision avoidance.Figure 29
The hazard curve of ship collision avoidance described in this scene.Table 3
Relevant data of chase scene experiment.
Related parametersValuePosition132.85°Relative position10.75°Relative velocity7.02n mile/hRelative speed heading298.80°DCPA−0.77/n mileTCPA26.32/minRelative heading2.90°Ship spacing3.48n mileCurrent risk−0.62There is a danger of collision in the current scene. The analysis in Section4.3 shows that the steering should be driven to the left. Figure 23 shows the collision risk curve of the ship depicted in the scene. As the ship steers to the left (the left direction is counterclockwise and the sign is negative), the ship’s collision risk curve gradually increases first, reaching the highest point of the curve at 1.424 at 15.2 degrees, and then it almost stabilized in the 1.42 to 1.20 range. Therefore, the ship steers 15.2 degrees to the left to avoid collisions, and the experimental results meet the requirements of the ship collision avoidance rules.Figures24 and 25 are the encounter scenes of the ship. The speed of the ship is 15 knots and the speed of the target ship is 8 knots. The specific parameters of the ship are shown in Table 4.Table 4
Relevant data of encounter scene experiment.
Related parametersValuePosition91.0°Relative position0.70°Relative velocity23.0n mile/hRelative speed heading270.20°DCPA−0.07/n mileTCPA12.51/minShip spacing2.83n mileCurrent risk0.02Relative heading179.70°There is a danger of collision in the current scene. The analysis in Section 4.3 above shows that the steering should be driven to the right. Figure26 shows the collision risk curve of the ship depicted in the scene. As the ship steers to the right (the clockwise direction is positive), the ship’s collision risk curve gradually increases first, reaching the highest point of the curve at 27.8 degrees at 1.126, and then slightly drops to around 1.0. Therefore, the ship steers 27.8 degrees to the right to avoid the collision, and the experimental results meet the requirements of the ship collision avoidance rules.Figures27 and 28 are the crossing situation of the ship, and the specific parameters of the ship are shown in Table 5.Table 5
Cross-encounter scene experimental data.
Related parametersValuePosition129.28°Relative position38.48°Relative velocity14.50n mile/hRelative speed heading302.21°DCPA−0.53/n mileTCPA17.76/minRelative heading70.80°Ship spacing3.23n mileCurrent risk−1.18There is a danger of collision in the current scene. The analysis in 4.3 above shows that the rudder should be driven to the right. The collision risk curve of own ship depicted in the scene is shown in Figure29. As the ship steers to the right, the collision risk curve of the ship gradually increases, reaching the highest point 1.066 of the curve at 35 degrees. Therefore, own ship steers 35 degrees to the right to avoid the collision, and the experimental results meet the requirements of the ship collision avoidance rules.


### 6.2. Steering Angle Decision Verification

We use the ship steering collision avoidance model proposed in this paper to carry out the collision avoidance simulation experiment. The simulation environment diagram is shown in Figure30. In the simulation initial conditions, the initial course of the ship is 92.0 degrees, the speed is 15 knots, the longitude is 120.87 degrees, and the latitude is 36.35 degrees; Ship-1 is the first target ship, its course is 270.0 degrees, its speed is 7 knots/hour, longitude is 120.87 degrees, and the latitude is 36.35 degrees; Ship-2 is the second target ship, its course is 40.0 degrees, the speed is 8 knots/hour, the longitude is 120.90 degrees, and the latitude is 36.29 degrees; Ship-3 is the third target ship, its course is 190.0 degrees, its speed is 9 knots, longitude is 120.87 degrees, and its latitude is 36.35 degrees.Figure 30
Initial simulation environment diagram.Figures31(a) and 31(b) are the situations where the ship and the three target ships will encounter the situation. By analyzing the system log of the collision avoidance module in the scenario in Figure 31, the collision risk change during the collision avoidance process is obtained. The drawn curve is shown in Figure 32.Figure 31
The encounter situation between the ship and the three target ships. (a) Avoid target Ship-1. (b). Avoid target Ship-2.
(a)(b)Figure 32
Change curve of collision risk during collision avoidance.In the initial scenario, own ship and Ship-1 are facing each other, and there is a danger of collision. The analysis in 4.3 above shows that own ship should steer to the right at this time. Figure32 shows the ship collision risk curve depicted in the scene. As the ship steers to the right, the collision hazard curve of own ship and Ship-1 gradually increases, while the hazard curve with Ship-2 gradually decreases. This is because own ship steers to the right, causing the ship to move closer to Ship-2, which increases the risk of collision. The hazard curve of the own ship and Ship-3 is relatively stable above 1.4, and there is no danger of collision. The hazard curve of Ship-2 and Ship-1 intersects at 22.5 degrees, so own ship steers 22.5 degrees to the right to avoid the collision. The collision avoidance state is shown in Figure 31(a). After evading Ship-1 (the most dangerous ship at present), evade Ship-2. The collision avoidance state is shown in Figure 31(b).As shown in Figure33(a), the own ship is ready to take action to resume sailing after avoiding the dangerous target ship and keeping clear. As shown in Figure 33(b), the position of own ship finally returned to the original route. Hence, the results indicate that the own ship can take proper action to avoid other target ships and has a better performance. During the entire experiment, the ship can avoid other target ships reasonably and has a better avoidance effect.Figure 33
Picture of the end of own ship avoidance. (a) Location map of own ship after evading Ship-2. (b) End of own ship avoidance.
(a)(b)


## 6.1. Steering Angle Direction Decision Verification

Figures21–29 show the ship encounter scenarios, verifying whether the model meets the rules of collision avoidance. Figures 21 and 22 are the scenes of own ship as overtaking ship. The own ship speed is 15 knots and the target ship speed is 8 knots. Besides that, the specific parameters of the ship are shown in Table 3.Figure 21
Own ship is overtaking ship.Figure 22
Right-steering collision avoidance.Figure 23
The hazard curve of ship collision avoidance described in this scene.Figure 24
Own ship is facing the ship.Figure 25
Right-steering collision avoidance.Figure 26
The hazard curve of ship collision avoidance described in this scene.Figure 27
Own ship is a give way ship.Figure 28
Right-steering collision avoidance.Figure 29
The hazard curve of ship collision avoidance described in this scene.Table 3
Relevant data of chase scene experiment.
Related parametersValuePosition132.85°Relative position10.75°Relative velocity7.02n mile/hRelative speed heading298.80°DCPA−0.77/n mileTCPA26.32/minRelative heading2.90°Ship spacing3.48n mileCurrent risk−0.62There is a danger of collision in the current scene. The analysis in Section4.3 shows that the steering should be driven to the left. Figure 23 shows the collision risk curve of the ship depicted in the scene. As the ship steers to the left (the left direction is counterclockwise and the sign is negative), the ship’s collision risk curve gradually increases first, reaching the highest point of the curve at 1.424 at 15.2 degrees, and then it almost stabilized in the 1.42 to 1.20 range. Therefore, the ship steers 15.2 degrees to the left to avoid collisions, and the experimental results meet the requirements of the ship collision avoidance rules.Figures24 and 25 are the encounter scenes of the ship. The speed of the ship is 15 knots and the speed of the target ship is 8 knots. The specific parameters of the ship are shown in Table 4.Table 4
Relevant data of encounter scene experiment.
Related parametersValuePosition91.0°Relative position0.70°Relative velocity23.0n mile/hRelative speed heading270.20°DCPA−0.07/n mileTCPA12.51/minShip spacing2.83n mileCurrent risk0.02Relative heading179.70°There is a danger of collision in the current scene. The analysis in Section 4.3 above shows that the steering should be driven to the right. Figure26 shows the collision risk curve of the ship depicted in the scene. As the ship steers to the right (the clockwise direction is positive), the ship’s collision risk curve gradually increases first, reaching the highest point of the curve at 27.8 degrees at 1.126, and then slightly drops to around 1.0. Therefore, the ship steers 27.8 degrees to the right to avoid the collision, and the experimental results meet the requirements of the ship collision avoidance rules.Figures27 and 28 are the crossing situation of the ship, and the specific parameters of the ship are shown in Table 5.Table 5
Cross-encounter scene experimental data.
Related parametersValuePosition129.28°Relative position38.48°Relative velocity14.50n mile/hRelative speed heading302.21°DCPA−0.53/n mileTCPA17.76/minRelative heading70.80°Ship spacing3.23n mileCurrent risk−1.18There is a danger of collision in the current scene. The analysis in 4.3 above shows that the rudder should be driven to the right. The collision risk curve of own ship depicted in the scene is shown in Figure29. As the ship steers to the right, the collision risk curve of the ship gradually increases, reaching the highest point 1.066 of the curve at 35 degrees. Therefore, own ship steers 35 degrees to the right to avoid the collision, and the experimental results meet the requirements of the ship collision avoidance rules.


## 6.2. Steering Angle Decision Verification

We use the ship steering collision avoidance model proposed in this paper to carry out the collision avoidance simulation experiment. The simulation environment diagram is shown in Figure30. In the simulation initial conditions, the initial course of the ship is 92.0 degrees, the speed is 15 knots, the longitude is 120.87 degrees, and the latitude is 36.35 degrees; Ship-1 is the first target ship, its course is 270.0 degrees, its speed is 7 knots/hour, longitude is 120.87 degrees, and the latitude is 36.35 degrees; Ship-2 is the second target ship, its course is 40.0 degrees, the speed is 8 knots/hour, the longitude is 120.90 degrees, and the latitude is 36.29 degrees; Ship-3 is the third target ship, its course is 190.0 degrees, its speed is 9 knots, longitude is 120.87 degrees, and its latitude is 36.35 degrees.Figure 30
Initial simulation environment diagram.Figures31(a) and 31(b) are the situations where the ship and the three target ships will encounter the situation. By analyzing the system log of the collision avoidance module in the scenario in Figure 31, the collision risk change during the collision avoidance process is obtained. The drawn curve is shown in Figure 32.Figure 31
The encounter situation between the ship and the three target ships. (a) Avoid target Ship-1. (b). Avoid target Ship-2.
(a)(b)Figure 32
Change curve of collision risk during collision avoidance.In the initial scenario, own ship and Ship-1 are facing each other, and there is a danger of collision. The analysis in 4.3 above shows that own ship should steer to the right at this time. Figure32 shows the ship collision risk curve depicted in the scene. As the ship steers to the right, the collision hazard curve of own ship and Ship-1 gradually increases, while the hazard curve with Ship-2 gradually decreases. This is because own ship steers to the right, causing the ship to move closer to Ship-2, which increases the risk of collision. The hazard curve of the own ship and Ship-3 is relatively stable above 1.4, and there is no danger of collision. The hazard curve of Ship-2 and Ship-1 intersects at 22.5 degrees, so own ship steers 22.5 degrees to the right to avoid the collision. The collision avoidance state is shown in Figure 31(a). After evading Ship-1 (the most dangerous ship at present), evade Ship-2. The collision avoidance state is shown in Figure 31(b).As shown in Figure33(a), the own ship is ready to take action to resume sailing after avoiding the dangerous target ship and keeping clear. As shown in Figure 33(b), the position of own ship finally returned to the original route. Hence, the results indicate that the own ship can take proper action to avoid other target ships and has a better performance. During the entire experiment, the ship can avoid other target ships reasonably and has a better avoidance effect.Figure 33
Picture of the end of own ship avoidance. (a) Location map of own ship after evading Ship-2. (b) End of own ship avoidance.
(a)(b)


## 7. Conclusions

In this paper, a decision-making method for ship collision avoidance based on improved cultural particle swarm is proposed. Aiming at the fact that traditional evolutionary algorithms do not use the information of population iteration which leads to the slow adjustment ability and convergence speed of the algorithms, the cultural particle swarm is improved and applied to collision avoidance system in this paper. Firstly, AIS data of ship are acquired based on electronic chart platform. However, in the actual AIS ship data transmission, the update is not timely and the error is large. Hence, the Kalman filter is used to smooth and predict the ship trajectory in this paper. Secondly, based on the fuzzy distribution method, the danger degree of the ship is estimated and the steering angle direction is determined by combining the COLREGs and the encounter status of the ship. Finally, the optimal steering angle of the ship is found by cultural particle swarm optimization algorithm to realize the decision making of ship collision avoidance.The complex situations of three ships are simulated in electronic chart. The results show that the ship adopts the optimal and reasonable steering angle decision in this encounter scene and realizes the autonomous collision avoidance. The cultural particle swarm optimization algorithm adopted in this paper is compared with other three evolutionary methods. Experiments demonstrate that the cultural particle swarm algorithm has faster convergence speed and higher accuracy and can achieve continuous job output, which further validates the effectiveness of the algorithm. However, the speed decision of ships is not considered in this paper, and there are a large number of collision avoidance scenarios for ships at sea. The test scenarios in this paper are not comprehensive enough. How to consider the decision of ship steering angle and ship speed, as well as to divide and test the scene in a complex encounter situation, is the focus of the next step of this thesis.



---

*Source: 8898507-2021-01-15.xml*