An Improved NSGA-II Algorithm for MASS Autonomous Collision Avoidance under COLREGs

Abstract

Autonomous collision avoidance decision making for maritime autonomous surface ships (MASS), as one of the key technologies for MASS autonomous navigation, is a research hotspot focused on by relevant scholars in the field of navigation. In order to guarantee the rationality, efficacy, and credibility of the MASS autonomous collision avoidance scheme, it is essential to design the MASS autonomous collision avoidance algorithm under the stipulations of the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs). In order to enhance the autonomous collision avoidance decision-making capability of MASS in accordance with the relevant provisions of COLREGs, an improved NSGA-II autonomous collision avoidance decision-making algorithm based on the good point set method (GPS-NSGA-II) is proposed, which incorporates the collision hazard and the path cost of collision avoidance actions. The experimental results in the four simulation scenarios of head-on situation, overtaking situation, crossing situation, and multi-ship encounter situation demonstrate that the MASS autonomous collision avoidance decision making based on the GPS-NSGA-II algorithm under the constraints of COLREGs is capable of providing an effective collision avoidance scheme that meets the requirements of COLREGs in common encounter situations and multi-ship avoidance scenarios promptly, with a promising future application.

1. Introduction

The integration of cutting-edge technologies, including artificial intelligence, big data, communications, and the Internet of Things, with traditional ships has led to the emergence of MASS, a technology that revolutionises the conventional ship navigation model. MASS controls the ship’s navigation process through advanced sensors and machine learning algorithms, which enable the navigation of ships in a more efficient and safer manner [1,2,3]. Currently, MASS is still in the experimental phase, and its full implementation is constrained by several challenges. One such challenge is the development of an autonomous system capable of avoiding collisions with other vessels in the complex maritime environment [4]. The issue of autonomous collision avoidance among ships is not only concerned with intelligent collision avoidance path planning, but also needs to comply with the relevant provisions of COLREGs [5,6]. COLREGs are universally recognised and commonly adhered to maritime navigation rules, and also form a supporting document for the MASS autonomous navigation decision-making system. Only by incorporating the relevant provisions of the COLREGs into the design of the MASS autonomous collision avoidance system can a safe and effective autonomous collision avoidance decision-making system be constructed [7,8].

The traditional autonomous collision avoidance system for ships employs a geometric collision avoidance method, which provides advice on the avoidance programme for vessels in accordance with COLREGs based on the relative positional relationships between vessels [9,10,11]. MASS is mainly land-based or unmanned, and the traditional collision avoidance decision-making methods can no longer adapt to the requirements of autonomous collision avoidance for MASS. In light of the autonomous collision avoidance problem of MASS, various solutions have been proposed by researchers, including the artificial potential field method [12,13], heuristic algorithms [14,15], path planning algorithm [16,17], reinforcement learning approaches [18], velocity obstacles (VO) [19], and so on. Heuristic algorithms and VO are the two most commonly employed methods.

Heuristic algorithms employ the cognitive processes of human intelligence to address complex problems, which employ a combination of reasoning and searching to rapidly identify optimal solutions to search problems, and therefore have a wide range of applications in MASS autonomous collision avoidance decision-making research [20]. Liu et al. [21] proposed an algorithm based on a combination of an enhanced bacterial foraging algorithm and a particle swarm algorithm with global search capability to optimise the collision avoidance path. The algorithm was subsequently integrated with a hybrid optimisation algorithm and a collision risk model to assess the collision risk of the ship and facilitate autonomous collision avoidance in the MATLAB simulation environment. Liu et al. [22] proposed a beetle antennae search algorithm based on multi-ship encounters, which combined COLREGs and ship maneuvering performances. The algorithm was validated through case studies using voyage loss as the objective function, and the results demonstrated that this algorithm is a viable solution for the problem of multi-ship encounters. Zhou et al. [23] employed real-time ship navigation data to construct a state set for deep reinforcement learning. Subsequently, a deep reinforcement learning collision avoidance algorithm was proposed, based on COLREGs’ constraints, and its efficacy was verified through simulation tests. Finally, the efficacy of the algorithm was demonstrated in two-vessel and multi-vessel rendezvous scenarios. Zheng et al. [24] proposed an algorithm for ship collision avoidance based on an improved particle swarm algorithm. This algorithm determines the optimal steering angle for collision avoidance between ships and has been verified as a feasible solution. Xin et al. [25] proposed an intelligent collision avoidance algorithm based on COLREGs. This algorithm automatically extracts ship state features using deep neural networks, ensuring that the ship navigates to the target and dynamically avoids obstacles through a reward and punishment mechanism. Xie et al. [26] proposed a real-time collision avoidance prediction optimisation strategy based on a simplified three-degree-of-freedom hydrodynamic model for the real-time prediction of ship states and collision risks. The objective was to minimise safety and economic costs. Huang et al. [27] proposed a Softmax deep double deterministic strategy gradient multi-ship coordinated collision avoidance model, with an improved double-delay deep deterministic strategy gradient algorithm to address the issue of autonomous collision avoidance among multiple ships. Approaches based on heuristic algorithms consider the planning of collision avoidance behaviour as an optimisation problem and transform other dynamical equations and collision avoidance requirements, among other factors, into constraint relations or optimisation terms. Such approaches exhibit superior real-time performance, yet their optimisation problems are non-convex. The optimisation results are contingent upon the initial conditions, and the outcomes are inherently stochastic. And, there is a risk of violating the COLREGs regulations.

The VO algorithm was first proposed by Fiorini et al. [28] in 1998 for the collision avoidance planning of mobile robots, with the advantages of a simple principle and fast computation speed. In addition to evaluating the risk of collision, VO also provides collision avoidance methods, making it widely used in path planning and collision avoidance studies in MASS. He et al. [29] integrated VO and COLREGs with a comprehensive analysis of the ship and other obstacles to transform the actual collision avoidance problem into a convex optimisation problem. This approach provides real-time collision avoidance reference information for MASS. Zhao Guixiang et al. [30] proposed an enhanced VO method suitable for unmanned ships, addressing the shortcomings of lengthy collision avoidance routes, extended avoidance times, and the overlooking of avoidance responsibility in emergency situations when the conventional VO method is employed for local path planning. They developed a collision avoidance model for unmanned ships by incorporating the Quaternion’s ship domain into the calculation of the collision avoidance timing of VO. Xu et al. [31] devised an alternating local path planning method based on VO and an enhanced APF algorithm. By modifying the algorithm’s parameters, it is possible to achieve precise collision avoidance for both static and dynamic obstacles. Hong et al. [32] constructed a model of an obstacle-enclosed rectangle and an unmanned ship relative motion model. They then improved the VO to achieve unmanned ship path planning in complex environments. Zhu et al. [33] employed ellipses to represent safe distances from obstacles, overcoming the limitations of excessive constraints on VO and the inapplicability of representing obstacles as circles. Kuwata et al. [34] integrated COLREGs with VO for unmanned ship path planning. Zhang et al. [35] proposed a hybrid algorithm of APF and VO, which considered COLREGs with respect to the give-way ship clause constraints. Emil et al. [36] determined which side of an obstacle an unmanned ship passes from based on COLREGs and developed a VO collision avoidance algorithm based on the extended domain, whereby an extended domain was assigned to a dynamic obstacle. The velocity obstacle method is not well suited to deal with nonlinear motion and high dynamics, the presence of crossover phenomena in motion trajectories, or in dealing with velocity-independent obstacles. In order to address these limitations, the algorithms can be enhanced by combining, for instance, the dynamic window method and the potential-field-based method. CHO et al. [37] proposed an automatic collision avoidance algorithm based on the use of VO technology for ships that were in compliance with the COLREGs. This algorithm was applied to the case of a multi-ship rendezvous. In a study by LIU et al. [38], a speed-derived heading obstacle algorithm was proposed to satisfy COLREGs constraints based on VO. The determination of the obstacle extension domain in the VO method is more subjective and often does not take into account the size, speed, manoeuvrability, etc., of the vessel, which can lead to excessively long collision avoidance paths and times. In addition, VO methods based on COLREGs usually ignore the constraints of the duty to avoid close-quarters situations.

From the above studies on MASS autonomous collision avoidance, it can be seen that the current MASS autonomous collision avoidance algorithms do not fulfill the collision avoidance responsibilities required by the COLREGs well, and thus the collision avoidance schemes provided do not comply with the requirements of the COLREGs or the ordinary practice of seamen. Some researchers considered the constraints of the COLREGs and designed an autonomous collision avoidance problem based on the aforementioned constraints. Wang et al. proposed an enhanced APF algorithm integrating DCPA and TCPA in the repulsion field, which enhances the collision avoidance capability in the case of dynamic obstacles. However, the algorithm does not take into account the impact of wind and currents on the movement of the ship, which limits its applicability and generality [39]. Xu et al. and Kim et al., respectively, improved the DWA algorithm, which significantly improved the ability of the predicted trajectories to closely follow the extraction points of the global paths, resulting in a better match between the locally planned paths and the globally optimal routes, but the simulation environments were not constructed with the complexity of multi-ship encounters in mind [40,41]. Zhang et al. proposed a finite-time adaptive event-triggered control method with consideration of COLREGs. As their potential field function did not fully meet expectations, the steering method used only the direction of the resultant quantity and ignored the consideration of its magnitude [42]. Bayrak et al. devised an RRT-based local path planning algorithm compliant with COLREGs for ship encounters [43]. Although the above researchers took into account the constraints of COLREGs, the experimental simulations were poor, and the models and methods for solving multi-ship encounter situations remain challenging dilemmas. The NSGA-II algorithm, as a classical heuristic algorithm, has received considerable attention for its efficiency in solving complex optimisation problems. It is suitable for dealing with multivariate and multi-constrained collision avoidance path planning problems, and thus has a wide range of applications in MASS collision avoidance decision making [44,45,46]. However, the NSGA-II algorithm is susceptible to premature convergence and the formation of local optimal solutions, which constrains the applicability of the NSGA-II algorithm in practical MASS autonomous collision avoidance. To address this issue, this paper employs the concept of good point set theory to optimise the initial population selection of an NSGA-II algorithm. On this basis, an autonomous collision avoidance decision-making method for MASS based on the improved NSGA-II algorithm under COLREGs is proposed. The method fully considers the requirements of COLREGs with regard to ship manoeuvring and realises the autonomous collision avoidance of MASS under the constraints of COLREGs.

2. Collision Risk Assessment Modeling

The term ‘risk of collision’ refers to the intermediate state between safe navigation and a collision accident. It is one of the key standards used to assess the degree of collision risk between two ships. Article 7(1) of COLREGs stipulates that ‘Every vessel shall use all available means appropriate to the prevailing circumstances and conditions to determine if risk of collision exists. If there is any doubt such risk shall be deemed to exist’. It is crucial to evaluate the risks of a ship collision during the design phase of an MASS autonomous collision avoidance algorithm. Seafarers utilise a combination of Automatic Identification System (AIS), radar, and other equipment, as well as their own experience, to assess the risk of collision when two ships are encountered. This approach has been proven effective in the seafarer-led ship navigation mode. However, in the context of MASS autonomous collision avoidance, the absence of a seafarer’s observation and judgement means that the traditional method is no longer suitable for the needs of ship collision avoidance. A great deal of research has been conducted by scholars on the risk of collision. One common practice in this field is to measure the collision risk of a ship using the Collision Risk Index (CRI), which is shown in Equation (1).

$$\mathrm{C}\mathrm{R}\mathrm{I}=\{\mathrm{S},\mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A},\mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A},\mathrm{K},\mathrm{Q}\}$$

(1)

where distance to closest point of approach (DCPA) represents the distance between the two ships during the encounter, time of closest point of approach (TCPA) denotes the time at which the two ships reached the closest encounter point, S denotes the distance between the two ships, K represents the speed ratio between the two ships, and Q denotes the true bearing of the other ship relative to the present ship. The CRI methodology incorporates a wide range of variables for evaluating collision risk, in particular the parameters DCPA and TCPA, which are required by the COLREGs and adopted by seafarers as a matter of common practice. This integrated assessment method provides a more accurate reflection of the actual collision risk between ships and also offers a standarised quantitative index of collision risk. Such a system would facilitate the consistent application of assessment criteria to different vessels and navigational conditions, thereby reducing the potential for human error in judgement.

Due to the inherent ambiguity and uncertainty associated with CRI, the affiliation function is often employed when assessing the risk of collision between ships using DCPA and TCPA. This approach allows for a more comprehensive consideration of the safety of collision avoidance in different scenarios [47,48].

2.1. Distance between Two Vessels

The distance between two vessels is calculated according to the Equation (2).

$$\mathrm{S}=\sqrt{{({\mathrm{X}}_{\mathrm{A}}-{\mathrm{X}}_{\mathrm{B}})}^2+{({\mathrm{Y}}_{\mathrm{A}}-{\mathrm{Y}}_{\mathrm{B}})}^2}$$

(2)

where (X_A,Y_A), (X_B,Y_B) represent the position coordinates of the ship.

If there is a risk of collision, ships will take appropriate collision avoidance actions. The timing of collision avoidance actions is generally determined by the distance between the ships. In the event that a ship takes collision avoidance action, there is a designated action node, which is defined as the point at which the distance between the two ships is less than S₁. This is considered to be the point at which the ship is bound to collide. Similarly, there exists a safe distance, S₂, for ships in the process of rendezvous, i.e., there is no danger of collision between two ships when the distance between them is greater than S₂. The calculation of S₁ and S₂ is shown in Equations (3) and (4).

$${\mathrm{S}}_1=\left\{\begin{array}{ll}1.1-{\displaystyle \frac{\mathrm{Q}}{180°}}\times 0.2& 0°\le \mathrm{Q}\le 112.5°\\ 1.0-{\displaystyle \frac{270°-\mathrm{Q}}{180°}}\times 0.8& 112.5°\le \mathrm{Q}\le 247.5°\\ 1.1-{\displaystyle \frac{360°-\mathrm{Q}}{180°}}\times 0.4& 247.5°\le \mathrm{Q}\le 360°\end{array}\right.$$

(3)

$${\mathrm{S}}_2=2 \times {\mathrm{S}}_1$$

(4)

The ship distance affiliation function is employed to quantify the probability of a collision between two ships in the process of approaching each other. Through the ship distance affiliation function, the actual distance between the two ships can be converted into an affiliation value between 0 and 1, which indicates the degree of collision risk at a specific distance. This is demonstrated in Equation (5). The likelihood of collision is inversely proportional to the affiliation value, with a closer value indicating a higher likelihood and a further value indicating a lower likelihood.

$${\mu }_{\mathrm{S}}=\left\{\begin{array}{cc}1& \mathrm{S}\le {\mathrm{S}}_1\\ {({\displaystyle \frac{{\mathrm{S}}_2-\mathrm{S}}{\mathrm{S}-{\mathrm{S}}_1}})}^2& {\mathrm{S}}_1<\mathrm{S}\le {\mathrm{S}}_2\\ 0& \mathrm{S}>{\mathrm{S}}_2\end{array}\right.$$

(5)

2.2. DCPA and TCPA

The distance between the other ship and our ship during the encounter is referred to as DCPA, while TCPA represents the time required for the target ship to move from its current position to the nearest point of encounter. Both DCPA and TCPA have been widely used in nautical practice and the research of autonomous collision avoidance for ships [49,50,51]. In the context of nautical practice, the ship pilot acquires information regarding the movement of the ship in question and other ships in the vicinity through the use of navigational aids, such as AIS or radar. This information is then used to determine the potential for a collision between the ships in question, with the aim of steering clear of any such danger. During the navigation process of a ship, the DCPA and TCPA are employed to quantify the collision risk in both the spatial and temporal dimensions. If both DCPA and TCPA are below a specified threshold, it is deemed that there is a collision risk. In such instances, the ship must alter course or speed in order to avoid a potential collision, in accordance with COLREGs. V_t represents the speed of the approaching ship, V₀ indicates the speed of the ship, and V_r denotes the relative speed of the two vessels. Figure 1 illustrates the schematic diagram of DCPA.

Modern navigation systems frequently possess the capacity to automatically calculate and monitor TCPA and DCPA, effectively integrating existing technical systems and applying them to real-time navigation [52,53]. The information is then analysed to determine the potential for collision between the ships, and appropriate avoidance actions are implemented in response. DCPA and TCPA are employed to quantify the collision hazard in both the spatial and temporal dimensions, respectively, while the ship is underway. In the event that both the DCPA and TCPA fall below a specified threshold, it is deemed that a collision is imminent. In such a scenario, the ship should steer or change speed to avoid a collision in accordance with the principles of ‘early, large, wide and clear’ as outlined in the COLREGs.

The expressions for DCPA and TCPA affiliation functions are provided in Equations (6) and (7). The DCPA’s affiliation function is employed to convert DCPA values into collision risk, with a value between 0 and 1. When the DCPA value is minimal, the affiliation is proximate to 1, signifying a markedly elevated spatial collision risk. Conversely, when the DCPA value surpasses a predefined threshold, the affiliation diminishes to 0, indicating that the spatial dimension of the collision risk is negligible. The TCPA affiliation function is analogous to the DCPA affiliation function in that it is employed to assess collision risk in the time dimension.

$${\mu }_{\mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}}=\left\{\begin{array}{cc}1& \mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}\le {\mathrm{S}}_1\\ {\displaystyle \frac{1}{2}}-{\displaystyle \frac{1}{2}}\sin [{\displaystyle \frac{\pi }{{\mathrm{S}}_2-{\mathrm{S}}_1}}(\mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}-{\displaystyle \frac{{\mathrm{S}}_1+{\mathrm{S}}_2}{2}})]& {\mathrm{S}}_1<\mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}\le {\mathrm{S}}_2\\ 0& \mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}>{\mathrm{S}}_2\end{array}\right.$$

(6)

$${\mu }_{\mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A}}=\left\{\begin{array}{cc}1& \mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A}\le {\mathrm{t}}_1\\ {\displaystyle \frac{{\mathrm{t}}_2-\mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A}}{{\mathrm{t}}_2-{\mathrm{t}}_1}}& {\mathrm{t}}_1<\mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A}\le {\mathrm{t}}_2\\ 0& \mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A}>{\mathrm{t}}_2\end{array}\right.$$

(7)

where t₁ represents the latest opportunity for a ship to take collision avoidance action. This is defined as the time required for a ship to travel from a distance of S₁ to the nearest encounter point. The latest time for a ship to take collision avoidance action is used to characterise the collision risk of a ship in the time dimension, forming an imminent situation. t₂ is the time required for the ship to manoeuvre to the nearest encounter point, starting from the time when the two ships are at a distance of S_r (S_r ≥ S₂). The ship manoeuvre time is employed to quantify the probability that the two ships will have sufficient temporal separation to avoid a collision. If TCPA is greater than t₂, it is assumed that the two ships have sufficient time to perform adequate collision avoidance behaviours. The calculation of t₁ and t₂ is presented in Equations (8) and (9).

$${\mathrm{t}}_1=\left\{\begin{array}{cc}{\displaystyle \frac{\sqrt{{\mathrm{S}}_1^2-\mathrm{D}\mathrm{C}\mathrm{P}{\mathrm{A}}^2}}{{\mathrm{v}}_{\mathrm{r}}}}& \mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}\le {\mathrm{S}}_1\\ {\displaystyle \frac{\mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}-{\mathrm{S}}_1}{{\mathrm{v}}_{\mathrm{r}}}}& \mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}>{\mathrm{S}}_1\end{array}\right.$$

(8)

$${\mathrm{t}}_2={\displaystyle \frac{\sqrt{{\mathrm{S}}_{\mathrm{r}}^2-\mathrm{D}\mathrm{C}\mathrm{P}{\mathrm{A}}^2}}{{\mathrm{v}}_{\mathrm{r}}}}\hspace{1em}{\mathrm{S}}_{\mathrm{r}}\ge {\mathrm{S}}_2$$

(9)

2.3. Velocity Ratio of Two Ships K

The velocity ratio is defined as the ratio of the speeds of two ships. This parameter reflects the speed of the relative motion of the two ships, which is of great significance to the collision avoidance decision. The affiliation function of the speed ratio of the two vessels is used to evaluate the impact of collision risk based on relative speed. The calculation of the affiliation function of the ship speed ratio is shown in Equation (10).

$${\mu }_{{\mathrm{K}}_{\mathrm{i}}}=1/[1+({\displaystyle \raisebox{1ex}{$2$}\!\left/ \!\raisebox{-1ex}{${\mathrm{K}}_{\mathrm{i}}\sqrt{{\mathrm{K}}_{\mathrm{i}}^2+2{\mathrm{K}}_{\mathrm{i}}\sin \mathrm{C}+1}$}\right.})]$$

(10)

where $\sin \mathrm{C}=\left|\sin (\left|{\mathrm{C}}_{\mathrm{R}}-{\mathrm{C}}_0\right|)\right|$, ${\mathrm{C}}_{\mathrm{R}}$ and ${\mathrm{C}}_0$ are the heading of the vessel and the target vessel, respectively.

2.4. True Bearing Q

The true bearing describes the position of a ship relative to another ship and takes values from 0° to 360°. The affiliation function of the true bearing converts this true bearing, Q, into an affiliation value reflecting the degree of collision risk, which is between 0 (no risk) and 1 (maximum risk). This value is used to characterise the effect of the relative position between two ships on the collision risk. The literature [54] specifies the affiliation function of the true bearing Q. The calculation is shown in Equation (11), which is based on the results of this research.

$${\mu }_{{\mathrm{Q}}_{\mathrm{i}}}=[\cos ({\mathrm{Q}}_{\mathrm{i}}-19°)+\sqrt{440/289+{\cos }^2({\mathrm{Q}}_{\mathrm{i}}-19°)}]/2-{\displaystyle \frac{5}{17}}$$

(11)

2.5. Crash Hazard Evaluation Set

The varying influence of each factor on CRI necessitates the application of a weighting system to determine the value of CRI. The literature [47] has conducted a comprehensive analysis and calculation of these weights, and the resulting Equation (12) illustrates the calculation of CRI.

$$\mathrm{C}\mathrm{R}{\mathrm{I}}_{\mathrm{i}}=0.40{\mu }_{\mathrm{D}\mathrm{C}\mathrm{P}\mathrm{A}}+0.367{\mu }_{\mathrm{T}\mathrm{C}\mathrm{P}\mathrm{A}}+0.167{\mu }_{\mathrm{S}}+0.033{\mu }_{{\mathrm{K}}_{\mathrm{i}}}+0.033{\mu }_{{\mathrm{Q}}_{\mathrm{i}}}$$

(12)

The value of CRI is within the range of [0, 1], with the lower limit of the interval representing the absence of danger of collision, and the upper limit representing the inevitability of collision. Different CRI values represent varying degrees of collision danger, and the actions required by the ship are also different. See

Table 1. Collision risk evaluation set.

Collision Risk Evaluation Set	CRI
Very safe	0 ≤ CRI < 0.2
Safe.	0.2 ≤ CRI < 0.4
Normal.	0.4 ≤ CRI < 0.6
Dangerous.	0.6 ≤ CRI < 0.8
Very dangerous.	0.8 ≤ CRI ≤ 1

for details. When CRI ≤ 0.4, both ships are in the free action phase. When 0.4 ≤ CRI < 0.6, the vessel on the right should take action as soon as possible. When the collision danger reaches 0.6, the vessel on the right should take action immediately, as failure to do so may result in the vessel on the left taking action alone. When the collision danger reaches 0.8, the two vessels should take the action that is most helpful for collision avoidance, as shown in Table 1. The cross-encounter posture of two ships is used as an illustrative example in Figure 2, which depicts the ship’s actions under different collision hazards.

3. Constraints from COLREGs

3.1. Encounter Situation Classification

In accordance with COLREGs, the encounter situation between two ships can be classified into three categories: head-on, overtaking, and crossing situation. These categories are illustrated in Figure 3. The relevant provisions for ships in these encounter situations are outlined in

Table 2. Compliance rules and articles in various encounter situations according to the COLREGS.

Encounter Situation	The Relevant Provisions That Apply the Collision Avoidance Rules
Overtaking (Give-way vessel)	Chapter 2, Articles 6, 8, 13, 16, and 18; Chapter 3—Bugle Lights and Types; and Chapter 4—Acoustic and Light Signals.
Overtaking (Stand-on vessel)	Chapter 2, Articles 6, 8, 13, 17, and 18; Chapter 3—Bugle Lights and Types; and Chapter 4—Acoustic and Light Signals.
Head-on	Chapter 2, Articles 6, 8, 14, 16, and 18; Chapter 3—Bugle Lights and Types; and Chapter 4—Acoustic and Light Signals.
Crossing (Give-way vessel)	Chapter 2, Articles 6, 8, 15, 16, and 18; Chapter 3—Bugle Lights and Types; and Chapter 4—Acoustic and Light Signals.
Crossing (Stand-on vessel)	Chapter 2, Articles 6, 8, 15, 17, and 18; Chapter 3—Bugle Lights and Types; and Chapter 4—Acoustic and Light Signals.

.

In different encounter situations, ships should take appropriate collision avoidance actions.

1. Head-on: Two ships in the opposite or nearly opposite direction of the encounter, which constitutes a risk of collision, constitute the situation of the encounter. The opposite heading means that the difference between the bow direction of the two ships is 180°. A near-opposite heading usually means that the crossing angle of the two ships is approximately 6°. Once an encounter has been established, each vessel must turn to the right in order to pass on the port side of the other vessel, as required by the COLREGs. The combined effect of the actions taken by the two vessels will not necessarily result in the passage of the two vessels at a safe distance. Rather, each vessel must take an early and substantial right-hand turn, and the actions of each vessel will result in the passage of the two vessels at a safe distance.

2. Overtaking: In accordance with the COLREGs, a vessel is considered to be in the overtaking situation when it is catching up with another vessel from a direction greater than 22.5° directly behind the transverse of the other vessel. This occurs when the vessel in the overtaking situation is in such a position with respect to the vessel it is overtaking that, at night, it is only possible to see the tail light of the vessel in overrun, but not either of its port lights. In the event that two vessels have constituted an overtaking situation, the overtaking vessel is obliged by the COLREGs to yield to the vessel being overtaken. Furthermore, any subsequent change of bearing between the two vessels does not relieve the overtaking vessel of the duty to yield to the vessel being overtaken until it has finally sailed through to yield.

3. Crossing: This is defined as a bow-to-bow crossing of two vessels, i.e., a bow-to-bow crossing greater than 6° of broadside, but less than 112.5° of broadside. With regard to the distance at which a cross-encounter situation is deemed to commence, it is widely acknowledged that a cross-encounter situation commences when one vessel is able to visually discern the masthead light of the other vessel. In accordance with the requirements of COLREGs, when two vessels constitute a cross-encounter situation, the vessel on the port side shall give way to the vessel on the starboard side, which is the giving wayvessel. Conversely, when there is another vessel on the starboard side of the vessel, the vessel on the port side is the straight vessel, and the other vessel shall give way to the vessel.

3.2. Responsibilities for Collision Avoidance between Vessels

According to the various provisions of COLREGs, the responsibilities for collision avoidance between vessels can be categorized as follows:

1. Stand-on vessel responsibilities: A stand-on vessel should not impede the passage or safe transit of another vessel. According to Rule 17 of COLREGs, the stand-on vessel has different responsibilities and obligations at various stages, which include maintaining course and speed, taking independent manoeuvering actions when necessary, and performing actions that most effectively aid in collision avoidance.

2. Give-way vessel responsibilities: A give-way vessel should take early and substantial action to keep well clear of the other vessel. In addition to taking early, substantial, and clear actions, the give-way vessel must adhere to other COLREGs provisions. For instance, in a crossing situation, the give-way vessel should avoid crossing ahead of the stand-on vessel.

The constraints on the collision avoidance actions of MASS for the three cases of head-on, overtaking, and crossing are illustrated in Figure 4.

When two vessels are in a head-on situation, the relative speed is high, and the time available for judgment, consideration, and evasive action is limited. Consequently, COLREGs stipulate that each ship must turn to the right to pass port to port. Furthermore, each ship must make a substantial right turn at the earliest possible opportunity, with the objective of ensuring that the two ships pass at a safe distance from each other.

When two vessels are in a crossing situation, one ship shall give way to the other, and in order for the giving way ship to be able to assume the obligation to stand-on ship, she must be able to ascertain the position and dynamics of the stand-on ship, as well as whether or not it is stabilising at a certain speed in a certain direction.

When the two vessels are in an overtaking situation, the relative speed of the two ships is relatively low, the transfer is small, the time spent in parallel is considerable, and the probability of a collision is high. Consequently, when there is uncertainty as to whether or not overtaking is occurring, it is prudent to assume that overtaking is taking place. COLREGs stipulate that in the case of an overtaking situation, the obligation to give way continues until the ship has passed and it is clear. It is worth noting that an overtaking situation can easily be confused with a wide-angle crossing situation, and when there is doubt as to whether it constitutes an overtaking, it should be assumed that the ship is overtaking and appropriate action should be taken accordingly. While Regulation 13 of the COLREGs provides comprehensive guidance on the pursuit of ships, it does not explicitly delineate the side from which the pursuing ship is to be pursued. It is important to note that overtaking from the starboard side of the vessel being pursued, in particular from the vicinity of an azimuth of approximately 22°, is a risky manoeuvre. It is considered risky practice among seafarers to overtake a vessel from a position 5° aft of the right main transverse. Such a manoeuvre can easily be confused with a wide-angle cross-encounter, as defined in COLREGs Regulation 14. This can result in uncoordinated actions between the pursuing vessel and the vessel being pursued, increasing the risk of collision. In light of the aforementioned requirements pertaining to the common practice of seafarers, this paper imposes restrictive constraints on the actions of the pursuing vessel in an overrun situation. Specifically, it requires the pursuing vessel to overrun from the port side of the vessel being overrun, with the aim of enhancing the safety, reasonability, and reliability of the collision avoidance decision.

4. MASS Collision Avoidance Decision-Making Model Based on GPS-NSGA-II Algorithm

4.1. NSGA-II Algorithm

The non-dominated Sorting Genetic Algorithm II (NSGA-II) is a multi-objective optimisation algorithm developed by Kalyanmoy Deb et al. It is based on the traditional genetic algorithm framework and is specifically designed for solving problems with multiple conflicting objectives. Collision avoidance between ships necessitates the avoidance actions of two or more ships, which must consider both the potential for collisions between the ships and the constraints of the COLREGs when taking the avoidance actions. Consequently, this is a typical multi-objective optimisation problem. NSGA-II is more suitable for this kind of problem than traditional genetic algorithms, due to its high efficiency in dealing with multi-objective problems.

One of the advantages of NSGA-II is its rapid non-dominated sorting algorithm. The algorithm employs a Pareto dominance-based ranking mechanism to effectively manage the population structure of the set of collision avoidance schemes by ranking and stratifying all unknown collision avoidance schemes according to their non-dominated relations in the avoidance space. The NSGA-II algorithm classifies unknown collision avoidance schemes into dominated tiers according to the number of other collision avoidance schemes that they are dominated by. The collision avoidance schemes within each tier are not dominated by those in other tiers, thus ensuring the diversity and quality of the collision avoidance schemes. Pareto, the sorting mechanism works as follows:

In the context of a certain collision avoidance scheme X_i within the MASS collision avoidance process, whose objective function is (f_i1, f_i2), if another collision avoidance scheme X_j = (f_j1, f_j2) that satisfies the following conditions: {f_j1 ≤ f_i1,f_j2 ≤ f_i2} and {f_j < f_i1 or f_j2 < f_i2}, then X_i is said to dominate X_j (denoted as ${\mathrm{X}}_{\mathrm{j}}\prec {\mathrm{X}}_{\mathrm{i}}$). For the sake of argument, consider five avoidance schemes, A, B, C, D, and E. According to the definition of domination, there are two sets of domination relations, namely {(C A, B)} and {(D A, E)}, as illustrated in Figure 5. According to the Pareto ordering mechanism, points C and D are assigned to the ParetoLv.1 stratification because they have no dominated elements. The curve where the set of solutions of Lv.1 is located is called the Pareto frontier curve. There is no superiority or inferiority of the points on the Pareto frontier; rather, they are simply evaluated differently. The function value of f₁ for the C solution is the smallest, while the function value of f₂ for the C solution is the largest among all solutions under the same stratification. The curve representing the Pareto frontier is defined as the Pareto frontier curve. Consequently, the evaluation of avoidance solutions may vary according to the specific requirements.

Furthermore, NSGA-II employs an elite strategy to perpetuate the inheritance of superior individuals. This entails selecting the most effective avoidance schemes from the current set and the set of offspring schemes to form a new population. This process ensures the continued evolution of the algorithm, while maintaining the stability and excellence of the avoidance schemes.

In Figure 5, points C and D are not dominated by any solution, thus the number of dominated is 0, which is located in ParetoLv.1. Points B and E are dominated by points C and D, respectively, and the number of domination points is 1, which is located in ParetoLv.2. Point A is dominated by points C and D, and the number of domination points is 2, which is located in ParetoLv.3. In a similar encounter scenario, there are numerous collision avoidance strategies. When multiple targets must be considered simultaneously and the diversity of collision avoidance strategies is maintained, the NSGA-II algorithm is more adept at evaluating whether a collision avoidance strategy aligns with the ordinary practice of seamen from multiple perspectives rather than traditional genetic algorithms.

4.2. An Improved NSGA-II Algorithm Based on a Good Point Set

The outcome of NSGA-II is influenced by the initial population. If the initial population is randomly generated to solve the collision avoidance scheme, there may be a phenomenon of population aggregation, which may result in the selection of the collision avoidance scheme falling into the local optimum. This may prevent the identification of the optimal collision avoidance scheme by traversing the whole situation. Nevertheless, if the initial collision avoidance scheme is highly similar to the optimal collision avoidance scheme, not only can the convergence speed be enhanced, but the optimisation accuracy can also be improved, and the optimal collision avoidance scheme can be obtained in a shorter time under the condition of a certain number of iterations. As the position of the optimal collision avoidance scheme in the initial population is unknown when the NSGA-II is employed to identify the optimal collision avoidance scheme, a uniform distribution is employed to distribute the initial collision avoidance scheme of the population within the permissible range. This is completed to ensure that the first generation of collision avoidance scheme is as close to the optimal value as possible.

The good point set (GPS), proposed by Hua Luogeng et al. [55], is a method for selecting points in a multidimensional space that can be used to design a set of sampling point sets. The uniformity of the GPS allows for the initialisation of the population of NSGA-II, which can improve the diversity of the population and make the initial population more ergodic. This, in turn, can better achieve the purpose of a global optimality search.

The principle of the good point set is as follows: let G_s be the unit cube in the s-dimensional Euclidean space. If $\mathrm{r}\in {\mathrm{G}}_{\mathrm{s}}$, then the good point set can be expressed as Equation (13).

$${\mathrm{P}}_{\mathrm{n}}(\mathrm{k})=\{(\{{\mathrm{r}}_1^{(\mathrm{n})}\cdot \mathrm{k}\},\{{\mathrm{r}}_2^{(\mathrm{n})}\cdot \mathrm{k}\},\dots ,\{{\mathrm{r}}_{\mathrm{s}}^{(\mathrm{n})}\cdot \mathrm{k}\}),1\le \mathrm{k}\le \mathrm{n}\}$$

(13)

The deviation $\phi (\mathrm{n})$ in Equation (13) is such that $\phi (\mathrm{n})=\mathrm{C}(\mathrm{r},\epsilon ){\mathrm{n}}^{-1+\epsilon }$ is satisfied, where it is a constant related only to r and $\epsilon$ ($\epsilon$ is any positive number). In this case, ${\mathrm{P}}_{\mathrm{n}}(\mathrm{k})$ is said to be the set of good points, and r is the good point. $\{{\mathrm{r}}_{\mathrm{s}}^{(\mathrm{n})}\cdot \mathrm{k}\}$ represents the fractional part, and n represents the number of points, taking $\mathrm{r}=\{2\cos (2\pi \mathrm{k}/\mathrm{p}),1\le \mathrm{k}\le \mathrm{s}\}$ (p is the smallest prime number satisfying $(\mathrm{p}-3)/2\ge \mathrm{s}$). The mapping of this to the search space is illustrated by Equation (14).

$${\mathrm{x}}_{\mathrm{i}}(\mathrm{j})=({\mathrm{j}}_{\mathrm{u}\mathrm{b}}-{\mathrm{j}}_{1\mathrm{b}})\{{\mathrm{r}}_{\mathrm{j}}^{(\mathrm{i})}\cdot \mathrm{k}\}+{\mathrm{j}}_{1\mathrm{b}}$$

(14)

The location of the jth dimension is defined by the upper and lower bounds, denoted by j_ub and j_1b, respectively.

Figure 6 illustrates the initial population distribution of 250 populations generated using the good point set and random method within the range of [0, 1].

It can be observed from the figure that the distribution of populations generated using good point sets is relatively uniform in space, with a low probability of population aggregation. This advantage is not limited to two-dimensional space, it also applies to high-dimensional problems. The construction of the good point set has no relation to the number of dimensions. Mapping it to the target solution space can still result in a very uniform distribution. The corresponding algorithm performs more stably and always maintains a good diversity of the initial population, thus avoiding the phenomenon of precocity and ultimately converging to the global optimum.

The following steps are to be taken in order to optimise the NSGA-II population using the set of good points:

1. The parameter space must be determined and the range of values for each parameter specified;

2. An initial population must be created using the good point set generator. The dimensions of the problem and the required population size must be taken into account in order to generate the corresponding number of points;

3. The generated sequence of points must be mapped to the actual parameter space;

4. Utilise the mapped points as the initial population for the NSGA-II algorithm.

Following optimisation of the NSGA-II algorithm population using the good point set, the algorithm exhibits a reduction in the number of iterations and a more uniform distribution of solutions. This is beneficial for the algorithm to explore the solution space more extensively at an early stage, compared with a randomly generated population. The process of GPS-NSGA-II algorithm is illustrated in Figure 7.

4.3. Parameter Coding and Fitness Evaluation Function

4.3.1. Parameter Encoding and Iterative Approach

The selection of an appropriate coding method is a crucial aspect of the design of a mass collision avoidance scheme, as it directly impacts the efficacy of the system’s operation and the effectiveness. The most common coding methods include binary coding, real-valued coding, permutation coding, and tree coding. Real-valued coding is employed to encode the pertinent parameters within the MASS collision avoidance algorithm, as it facilitates the handling of constraints on complex decision variables and offers a greater advantage in terms of search efficiency.

1. The parameters of own ship and the target ship are as follows: The OS is recorded as the own ship, while the TS is recorded as the target ship. The attributes of the own ship are the ship’s position coordinates (X_os, Y_os), the own ship’s course Course_os, and the own ship’s speed Vos. The attributes of the target ship are (X_ts, Y_ts), Coursets, and V_ts.

2. With regard to the coding of the encounter situation, it should be noted that the ship designated as the ‘give-way’ ship will generate an avoidance space in advance. This space encompasses all the points that the ship is about to move to in order to avoid a collision. It is important to ensure that the setup of the avoidance space is not overly expansive, as this will have a detrimental impact on the iteration efficiency and increase the computation time. The polar coordinate system is employed to represent the entire space, with ${\rho }_{\mathrm{o}\mathrm{s}}$ designated as the angle of rotation of the polar axis with the north direction serving as the reference. r_os represents the polar radius, and the avoidance space can be expressed as $\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{e}=\{0\le {\rho }_{\mathrm{o}\mathrm{s}}\le 50,0.5\le {\mathrm{r}}_{\mathrm{o}\mathrm{s}}\le 1\}$. Each position point in the avoidance space represents a specific avoidance scheme.

Assuming that the coordinates of the ship are (X_next, Y_next), the speed of the ship in the collision avoidance process can be calculated by Equation (15).

$${\mathrm{V}}_{\mathrm{o}\mathrm{s}}={\displaystyle \frac{\sqrt{{({\mathrm{X}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{X}}_{\mathrm{o}\mathrm{s}})}^2+{({\mathrm{Y}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{Y}}_{\mathrm{o}\mathrm{s}})}^2}}{0.25/60}}$$

(15)

The course of the ship during navigation is shown in Equation (16).

$$\mathrm{C}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{s}{\mathrm{e}}_{\mathrm{o}\mathrm{s}}=\left\{\begin{array}{ll}{90}^{\circ }-\arctan ({\displaystyle \frac{{\mathrm{Y}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{Y}}_{\mathrm{o}\mathrm{s}}}{{\mathrm{X}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{X}}_{\mathrm{o}\mathrm{s}}}})& {\mathrm{X}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}>{\mathrm{X}}_{\mathrm{o}\mathrm{s}}\\ {270}^{\circ }-\arctan ({\displaystyle \frac{{\mathrm{Y}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{Y}}_{\mathrm{o}\mathrm{s}}}{{\mathrm{X}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{X}}_{\mathrm{o}\mathrm{s}}}})& {\mathrm{X}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}<{\mathrm{X}}_{\mathrm{o}\mathrm{s}}\end{array}\right.$$

(16)

Once the original population has been generated using the set of good points, it is necessary to map the population using a linear transformation. This is achieved by setting $(0\le {\rho }_{\mathrm{o}\mathrm{s}}\le 50)\to (0\le {\rho }_{\mathrm{o}\mathrm{s}}^{\prime }\le 1)$ and$(0.5\le {\mathrm{r}}_{\mathrm{o}\mathrm{s}}\le 1)\to (0\le {{\mathrm{r}}_{\mathrm{o}\mathrm{s}}}^{\prime }\le 1)$. The individuals of the population are coded as (X_a, X_b, Y_a, Y_b), where X_a represents the integer part of the X coordinate of the collision avoidance scheme, X_b represents the fractional part of the X coordinate of the collision avoidance scheme, Y_a represents the integer part of the Y coordinate of the collision avoidance scheme, and Y_b represents the fractional part of the Y coordinate of the collision avoidance scheme.

The initial stage of the iterative process is to select the sorted population, utilising a roulette wheel to identify the parents of the subsequent generation that is prepared for cross mutation. The advantage of employing a roulette for selection is that even individuals situated at the lower end of the sorting list still have the opportunity to be selected, thereby ensuring diversity of the population. The crossover method is selected as a single-point random crossover, which is the classical crossover method employed in genetic algorithms. This method randomly selects a point on the coding of the parent individuals as the crossover point, and then exchanges part of the genes of the two parent individuals at this point in order to generate two new offspring individuals. The single-point random crossover operation of real-valued coding can increase the genetic diversity of the population and effectively improve the search ability of the algorithm.

4.3.2. Adaptation Evaluation Function

The adaptation degree is the primary indicator of the efficacy of individual collision avoidance schemes. The superiority or inferiority of these schemes is determined by the magnitude of their adaptation degree. The fitness function serves as the criterion for distinguishing between optimal and suboptimal individual collision avoidance schemes among all collision avoidance schemes. Therefore, the selection of an appropriate fitness function is crucial for achieving optimal global optimisation performance of the autonomous collision avoidance algorithm. Inadequate selection of the fitness function may result in the identification of a local optimal collision avoidance scheme rather than a global optimal solution. In this paper, we determine the fitness function from two perspectives: the ship collision risk change function $\Delta \mathrm{C}\mathrm{R}\mathrm{I}$ and the path optimisation cost function (POCF), which considers the steering angle of the ship and the sailing distance. The CRI formula is presented in Equation (17), and the POCF calculation is shown in Equation (18).

$$\Delta \mathrm{C}\mathrm{R}\mathrm{I}=\mathrm{C}\mathrm{R}{\mathrm{I}}_{\mathrm{j}}-\mathrm{C}\mathrm{R}{\mathrm{I}}_{\mathrm{i}}$$

(17)

$$\mathrm{P}\mathrm{O}\mathrm{C}\mathrm{F}={\rho }_{\mathrm{o}\mathrm{s}}+\sqrt{{({\mathrm{X}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{X}}_{\mathrm{o}\mathrm{s}})}^2+{({\mathrm{Y}}_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}-{\mathrm{Y}}_{\mathrm{o}\mathrm{s}})}^2}$$

(18)

where CRI_i represents the collision risk between the two ships in the absence of collision avoidance measures. The relevant calculation is based on Equation (12), while CRI_j denotes the collision risk between the two ships following the implementation of collision avoidance measures. The difference in collision risk before and after the collision avoidance measures are employed serves to indicate the impact of the aforementioned measures. If the value is negative, it indicates that the collision risk between the ships after taking collision avoidance action has decreased, thereby demonstrating the effectiveness of the collision avoidance action taken.

In Equation (18), (X_os, Y_os) and (X_next, Y_next) represent the position of the ship prior to the collision avoidance action and the position of the ship following the completion of the collision avoidance action, respectively. The parameter ${\rho }_{\mathrm{o}\mathrm{s}}$ denotes the change in heading direction relative to the ship’s heading direction, with the latter serving as the reference. The schematic of the parameter is illustrated in Figure 8.

The rationale behind the adoption of $\Delta \mathrm{C}\mathrm{R}\mathrm{I}$ and POCF as the adaptation evaluation functions in the GPS-NSGA-II algorithm is that these two objective functions consider both the safety and the manoeuvring cost of the collision avoidance scheme. Under the constraint of the two objective functions, the position point with the smallest value in the position set of the Pareto front is selected as the moving point of the ship, which represents the optimal solution in all the collision avoidance position sets.

4.4. Autonomous Collision Avoidance Decision Making for MASS under COLREGs

The autonomous collision avoidance decision-making process of MASS based on the GPS-NSGA-II algorithm under COLREGs is shown in Figure 9. This process is divided into three parts: data processing, constraint from COLREGs, and the algorithm controller. The operation of this collision avoidance decision is contingent upon the satisfaction of three conditions:

1. The sea conditions were favourable with good visibility;

2. The navigable waters are sufficiently wide for MASS to take collision avoidance action when a collision hazard exists;

3. The MASS responds in a timely manner, and the stand-on vessels take action in accordance with Article 17 of the COLREGs.

In accordance with Section 3.2, the principal responsibility and obligation of the stand-on vessel is to maintain course and speed. Consequently, when the stand-on vessel is required to take action, it can be inferred that the give-way vessel has not complied with the COLREGs. One of the preconditions of the COLREGs-based MASS collision avoidance model proposed in this paper is that “The MASS responds in a timely manner, and the stand-on vessels take action in accordance with the Article 17 of COLREGs.” Therefore, the situation requiring action by the stand-on vessel does not align with the experimental configuration. Consequently, in the experiment, the stand-on vessel only bears the responsibility and obligation to maintain direction and speed.

The following steps are to be taken in order to implement MASS autonomous collision avoidance decision making under COLREGs constraints:

Step 1: Obtain the ship’s navigational data through radar, AIS, and other navigational aids, including the ship’s initial position, relative distance, speed, relative bearing, heading, and other relevant data.

Step 2: The data obtained are used to calculate the parameter, including TCPA, DCPA, and the collision risk. The initial evaluation of the collision risk is conducted, and a decision is made as to whether the ship will take collision avoidance action according to the collision risk. If there is no risk of collision between the two ships, then no collision avoidance action is required, and the own ship will maintain its course and speed.

Step 3: Determine whether the ship has reached the predefined threshold for initiating collision avoidance measures. In accordance with the ordinary practices of seamen, in open water, the threshold for initiating collision avoidance action is typically deemed to have been reached if the conditions set out in {DCPA < 1 n mile, TCPA < 12 min} are met.

Step 4: If the threshold for taking action is reached, an analysis of the encounter situation between the own ship and the ship with the highest risk of collision must be conducted. The own ship’s obligations, with regard to avoidance in different encounter situations, are delineated in accordance with the COLREGs.

Step 5: In the event that the own ship is required to steer in order to avoid a collision, the steering avoidance space must be set in accordance with the avoidance responsibilities specified in the COLREGs. If, however, the own ship is not required to steer in order to avoid a collision, it is the responsibility of the own ship to keep her course and speed.

Step 6: Code the collision avoidance space.

Step 7: Generate the collision avoidance scheme set using the good point set theory within the collision avoidance scheme space.

Step 8: Initiate the algorithm controller to call upon the GPS-NSGA-II collision avoidance decision-making algorithm to select the optimal collision avoidance scheme.

Step 9: Collision avoidance scheme legitimacy check to ascertain whether the given scheme complies with the COLREGs.

Step 10: Repeat steps 1–9 until the ship has successfully passed and cleared all the target ships.

Step 11: Upon completion of the aforementioned collision avoidance scheme, the own ship is permitted to resume its scheduled route.

In the third step, we qualify the values of the DPCA and the TCPA. The DCPA and TCPA are the two most significant and frequently utilised indicators for the assessment of potential collision risks between two ships. The dimensions of the vessel, its location in the waterway, and the circumstances of its proximity to other maritime crafts all contribute to the values of DCPA and TCPA. Therefore, relevant international conventions, such as IMO and COLREGs, do not give a quantitative index for the values of DCPA and TCPA. In accordance with the customary procedures observed by maritime professionals in open waters, when the DCPA between two ships exceeds one nautical mile and the TCPA exceeds 12 min, collision avoidance measures may be temporarily discontinued. Consequently, the evaluation of whether the DCPA is less than 1 nautical mile and the TCPA is less than 12 min serves as an effective criterion for measuring the collision risk of ships in both spatial and temporal dimensions, which is also consistent with the standards set by the customary practices of seafarers.

5. Simulation Experiment and Result Analysis

5.1. Simulation Test Scenarios

In order to assess the efficacy of the MASS autonomous collision avoidance decision-making model proposed in this paper, three representative test scenarios in two-ship encounters, cross-situation, crossing situation, and overtaking situation have been devised. Additionally, in order to evaluate the efficacy of the autonomous collision avoidance decision-making model in multiple-ship encounters, a scenario of autonomous collision avoidance in three-ship encounters has been constructed. The initial state parameters of the ships and target ships are presented in

Table 3. Parameter table of the initial state of the ship.

Scenario	Ship	Initial Position	Course (°)	Speed (knots)	Encounter Situation
1	OS	(3.5, 1)	0	10	Head-on situation
	TS	(3.5, 6)	180	10
2	OS	(3.5, 1)	0	10	Crossing situation
	TS	(7.5, 5)	270	10
3	OS	(3, 1.5)	0	20	Overtaking situation
	TS	(3, 3)	0	10
4	OS	(4, 2)	0	10	Multi-ship situation
	TS1	(8, 8)	243	11
	TS2	(12, 6)	270	12

.

The test scenario is set in open water with good visibility. All ships comply with the COLREGs. The stand-on ships keep her course and speed. The give-way ships take avoidance actions as early as possible. The ship operation process does not take into account the change of speed. The ships resume their original route after avoidance is completed and then carry out the next avoidance operation according to the risk of collision.

5.2. Collision Avoidance Actions in a Head-On Situation

Figure 10 presents a schematic diagram of the posture of the two ships at the critical node in the head-on situation. The blue line indicates the trajectory of the own ship, while the orange line indicates the trajectory of the target ship. Figure 10a depicts the initial position of the two ships, demonstrating that there is no imminent danger of collision. However, should the two ships continue to adhere to their original sailing plan, the distance between them will gradually diminish, eventually leading to a pair encounter situation until a collision accident occurs. Upon reaching the (3.5, 1.5) coordinate position, the own ship encounters the target ship at the (3.5, 5.5) coordinate position, thereby forming a head-on situation. At this juncture, the DCPA and TCPA of the two ships reach the threshold of taking avoidance action, as depicted in Figure 10b.

In accordance with COLREGs Article 14, each of the two ships turns to the right. Once the two ships have initiated collision avoidance manoeuvers, the own ship successfully avoids the target ship at t = 675 s. At this point, the distance between the two ships is 1.39 n mile, as shown in Figure 10c. Subsequently, the efficacy of the avoidance action is validated, and the original route is resumed in accordance with the requirements of the COLREGs, as shown in Figure 10d.

The alterations in the distance between the vessels and the DCPA throughout the collision avoidance procedure between the two vessels in a head-on configuration are depicted in Figure 11.

5.3. Collision Avoidance Actions in Crossing Situation

Figure 12 presents a schematic diagram of the posture of the two ships at the critical node in the crossing situation. The blue line indicates the trajectory of the ship, while the orange line indicates the trajectory of the target ship. Figure 12a depicts the initial position of the two ships, demonstrating that there is no imminent danger of collision. However, if the two ships continue to navigate according to their original plan, as the distance between them decreases, a crossing situation will arise until a collision accident occurs. Upon reaching (3.5, 3) and (5.5, 5), respectively, the ships encounter each other in a crossing situation. At this juncture, the DCPA and TCPA of the two ships reach the threshold for taking avoidance action, as depicted in Figure 12b. In accordance with COLREGs Article 15, the own ship will alter course to the right. Once the ship has initiated collision avoidance action, at t = 1080 s, the own ship has successfully avoided the target ship, with a distance of 0.81 n mile between the two ships, as shown in Figure 12c. Thereafter, the avoidance action is verified and the original route is resumed in accordance with the COLREGs, as shown in Figure 12d. The change in distance between the two ships and the change in DCPA during the collision avoidance process between the two ships in a crossing situation is illustrated in Figure 13.

5.4. Collision Avoidance Actions in Overtaking Situation

Figure 14 presents a schematic diagram of the posture of the two ships at the critical node in overtaking situation. The blue line indicates the trajectory of own ship, while the orange line indicates the trajectory of the target ship. Figure 14a depicts the initial position of the two ships, wherein there is no danger of collision. However, should the two ships continue to navigate according to their original plan, as the distance between them decreases, an overtaking situation will be constituted, which may culminate in a collision. Upon the own ship reaching (3, 2.5) and the target ship reaching (3, 3.5), an overtaking situation is formed. At this juncture, the DCPA and TCPA of the two ships reach the threshold of taking avoidance action, as depicted in Figure 14b. In accordance with COLREGs Article 13, the ship initiates a turn to avoid collision. Following the implementation of collision avoidance actions, the own ship successfully avoids the target ship at t = 255 s, with a distance of 0.89 n mile between the two ships, as illustrated in Figure 14c. Thereafter, the efficacy of the avoidance action is validated and the original route is resumed in accordance with the COLREGs, as depicted in Figure 14d. The alterations in the distance between the ships and the DCPA during the collision avoidance process between the two ships in the overtaking situation are illustrated in Figure 15.

5.5. Collision Avoidance Actions in a Multi-Ship Situation

In the experiment of a multi-ship encounter, the objective of our algorithmic design is to address the issue of collision avoidance between the own ship and other target ships. The potential for collision avoidance between target ships is not within the scope of this investigation. As the number of target ships increases, it is inevitable that the issue of collision avoidance between target ships will arise, which falls beyond the remit of this paper. Furthermore, when the number of target ships is excessive, some ships will deviate from the COLREGs when taking action. The collision avoidance actions taken by these ships are unpredictable, which renders the constraints of the COLREGs ineffective. Accordingly, the objective of the three-ship encounter scenario presented in this paper is to ensure that all vessels adhere to the COLREGs guidelines for collision avoidance, thereby preventing any deviation from these regulations. In subsequent research, we will direct our attention to the issue of vessels failing to comply with the COLREGs in their collision avoidance manoeuvers. Finally, in the conclusion of this paper, we will present this issue as a potential avenue for future research.

In the multi-ship encounter experiment, the blue line represents the trajectory of the own ship, the orange line indicates the trajectory of target_ship1, and the green line indicates the trajectory of target_ship2, as shown in Figure 16a. The own ship first forms a collision risk with target_ship1, and the two ships will collide if they continue to follow the original route. Upon reaching (4, 4), target ship No. 1 proceeded to (6, 7), at which point the DCPA and TCPA of the two ships reached the threshold for avoidance action. This resulted in the formation of a crossing situation, in accordance with the requirements of the COLREGs. The own ship was required to alter course to starboard, while target_ship1 was instructed to keep her course and speed. As illustrated in Figure 16b, at t = 870 s, the own ship successfully avoided target_ship1, and at this time, the distance between the two ships was 2.63 n mile. The own ship continues sailing and has a risk of collision with target_ship2. At this time, the two ships form a crossing situation. In accordance with the requirements of the COLREGs, the own ship will alter its course to starboard, as shown in Figure 16c. At t = 1365s, own ship successfully avoids target_ship2 at a distance of 1.28 nm. Once the collision avoidance procedure has been completed, own ship will gradually turn and resume its original route, as illustrated in Figure 16d. The statistics of DCPA parameters between the own ship and the target ships during the collision avoidance in the multi-ship situation are presented in Figure 17.

6. Conclusions

The completion of the collision avoidance decision by the ship’s autonomy system places significant demands on the effectiveness and reliability of the decision-making process. This paper takes the autonomous collision avoidance of MASS as its research object. The responsibility for avoiding collisions between ships is determined in accordance with the COLREGs, and an evaluation function for the adaptability of MASS autonomous collision avoidance is constructed based on the collision risk of ships (CRI) and the economic cost function (POCF) of collision avoidance actions. On this basis, a MASS autonomous collision avoidance decision algorithm (GPS-NSGA-II) is proposed for MASS autonomous collision avoidance, which incorporates a good point set improvement NSGA-II under COLREGs constraints. The MASS automatic collision avoidance decision-making model, as proposed in this paper, offers the following advantages: Firstly, the MASS fully considers the constraints of the COLREGs in the autonomous collision avoidance process, taking actions in strict accordance with the requirements of the COLREGs. Consequently, the autonomous collision avoidance scheme of the MASS satisfies the requirements of the COLREGs. Secondly, the MASS collision avoidance scheme is designed to consider both the collision risk between ships and the path cost of the avoidance scheme. This ensures that the autonomous collision avoidance scheme of MASS aligns with the actual collision avoidance manoeuvres of the ships. The simulation experiments conducted in a variety of scenarios demonstrate that the MASS autonomous collision avoidance decision-making model proposed in this paper is an effective solution to the autonomous collision avoidance problem of MASS in open water, with significant practical value. However, the MASS autonomous collision avoidance decision-making model proposed in this paper does not consider the possibility of MASS deviating from the COLREGs, nor is it applicable to the autonomous collision avoidance of MASS in complex waters with spatial limitations. Further research is required to better meet the needs of MASS autonomous collision avoidance in different waters.