Multi-ship collision avoidance decision-making method under complex encounter situations

Abstract

This work addresses the issue of multi-ship collision avoidance decision-making complex encounter situations, and proposes a novel velocity varying-steering collision avoidance method based on an improved particle swarm optimization (IPSO) algorithm. The proposed method establishes a limited range based on the International Regulations for Preventing Collisions at Sea (COLREGs) and creates a multi-objective model, in which the collision risk of ships, the energy loss caused by velocity varying and the voyage loss caused by steering are taken into account. To obtain an optimal solution of the multi-objective model, an IPSO is introduced to determine the feasible solution domain for ship collision avoidance decision making(CADM). The proposed CADM is validated by numerical simulations and navigation simulator. The results indicate that the recommended velocity and course can effectively remove the risk of collision between the ship and target ships.

1 Introduction

As the conduit of global trade and a barometer of world economic development, the shipping industry offers numerous advantages, including its ability to transport large volumes of goods over vast distances at low cost. In fact, over 80% of the world’s total international trade volume is transported by ships [1]. Currently, the maritime trade and transportation industry is facing increasingly complex navigation environments, which often lead to ship traffic accidents. As a result, this issue has garnered significant attention from both the shipping industry and the International Maritime Organization. The “Safety and Shipping Review 2023” report published by Allianz Insurance [2] reveals that losses and casualties (accidents) of ships over 100 gross tonnes in the last 10 years, of which 3098 collisions occurred, with ship collisions accounting for 11.3% of the total number of accidents. Thus, it is evident that ship collision is a major cause of water traffic accidents. Therefore, developing effective methods for collision avoidance to ensure navigation safety and reduce the occurrence of such accidents has become a crucial research topic in the field of maritime navigation safety.

In a complex encounter situation, a multi-ship encounter situation could occur. For such a situation, however, relevant conventions and regulations have not established a guidance principle or responsibility distinction. As a result, ship operators face challenges in making collision avoidance decisions. In this context, it is extremely significant to find an optimal path that ensures navigation safety while minimizing the distance traveled and the degree of velocity varying or course adjustment angle to meet economic requirements. Although various navigation safety assurance technologies, such as IBS, AIS, ARPA, ECDIS, GIS, etc., which can assist ship operators in making collision avoidance decisions, the intelligent collision avoidance decision-making(CADM) function is not endowed with the aid of these assurance technologies. In this context, operators must rely on their own subjective analysis and navigation experience, which may lead to human errors when making decisions. Therefore, many scholars have conducted extensive work for the issue of ship CADM. Currently, there are three main types of ship CADM methods [3], i.e., deterministic methods, heuristic methods, and hybrid intelligent systems.

Regarding deterministic methods for ship CADM, Li et al. [4] and Li et al. [5, 6] have played attention to the issue of distributed multi-ship collision avoidance, which minimizes risks for all ships and maximizes benefits for all ships as evaluation criteria. Huang et al. [7] proposed a velocity obstacle(VO)-based multi-ship collision method, which calculates the minimum safe distance and optimal collision avoidance strategy between ships. Wilson et al. [8] proposed a line-of-sight guidance-based two-ship collision avoidance method. Meanwhile, Petres et al. [9], Liu et al. [10], Singh et al. [11], Lee et al. [12], Xue et al. [13], and Lyu [14] have played attention to the artificial potential field (APF)-based ship collision avoidance. [9,10,11] only considers the issue of avoiding static obstacles. In contrast, [12,13,14] considers both static and dynamic obstacles and has yielded promising applications. In addition, Lyu and Yin [15] proposed a modified APF-based method for autonomous ship collision avoidance path planning,which has made significant contributions to subsequent research in autonomous ship collision avoidance.

In terms of heuristic methods for the ship CADM issue, heuristic methods include fuzzy logic, evolutionary algorithms, swarm intelligence algorithms, artificial neural networks (ANN), etc. Perera et al. [16, 17], Nguyen et al. [18], Zhang et al. [19], Su et al. [20] proposed various fuzzy logic-based decision-making methods. Tsou and Hsueh [21],Lazarowska [22, 23] introduced the ant colony algorithm to solve the this issue. Particle swarm optimization algorithm (Xue [24], Han [25], Zheng et al. [26],Liang et al. [27]) and genetic algorithm (Tsou [28, 29], Vagale et al. [30]) are also widely used in this issue. Xu et al. [31] proposed a multi-objective optimization method for multi-ship collision avoidance issues. Additionally, various evolutionary and swarm intelligence algorithms, such as Beetle Antennae Search [32], Danger Immune Algorithm [33], and Simulated Annealing Algorithm [34], had been applied to resolve the ship CADM issue. Furthermore, ANN’s excellent computing and learning capabilities have been utilized to solve ship CADM issue [35, 36].

Hybrid intelligent systems for the ship CADM issue have also been explored. For example, Cheng and Liu [37] combined genetic algorithm (GA) with simulated annealing algorithm (SA) to achieve a better solution performance. Perera et al. [38] established a hybrid collision avoidance system by combining fuzzy logic and ANN. Shen et al. [39] proposed a deep reinforcement learning-based multi-ship system collision avoidance method. Ahn et al. [40] proposed a comprehensive multi-ship collision avoidance system by combining fuzzy inference system and expert system. In this work, the neural network is used to obtain the risk of ship collision. Meanwhile, the multi-layer perceptron neural network is introduced to remedy the difficulty caused by the adaptive fuzzy inference. Szlapczynski [41,42,43,44] proposed a new method of multi-ship collision avoidance (ESoSST) combining the advantages of game theory and evolutionary algorithm. Although these results are inspired, what needs to be further discussed is whether these methods can solve the issue of multi-ship avoidance in intersection waters.

This work summarizes the ship collision avoidance methods mentioned above and evaluates them based on six aspects:(1) Compliance with the International Regulations for Preventing Collisions at Sea (COLREGs), categorized as “yes” for compliant and “no” for non-compliant; (2) Consideration of the number of collision avoidance ships, represented as “multiple” if more than 5 ships are involved; (3) Consideration of maneuvering characteristics, i.e., whether to establish a detailed mathematical model of the ship’s motion, capable of accurately describing the various motion characteristics of the ship in the process of collision avoidance, such as changes in velocity, steering characteristics, etc., classified as high, medium and low; (4) Collision avoidance measures of ships, categorized as steering, velocity varying, or a combination of both; (5) Algorithm computation time, divided into high (within 10 s), medium (within 1 min), and low (over 1 min or even longer); (6) Verification of results through numerical simulation or full-scale ship trial. The comparison results are presented in Table 1.

Table 1 Comparison between typical ship CADM method

From Table 1, it can be found clearly that each of these methods is of its advantages and disadvantages. For the ship CADM issue, it is also necessary to identify, classify, and analyze the motion status of other ships and obstacles, determine potential encounter situations, and take collision avoidance measures to guarantee the safety of navigation and comply with the collision avoidance rules. Additionally, it is important to balance the computational accuracy and real-time performance of the algorithm to reduce the complexity of algorithm implementation.

Based on the analysis of the three types of ship CADM methods mentioned above, it can be concluded that the current researches have several issues: (1) The navigation environment factors have not been fully considered, and the CADM methods ensure that the collision avoidance action between target ships can be finished safely, but it could violate “COLREGs”; (2) The motion pattern of ships is often oversimplified, failing to fully consider the ship type, size, and ship domain model; (3) Most presented collision avoidance measures are for multi-ship encounters in complex situations, mainly focusing on steering, which implies that the measure is unitary.

At present, most of the multi-ship CADM studied are mainly applicable to open waters, where ships need to achieve collision avoidance by significantly altering course. However, when sailing into or out of narrow waters, the large scale and high velocity of ships, combined with restricted channel widths, severely limit the ships’ ability to change course. Therefore, decision-making methods applicable to open waters may no longer be applicable in these situations. Most of the research on multi-ship CADM methods for narrow waters focuses on the collision avoidance behavior itself, ignoring other important factors such as energy loss and voyage loss. This may cause the collision avoidance decision to be too biased towards safety, while neglecting economy and efficiency. Some methods rely excessively on empirical rules or heuristic algorithms and lack a systematic mathematical modeling and solution framework, making it difficult to cope with complex multi-ship encounter scenarios. In this work, we propose a decision-making method for multi-ship collision avoidance when sailing into or out of narrow waters and encountering complex situations. Our approach is mainly based on the “COLREGs” classification of encounter situations and establishes a multi-objective collision avoidance model. We evaluate the advantages and disadvantages of collision avoidance using three sub-objective models, taking into account factors such as ship maneuvering characteristics, ship domain, and COLREGs. We propose a specific velocity varying-steering collision avoidance measure based on the characteristics of the navigation water area. By using the improved particle swarm optimization (IPSO) algorithm, the collision avoidance constraint of COLREGs is set to the feasible solution range, and the algorithm parameters are dynamically adjusted within the range to quickly calculate the optimal collision avoidance decision value for velocity varying-steering. Finally, we conduct simulation experiments on a ship maneuvering simulator to verify the effectiveness and superiority of the given decision values.

In conclusion, this work aims to enhance the safety and efficiency of water traffic at the junction of open and narrow waters by providing an effective CADM method that assists ship operators in making accurate collision avoidance decisions in complex encounter situations. The main contributions of this work are as follows:

• (1) A multi-ship CADM method for sailing into or out of narrow waters is proposed to solve the problem of collision avoidance in complex encounter situations. A multi-objective collision avoidance model is established comprehensively by considering factors such as ship maneuvering characteristics, ship domains and COLREGs, which are used as the evaluation of the advantages and disadvantages of collision avoidance. The effectiveness and superiority of the method are verified in multi-ship collision avoidance scenarios and ship maneuvering simulator tests.

• (2) A fuzzy quaternion ship domain model is introduced in the determination of the safe encounter distance and the relevant mathematical model is established. Unlike the previous method of simply setting a fixed threshold, this method determines the safe encounter distance between ships based on different encounter situations. This introduction can more accurately take into account the dynamic characteristics of ships and thus provide a more reliable assessment of the safe encounter distance.

• (3) During the optimal velocity varying-steering collision avoidance decision value search process, the search strategy is optimized from both vertical and horizontal perspectives by dynamically adjusting the control parameters of the PSO. By comparing with the classical evolutionary algorithm, it is concluded that IPSO has certain advantages in convergence speed, computational accuracy, and computational speed, and solves the problem that the original algorithm is easy to fall into the local optimal solution.

2 Problem description

As implementing velocity varying-steering collision avoidance measures, it is important to consider the risk of collision after velocity varying-steering, energy loss due to velocity varying, and the voyage loss resulting from steering. In this work, one evaluates the advantages and disadvantages of the ship’s velocity varying-steering collision avoidance based on these three objectives. The problem can be abstracted as finding the optimal velocity and course among many solutions in the multi-objective model of ship collision avoidance, within the range of feasible solutions. The optimization process of the particle swarm optimization (PSO) algorithm is used for reference for this work. The comparison between velocity varying-steering CADM and the PSO algorithm optimization process is shown in Table 2.

Table 2 Comparison of velocity varying-steering CADM and PSO

Articles 12 to 15 of COLREGs clearly stipulate the division of encounter situations for ships. This work will list the actions that the ships should take under different encounter situations [45]. Figure 1 displays the division of the encounter situations centered on the ship.

Fig. 1

Encounter situation division

• (1) Head-on encounter situation: When two ships meet in reciprocal or near reciprocal directions (with the other ship located in area A), the two ships shall take care to avoid each other, it is considered a head-on situation. If there is a risk of collision, the two ships shall change course, usually each ship should alter its course to starboard so that they pass on the port side or pass behind the stern of the other ship;

• (2) Crossing encounter situation: when two ships can only see each other’s side of the broadside lights, which are located in the other ship’s bow to the left and right of $5^{\circ }$ to $112.5^{\circ }$, the situation can be considered a crossing situation. Cross encounters are further divided into small-angle crossings (other ships located in regions B and F) and large-angle crossings (other ships located in regions C and E). According to the “Let red not let green” provisions of COLREGs, when there is another ship in area B and C and there is a risk of collision between the two ships, the ship shall give way. Usually, the ship should slow down or steer left to avoid collision, while the other ship should maintain its course and velocity.

• (3) Overtaking encounter situation: When another ship catches up and overtakes the ship in a direction greater than $22.5^{\circ }$ from directly behind the ship’s beam (with the other ship located in zone D), it is considered an overtaking situation. According to COLREGs, when another ship overtakes the ship, the ship should give way to the ship being overtaken since it has the right of way.

3 Multi-objective model for ship collision avoidance

In this work, the problem of multi-ship collision avoidance in complex encounter situations can be viewed as a multi-objective model optimization problem. The IPSO algorithm is utilized to calculate the optimal collision avoidance decision value in accordance with the “COLREGs” and constraints based on the encounter situation between ships. Three sub-objectives are defined within the multi-objective model for ship collision avoidance: the CRI sub-objective $f_1$, velocity varying energy loss sub-objective $f_2$, and loss of voyage sub-objective $f_3$ resulting in the following model:

$$\begin{aligned} f\left( v_i, \psi _i\right) =a_1 f_1\left( v_i, \psi _i\right) +a_2 f_2\left( v_i\right) +a_3 f_3\left( \psi _i\right) \end{aligned}$$

(1)

where $a_1$, $a_2$ and $a_3$ are weight coefficients with $a_1+a_2+a_3=1$, the percentage of each weight needs to be determined based on the experimental test; $v_i$ is the velocity of the ship relative to the ith target ship, and $\psi _i$ is the course of the ship with respect to the ith target ship.

3.1 CRI objective model

The Collision Risk Index (CRI) is a measure of the possibility of collision between ships, as well as a measure of whether there is a collision risk when two ships meet. The value range of CRI is [0,1]. CRI=0 means there is no risk of collision between ships and they can navigate freely. CRI=1 means the ship is bound to collide, when the CRI reaches or exceeds a certain threshold, the ship or the target ship must take action, otherwise a collision will occur. The fuzzy comprehensive evaluation method which is based on fuzzy mathematics, can be applied to measure collision risk [46]. In complex encounter situations, the Distance to Closest Point of Approach (DCPA) between ships in the encounter situation is an important parameter used to measure collision risk after the ship takes velocity varying-steering measures. The DCPA is calculated as follows:

$$\begin{aligned} D C P A=f_{D C P A}\left( v_0, C_0, v_t, C_t, D, T_B\right) \end{aligned}$$

(2)

where the velocity of the ship $v_0$, the course of the ship $C_0$, the velocity of the target ship $v_t$, the course of the target ship $C_t$, the distance D between ships and the true bearing of the target ship $T_B$. During the process of velocity varying avoidance, the ship needs to slow down to an optimal velocity that meets the constraints. Based on the motion characteristics of the ship, it needs drop speed stroke $D_S$ and stroke time $T_S$ to slow down to the predetermined velocity [47]. $T_S$ is the time taken by the ship from the point of loss of control to the disappearance of inertia. Its magnitude can be found in Eq. 3.

$$\begin{aligned} {T_S=-T_{st}ln(v{/~}v_0)} \end{aligned}$$

(3)

where $T_{st}$ is the time constant of ship’s deceleration, $T_{st}$ = C/ln2, C is the time constant of ship’s velocity halving, and the value of C is shown in Table 3; v is the ship’s velocity at any moment in the stroke time. $D_S$ is the distance traveled in the direction of the ship’s velocity in $T_S$, which can be estimated by Eq. 4.

$$\begin{aligned} {D_{S} = v_{0}T_{st}\left( 1-e^{-T_{S}{/~}T_{st}} \right) } \end{aligned}$$

(4)

Table 3 Reference to the value of ship velocity halving time constant C

As the ship decelerates, the DCPA values of the ship and the target ship are continuously changing. When the ship decelerates to the predetermined velocity $v_1$, the DCPA value will remain unchanged. At this point, the position of the ship $(x_0,y_0)$ and the position of the target ship relative to the ship $(x_1,y_1)$ can be obtained at this time, the new true bearing $T_{B1}$ and the new distance $D_1$ between ships can be calculated. The $DCPA_1=f_{DCPA}(v_1,C_0,v_t,C_t,D_1,T_{B1})$ of the ship and the target ship after deceleration. The model for calculating the DCPA value of the ship under velocity varying measures is shown in Fig. 2.

Fig. 2

DCPA acquisition model under ship velocity varying measures

The position $(x_1,y_1 )$ of the target ship relative to the ship after the velocity varying measure can be obtained from Eq. 5. The new distance and true bearing between ships can be calculated from Eqs. 6 and  7.

$$\begin{aligned}{} & {} \left\{ \begin{array}{l} x_1=D\sin T_B+v_tT_S\sin C_t+D_S\sin \left( C_0+180^{\circ }\right) \\ y_1=D\cos T_B+v_tT_S\cos C_t+D_S\cos \left( C_0+180^{\circ }\right) \end{array}\right. \end{aligned}$$

(5)

$$\begin{aligned}{} & {} D_1=\sqrt{\left( x_1-x_0\right) ^2+\left( y_1-y_0\right) ^2} \end{aligned}$$

(6)

$$\begin{aligned}{} & {} T_{B 1}=\left\{ \begin{array}{cr} \arctan \left( \frac{x_1-x_0}{y_1-y_0}\right) , &{} y_1>0 \\ 180^{\circ }+\arctan \left( \frac{x_1-x_0}{y_1-y_0}\right) , &{} y_1<0\\ 0^{\circ }, &{} y_1=0;x_1=0 \\ 90^{\circ }, &{} y_1=0;x_1>0 \\ 270^{\circ }, &{} y_1=0;x_1<0 \end{array}\right. \end{aligned}$$

(7)

After implementing velocity varying measures, the DCPA value between ships needs to be greater than a minimum safe distance $d_1$. However, in complex encounter situations, it may still be difficult to maintain a safe encounter distance between ships using only velocity varying measures. For example, when the course intersection angle of the two ships is less than 5$^{\circ }$, the DCPA value of the ship after velocity varying measures does not change significantly, which cannot satisfy the condition of greater safe encounter distance. In such cases, the target ship whose DCPA value is less than the safe encounter distance should take steering measures to avoid collision. Set the course adjustment angle of the ship to avoid as Q, the time from the initial course $C_0$ to the required course $C_Q$ ($C_Q=C_0 \pm Q$, “+”Indicates the ship alteration of course to the right, “-” Indicates the ship alteration of course to the left) as t, the initial time of the ship’s steering is $t_1$, the time of the ship’s steering to the required course is $t_2$. The displacement of the local ship is obtained from Eq. 8, and the relative displacement of the target ship is obtained from Eq. 9.

$$\begin{aligned}{} & {} \left\{ \begin{array}{c} x_t=\int _{t_1}^{t_2} v_1 \cos C_Q d t \\ y_t=\int _{t_1}^{t_2} v_1 \sin C_Q d t \end{array}\right. \end{aligned}$$

(8)

$$\begin{aligned}{} & {} \left\{ \begin{array}{l} x_2=x_1+\int _{t_1}^{t_2}\left( v_t \cos C_t-v_1 \cos C_Q\right) d t \\ y_2=y_1+\int _{t_1}^{t_2}\left( v_t \sin C_t-v_1 \sin C_Q\right) d t \end{array}\right. \end{aligned}$$

(9)

Once the relative displacement of the ship and the target ship is determined, the following parameters can be calculated based on the above parameters: the relative orientation $\alpha$, distance $D_2$, relative course $C_R$ and relative velocity $v_R$ between ships.

$$\begin{aligned} \alpha= & {} \arctan \frac{y_2-y_t}{x_2-x_t} \end{aligned}$$

(10)

$$\begin{aligned} D_2= & {} \sqrt{\left( x_2-x_t\right) ^2+\left( y_2-y_t\right) ^2} \end{aligned}$$

(11)

$$\begin{aligned} C_R= & {} \arctan \frac{v_t \cos C_t-v_1 \cos C_Q}{v_t \sin C_t-v_1 \sin C_Q} \end{aligned}$$

(12)

$$\begin{aligned} v_R= & {} \sqrt{v_1^2+v_t^2-2 v_1 v_t \cos \left( C_Q-C_t\right) } \end{aligned}$$

(13)

The DCPA value between ships after steering can then be found by the above parameters.

$$\begin{aligned} D C P A_2=D_2 \sin \left( C_R-\alpha -180^{\circ }\right) \end{aligned}$$

(14)

The traditional model for ship collision risk index assessment is based on the DCPA to determine the CRI of the ship’s encounter. Typically, a fixed threshold limit value is established, and when the encounter distance is less than this value, there is a greater risk of collision. However, using the same threshold limit value in all directions of the ship ignores the influence of ship parameters, maneuvering performance, etc. on the encounter distance. To address this issue, the ship domain model is introduced, which is an area surrounding the ship that allows it to navigate safely and avoid collision. The size of the ship domain model is influenced by various factors such as ship size, velocity, encounter situation, and visibility. Utilizing the ship domain model to measure CRI can solve the aforementioned issue of incomplete consideration. This work references a fuzzy quaternion ship domain model proposed by WANG [48], which considers the ship’s motion parameters and maneuvering performance. The model’s domain shape can be adapted to various waters based on the adjustment of the boundary parameter K. The boundary parameter K determines the shape of the boundary of the fuzzy quaternion ship domain model, and the boundary is used to set a safety interval around the ship to represent a buffer region. This parameter allows the boundary to be either polygonal or elliptical, and also narrow or wide, and it provides flexibility in defining the shape of the boundary of the ship domain. When K=1 the boundary is a polygon, when K=2 the boundary is an ellipse, the ellipse boundary can describe the shape of the ship more accurately, which can help the ship to judge whether other ships are intruding into the ship domain in all directions. The fuzzy quaternion ship domain model with ellipse boundary is selected for this work. As shown in Fig. 3, a coordinate system is established with the ship as the center, the vertical axis y of the coordinate system is the ship’s bow direction, and the horizontal axis x is the right direction perpendicular to the ship’s bow direction. The fuzzy quaternion ship domain model is determined by multiple ellipses with different directional radius, and 1/4 of the ellipses are taken to form an irregular closed curve. $R_{fore}$ and $R_{aft}$ represent the front and back radii of the longitudinal radius of the ship domain model, while $R_{starb}$ and $R_{port}$ represent the left and right radii of the transverse radius of the ship domain.

Fig. 3

Fuzzy quaternion ship domain model

$$\begin{aligned}{} & {} \left\{ \begin{array}{l} {k_{A_D}}=10^{0.3591 \lg v+0.0952} \\ {k_{T_D}}=10^{0.5441 \lg v-0.0795} \end{array}\right. \end{aligned}$$

(15)

$$\begin{aligned}{} & {} \left\{ \begin{array}{l} R_{\text{ fore } }=\left( 1+1.34 \sqrt{{k_{A_D}}^2+\left( {k_{D_T}} / 2\right) ^2}\right) L \\ R_{\text{ aft } }=\left( 1+0.67 \sqrt{{k_{A_D}}^2+\left( {k_{D_T}} / 2\right) ^2}\right) L \\ R_{\text{ starb } }=\left( 0.2+{k_{D_T}} \right) L \\ R_{\text{ port } }=\left( 0.2+0.75 {k_{D_T}} \right) L \end{array}\right. \end{aligned}$$

(16)

where $k_{T_D}$ is the coefficient of the tactical diameter, $k_{A_D}$ is the coefficient of the advance, and L is the ship’s length.

When another ship enters this defined domain, it is identified as a collision risk, assigning a CRI value of 1. The boundary of the fuzzy quaternion ship domain is taken as the minimum safe encounter distance $d_1$, and the value of $d_1$ will change depending on the orientation change between ships. The safe passage distance $d_2$ is defined as twice the minimum safe encounter distance $2d_1$, and the CRI is considered 0 when the encounter distance between two ships exceeds the value of $d_2$. This work is based on the distance from any point on the ellipse to the center of the ellipse. The distance d formula:

$$\begin{aligned} d=\sqrt{a^2b^2/\left( a^2\sin {\gamma }^2+a^2\cos {\gamma }^2\right) } \end{aligned}$$

(17)

where a is the long radius of the ellipse, b is the short radius of the ellipse, and $\gamma$ is the angle between the line from any point on the ellipse to the center of the ellipse and the long semi-axis.

The calculation formula of the $d_1$ can be deduced as follows:

$$\begin{aligned} d_1= {\left\{ \begin{array}{ll}\sqrt{\frac{R_{\text{ fore }}^2 R_{\text{ starb }}^2}{R_{\text{ fore }}^2 \sin \gamma _1^2+R_{\text{ starb }}^2 \cos \gamma _1^2}} &{} x \ge 0, y>0 \\ \sqrt{\frac{R_{\text{ starb } }^2 R_{\text{ aft } }^2}{R_{\text{ starb }}^2 \sin \gamma _2^2+R_{\text{ aft }}^2 \cos \gamma _2^2}} &{} x>0, y \le 0 \\ \sqrt{\frac{R_{\text{ port }}^2 R_{\text{ aft }}^2}{R_{\text{ port } }^2 \sin \gamma _3^2+R_{\text{ aft }}^2 \cos \gamma _3^2}} &{} x \le 0, y<0 \\ \sqrt{\frac{R_{\text{ fore }}^2 R_{\text{ port }}^2}{R_{\text{ fore }}^2 \sin \gamma _4^2+R_{\text{ port }}^2 \cos \gamma _4^2}} &{} x<0, y\ge 0 \end{array}\right. } \end{aligned}$$

(18)

where $\gamma _1$,$\gamma _2$,$\gamma _3$,$\gamma _4$ are the angles between the line of this ship to the closest point of approach(CPA) and $R_{fore}$, $R_{aft}$, $R_{starb}$, $R_{port}$ respectively; (x, y) are the coordinates of the CPA in the coordinate system established by the ship domain.

The collision risk index between ships is as follows:

$$\begin{aligned} C R I= {\left\{ \begin{array}{ll}1, &{} 0 \le DCPA_2 \le d_1 \\ \frac{1}{2}-\frac{1}{2} \sin \left( \frac{180^{\circ }}{d_2-d_1}\left( DCPA_2-\frac{d_1+d_2}{2}\right) \right) , &{} d_1<DCPA_2 \le d_2 \\ 0, &{} DCPA_2>d_2\end{array}\right. } \end{aligned}$$

(19)

The larger the DCPA$_2$ value between ships after taking velocity varying-steering measures, the safer it is, i.e., the smaller the CRI is, so the collision risk index sub-objective $f_1$ is constructed as:

$$\begin{aligned} \min f_1\left( v_i, \psi _i\right) =CRI \end{aligned}$$

(20)

where $f_1(v_i,\psi _i )$ has a value range of [0,1], and the smaller the value is, the smaller the collision risk index is.

3.2 Velocity varying energy loss objective model

In the context of velocity adjustment for collision avoidance, adherence to the COLREGs article 8 is mandatory. This article stipulates that actions taken to avoid collisions must be “substantial“, including the requirement to reduce the ship’s velocity to at least 1/2 of its original velocity. [49]. The range of ship velocity varying should be maintained between the minimum velocity $v_{min}$ and 1/2 of the original velocity $v_0$ to maintain steerage, basically set 1/2 of the original velocity is greater than the minimum velocity, then the velocity $v_i$ feasible solution domain in accordance with the Rules is $[v_{\min },v_0/2]$. The ship drops to a lower velocity to avoid collision and then returns to the original velocity making more energy loss of the ship. Therefore, in the process of velocity varying collision avoidance, it is desirable to choose the velocity that is consistent with COLREGs and as large as possible, then the velocity varying energy loss sub-objective $f_2$ is taken as:

$$\begin{aligned} \min f_2\left( v_i\right) =\frac{v_i-v_0 / 2}{v_{\min }-v_0 / 2}, \quad v_{\min } \le v_i \le v_0 / 2 \end{aligned}$$

(21)

where $v_{\min }$ is the minimum velocity of the ship to maintain steerage; $v_0$ is the initial velocity of the ship; the value range of $f_2(v_i )$ is [0,1], and the larger the value of $v_i$ the smaller its value is, which means the smaller the velocity varying energy loss is.

3.3 Loss of voyage objective model

During the steering collision avoidance process of the ship, it is necessary to take into account the action to avoid collision in article 8 of COLREGs, which requires the ship to take a “substantial” avoidance action [49]. The ship should steer to the required course not less than $\psi ^{\prime }$, but the difference between the course after steering and the original course will inevitably make the ship sail back to the original course too much. To reduce the loss of voyage, the steer to the required course should not be greater than $\psi ^{\prime \prime }$. Then, in the process of steering collision avoidance, the ship’s course should be changed as little as possible while meeting the requirements for collision avoidance. Then the sub-objective for voyage loss $f_3$ is defined as follows:

$$\begin{aligned} \min f_3\left( \psi _i\right) =\frac{\psi _i-\psi ^{\prime }}{\psi ^{\prime \prime }-\psi ^{\prime }}, \quad \psi ^{\prime } \le \psi _i \le \psi ^{\prime \prime } \end{aligned}$$

(22)

where $f_3(\psi _i )$ has a value range of [0,1], and the smaller the angular difference between the value of $\psi _i$ and the original course, the smaller the loss of voyage.

4 Ship CADM based on IPSO

4.1 IPSO

The PSO algorithm is a widely used population-based optimization algorithm. The fundamental concept of PSO is to simulates the behavior of a population, such as a flock of birds or a school of fish, to perform optimization computations. The algorithm views the problem to be solved as an optimization problem in a multidimensional space, where it continuously searches for the optimal solution by iterating and constantly updating the positions and velocities of the particles [50]. Each particle in the swarm represents a potential solution to the problem, having its own individual position and velocity information. For an N-dimensional space of M particles, the position and velocity vectors of the ith particle are $X_i=(X_{i1},X_{i2},\cdots ,X_{iN} )$and $V_i=(V_{i1},V_{i2},\cdots ,V_{iN} )$, respectively, where the value of i is [1, M]. The optimal position of the ith particle searched so far is represented by $P_i=(P_{i1},P_{i2},\cdots ,P_{iN} )$, and the optimal position of the entire cluster searched so far is $P_g=(P_{g1},P_{g2},\cdots ,P_{gN} )$. The adaptation value of each particle $X_i$ is calculated by substituting it into the objective function $f(X_i )$, and the particle’s state is updated in accordance with the following formula.

$$\begin{aligned} V_{i n}^{k+1}= & {} w V_{i n}^k+c_1 r_1\left( P_{i n}^k-X_{i n}^k\right) +c_2 r_2\left( P_{g n}^k-X_{i n}^k\right) \end{aligned}$$

(23)

$$\begin{aligned} X_{i n}^{k+1}= & {} X_{i n}^k+V_{i n}^{k+1} \end{aligned}$$

(24)

where w is the inertia weight, k is the number of current iterations, $n=1,2,\cdots ,N$; $V_{in}$ is the velocity of the particle; $c_1$ and $c_2$ are non-negative acceleration factors; $r_1$ and $r_2$ are random numbers distributed between [0,1]; To prevent the blind search of the particle, it is generally recommended to set $V_{in}$ $\in$ $[V_{\min },V_{\max } ]$ for the flight speed of the particle with a limit, $V_{\min }$, $V_{\max }$ are constants, which can be set according to the specific problem.

This work aims to address the issues inherent in traditional PSO algorithms, which rely on fixed control parameters. These parameters lack focus and make it difficult to diversify the population. To tackle this problem, a method is proposed to dynamically adjust the control parameters from both vertical and horizontal perspectives. By varying the control parameters during different phases of the optimization search tasks, particles can focus on executing the most suitable strategy while avoiding competition between global and local searches. Overall, this method results in a more efficient search process and simultaneously improves global and local search capabilities. As a result, search results are significantly enhanced.

4.1.1 Dynamically adjust the inertia weight

According to the strategy of needing to maintain a large inertia weight w in the early stage and gradually reducing the value of w in the later stage, the inertia weight adjustment method of cosine decay is used in this work, and the inertia parameter $w_s$ under the influence of the number of iterations is used as a function of s. The calculation of $w_s$ is shown in Eq. 25:

$$\begin{aligned} w_s=\left( w_{\max }-w_{\min }\right) \cos \frac{\pi s}{2 T}+w_{\min } \end{aligned}$$

(25)

The particle swarm calculates the fitness values of the particles after each iteration, removes the particles with infinite fitness values, finds the maximum fitness value $f_{\max }$ and the minimum fitness value $f_{\min }$ among the remaining particles, and calculates the average fitness value ${\bar{f}}$ Then the inertia parameter $w_f$ under the influence of the fitness value is used as a function of f. The calculation of $w_f$ is shown in Eq. 26:

$$\begin{aligned} w_f=\left( w_{\max }-w_{\min }\right) \left( \frac{f_i-{\bar{f}}}{f_{\max }-f_{\min }}+1\right) +f_{\min } \end{aligned}$$

(26)

Considering the influence of the number of iterations s and the fitness value f on the inertia parameter w, w is calculated as shown in Eq. 27:

$$\begin{aligned} w=\alpha w_s+\beta w_f \end{aligned}$$

(27)

where $\alpha$ and $\beta$ are proportional coefficients to regulate the degree of influence of s and f on w.

4.1.2 Adjust the acceleration factor dynamically

The individual acceleration factor $c_1$, the group acceleration factor $c_2$ are calculated based on the dynamic adjustment of the inertia weight w [51]. The initial $c_1$=2.5, $c_2$=1.5, and the final $c_1$=1.5, $c_2$=2.5; $w_{\max }$=1.4, $w_{\min }$=0.6. The linear system of equations for $c_1$ and $c_2$ concerning w is obtained using the method of undetermined coefficient $\{\begin{aligned} c_1=k_{1}w+b_1 \\ c_2=k_{2}w+b_2 \end{aligned}$ to be determined as shown in Eq. 28:

$$\begin{aligned} \left\{ \begin{array}{l} c_1=1.25 w+0.75 \\ c_2=-1.25 w+3.25 \end{array}\right. \end{aligned}$$

(28)

4.2 Solution process

The improved algorithm follows the following steps:

• (1) Initialization: Randomly initialize the position and velocity of the particle swarm set the maximum number of iterations and the algorithm termination condition.

• (2) Evaluation: Assess the initial fitness value of each particle in the swarm.

• (3) Historical optima update: Update the historical optimal position of individual particles and the historical optimal position of the particle swarm in this generation.

• (4) Parameter calculation: Calculate $w_s$ according to the number of iterations, $w_f$ according to the adaptation value, the inertia weight w by Eq. 26 according to certain weights, and then the individual acceleration factor $c_1$ and group acceleration factor $c_2$ by Eq. 28.

• (5) Velocity and position update: Substitute the control parameters w, $c_1$, $c_2$ into Eq. 23 to calculate and update the velocity and position of each particle.

• (6) Termination check: Judge whether the algorithm satisfies the termination condition, if not, go to step (3), and if it does, end the algorithm (Fig. 4).

  Fig. 4

  

  IPSO algorithm solving process

5 Simulation experimental research

5.1 Numerical simulation verification

To evaluate the performance of the improved algorithm, the Schaffer test function, a complex two-dimensional function replete with innumerable local minima, is utilized. Due to the function’s strong oscillation state, obtaining the global optimal solution is difficult. The function is expressed in Eq. 29 with a search range of [-10,10], the optimal solution is (0,0), and the optimal value is 0.

$$\begin{aligned} f(x, y)=0.5+\frac{\left( \sin \sqrt{x^2+y^2}\right) ^2-0.5}{\left( 1+0.001\left( x^2+y^2\right) \right) ^2}, \quad -10 \le x; y \le 10 \end{aligned}$$

(29)

The algorithm is configured using the following parameters: a population size of 300, a maximum iteration count of 300, and a particle velocity update limit range of [$-$1.5,1.5]. The dynamic adjustment range of w with IPSO algorithm is [0.6,1.4], and the dynamic adjustment range of $c_1$ and $c_2$ is both set to [1.5, 2.5]. In PSO algorithm, w is set as 0.9, and $c_1$, $c_2$ are set as 2. PSO algorithm and IPSO algorithm are used respectively to optimize Schaffer test function, and the algorithm iteration curve is obtained, as shown in Fig. 5.

Fig. 5

Comparison of iteration curves of two algorithms

Upon examining the iteration curves of both algorithms, the IPSO algorithm, characterized by its dynamic adjustment of inertia weight and acceleration factor, demonstrates superior optimization capabilities over the PSO algorithm. Additionally, the IPSO algorithm also demonstrates a stronger ability to escape local optimal. Throughout the optimization process, it maintains stability and exhibits a significantly faster convergence speed than the PSO algorithm. According to these results, it can be concluded that the IPSO algorithm outperforms the traditional PSO algorithm in terms of optimization and efficiency.

5.2 Simulation scenario 1

In this work, MATLAB R2021a is utilized for simulations and result analyses. To verify the feasibility of this method, a scenario wherein ships encounter a complex situation while leaving the narrow waters is selected. It is assumed that the ship (OS) is 299.0m in length, 86900.0t in dead weight, and sailing in narrow waters with a course of 000$^{\circ }$ and a velocity of 15 knots. At the same time, it is in the encounter situation with five target ships ($TG_1$-$TG_4$), the encounter situation is shown in Fig. 6 and the information on the encounter situation of each target ship obtained through radar plotting and AIS is presented in Table 4.

Fig. 6

Scenario 1 Encounter situation of OS and each TG

Table 4 Scenario 1 The parameters of the target ship at a certain moment obtained

Judging from Fig. 6 and Table 4, the encounter distance of $TG_1$, $TG_2$ and $TG_3$ ships is significantly below the safe encounter distance of the ship, and there is a close-quarters situation with a greater risk of collision. The ship must engage in a reverse deceleration process to avoid this situation, as per Article 19 of COLREGs. After the implementation of this process, the ship will maintain a safe encounter distance with $TG_1$ and $TG_3$. However, it will still face the possibility of encountering and crossing with $TG_2$ and $TG_4$, with a considerably high risk of collision. As per Articles 14 and 15 of COLREGs, the ship, being the avoidance ship, must steer to the right and avoid crossing path in front of $TG_4$.

The relevant parameter settings in the algorithm are as follows: The population size is set to 50, the iteration count is set to 250, and the update speed range is limited to [$-$1.5,1.5]. IPSO algorithm dynamically adjusts w within a range of [0.6, 1.4], while the dynamic adjustment range of $c_1$ and $c_2$ is both set to [1.5, 2.5]. The PSO algorithm sets w to 0.9 and $c_1$, $c_2$ are set to 2. The feasible solution domain for $v_i$ is [2, 7.5], while the feasible solution domain for $\psi _i$ is [30, 50]. The values for $a_1$, $a_2$, and $a_3$ are respectively set to 0.6, 0.2, and 0.2.

The simulation results are presented in Table 5 and Fig. 7. The values of $(f_{bset},v_{bset},\psi _{bset} )=(0.28698,6.2112,41.7156)$ are obtained by executing the algorithm 30 times. The average speed of iteration for the IPSO algorithm is approximately 11 s, which is faster than the PSO algorithm. IPSO algorithm tends to stabilize by the 20th generation, whereas the PSO algorithm tends to stabilize by the 58th generation. The optimal fitness value obtained by the PSO algorithm is higher than that obtained by the IPSO algorithm. It indicates that the IPSO algorithm delivers superior optimization performance. In order to avoid collision, it is recommended that the ship decelerate from its initial velocity of 15 knots to 6.2 knots, with a drop speed stroke ($D_S$) of 1.53 n miles and a stroke time ($T_S$) of 11.4 min. After stabilizing at 4.4 knots, the DCPA value of OS with $TG_1$-$TG_4$ is $(1.16, -0.54,2.87,0.16)$. The values of DCPA of $TG_1$ and $TG_3$ are all greater than 1 n miles, which can safely pass the bow of the ship. For $TG_2$ and $TG_4$ target ships, the ship should be adjusted to a course angle of approximately 47.1$^{\circ }$. After course adjustments the DCPA values with $TG_2$ and $TG_4$ are (− 2.04, − 2.25), and the absolute DCPA values for all target ships are greater than 2 n miles. The results demonstrate the efficacy of CADM in this scenario, enabling safe navigation and avoidance of target ships at risk of collision.

Table 5 Scenario 1 Results of comparison simulation experiment

Fig. 7

Scenario 1 Comparison of iterative curves of optimal fitness values

5.2.1 Collision avoidance effectiveness analysis

To verify whether the ship maintains the established safe encounter distance, the safe encounter distance values ($d_1$) are calculated separately for OS and $TG_1$-$TG_4$ in scenario 1, resulting in values of (0.5479,0.5479,0.8256,0.7495). The alteration in distance between OS and each TG over time is subsequently computed individually, and the outcomes are presented in Fig. 8.

In Fig. 8, it is evident that utilizing the decision value generated by the IPSO algorithm for collision avoidance effectively maintains the distance change between OS and each TG above the designated safe limit. On the other hand, the dashed line on the chart indicates the deviation in separation distance between OS and each TG after applying the PSO algorithm’s decision value. Notably, the extended duration of the PSO operation algorithm results in relatively close proximity between OS and each TG. Importantly, the closest encounter distance between OS and $TG_1$, $TG_2$, and $TG_4$ falls below each ship’s designated safety threshold.

Fig. 8

Scenario 1 Variation of distance between OS and each TG

Figure 9 presents the time-series variation curves of the ship’s heading, velocity and steering angle during the collision avoidance process. OS completes the deceleration collision avoidance action in about 11 min and stabilizes the speed to 6.2 knots. The steering collision avoidance action is completed at about 17 min by a small adjustment of the steering angle to the heading to 47°, and after 26–28 min the collision avoidance is completed. The ship then returns to its original heading by steering angle adjustment and gradually accelerates to 9 knots. This indicates that the IPSO algorithm can provide support for ship collision avoidance by providing velocity varying-steering CADM, allowing the ship to navigate at an optimal encounter distance.

Fig. 9

Scenario 1 Variation in OS heading, velocity and steering angle

5.2.2 Navigation simulator-based simulation verification

To further verify the feasibility of the decision making, the navigation simulator is used to carry out the maneuvering experiment. The parameters of each test ship are shown in Table 6.

Table 6 Scenario 1 Test ship parameters

Figure 10 shows the motion trajectory of OS and $TG_1$-$TG_4$ at different moments, where the horizontal and vertical axes distance unit is nautical mile, moment $t_1<t_2<t_3<t_4$. Figure 11 shows the change of DCPA value and TCPA value between OS and each TG respectively, the figure shows the ship can safely avoid all target ships after traveling 26–28min under this encounter situation, which indicates that the velocity varying-steering measures taken by the ship are more feasible, and the ship completes the avoidance action which meets the requirements of COLREGs.

Fig. 10

Scenario 1 simulation test ship motion trajectory

Fig. 11

Scenario 2 Simulation test ship DCPA &TCPA value change

5.3 Simulation scenario 2

Scenario 2 selects a situation where the Ship encounters a complex encounter with multiple ships while sailing into narrow waters. It is assumed that the ship (OS) is 274.3m in length, 89634.0t in dead weight, and sailing in open waters at a course of 000$^{\circ }$ and a velocity of 14 knots. At the same time, it is in the encounter situation with three target ships ($TG_1$-$TG_3$), the encounter situation is shown in Fig. 12, and the information on the encounter situation of each target ship obtained through radar plotting and AIS is presented in Table 7.

Fig. 12

Scenario 2 Encounter situation of OS and each TG

Table 7 Scenario 2 The parameters of the target ship at a certain moment obtained

Judging from Fig. 11 and Table 7, it can be inferred that the encounter distance between OS and $TG_1$ and $TG_3$ is less than the safe encounter distance of the ship, and there is a close-quarters situation with a greater risk of collision. The ship must engage in a reverse deceleration process to avoid this situation, as per Article 19 of COLREGs. After the astern deceleration, the ship will maintain a safe encounter distance with the target ships $TG_1$ and $TG_3$, but after the deceleration, it will still be in an encounter situation with the target ship $TG_2$, and maintain a small encounter distance with the ship, with a large risk of collision. According to the requirements of Article 14 and Article 15 of COLREGs, the ship shall be the avoidance ship. Steer right into the fairway and stay on the right.

The parameter settings of the two algorithms are consistent with the simulation scenario 1. The feasible solution domain of $v_i$ is [2,7] and that of $\psi _i$ is [30,60]. The values of $a_1$, $a_2$, and $a_3$ are 0.6, 0.2, and 0.2, respectively.

The simulation results are presented in Table 8 and Fig. 13. The values of $(f_{bset},v_{bset},\psi _{bset})=(0.31506,4.4048,41.3366)$ are obtained by executing the algorithm 30 times. The average iteration speed of the IPSO algorithm is approximately 10 s, which is faster than the PSO algorithm. The IPSO algorithm tends to stabilize by the 18th generation, whereas the PSO algorithm tends to stabilize by the 59th generation. In order to avoid collision, it is recommended that the ship decelerate from its initial velocity of 14 knots to 4.4 knots, with a drop speed stroke ($D_S$) of 1.35 n miles and a stroke time ($T_S$) of 10.1 min. After stabilizing at 4.4 knots, the DCPA value of OS with $TG_1$-$TG_3$ is (1.6, $-$0.31, 2.57). The value of DCPA of $TG_1$ and $TG_3$ is greater than 1.5 n miles, which can safely pass the bow of the ship. For $TG_2$, the ship should be adjusted from course 000$^{\circ }$ to 041.3$^{\circ }$. After course adjustments the DCPA value with $TG_2$ is $-$2.46 n miles and the absolute DCPA values for all target ships are greater than 2 n miles. The results demonstrate the efficacy of CADM in this scenario, enabling safe navigation and avoidance of target ships at risk of collision.

Table 8 Scenario 2 Results of comparison simulation experiment

Fig. 13

Scenario 2 Comparison of iterative curves of optimal fitness values

5.3.1 Collision avoidance effectiveness analysis

In Scenario 2, the safe encounter distance values ($d_1$) are calculated separately for OS and $TG_1$-$TG_3$, resulting in values of (0.4778, 0.3626, 0.6084). The alteration in distance between OS and each TG over time is subsequently computed individually, and the outcomes are presented in Fig. 14.

Fig. 14

Scenario 2 Variation of distance between OS and each TG

In Fig. 14, it is evident that utilizing the decision value provided by the IPSO algorithm ensures collision avoidance and maintains the distance change between OS and each TG above the specified safe encounter distance. The dashed line in the figure illustrates the distance change between OS and each TG after collision avoidance with the decision value derived from the PSO algorithm. It is evident that the PSO algorithm takes a considerable amount of time to generate results, resulting in the distance between OS and each TG is relatively close.

Figure 15 presents the time-series variation curves of the ship’s heading, velocity and steering angle during the collision avoidance process. OS completes the deceleration collision avoidance action in about 10 min and stabilizes the speed to 4.4 knots. The steering collision avoidance action is completed at about 14 min by a small adjustment of the steering angle to the heading to 41$^{\circ }$, which is completed after 32 min. The ship then adjusts its heading to 92$^{\circ }$ by adjusting the steering angle and gradually accelerates to 7.5 knots. This indicates that the IPSO algorithm can provide support for ship collision avoidance by providing velocity varying-steering CADM. The method’s recommended velocity and heading adjustment angle enable the ship to safely and effectively avoid the target ship.

Fig. 15

Scenario 2 Variation in OS heading, velocity and steering angle

5.3.2 Navigation simulator-based simulation verification

In the navigation simulator maneuvering experiment, the parameters of each test ship are presented in Table 9.

Table 9 Scenario 2 Test ship parameters

Figure 16 shows the motion trajectory of OS and $TG_1$-$TG_3$ at different moments, where the horizontal and vertical axes distance unit is nautical mile, moment $t_1<t_2<t_3<t_4$. Figure 17 shows the change of DCPA value and TCPA value between OS and each TG respectively, the figure shows the ship can safely avoid all target ships after traveling 22–23min under this encounter situation, which indicates that the velocity varying-steering measures taken by the ship is more feasible, and the ship completes the avoidance action which meets the requirements of COLREGs.

Fig. 16

Scenario 2 simulation test ship motion trajectory

Fig. 17

Scenario 2 Simulation test ship DCPA &TCPA value change

6 Conclusion

This work proposed an IPSO algorithm-based ship varying-steering CADM method, which solves the multi-ship CADM problem for the encounter situation of ships sailing in narrow waters. The proposed method can limit the range of velocity varying and course adjustment decision, which is used as the range of particle motion for the IPSO algorithm, i.e., the feasible solution region. To guarantee the accuracy of CRI assessment and the safety of decision making, the CRI, velocity varying energy loss, and voyage loss are involved in the constraint evaluation of multi-objective model. To verify the effectiveness of varying-steering CADM method, two complex encounter scenarios are constructed in the simulator platform and the simulations are carried out. The simulation results demonstrate that the proposed varying-steering CADM method can guarantee the safe navigation of ships at a safe encounter distance.

It should be pointed out that the proposed method does not match the entirety of complex encounter scenarios. In the future, to implement the multi-ship collision avoidance from a practical perspective, our method is extended to include the more types of navigational scenarios such as complex waterways. In addition, shallow water effect, bank effect, etc., are introduced as influencing factors on ship maneuvering performance, and the maneuvering characteristics of different types of ships are analyzed in detail. These considerations are integrated into the optimization model to derive the decisions that more closely replicate actual collision avoidance strategies.