Ship Manoeuvrability-Based Simulation for Ship Navigation in Collision Situations

Abstract

In this article, a ship manoeuvrability-based simulation for ship navigation in collision situations is established. Under the general requirement from the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) and good seamanship, the determination of encounter situations is quantified to reduce navigators’ intervention. Meanwhile, the action manner by course alteration or changing speed in some typical encounter situations is graphically analysed for both the give-way and stand-on vessels. Then, the multiple genetic algorithm and linear extension algorithm are adopted to perform trajectory planning for collision avoidance. To improve the reliability of the simulation system, the mathematical model of ship motion and ship manoeuvring control mechanism are adopted, which can eliminate the insufficiency of neglect of ship manoeuvrability in the process of collision avoidance. Meanwhile, the course encoding technique is adopted to fit the ship manoeuvring control mechanism. Finally, a set of traffic scenarios emulating different encounter situations are applied to demonstrate the effectiveness, consistency, and practicality of this system.

1. Introduction

With the recent growing interest in the ocean for civilian and military applications, there has been increasing demand for the autonomy of unmanned surface vehicles (USVs). For example, in 2005, e-navigation was an initiative started by the International Maritime Origination (IMO) to increase navigation safety by using modern technology. In 2012, the European Union invested in the Maritime Unmanned Navigation through Intelligence in Networks (MUNIN) project to develop an autonomous dry bulk carrier. In 2015, the Finnish Funding Agency approved the academic research project—Advanced Autonomous Waterborne Applications (AAWA). In 2016, Rolls-Royce published their plan for the construction of autonomous ships. In 2018, the IMO published the degree level on Maritime Autonomous Surface Ship (MASS). Through years of progress, many decision support systems have achieved significant results [1,2,3,4,5,6,7,8,9,10]. For example, Szlapczynski [6] presented the evolutionary sets of safe trajectories (ESoSST) to obtain a set of trajectories of all the ships instead of just one ship; Tam [7] determined priority based on the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) [11] and ship manoeuvrability, standardized the evasive turning angle for all vessels to 30°, and then determined the linear extension after the evasive manoeuvre; Tsou [8] integrated a geographic information system (GIS) module to conduct obstacle avoidance processing and selection of a route; Sun [12] established a collision avoidance system based on finite control set model predictive control (FCS-MPC); and Lv [13] adopted a modified Artificial Potential Field (APF) to realize real-time and deterministic path planning. Among these results, the simulation for ship navigation could be a powerful tool for operational planning and design studies of waterways [14]. The key technology is to determine the encounter situation and perform autonomous trajectory finding in collision situations with no or minimum intervention of navigators.

Nevertheless, the above-mentioned decision support systems lay emphasis on trajectory optimization, thus the encounter situation is usually a prior assumption in the simulation based on Rules 13–15 of COLREGs. In fact, the determination of an encounter situation, which classifies the avoidance responsibility and confirms the action time horizon, is an important precondition for trajectory optimization. To improve the autonomy of this simulation system, the qualitative provisions are materialized with the quantified criteria including collision risk verification, crossing angle bearing orientation, and applicable distance. The concept of risk of collision interpreted in Rule 7 is an important condition. In practice, the distance of the closest point of approach (DCPA) and the time of the closest point of approach (TCPA) for the two approaching vessels are the most important factors in determining whether the risk of collision exists [15]. Considering the visible range of lights defined in Rule 22 and navigational practice, the applicable distance at which an encounter situation applies is analysed. More importantly, to ensure evasive action compliance with navigational practice and reduce the doubt about the evasive manoeuvre especially in encounters between ships with this automatic simulation system and ships without this system, the action manners, including course alteration and changing speed for different encounter situations, are analysed based on COLREGs, good seamanship, and the cost of avoidance.

The optimization methods for trajectory planning have been previously reviewed and discussed [16]. In general, the methods can be divided into two groups, the deterministic approach and the heuristic approach. The former calculates and determines the final decision in strict accordance with the defined process characterized by a low dimensional state space (typically up to two dimensions); the latter is to search inside a subspace of the search space for an acceptable solution rather than the best solution that satisfies the design requirement. Nevertheless, each approach has its limitations. For the deterministic approach, it is constrained by the optimization ability to only deal with a single variable. Therefore, it usually applies a distributed computing method to calculate the optimal trajectory with a prior assumption of other relevant parameters. Moreover, the obtained optimal trajectory just returned to the original course rather than the original track, whereas, in practice, the give-way ship should return to the original track as much as possible once the risk of collision is cleared. For the heuristic approach, trajectory planning is required to generate a sequence of actions from a start position to the original track. Considering the presence of random variables in large quantities in the process of optimization, the evasive manoeuvre usually covers many times of course alteration, so the consistency of the optimal solution cannot be guaranteed, which is not compliant with navigational practice. In addition, with the heuristic approach it is easy to trap in the trouble of premature convergence.

It is remarkable that there is one common shortage in the above-mentioned research, most of the published methods are characterized by an idealised mathematical model of ship motion without considering ship manoeuvrability in the process of trajectory planning. Generally speaking, ship manoeuvrability weighs the response capability when a ship is handled by an operator or interfered with by an external environment [17]. Therefore, ship manoeuvrability is a major and important issue for the simulation of ship navigation, especially in collision situations when a series of actions are taken.

Motivated by the mentioned observations, a ship manoeuvrability-based simulation for ship navigation in collision situations is presented in this paper. Under the general requirements of COLREGs and good seamanship, the determination of an encounter situation is quantified to reduce the intervention of navigators. Meanwhile, the action manner by course alteration or changing speed in some typical encounter situations is graphically analysed for both give-way and stand-on vessels. For the manner of course alteration, the authors have recently reported a trajectory planning module using the modified genetic algorithm to improve the optimization performance [18]. For the manner of changing speed, a linear extension algorithm is adopted to ensure the safe trajectory is found. More importantly, the dynamic property of a ship during altering course or changing speed is considered to eliminate the insufficiency consideration of ship manoeuvrability in the process of collision avoidance. The course encoding technique is adopted to fit the control mechanism of ship manoeuvring into the algorithm.

The paper is organized as follows. Section 1 introduces the development of ship trajectory planning as well as the motivation behind the study. Section 2 describes the dynamic simulation system for ship navigation, including the quantification for the encounter situation, the analysis for the action manner, as well as the trajectory planning model. Section 3 illustrates the simulation results of different traffic scenarios with a discussion and performance analysis. Section 4 concludes the paper and discusses future work.

2. Dynamic Ship Collision-Avoidance System

2.1. The Analysis of Encounter Situation

The encounter situation is a major and indispensable issue for collision avoidance since the obligation for the two parties takes effect when satisfying the requirements of the specific encounter situation [19]. However, there are different interpretations of the term ‘encounter situation’, though the exact definition is given in the COLREGs. For example, the applicable distance for which the various stages begin to apply varies considerably.

Currently, there are still no specialized reports on encounter situations except in research on the autonomy of ships. For example, the encounter situation is further divided into six types (crossing from the port/right side, overtaking, overtaken, head-on, and target ship with no speed) for the expert system [20]. Based on a survey of the navigators’ perception of the encounter situation, the boundary line for the three encounter situations is obtained by applying the method of fuzzy statistics [21]. Considering the determination of encounters by a single factor, the combined factors, including relative bearing, crossing angle, and speed, are applied to further divide the crossing situation into a large/small angle port/right side encounter [22]. Considering the consistency of the collision-avoidance actions, the recommended distinguishable relative bearing angles between head-on and crossing situations is enlarged [23].

In this article, the following principles for the division of encounter situations should be considered.

(1)

The division is based on the COLREGs, the navigator’s practical practice, and good seamanship.

(2)

All types of encounter situations are completely divided, and every encounter that needs to take collision avoidance actions can find corresponding encounter situations to guide collision avoidance behaviour.

(3)

The quantitative judgement results for each encounter situation should be unique.

(4)

Full accounts should be taken of the incompatibility between the two ships in their understanding and action of the situation.

2.1.1. The Quantified Criteria of Encounter Situations

Some assumptions are made to perform the determination of encounter situations. The ship domain is treated as circle, and the collision risk borrows the concept of ship domain by comparing the distance to the closest point of approach (DCPA) with the radius of ship domain D_s, whose radius is a statistical result in the open sea [24]. The applicable distance for a specific encounter situation is based on the visibility of lights for ships with lengths larger than 50 m.

First, the orientation division of the target ship (TS) is illustrated in Figure 1. The orientation division of the TS is categorized into six regions (P₁, P₂, P₃, P₄, P₅, and P₆). The corresponding values of the bearing lines taken clockwise are [π/8, π/2, 5π/8, 11π/8, 3π/2, and 15π/8], respectively, and are mainly based on the provision of the light’s arc of horizon defined in the COLREGs. The description of every possible encounter situation is listed in

Table 1. Abbreviations and brief descriptions of the encounter types.

Abbreviations	Description
HO	Head-on encounter when OS and TS give way simultaneously
OT1	OS is overtaken by TS when TS gives way
OT2	TS is overtaken by OS when OS gives way
CR1	Crossing encounter when TS gives way
CR2	Crossing encounter when OS gives way
SF	Safe encounter

. In terms of legal status, only one ship needs to perform the evasive manoeuvre in a crossing situation, while both ships must perform evasive manoeuvres in a head-on situation according to Rule 14(c), ‘when a vessel is in any doubt as to whether such a situation exists she shall assume that it does exist and act accordingly’, the head-on section values (angles of π/8 radians) are larger than those recommended. Therefore, the enlarged section P₁ reduces the sensitivity upon small changes in the own ship’s (OS) heading when changing HO to either GW or SO. To reduce the complexity of the procedure, the quantified criteria for specific encounter situations are clearly described in

Table 2. The quantified criteria for specific encounter situations.

Region	HO	CR1	CR2	OT1	OT2
P1 θT∈ [0, π/8] ∪ [15π/8,2π]	CT∈ [7π/8, 9π8] Ds ≤ DCPA R ≤ 6 n mile	CT∈ [3π/8,7π8] Ds ≤ DCPA R ≤ 6 n mile	CT∈ [9π/8,13π/8] Ds ≤ DCPA R ≤6 n mile	---	CT∈ [0,3π/8] ∪ [15π/8,2π] Ds ≤ DCPA R ≤ 3 n mile
P2 θT∈ [π/8,π/2]	-----	-----	CT∈ [π,2π] θO < 11/8π Ds ≤ DCPA R ≤ 6 n mile	---	CT∈ [π,2π] θO < 11/8π Ds ≤ DCPA R ≤ 3 n mile
P3 θT∈[π/2,5π/8]	---	---	CT∈ [3π/2,2π] Ds ≤ DCPA R ≤ 6 n mile	---	---
P4 θT∈ [5π/8,11π/8]	---	---	---	CT∈ [0,2π] ∪ [3π2,2π] Ds ≤ DCPA R ≤ 3 n mile	---
P5 θT∈[11π/8,3π/2]		CT∈ [0, π/2] Ds ≤ DCPA R≤6n mile
P6 θT∈[3π/2,15π/8]		CT∈ [0, π] θO < 5/8π Ds ≤ DCPA R ≤ 6 n mile			CT∈ [0, π] θO > 5/8π Ds ≤ DCPA R ≤ 3 n mile

Safe encounter (SF) is not described in the table, as this encounter shares the same characteristic in which the parties move away from each other; $C_{\mathrm{T}}$ is the heading crossing angle for TS with respect to OS; θ_O indicates OS’s relative bearing with respect to TS; θ_T is TS’s relative bearing with respect to OS; R is the distance between OS and TS; D_s is the radius of the ship domain.

, and are based on the COLREGs, navigational practices, and good seamanship. The quantified criteria are established from the aspects of crossing angle, relative bearing, collision risk, and applicable distance for different encounters.

2.1.2. The Action Manner

To ensure that the evasive action complies with navigational practice. The action manner is mainly analysed based on COLREGs, good seamanship, and the cost of avoidance. The results are presented in Figure 2, Figure 3 and Figure 4. For a head-on situation, the action manner is an alteration of course to starboard regardless of a port-to-port encounter or a right-to-right encounter. For a crossing situation, usually a give-way vessel may keep clear of the other in the following ways: (1) For a small angle crossing angle, by altering course to right to cross stern of the give-way vessel; (2) for a right angle crossing situation, either by reducing speed or altering course to right to make other vessel cross ahead; (3) for a large angle crossing situation, by reducing speed to make the other vessel cross ahead. For an overtaking situation, the action manner is based on the bearing angle and the DCPA symbol (Zheng, 2000). (1) If DCPA > 0 and θ_T∈ [7π/6, 11π/8], the overtaking vessel alters course to starboard; (2) if DCPA ≤ 0 and θ_T∈ [7π/6, 11π/8] or the two ships heading in parallel, the overtaking vessel alters course to port; (3) if DCPA < 0 and θ_T∈ [5π/8, 7π/6], the overtaking vessel alters course to port; (4) if DCPA ≥ 0 and θ_T∈ [5π/8, 7π/6] or the two ships are heading in parallel, the overtaking vessel alters course to starboard.

2.2. Ship Manoeuvrability Model

Accurate and reliable simulation system for ship navigation requires precise knowledge of the manoeuvring behaviour of the ship no matter whether taking the manner of course alteration or speed reduction. In order to represent a manoeuvring ship fully in space, a mathematical model with six degrees of freedom is required. To simplify the problem, it is assumed that the steering of a ship can be regarded as a rigid body motion on the horizontal plane, as is customary.

2.2.1. The Manoeuvre of Course Alteration

The transfer function of a ship as a course control object can be defined in a simplified form as a first-order Nomoto model. The relationship between the rudder angle δ and the ship’s heading angle ϕ is expressed as follows [25]:

$$\stackrel{‥}{\varphi }+\frac{1}{T}H(\stackrel{·}{\varphi })=\frac{K}{T}\delta$$

(1)

where K is the steering quality index, and T is the steering quality time constant.

The nonlinear function of $H(\stackrel{·}{\varphi })$ with respect to $\stackrel{·}{\varphi }$ can be approximately represented by:

$$H(\stackrel{·}{\varphi })=a_1\stackrel{·}{\varphi }+a_2\stackrel{‥}{\varphi }+a_3\stackrel{\dots }{\varphi }+\cdots$$

(2)

where a_i (i = 1, 2, 3, …) is the nonlinear constant coefficients.

The velocity of the ship’s manoeuvring function can be expressed as follows [26]:

$$\stackrel{·}{V}+a_{vv}{V}^2+a_{rr}{\stackrel{·}{\varphi }}^2+a_{\delta \delta }{V}^2{\delta }^2=a_{nn}{n_D}^2+a_{nv}{n}_{D}V$$

(3)

where $n_D$ is the rational speed of the main engine, V is the velocity, a_nn and a_nv are the propulsive coefficients, and a_vv, a_rr, and a_δδ are the damping coefficients.

These coefficients can be expressed as follows:

$$a_{vv}=\frac{1}{L}\cdot a^{\prime }{}_{vv}=\frac{1}{L}\cdot \frac{X^{\prime }{}_{vv}}{\left(m^{\prime }{+m}^{\prime }{}_x\right)}$$

(4)

$$a_{nn}=L\cdot a^{\prime }{}_{nn}=L\cdot \frac{{2C}_1}{{(m^{\prime }+m}^{\prime }{}_x)}\cdot {(\frac{D}{L})}^3\cdot (\frac{D}{d})$$

(5)

$$a_{rr}=L\cdot a^{\prime }{}_{rr}=\frac{l_p{(m^{\prime }+c}_m{m}^{\prime }{}_y)}{{(m^{\prime }+m}^{\prime }{}_x)}$$

(6)

$$a_{nv}{=a}^{\prime }{}_{nv}=-\frac{{2C}_2}{{(m^{\prime }+m}^{\prime }{}_x)}\cdot {(\frac{D}{L})}^2\cdot (\frac{D}{d})$$

(7)

$$a_{\delta \delta }=\frac{1}{L}\cdot a^{\prime }{}_{\delta \delta }=\frac{1}{L}\cdot \frac{X^{\prime }{}_{\delta \delta }}{{(m^{\prime }+m}^{\prime }{}_x)}\cdot (\frac{A_R}{L\cdot d})$$

(8)

where L is the overall length, d is the draft, D is the diameter of the propeller, A_R is the rudder area, l_p is the distance between the gravity and pivoting point, c_m is equivalent to the block coefficient of hull c_b, C₁ and C₂ are the dimensionless values of effective thrust, and m^’, m^’_x, and m^’_y are the dimensionless values of mass, longitudinal added mass, and lateral added mass, respectively.

The parameters m^’, m^’_x, m^’_y, X^’_vv, and X^’_δδ are determined as follows:

$$m^{\prime }=\frac{2m}{{\rho L}^{2}d}$$

(9)

$$m^{\prime }{}_{x,y}=\frac{{2m}_{x,y}}{{\rho L}^{2}d}$$

(10)

$$X^{\prime }{}_{vv}=\frac{{2R}_t}{{\rho v)V}^2}$$

(11)

$$X^{\prime }{}_{\delta \delta }{=f}_{\alpha }\left(\lambda \right)\cdot {(\frac{U_{Reo}}{V})}^2$$

(12)

where ρ is the density of water, R_t represents the resistance of stable directional voyage, U_Reo represents the effective inflow speed of the rudder, and f_α (λ) represents the nominal force gradient against the attack angle in the open sea.

The characteristics of the steering engine described in Equation (17) should not be ignored.

$$\stackrel{·}{\delta }=\frac{1}{T_E}\delta +\frac{K_E}{T_E}{\delta }_E$$

(13)

where δ_E is the rudder command angel, δ is the actual rudder angle, and T_E and K_E are the time constant and gain control of the steering engine, respectively. The maximum rudder angle should be smaller than 35°.

In this paper, a proportional-integral-derivative (PID)controller is adopted to control the ship’s heading. A PID controller attempts to correct the error between a measured process variable and a desired point by calculating and then outputting a corrective action that adjust the process accordingly. The rudder angle δ_E is controlled based on the heading error e = ϕ_r − ϕ, and ϕ_r is the desired heading angle, as expressed in Equation (18).

$${\delta }_E=K_{p}e+K_d\stackrel{·}{e}+K_i\int edt$$

(14)

where K_p is the proportional gain constant, K_d is the derivative time constant, and K_i is the integral time constant. The controller gains can be derived by pole placement using the design parameters ${\omega }_n$ and ζ as follows:

$$K_p=\frac{{T\omega }^2{}_n}{K},K_d=\frac{1.8\varsigma {.\omega }_n-1}{K},K_i=\frac{{\omega }^3{}_{n}T}{10K}$$

(15)

where ${\omega }_n$ is the natural frequency and ζ is the relative damping ratio of the first order system.

The implementation of the ship’s course control in the safe trajectory determination algorithm is manipulated by a PID controller. For a specific value of the ship’s speed, a family of characteristics showing the relationships of the manoeuvre time as a function of course and speed for different desired heading changing values is introduced in Figure 5. The corresponding heading angle value and speed value over manoeuvre time are saved and stored in a table and are read from the table for the fitness evaluation.

2.2.2. The Manoeuvre of Speed Reduction

The ship’s motion mathematical model of MMG, including the forces and moments acting upon the ship’s hull, propeller rudder and the interactions within them, is used to simulate the ship’s actual movement in various sea conditions. Considering the thrust deduction coefficient and wake coefficient, the expression is given as follows [27]:

$$Z_{p}P\left(1-t\right)-{R=(m+m}_s)\frac{{dV}_s}{dt}$$

(16)

$${P=K}_P{\rho n}^2{D}^4$$

(17)

$$R_r{=\epsilon v}_s^2$$

(18)

$${M=K}_M{\rho n}^2{D}^5$$

(19)

$$K_P{=K}_P\left(J\right)$$

(20)

$$K_M{=K}_M\left(J\right)$$

(21)

$$J=\frac{v_s(1-\omega )}{nD}$$

(22)

where Z_p is the number of propellers, m_s is the additional mass, m is the ship mass (kg), v_s is the ship speed relative to water (m/s), t is the thrust reduction coefficient, R_r is the ship resistance (N), P is the propeller thrust (N), M is the propeller torque (N.m), n is the propeller revolution speed (r/s), D is the propeller diameter (m), ρ is the water density (kg/m³), ω is the wake coefficient, K_p is the thrust coefficient, K_M is the torque coefficient, and J is the advance coefficient.

In this article, the Wageningen B-screw series propellers chart is adopted, and the principal parameters of this series of propellers are disc-square ratio (A/Ad)₀ = 0.45, blade number Z₀ = 4, and patch ratio H/D = 0~1.6. As n approaches zero, J approaches infinity, which leads to data overflow in the computation [28]; thus, the expression is rewritten as follows:

$$J^{\prime }{=v}_p/\sqrt{v_p^2{+D}_P^2{n}^2}$$

(23)

$$v_p{=v}_s(1-\omega )$$

(24)

$${P=\alpha K}_P^{\prime }{\rho D}_P^2{(V}_P^2{+D}_P^2{n}^2)$$

(25)

$${M=\alpha K}_M^{\prime }{\rho D}_P^3{(V}_P^2{+D}_P^2{n}^2)$$

(26)

$$\alpha =\sqrt[3]{Z_0{{(A/A}_d)}_0/{Z(A/A}_d)}$$

(27)

where v_p is propeller speed relative to water, α is the scaling factor, Z is the calculated blade number, and (A/A_d) is the calculated disk square ratio.

Generally, a function that is continuous can be expressed approximately as an n-order Chebyshev polynomial [29]. Then, the propeller thrust coefficient K’_P and torque coefficient K’_M about J’ can be obtained by Chebyshev polynomial fitting:

$$K_P^{\prime }{(J}^{\prime })=\frac{1}{2}{a}_{0P}{T}_0{(J}^{\prime }{)+a}_{1P}{T}_1{(J}^{\prime }{)+a}_{2P}{T}_2{(J}^{\prime })+\cdots {+a}_{nP}{T}_n{(J}^{\prime })$$

(28)

$$K_M^{\prime }{(J}^{\prime }{)=a}_{0M}{T}_0{(J}^{\prime }{)+a}_{1M}{T}_1{(J}^{\prime }{)+a}_{2M}{T}_2{(J}^{\prime })+\cdots {+a}_{nM}{T}_n{(J}^{\prime })$$

(29)

where T₀(J’) = 1, T₁(J’) = J’, T₂(J’) = 2J’²-1, T₃(J’) = 4J’³−3J’…., the general recursive formula for T_k(J’) is T_{k + 1}(J’) −2J’T_k(J’) + T_k-1(J’) = 0 (k = 1,2,…n). The Chebyshev polynomial has the following features. First, the polynomial coefficients are independent of the order number n. Second, the fitting error is small, and the fitting result with finite order number n is the best approximation, meaning that the mean square error is the minimum. Finally, it is convenient to change from a given Chebyshev polynomial expression into ordinary polynomial.

There are two inertia subsystems in the ship-propeller system: Propeller rotation and ship translation. Translations of the thrust and torque within the two subsystems and their motions are interactive. The block diagram of the ship-propeller model is shown in Figure 6 [30].

The implementation of the ship’s speed control in the safe trajectory determination algorithm is realized by the ship-engine system. For a specific value of the ship’s propeller revolution, a family of characteristics showing the relationships of the manoeuvre time as a function of different desired revolution changing values is introduced in Figure 7.

2.3. Trajectory Planning for Collision Avoidance

Following the above-mentioned scheme, the encounter situation and the manner of evasive manoeuvre are determined. Then, the next focus is the trajectory planning to keep all the ships clear of the OS ship’s domain all the time. The complete collision-avoidance process incorporates the action of collision avoidance and restoration to the original trajectory.

2.3.1. Multiple Genetic Algorithm

Considering the manner of course alteration, the speed and velocity change simultaneously, so the optimization has to deal with multiple variables. The Multiple Genetic Algorithm (MPGA) illustrated in Figure 8a is adopted to overcome the deficiency of Single Genetic Algorithm (SGA) in the aspects of premature convergence, local optimization ability, and parameter settings of genetic operators. The populations with different combinations of parameter settings of genetic operators are closely interwoven by the establishment of an immigrant operator, and the main idea is that the worst chromosome in any population is replaced by the best chromosome in the adjacent population to achieve co-evolution. By establishing an elite-individual operator, the individuals with lower fitness will be chosen to enter the elite population so that the superior individuals will not be lost, making it possible to find the global optimal solution. It is noticeable that the elite population does not perform selection, crossover, or mutation operation to ensure the integrity of the best individuals. The main difference between this algorithm and the MPGA used in [18], is that the evolutionary order of SGA phases shown in Figure 8b is adjusted here to improve the optimization efficiency. The crossover and mutation operators precede evaluation and selection instead of following them. The population size is tripled, then all the individuals in the expanded two population could be sufficiently crossed with each other due to the communication scheme. This change allows for sufficiently taking advantage of the local searching ability and preparing for the tournament selection strategy. In addition, the important change concerns population initialization. Apart from randomly generated individuals, the initial population is generated by a heuristic method (satisfying the constraints for course alteration based on COLREGs). Meanwhile, the evolutionary results of relevant genetic operations are also adjusted to keep the consistency of the optimal solution.

Encoding Technique

In this article, a real number encoding method is employed. Each gene is substituted with a desired course change value between adjacent turning points, as shown in Figure 9. In addition, the direction of course alteration is assumed as follows. If △${\varphi }_i>0$, the give-way ship turns right, otherwise, the give-way ship turns left. This encoding technique is applied to fit the PID controller.

Constraint Conditions

To generate satisfactory trajectory compliance with the COLREGs and good seamanship, some constraints are set as follows. First, the direction of the course alteration is determined in Section 2.1.2. According to Rule 8(b), ‘any alteration of course and/or speed to avoid collision shall, if the circumstances of the case allow, be large enough to be readily apparent to another vessel observing visually or by radar’, therefore, the course alteration angle should be larger than 15° and smaller than π/3 to ensure the evasive manoeuvre is kept obvious [7]. It should be remarkable that the course alteration angle of the last gene is larger than 5° in order to guarantee the restoration to the initial track.

$$\Delta {\varphi }_i\to \{\begin{array}{c}\left|\Delta {\varphi }_1\right|=\frac{\mathsf{\pi }}{6}\\ \begin{array}{c}\frac{\mathsf{\pi }}{12}<\left|\Delta {\varphi }_i\right|\le \frac{\mathsf{\pi }}{6}\left(i=2,3,\cdots ,N-1\right)\\ \left|\Delta {\varphi }_{\mathrm{M}}\right|\in \frac{\mathsf{\pi }}{36}\times \mathrm{k}\left(\mathrm{k}\in {\mathrm{Z}}^{+}\right)\end{array}\end{array}$$

(30)

Fitness Function Model

The fitness function of a chromosome measures the cost of the trajectory it represents. As for the two-ship encounter, the function should consider three different optimisation factors: (1) Satisfy the clearance requirements, (2) maintain a smooth trajectory, and (3) guarantee less distance travelled; a linear combination of these factors is shown Equation (25).

$$=\{\begin{array}{cc}{\alpha }^{\ast }{D}_e+{1000}^{\ast }{D}_t& D_t{<D}_{\mathrm{s}}\\ {\alpha }^{\ast }{D}_e+{\beta }^{\ast }(D_t-D_{\mathrm{s}})& D_t>D_{\mathrm{s}}\end{array}$$

(31)

$$D_e=\sqrt{{{(x}_n^k{-x}_n^{k^{\prime }})}^2{+(y}_n^k{-y}_n^{k^{\prime }}{)}^2}(i=0,1,2,3,\cdots n,j=1,2,3,N)$$

(32)

$$D_t=\min (\sqrt{{{(x}_i^{j+1}{-\mathrm{x}}_i^j)}^2{+(\mathrm{y}}_i^{j+1}{-\mathrm{y}}_i^j{)}^2}$$

(33)

$$N_2=\min \left(⎡\frac{L}{V_j\times T}⎤{\times N}_3\right)$$

(34)

where $\{(x_i^j,y_i^j)|i=1,2,3,\dots ,n,j=1,2,3,\dots ,N\}$ is two-dimensional coordinate arrays that record the optimal trajectories of all the ships, N is the number of encountering ships, assume ship k is the give-way ship, ($x_i^{k^{\prime }},y_i^{k^{\prime }})$ is the planned trajectory of ship k, De is the destination deviation between the optimal trajectory and the planned route of the give-way ship, Dt is the minimum distance during the movement between any two ships, $\alpha$ and $\beta$ are weight coefficient and n is determined by the time step T, the number of turning points, the segment step L, as well as the corresponding ship’s velocity.

2.3.2. Linear Extension Algorithm

For the manner of speed reduction, considering that the course remains unchanged, the linear extension method is adopted to determine the reduced revolution ratio and the corresponding duration. The main idea is determine the appropriate propeller revolution as well as restoration time. It is structured as shown in the pseudocode below. The propeller revolution is decreased by a fixed value in each loop until the give-way vessel can keep away from the stand-on vessels. The corresponding speed variation curve is obtained by the ship-engine model in Section 2.2.2. It should be noted that in the algorithm, a lower bound of half of a revolution, is set to avoid reducing the speed impracticably. When the give-way vessel passes the closest point of approach (CPA), the propeller rate of revolution restores to the original state.

1

V = V_O: OS’s initial speed corresponding propeller revolution speed n = n_e

2

n = n−Δn: Δn is a fixed value

3

Obtain the velocity variation curve;

4

Compute the minimum distance $D_t$ and the corresponding time t_min;

5

While DCPA < D_s and V ≥ 0.5V_O

6

n = n−Δn;

7

End

8

If t ≥ t_min

9

n → n_e: The propeller revolution restores to the initial state

10

End

3. Simulation Results and Analysis

The ship manoeuvrability-based simulation for ship navigation is tested on various typical traffic scenarios emulating different types of encounter situations. The determination of the encounter situation is based on the quantified criteria in Section 2.1.1. Then, the action manner by course alteration or reducing speed to perform collision avoidance is confirmed in Section 2.1.2. Finally, the corresponding trajectory planning model is activated. The dynamic property of a ship is considered in the process of collision avoidance. The initial traffic configurations are given in

Table 3. Ship encounter information for different scenarios.

Parameters	Case I	Case II	Case III	Case IV
Position of ship A/n mile	(0, 0)	(0, 0)	(0, 0)	(5, −4)
Speed of ship A/n mile/h	13	13	19.5	13
Course of ship A/°	45	45	45	330
Position of ship B/n mile	(4.2, 4.2)	(5.4, 2.7)	(2.12, 2.12)	(0, −6)
Speed of ship B /n mile/h	10	13	9	13.6
Course of ship B/°	225	270	45	0
DCPA	0	0.52	0	0.19
R	5.9	6.0	3.0	5.4

. Among them, the DCPA is the distance under the state without taking any collision avoidance measures. The simulation adopts the two exemplary ships with the principal dimensions shown in

Table 4. Principal particulars and manoeuvrability characteristics of ship A.

Parameters	Value	Parameters	Value
Length Overall/m	126.0	KE	1
Breadth/m	20.0	TE	2.5
Draft/m	8.0	avv	1.4 × 10−4
Block coefficient	0.681	aδδ	1.6 × 10−3
Displacement/ton	14278	arr	101.5
N r/m	120	ann	1.4 × 10−2
K	0.48	anv	5.9 × 10−4
T	216.5

and

Table 5. Main principal particulars of the ship-propeller model of ship B.

Name	Value	Name	Value
Length overall/m	189.99	Propeller moment of inertia/kg × m3	22050
Draft/m	6.0	Propeller diameter/m	5.85
Displacement/m3	27522	Pitch ratio	0.748
Rated speed/n mile/h	13.6	Area ratio	0.558
Rated power of motor/kw	7440	Block coefficient	0.7883
Propeller number	1	Diamond coefficient	0.54
Propeller type	Fixed pitch	Propeller revolution speed/r × min−1	108
Propeller blade number	4	Mass/kg	14350

.

After careful consideration of the traffic scenarios for collision avoidance, the relevant parameters of the algorithm are set as follows: Group size, 100; crossover rate, 0.6; mutation rate, 0.04; and termination condition, 50. The parameters α and β in the fitness function model are 0.6 and 0.4, respectively. The simulation tests are run on a computer with a 2.5 GHz processor and 4 GB memory. When the optimal fitness value achieves convergence, or after it reaches the termination condition, the search is terminated, indicating that the optimal trajectory is supposedly found.

In fact, these tests primarily evaluate this simulation system’s performance in terms of effectiveness, consistency, and practicality. The simulation for each traffic scenario is run five times, and the corresponding optimal solutions are recorded in

Table 6. Optimal solutions in a head-on situation.

Sequence	∆ϕ1 (°)	∆ϕ2 (°)	∆ϕ3 (°)	∆ϕ4 (°)	∆ϕ5 (°)	∆ϕ6 (°)	∆ϕ7 (°)	∆ϕ8 (°)	∆ϕ9 (°)	∆ϕ10 (°)
Solution 1	30	0	−15	0	−30	0	0	0	0	5
Solution 2	30	0	−15	0	−30	0	0	0	0	5
Solution 3	30	0	−15	0	−30	0	0	0	0	5
Solution 4	30	0	−15	0	−30	0	0	0	0	5
Solution 5	30	0	−15	0	−30	0	0	0	0	5

,

Table 7. Optimal solutions in a small angle crossing situation.

Sequence	∆ϕ1 (°)	∆ϕ2 (°)	∆ϕ3 (°)	∆ϕ4 (°)	∆ϕ5 (°)	∆ϕ6 (°)	∆ϕ7 (°)	∆ϕ8 (°)	∆ϕ9 (°)	∆ϕ10 (°)
Solution 1	30	−15	−0	−15	0	0	−15	0	0	5
Solution 2	30	−15	−0	−15	0	0	−15	0	0	5
Solution 3	30	−15	−0	−15	0	0	−15	0	0	5
Solution 4	30	−15	−0	−15	0	0	−15	0	0	5
Solution 5	30	−15	−0	−15	0	0	−15	0	0	5

,

Table 8. Optimal solutions in an overtaking situation.

Sequence	∆ϕ1 (°)	∆ϕ2 (°)	∆ϕ3 (°)	∆ϕ4 (°)	∆ϕ5 (°)	∆ϕ6 (°)	∆ϕ7 (°)	∆ϕ8 (°)	∆ϕ9 (°)	∆ϕ10 (°)
Solution 1	30	−15	−0	−15	0	0	−15	0	0	5
Solution 2	30	−15	−0	−15	0	0	−15	0	0	5
Solution 3	30	−15	−0	−15	0	0	−15	0	0	5
Solution 4	30	−15	−0	−15	0	0	−15	0	0	5
Solution 5	30	−15	−0	−15	0	0	−15	0	0	5

and

Table 9. Optimal solutions in a large angle crossing situation.

Sequence	Initial Revolution (r/s)	Initial Velocity (n Mile/h)	Reduced Revolution (r/s)	The Reduced Velocity (n Mile/h)	Period of Staying on the New Revolution (s)
Solution 1	1.8	13.6	0.3	1.16	2785
Solution 2	1.8	13.6	0.3	1.16	2785
Solution 3	1.8	13.6	0.3	1.16	2785
Solution 4	1.8	13.6	0.3	1.16	2785
Solution 5	1.8	13.6	0.3	1.16	2785

. In the figures showing the initial traffic configuration and the optimal trajectory, each vessel is colour coded, and the numbers on each position indicate the corresponding time in minutes. The blue line indicates the trajectory of ship B; the red line indicates the optimal trajectory of ship A; the red dotted line indicates ship A’s original track; and the black line represents the optimal trajectory of ship A without considering the ship manoeuvrability. Moreover, the variation curves of relative distance, velocity, and rudder angle are also illustrated. The radius of the ship’s domain is the safety criterion.

3.1. Case I: Head-On Situation

As seen from the initial traffic status illustrated in Figure 10a, ship A and ship B move on a reciprocal heading. According to the quantified criteria in Table 2, the relevant parameters are compared and analysed as follows: Ship B is in the region P₁ of ship A (θ_B = 0∈ [0, π/8] ∪ [15π/8,2π]). As these two ships approach each other, the ship domain is violated, and risk of navigation collision occurs (DCPA = 0 n mile). Meanwhile, the criteria of crossing angle and applicable distance also satisfy the requirement of HO (C_T = π∈ [7/π8,9π/8], R ≤ 6 n mile). Therefore, the encounter can be identified as a head-on situation in which the ships should pass each other port to port according to Rule 14 of the COLREGs. However, this simulation only calculates the trajectory of ship A as it is viewed from the perspective of ship A, which has already ensured safe navigation. Conversely, the evasive manoeuvre of ship B is also calculated from the point of ship B, while assuming ship A is the stand-on vessel.

3.2. Case II: Small Angle Crossing Situation

As seen from the initial traffic status illustrated in Figure 11a, ship B is positioned before the starboard beam of ship A and the corresponding trajectories cross each other. According to the quantified criteria in Table 2, the relevant parameters are compared and analysed as follows: Ship B is also in the region P₁ of ship A (θ_B = 18.4° ∈ [0,π/8] ∪ [15π/8,2π]) As these two ships approach each other, the ship domain is violated, and risk of navigational collision occurs (DCPA = 0.52 n mile). Meanwhile, the criteria of crossing angle and applicable distance also satisfy the requirement of CR₂ (C_T = 225° ∈ [9π/8,13π/8], R ≤ 6 n mile. As a consequence, it allows us to evaluate the collision risk in Rule 15 of the COLREGs for a small angle crossing situation. Based on the analysis for the action manner in Section 2.1.2, it is compliant with the situation in Figure 3a so that ship A should alter course to starboard to pass the stern of ship B.

3.3. Case III: Overtaking Situation

As seen in the initial traffic status illustrated in Figure 12a, ship A is in the stern of ship B. The relevant parameters are compared and analysed as follows: Ship A is in region P₂ of ship B (θ_A = 180° ∈ [5π/8,11π/8]). As these two ships approach each other, the ship domain is violated, and risk of navigation collision occurs (DCPA = 0.19 n mile). Meanwhile, the criteria of crossing angle and applicable distance still satisfy the requirement of CR₂ (C_T = 0° ∈0, π/2 ∪ [3π/2,2π], R ≤ 6 n mile). Therefore, it allows us to evaluate the collision risk in Rule 15 of the COLREGs for an overtaking situation. Based on the analysis for the action manner in Section 2.1.2, it is compliant with the situation in Figure 4e in which ship A should alter course to starboard to overtake ship B.

3.4. Case IV: Large Angle Crossing Situation

As seen in the initial traffic status illustrated in Figure 13a, ship B is also positioned before the starboard beam of the ship, and the corresponding trajectories cross each other. Similarly, the relevant parameters are compared and analysed as follows: Ship A is in region P₂ of ship B (θ_A = 23.2° ∈ [π/8, π/2]. As these two ships approach each other, the ship domain is violated, and risk of navigational collision occurs (DCPA = 0.19 n mile). Meanwhile, the criteria of crossing angle, and the relative bearing of ship B with respect to ship A together with the applicable distance still satisfy the requirement of CR₂ (C_T = 330° ∈ [π,2π], θ_B = 233.2° < 11π/8, R ≤ 6 n mile). Therefore, it allows us to evaluate the collision risk in Rule 13 of the COLREGs for a small angle crossing situation. Based on the analysis for the action manner in Section 2.1.2, it is compliant with the situation of Figure 3c in which ship B should reduce speed to pass the stern of ship A.

3.5. Analysis and Discussion

For cases I, II, and III, the give-way vessel takes evasive manoeuvres by altering course. The simulation results remain unchanged, as illustrated in Table 6, Table 7 and Table 8, due to the fixed distance step and the altering angle constraints in the algorithm. To intuitively demonstrate the simulation of ship navigation, Figure 10, Figure 11 and Figure 12b show the optimal trajectory marked by different coloured circles; the numbers on each position indicate the corresponding time in minutes. The closest point of approach (CPA) is larger than the safety criterion, which are both clearly marked in Figure 10, Figure 11 and Figure 12c. Figure 10, Figure 11 and Figure 12d–e give the curves of the rudder angle and velocity in the process of collision avoidance. Figure 10, Figure 11 and Figure 12f show the good tracking performance for the give-way ship’s heading angle relative to the desired heading, which reflects the manoeuvring characteristic of ship motion and control, such as inertia and nonlinear. For case IV, the give-way vessel takes action by changing speed. The optimal solution also remains unchanged for a specific encounter situation because the fixed revolution reduction ratio is adopted shown in Table 9. However, the final CPA is much larger than the safety criteria illustrated in Figure 13c because this algorithm lowers the standard in terms of trajectory length in order to guarantee that the optimal solution is more practical. In fact, there are mainly two reasons including the adoption of the fixed reduced revolution ratio and the restoration time influencing the distance variation between ships. The more elaborate division of the fixed revolution reduction ratio, the greater closeness of CPA, and the safety criteria. This would increase the computation time and make no sense. In this article, the restoration time is when the give-way vessel passes the closet distance point CPA of the first speed-reducing action. If the restoration time is before the corresponding t_min just to make the trajectory length relatively short, it will result in the phenomenon that the give-way vessel speeds up to approach the stand-on vessel in the process of collision, which would lay a heavy burden on the navigator of the stand-on vessel. The other simulation results, including the optimal trajectory and velocity variation curves, are presented in Figure 13b,d. The planned trajectory of the give-way vessel is also marked by a green circle to compare it with the optimal trajectory. The density of the circle reflects the process of acceleration and deceleration.

From the simulation results, some conclusions can be drawn. The effectiveness of this simulation for ship navigation in collision situations is mainly reflected in two aspects. One is that the optimal trajectories in different traffic scenarios contain intact evasive manoeuvres, including the action of collision avoidance and the restoration to the original trajectory; the other is that the new CPAs exceed the safety criteria, i.e., the radius of the ship domain in the whole process of ship navigation. For the aspect of consistency demonstration, the avoidance obligation is certain as the encounter situation is derived from COLREGs from the perspective of either party. By adopting the fixed distance step, altering angle constraints as well as the fixed revolution reduction ratio in the algorithm, the optimal solutions could remain unchanged for the same input. Additionally, the action manner is determined based on the COLREGs, good seamanship, and cost of avoidance, which can reduce the doubt about the evasive manoeuvre to the greatest extent, especially in encounters between unmanned ships and manned ships. To demonstrate the practicality, the dynamic property of ship manoeuvring is considered in the process of collision avoidance to improve the reliability of the simulation system. More importantly, it is clear in the heading alteration curve that the evasive manoeuvres simulated by the multiple genetic algorithm are performed with fewer course deviations compared with the initial assumed number of turning points, which are compliant with navigational practice.

4. Conclusions

This paper has presented a method for automatic trajectory planning and collision avoidance for use in ship manoeuvrability-based simulation for ship navigation. Under the general requirements from the COLREGs and good seamanship, the determination of an encounter situation is quantified to reduce the intervention of navigators. Meanwhile, the action manner by course alteration or changing speed in some typical encounter situations is graphically analysed for both give-way and stand-on vessels to make the evasive action compliant with navigational practice and to reduce the doubt about the evasive manoeuvre, especially in encounters between unmanned ships and manned ships. By adopting the fixed distance step, altering angle constraints, and the fixed revolution reduction ratio in the algorithm, the optimal solution can remain unchanged for the same traffic scenario. More importantly, the mathematical model of ship motion and ship manoeuvring control mechanism is adopted, which can eliminate the insufficiency of neglect of ship manoeuvrability in the process of collision avoidance. Meanwhile, the course encoding technique is adopted to fit the ship manoeuvring control mechanism. Finally, a set of traffic scenarios simulating different encounter situations is applied to demonstrate the effectiveness consistency and practicality of this simulation system. However, since only the applicable distance for different encounter situations is analysed, the specific action time is not considered, and our future research will concentrate on the choice of action time, especially for multi-ship collision avoidance.