Mechanism of dynamic automatic collision avoidance and the optimal route in multi-ship encounter situations

Abstract

Autonomous navigation on the open sea involving automatic collision avoidance and route planning helps to ensure navigational safety. To judge whether all target ships (TSs) will pass safely and find the optimal route under multi-ship encounter situations, the relationship between the variations in the own ship (OS) velocity vector after nonlinear course altering motion and the collision avoidance result, which is defined as the collision avoidance mechanism, was analyzed. Methods producing the optimal route were also proposed. First, the static collision avoidance mechanism based on the ship domain and velocity obstacle (VO) was introduced. On that basis, the collision-free course alteration range of the OS, without consideration of the real manoeuvring process, was presented. Second, the ship motion equations and fuzzy adaptive proportion integral derivative (PID) control method were combined to develop a course control system. This system was then used to predict OS motions during the course-altering process. Based on this prediction, TS positions were calculated. Subsequently, the dynamic collision-free course altering ranges for the OS were obtained. Third, a model to compute the optimal route was introduced. Finally, simulations were performed under a situation including six TSs and two static objects, and the shortest collision-free route that satisfies both regulations for preventing collisions and good seamanship was found.

1 Introduction

Ship collisions are the largest contributor to maritime traffic accidents [7, 24], and most such accidents (96%) are caused by human factors [37]. To reduce the effect of human factors, and the occurrence of ship collision accidents, the intelligence level of ships should be improved. The “Rules for Intelligent Ships” [8] stipulate that intelligent navigation is one of the six functional modules of intelligent ships. The intelligent navigation module enables ships to navigate automatically following the planned route in open water and to avoid collisions automatically. To achieve automatic collision avoidance and autonomous navigation with multiple objectives, the following issues should be solved:

• (1) Is the own ship (OS) collision-free for all target ships (TSs) under the current situation?

• (2) If not, what collision avoidance actions should be taken to meet both the international regulations for preventing collisions at sea (COLREGs) and good seamanship?

• (3) How can we ensure that the OS is collision-free during an encounter and choose the optimal route after course altering?

A series of models and methods were analyzed to identify the encounter situation and draw conclusions regarding the principles of collision avoidance actions in accordance with COLREGs. He et al. [17] proposed theories and methods to solve Question 2. To answer Questions 1 and 3, as one part of a series of studies on this topic, this study presents fundamental theories and methods considering the following factors:

• Factor 1: The offset of the ship domain centre and all velocity vectors of the OS may be applied.

• Factor 2: The nonlinear variations in the OS speed vector and the position changes of TSs emerge during the OS manoeuvres.

• Factor 3: The collision-free route meets the requirements both for COLREGs and good seamanship.

To determine whether the OS is collision-free in a multi-ship encounter situation when different speed vectors of TSs are considered, the relationship between the OS’s speed vectors and the result of collision avoidance should be explored. The previous studies mostly focused on analyzing collision avoidance geometry. Among the collision avoidance models that have been established in the past decades, the distance to the closest point of approach (DCPA)/time to the closest point of approach (TCPA) model was widely applied in early studies. Moreover, Calvert [2] reported that the relative motion line of the ship would rotate counter clockwise when the ship altered course to the starboard side in an urgent situation. Mitrofanov [23] invented an anti-collision indicator that calculates the possible anti-collision actions based on manually input data from the radar. These calculations were performed by mathematical models of the speeds and courses of two ships. Jones [19] proposed a manoeuvring diagram for multi-ship encounter situations that provides information about critical collision hazard areas based on geometric relationships and that proposes possible collision avoidance actions. Degre and Lefevre [11] built a collision avoidance system in accordance with the speed vector manipulation space principle.

The term collision avoidance mechanism has been mentioned by [1, 35], but its scope and meaning currently remain unclear. In this paper, the theories and/or methods used for ship collision avoidance, which is based on the relationship between OS speed vectors and the collision avoidance result, are called the collision avoidance mechanism. Theory and/or methods, for instance, the abovementioned DCPA/TCPA model and the ship domain, may be included in the collision avoidance mechanism.

The characteristics of an automatic collision avoidance environment may be different from present practice. All decisions, which are presently made by officers, must be made by the programme automatically based on traffic conditions and the equipment on board in that specific environment. When solving problems in automatic collision avoidance, these theories and/or methods are referred to as the automatic collision avoidance mechanism. That consideration of factor 1 above is defined as the static automatic collision avoidance mechanism since the process of OS manoeuvring is ignored. In contrast, that consideration of factors 2 and 3 is defined as the dynamic automatic collision avoidance mechanism since the process of ship manoeuvring is fully integrated. In addition, methods for finding the optimal collision-free route are required in collision avoidance operations.

As extensions of collision avoidance mechanism research, some new methods have been developed. Pedersen et al. [25] proposed a method to judge whether a TS could pass safely by drawing upon the collision danger section of a ship’s true speed vector. Xiong et al. [34] and Wu et al. [33] introduced the relative velocity obstacle (VO) method to study a complex multi-ship collision avoidance situation and implemented a computer simulation of collision avoidance. A time-discrete nonlinear VO method based on the nonlinear VO algorithm and tested on historical automatic identification system data was proposed for collision candidate detection by Chen et al. [6]. Algorithms to detect collision dangers with TSs sailing nonlinearly and (probabilistically) predictably and then finding collision-free velocities in multi-ship scenarios were proposed by Huang et al. [18].

A couple of studies on route planning have been conducted in recent years. Tang et al. [31] presented a general local reactive obstacle avoidance algorithm for high-speed (> 20 knots) unmanned surface vehicles using the direction steady-state model and the translational velocity model. This algorithm was validated by both simulations and sea trials. Based on experience and accident statistics, Zhang and Furusho [38] developed a human-in-the-loop decision-support system, where the Bayesian network was used for risk and accident predictions. The visual technique can also be integrated to propose an automatic collision avoidance method. A deep convolutional neural network with strong visual processing capability was used to encounter pattern recognition by Xu et al. [36]. Singh et al. [30] extended the application of the A* approach in a traffic environment with static and moving obstacles. Chen et al. [5] proposed the concept of cooperative multi-vessel systems that consist of multiple coordinated autonomous vessels. Cho et al. [9] proposed a decision-making procedure by predicting the manoeuvring intent of traffic ships, assuming that the surrounding ship may or may not always follow the rules.

Many studies have focused on the route optimization of under actuated autonomous surface vehicles [3, 4, 20, 22, 27, 28, 40], and some novel methods have been proposed (e.g., neuron-evolutionary methods, approaches based on adaptive line-of-sight, multi-objective particle swarm optimization algorithms). Polvara et al. [26] described the most common techniques derived from classical graph search theory. Special attention was paid to intelligent methods, e.g., artificial neural networks and evolutionary algorithms.

Although the previous studies on collision avoidance mechanisms and route optimization during the practice of collision avoidance have been well developed, great efforts have been put forth, and numerous achievements have been gained, the following shortcomings can still be identified:

• (1) There are inadequate conclusions regarding the collision avoidance mechanism. Only simple velocity vector variations were included, whereas the process of OS manoeuvring was not considered. Therefore, constraints to ship manoeuvrability and changes in the traffic environment were not taken into account. In fact, constraints to ship manoeuvrability directly affect OS collision avoidance actions. The nonlinear changes of OS manoeuvring during collision avoidance were rarely included in the existing literature. As a result, the errors of position changes of TSs will simultaneously be generated.

• (2) All COLREG rules and good seamanship should be deliberately considered. Some COLREG rules, e.g., Rule 13, Rule 14, and Rule 15 were indeed considered in many works. It is also important to ensure that some other COLREG rules (e.g., Rule 2, Rule 7, Rule 8, and Rule 17) are fully incorporated into the mathematical models. It is noted that the interpretations of these rules are too linguistic to be express by the numerical model. These rules should be interpreted by good seamanship. The collision avoidance actions that should be taken by the OS were different in different stages, even under the same situation.

• (3) Few works have been designed to solve the automatic collision avoidance problem in multi-ship encounter situations. Compared to 2-ship encounter situations, it becomes much more complex for models to plan the route and take effective actions clearing all ships simultaneously.

• (4) Models failed to distinguish the required safe distances of different objects based on different directions of the OS. The criterion of TS safe passage is larger under the DCPA model than the minimum value or outside the circle ship domain, which is the simplest model. It will be much more complicated if the elliptical centre offset or other irregular OS ship domains are used.

In this context, a series of models were developed to determine the safe distance of TS and objects from OS with different bearings [15,16,17, 37], which were viewed from a ship domain with an offset centre. Meanwhile, COLREGs and good seamanship were also incorporated into the models. To further develop the models, this study will present some innovative models and methods to explore the dynamic collision avoidance mechanism by considering the following features:

• (1) The method to find collision-free velocity vector ranges in multi-ship encounter situations and the criterion of safe passage for TS pass and clear the elliptical centre offset OS ship domain.

  In practice, the required safe distances of the OS vary with the direction. The elliptical centre offset OS ship domain, which represents the safe distance required in practice, was integrated with VO theories to make out collision-free velocity vector ranges for multi-ship encounters.

• (2) The collision-free routes were presented by including OS manoeuvring characteristics, the OS course alteration process, and TS position changes during this process.

  MMG (mathematical model group) ship motion equations were employed to illustrate the characteristics of ship manoeuvring motion. The fuzzy adaptive PID control method, combined with the MMG model, was used to simulate the complex nonlinear variations in the OS speed vector and positions with a supposed autopilot control. TS positions can be calculated at the end time point of OS manoeuvring. Therefore, dynamic collision avoidance mechanisms were presented based on the static collision avoidance mechanism and the prediction of the OS manoeuvring process.

• (3) The optimal collision-free route, conforming to COLREGs and good seamanship, was produced by a computer programme based on feature analyses. COLREGs and good seamanship were incorporated into the methods to find this route.

This study is organized into six sections, including the Introduction.

Section 2 describes the theories of the static collision avoidance mechanism considering the VO sectors of an OS.

Section 3 elaborates dynamic collision avoidance mechanisms based on the course control system. The feasible range of the OS course alteration after manoeuvring will be calculated.

Section 4 focuses on a model to calculate the optimal or nearly optimal route. It is the shortest route in time or distance for the OS to follow without risk of collision.

Section 5 is the simulation model to verify the theories and methods presented. In this section, a complex traffic situation with six TSs and two static targets around the OS was set. The feasible OS course altering ranges were calculated. The ranges conforming to COLREGs and good seamanship were found, and an optimal route among them was discussed.

Section 6 is the conclusion.

Appendix 1 provides detailed definitions of the symbols and parameters used in this paper.

Appendix 2 provides information about the prototype ship (Panamax bulk carrier M/V HUAYANG DREAM).

2 Static collision avoidance mechanism based on the ship domain

2.1 Velocity obstacle

VO theory was originally proposed by Fiorini [12]. Similar ideas had been used by Degre and Lefevre [11], who developed these ideas to solve the anti-collision problem. This theory presented an applied instrument in which mobile targets are considered as static targets. Researchers [6, 18, 34] applied the basic principles of these methods in ship anti-collision research. The method by which an OS’s VO sector can be determined was applied in two-ship encounter situations. The OS will collide with a TS if the OS proceeds with a velocity vector inside this VO sector. When the TS remains at its current speed and course, all OS VO sectors, in which the OS will collide with the TS, will compose the VO area of the OS to the TS.

In Fig. 1, the OS and TS are located at points A and B, respectively; BO is the circle area considering the safety distance around B; the velocity vectors of the OS and TS are vectors ${V}_{A}$ and ${V}_{B}$, respectively; ${V}_{AB}$ is the relative velocity vector of the OS to the TS. The sector area ${C}_{AB}$ is formed by Lines $A{B}_{1}$ and $A{B}_{2}$.${C}_{AB}$ is the VO area of the OS to the TS. If the end of the velocity vector ${V}_{AB}$ is located in ${C}_{AB}$, the OS will collide with the TS.

Fig. 1

Schematic diagram of the VO

2.2 VO sector of the OS based on the ship domain

Most modern ships are equipped with fixed pitch propellers and often operate at fixed sea speed on the open sea. Due to the special engine protection programmes and high inertia of these ships, collision avoidance via speed change is not an appropriate option for automatic collision avoidance on the open sea [17]. Thus, only course alterations are considered here. This study primarily aims to determine a course (alterations) set that can effectively avoid all TSs and obstacles.

2.2.1 Ship domain and coordinate system

• (1) Ship domain

  Ship domain theory was originally proposed by Fujii and Tanaka [13]. The ship domain is the area around the ship that avoids the entrance of other ships for navigational safety. Fujii and Tanaka [13] firstly proposed the elliptical ship domain with the OS ship in the centre. However, Goodwin [14] observed the influence of COLREGs and developed a new ship domain with an integration of three different sectors. Davis et al. [10] smoothed the integrations with a circle boundary and set a “phantom ship” in the centre for the easy expression in math. The real centre of the domain is located astern of the phantom ship’s port side, and the domain also can be divided into three sectors to cover the original three sectors. Recently, the eccentric ellipse was measured for ship domain via Automatic Identification System and act as one of the criteria to measure safety between ships [29, 41]. Thus, we combine the advantages of these two ship domain models and present a centre offset eccentric shape for the OS’s ship domain (Fig. 2).

  Fig. 2

  

  Ship domain model and coordinate system

• (2) Coordinate system

  Two coordinate systems were introduced into the model. The O–X–Y coordinate system was fixed to the Earth, and the o–x–y coordinate system was fixed to the OS. To simplify the calculation of ship domain equations, the coordinate origin of o–x–y is located at the phantom ship, the x-axis pointing toward the starboard, the y-axis to bow, as shown in Fig. 2.

The relation of the phantom ship and the real ship can be expressed in Eq. 1 based on O–X–Y coordinate system:

$$\left\{ {\begin{array}{*{20}c} {X_{o}^{^{\prime}} = X_{o} + R_{d} \sin \left( {C + 19^{^\circ } } \right)/4} \\ {Y_{o}^{^{\prime}} = Y_{o} + R_{d} \sin \left( {C + 19^{^\circ } } \right)/4} \\ {R_{d} = ab/\sqrt {\left( {a\sin 199^{^\circ } } \right)^{2} + \left( {b\cos 199^{^\circ } } \right)^{2} } } \\ \end{array} } \right.,$$

(1)

where: $\left({X}_{o},{Y}_{o}\right)$ denotes the coordinates of the real OS, and $({X}_{o}^{^{\prime}},{Y}_{o}^{^{\prime}})$ is the coordinates of the phantom ship. a and b are the lengths of the semi-major and semi-minor axes of the ellipse, respectively. C is the true course of the OS. ${R}_{d}$ is the distance from the position of the phantom ship to the border of the ellipse along the direction of the real OS.

2.2.2 Static VO sector

When two ships (TS and OS) encounter at sea and will collide if they maintain their present course/speed (see Fig. 3), the OS’s navigators will determine which courses are dangerous and which are safe. A course of the OS that will result in the TS passing outside the ship domain of the OS is named a feasible course (heading). In contrast, a course of the OS that will make the TS crossing the ship domain of the OS is therefore named as an infeasible course (heading). Figure 3 shows the VO sector without considering the course alteration process. The original OS and TS speeds are $\overrightarrow{{\mathrm{v}}_{0}}$ and $\overrightarrow{{\mathrm{v}}_{1}}$. The TS has the relative motion line of AC, which will cross the centre of the OS ship domain.

Fig. 3

Static VO sector

When the ship turns to the port side, the centre of the ship domain and the relative motion line of the TS will move accordingly. This line will cross the ship domain of the OS at the beginning of course alteration. However, when the OS course is altered to $\overrightarrow{{v}_{0-p}}$, the relative motion line of the TS will touch the border of the ship domain. It is easy to understand that this line will not cross the ship domain of the OS if course alteration continues. In contrast, if the OS course is in the range from $\overrightarrow{{v}_{0}}$ to $\overrightarrow{{v}_{0-p}}$, the TS will cross the domain of the OS ship. It can be concluded that the OS course from $\overrightarrow{{v}_{0}}$ to $\overrightarrow{{v}_{0-p}}$ is one part of the OS static VO sector to this TS. It is noted that all the sectors are obtained without consideration of ship manoeuvrings.

Likewise, when the OS course is altered to the starboard side, another part of the OS static VO sector to this TS $\left[\overrightarrow{{v}_{0}},\overrightarrow{{v}_{0-s}}\right]$ will be available. Accordingly, the VO area of the OS to this TS is $\left[\overrightarrow{{v}_{0-p}},\overrightarrow{{v}_{0-s}}\right]$.

At time point $t$ since the current time, the location of the target ship in the O–X–Y coordinate system can be calculated by the following equations:

$$\left( {x_{r} ,y_{r} } \right)^{\left( t \right)} = \left( {x_{r} ,y_{r} } \right)^{\left( 0 \right)} + \left( {u,v} \right)t,$$

(2)

$$\left\{ \begin{aligned} & x_{r}^{{\left( 0 \right)}} = \left( {X_{R}^{{\left( 0 \right)}} - X^{\prime\left( 0 \right)}_{o}} \right)\cos C_{o} - \left( {Y_{R}^{{\left( 0 \right)}} - Y^{\prime\left( 0 \right)}_{o} } \right)\sin C_{o} \hfill \\ & y_{r}^{{\left( 0 \right)}} = \left( {X_{R}^{{\left( 0 \right)}} - X^{\prime\left( 0 \right)}_{o} } \right)\sin C_{o} - \left( {Y_{R}^{{\left( 0 \right)}} - Y^{\prime\left( 0 \right)}_{o}} \right)\cos C_{o} \hfill \\ & u = \left( {v_{R} \sin C_{R} - v_{o} \sin C_{o} } \right)\cos C_{o} - \left( {v_{R} \cos C_{R} - v_{o} \cos C_{o} } \right)\sin C_{o} \hfill \\ & v = \left( {v_{R} \sin C_{R} - v_{o} \sin C_{o} } \right)\sin C_{o} + \left( {v_{R} \cos C_{R} - v_{o} \cos C_{o} } \right)\cos C_{o} \hfill \\ \end{aligned} \right.,$$

(3)

where: in the o–x–y ship-fixed coordinate system, ${({x}_{r},{y}_{r})}^{(t)}$ are the TS coordinates at time point t; ${({x}_{r},{y}_{r})}^{(0)}$ are the target ship coordinates at the current time, and u and v are the velocity components of the target ship along with the directions of the $x$ and $y$ axes. In the O–X–Y Earth-fixed coordinate system, $\left({{X}_{R}}^{(0)},{{Y}_{R}}^{(0)}\right),{C}_{R},{v}_{R}$ are the current time coordinates, heading, and speed of the TS, respectively; and $\left({{X}_{o}^{^{\prime}}}^{(0)},{{Y}_{o}^{^{\prime}}}^{(0)}\right),{C}_{o},{v}_{o}$ are the current time coordinates, heading, and speed of the phantom ship of the ship domain of the OS, respectively.

The ship course of $\overrightarrow{{v}_{0-p}}$ and $\overrightarrow{ {v}_{0-s}}$ at which the TS relative motion line will touch the border of the elliptical OS ship domain can be obtained with Eq. 4:

$$\left( {\frac{{y_{r}^{\left( t \right)} }}{a}} \right)^{2} + \left( {\frac{{x_{r}^{\left( t \right)} }}{b}} \right)^{2} = 1,(a > b > 0).$$

(4)

To solve Eq. 4, Eq. 5 can be transformed.

$$\left( {a^{2} u^{2} + b^{2} v^{2} } \right)t^{2} + 2\left( {ux_{r} a^{2} + vy_{r} b^{2} } \right)t + a^{2} x_{r}^{2} + b^{2} y_{r}^{2} - a^{2} b^{2} = 0.$$

(5)

Assume that $K={a}^{2}{u}^{2}+{b}^{2}{v}^{2},M=2\left(u{{x}_{r}a}^{2}+v{{y}_{r}b}^{2}\right)$, and $L={a}^{2}{{x}_{r}}^{2}+{b}^{2}{{y}_{r}}^{2}-{a}^{2}{b}^{2}$.

$$\left\{ {\begin{array}{*{20}c} {M^{2} - 4KL = 0} \\ {K < 0} \\ \end{array} } \right..$$

(6)

When Eq. 6 is satisfied, the TS relative motion line will be tangent to the OS ship domain, and the border value of the static VO sector can be obtained; when ${M}^{2}-4KL<0$, the TS will not enter the ship domain; when ${M}^{2}-4KL>0$, the TS will enter the ship domain.

Because the real OS is offset from the centre of the ship domain model, it (the origin of the o–x–y coordinate system) changes accordingly while the ship alters its course. Equation 6 will finally become a very complex, transcendental and higher-order equation. The result of this equation is the OS course ($C$ or course alteration amplitude $\theta =C-{C}_{0}$). The analytical algorithm of this type of equation is difficult to be found. The numerical approach is an alternative and can be executed by software MATLAB with the function “solve”. Before computing, an initial value of alteration amplitude, θ, should be set. The initial value can be roughly determined by mariners, but varies. Therefore, we can deal with the Eq. 6 with any initial value and examined one by one. All possible alteration amplitudes, which can be taken by the OS, are discretized at regular intervals (1°). One degree of error in the OS course will not significantly influence the safe operation during collision avoidance on the open sea, especially, when TS is far away. For each discretized alteration amplitude, the likelihood that this OS course can avoid all objects safely will be checked one by one. If it cannot be avoided, then the course is not feasible as it belongs to one Static VO sector. All the courses beyond any static VO sectors, will make up the set of all feasible courses. Section 3.3 will give the details to computer the set of all feasible courses. It is noted that all the alterations have not taken ship manoeuvring process into account.

3 Dynamic VO area

Considering ship manoeuvring, the alterations will demonstrate nonlinear change which will influence the real VO sector. To describe the manoeuvring, MMG model and course control system is integrated and applied to determine the infeasible course alteration range, i.e. dynamic VO sector.

3.1 MMG model

In this study, to predict and simulate the manoeuvring of OS, three degrees of freedom of ship motion (surge, sway, and yaw) are modelled based on MMG:

$$\left\{ {\begin{array}{*{20}c} {\left( {m + m_{x} } \right)\dot{u} - \left( {m + m_{y} } \right)vr = X_{H} + X_{P} + X_{R} } \\ {\left( {m + m_{y} } \right)\dot{v} - \left( {m + m_{x} } \right)ur = Y_{H} + Y_{P} + Y_{R} } \\ {\left( {I_{ZZ} + J_{ZZ} } \right)\dot{r} = N_{H} + N_{P} + N_{R} } \\ \end{array} } \right.,$$

(7)

where $m$, ${m}_{x}$, ${m}_{y}$, ${I}_{ZZ}$ and ${J}_{ZZ}$ are mass of ship, added mass in x and y directions, inertia moment and additional inertia moment, respectively; subscript H, P, R are bare hull, propeller, rudder, respectively; u, v and r denote surge, sway velocity and yaw rate, respectively; X, Y, N are the external forces and moments in different directions, respectively.

In this study, a Panamax bulk carrier, named HUAYANG DREAM, was investigated. To verify the accuracy of the numerical MMG model, the speed performance at different revolutions per minute (RPM) of the propeller and turning circle were compared between the model and the real ship. Slight discrepancies were found, but the accuracy was acceptable overall (Appendix 2).

3.2 Course control system based on fuzzy adaptive PID control

For most modern ships, manoeuvring is executed by autopilot systems. To predict the OS’s position, speed and course at different time points after the ship is steered, the course control system should be studied. To date, the traditional PID control method has been widely used at sea. The fuzzy adaptive PID control model, as an improved method relative to the conventional method, was applied. It will make out output and control the ship's steering gear when the course alteration amplitude is set. Real-time dynamic adjustment of PID parameters through fuzzy inference can provide real-time and accuracy for course keeping or altering in a logical way. The fuzzy adaptive PID control principle is shown in Fig. 4.

Fig. 4

The diagram of fuzzy adaptive PID control

E is the heading error, EC is the error rate of change, and E and EC serve as the inputs of the fuzzy controller. The PID parameters ${K}_{P},{K}_{i},{K}_{d}$ serve as the fuzzy controller output. These parameters were adjusted automatically in real-time using the fuzzy control rules based on different E and EC values, i.e., different E and EC pairs are self-tuned for the PID parameters so that the controlled object exhibits good dynamic and static performance.

According to [21, 32] and expert experience, the quantization levels of the input variables (heading error E, the error rate of change EC) and the output variables (${K}_{P},{K}_{i},{K}_{d}$) were set as seven levels. The language values of the fuzzy subset were all expressed by {positive big (PB), positive median (PM), positive small (PS), zero (ZO), negative small (NS), negative medium (NM), negative big (NB)}. The fuzzy set theory fields are all {− 6, 6}. The Gaussian membership function was exploited for the fuzzy subset membership function of each variable.

Two control methods, namely, conventional and fuzzy adaptive PID control, were adopted for simulation, and the course control results are shown in Fig. 5. Two steering processes are shown based on the tracks of the OS when the OS was controlled to alter the course to the aimed value. It is easy to discriminate outputs between the fuzzy adaptive and pure PID control. As shown in Fig. 5a, general PID control has problems of slow response speed, big overshoot and bad robustness. As shown in Fig. 5b, under the general PID control, the larger course altering amplitude is, the larger the error is. The fuzzy adaptive PID control solves the above problems.

Fig. 5

Simulation of the course control system

3.3 Feasible course alteration range

3.3.1 Two ship encounter situation

The theories and methods for solving the static velocity obstacle sector are introduced in Sect. 2.2, among which the OS course alteration process is not considered. To predict the result of collision avoidance actions, the motion process of the OS and the positions of TSs upon the completion of course alteration should be predicted. MMG motion equations and the course control system can predict the motion conditions of the OS. The positions of TSs can also be calculated by the time of OS manoeuvring, speeds and courses of these TSs. In fact, the OS will experience a nonlinear motion process (see Fig. 6) during course alteration; the positions of TSs will also change during this process.

Fig. 6

Dynamically infeasible course alteration range

The dynamically infeasible course alteration range to the TS is shown in Fig. 6. The original OS and TS speed vectors are ${V}_{A}$ and ${V}_{B}$, respectively. Among the discussions, TS (B) will maintain her course and speed. OS alteration amplitude ${\alpha }_{1}$ to the starboard side is assumed. ${\mathrm{C}\mathrm{O}\mathrm{G}}_{0}$ is the original course of the OS. For easy presentation, at the beginning of alteration, two coordinate systems were set to coincide with each other in Fig. 6. Subsequently, the following is found:

If the ship's steering process is not considered, the ship heading will directly change from ${\mathrm{C}\mathrm{O}\mathrm{G}}_{0}$ to ${\mathrm{C}\mathrm{O}\mathrm{G}}_{0}+{\alpha }_{1}$. The ship will move in a straight line ${L}_{1}^{^{\prime}}$, which is inconsistent with the actual patterns of course change in practice. In contrast, if the steering process controlled by the course control system is considered, the OS headings and positions will undergo a series of nonlinear variations. The heading of the OS will certainly stabilize at ${\mathrm{C}\mathrm{O}\mathrm{G}}_{0}+{\alpha }_{1}$, eventually moving along the composite curve ${L}_{1}$. There is an appropriate ${\alpha }_{1}$ such that the TS will cross on the borderline of the OS ship domain. As shown in Fig. 6, when the OS moves to position ${\mathrm{P}}_{A1}$ from ${\mathrm{P}}_{A0}$, the TS will arrive at ${\mathrm{P}}_{B1}$ from ${\mathrm{P}}_{B0}$ and be tangent to the borderline of the OS ship domain. The TS will not violate the ship domain of the OS at any other time. It can obviously be inferred that the TS will enter the ship domain of the OS if the OS course alteration amplitude to the starboard side is less than ${\alpha }_{1}$. Therefore, the angle ${\alpha }_{1}$ is the critical angle of the course alteration amplitude to the starboard side.

Likewise, the critical angle of the course alteration amplitude to the port side ${\alpha }_{2}$ also exists. The TS will enter the OS ship domain if the OS course alteration amplitude to the port side is less than ${\alpha }_{2}$. Course alteration amplitude range $A=\left[{\alpha }_{1},{\alpha }_{2}\right]$ is called the infeasible course alteration range of the OS to this TS. The TS will enter the OS ship domain when the OS course is inside this range. The limit of $A$ is the intended heading such that the TS will touch the OS ship domain border if it is operated by the OS, as shown in Fig. 6.

3.3.2 Multiple ship encounter situation

When there are multiple objects, and the OS operates a certain course alteration amplitude, this course alteration should not be collision-free if any one of the TSs will enter the ship domain of the OS. Therefore, the infeasible course alteration range of the OS to all these TSs should be composed of each infeasible course alteration range of the OS to each TS, i.e., the infeasible course alteration range of the OS to all these TSs $\mathrm{V}\mathrm{O}$ can be calculated by:

$${\text{VO}} = U_{i = 1}^{n} A_{i} ,$$

(8)

where: the quantity of TSs is $n$, and ${A}_{i}$ is the infeasible course alteration range of the OS to the TS numbered $i$.

For instance, in a three-ship encounter situation, as shown in Fig. 7, VO can be calculated by:

$${\text{VO}} = U_{i = 1}^{3} A_{i} = A_{1} \bigcup {A_{2} } \bigcup {A_{3} } = \left[ {\alpha_{1} ,\alpha_{2} } \right]\bigcup {\left[ {\beta_{1} ,\beta_{2} } \right]} \bigcup {\left[ {\gamma_{1} ,\gamma_{2} } \right]} ,$$

(9)

where: $\alpha$, $\beta$ and $\gamma$ are the headings of the OS.

Fig. 7

Feasible course alteration range in a multi-ship situation

Feasible course alteration range in Fig. 7 can be expressed as Eq. 10:

$${\text{VO}}^{\prime} = \overline{{{\text{VO}}}} = \overline{{U_{i = 1}^{n} \alpha_{i} }} = \overline{{U_{i = 1}^{3} \alpha_{i} }} = \left( {\alpha_{1} ,\beta_{1} } \right)\bigcup {\left( {\beta_{2} ,\gamma_{1} } \right)} .$$

(10)

Each sub feasible course alteration range (e.g., $({\alpha }_{1},{\beta }_{1})$ in ${\text{VO}}^{\prime}$) is called a sub-range. All headings in each sub-range will ensure that the OS passes in the same direction (either ahead or astern) as the TS intended to be avoided. For instance, all headings in $({\alpha }_{1},{\beta }_{1})$ will ensure that the OS passes ahead of T₂ and astern of T₁. This phenomenon can easily be understood since the sub-range is continuous. It will be suspended if a change in the OS course results in another TS touching one side of the border of the OS ship domain. Figure 7 demonstrates that when the OS heading is changed to ${\beta }_{1}$ from ${\alpha }_{1}$, T₂ will reach the border of the OS ship domain.

Thus, how to solve ${\text{VO}}^{\prime}$ becomes the crucial problem of this study. If each infeasible course alteration range in multi-objective environmental conditions can be obtained, then the feasible course alteration range can be obtained correspondingly.

According to Eq. 9, for any course alteration amplitude, if the ship’s heading on the ending time of course alteration is not collision-free for any one TS, this course alteration amplitude belongs to VO. The error of course alteration amplitude will be within one degree. It is at the same magnitude as that of PID course control system fitted on-board ship and the general error is acceptable.

The possible course alteration range at sea is $[-180^\circ ,180^\circ ]$. However, the OS will not excessively alter the amplitude of its course so that it will turn backwards, and this range can be considered within $[-90^\circ ,90^\circ ]$. As above mentioned, we take every one degree of possible course alteration amplitudes for the calculation to check whether this course alteration amplitude belongs to any infeasible course alteration range. The course alteration amplitudes which don’t belong to any infeasible course alteration range compose ${\text{VO}}^{\prime}$. The motion process of the OS altering course is calculated using the course control system introduced in Sect. 3.2.

The numerical algorithm based on the enumeration method is designed to obtain ${\text{VO}}^{\prime}$ as the following steps:

Step 1: The possible course alteration range is limited to $\left[-90^\circ \right.,\left.90^\circ \right]$, and then, this range is discretized into 181 elements with an interval of 1°.

Step 2: Set the minimum course-altering amplitude in the range as the initial course-altering amplitude,

Step 3: Judge whether initial course-altering amplitude is smaller than 90°. If yes, calculate the position of the OS and the steering process time experienced since steering started to end. The course control system introduced in Sect. 3.2 is used to simulate the OS steering process from the present course to the aimed course. Otherwise, go to Step 8.

Step 4: Calculate the positions of all TSs based on the time of the steering process. The course and speeds are assumed with a steady change in this process.

Step 5: Judge whether the OS course at the end of the manoeuvring belongs to the static VO area of the OS to the TSs.

Step 6: If so, input the course-altering amplitude at this time into the VO set and go to the next step; otherwise, input the course-altering amplitude at this time into the ${\text{VO}}^{\prime}$ set and go to the next step.

Step 7: Add one degree to the course alteration amplitude and go to Step 3.

Step 8: Determine the automatic collision avoidance action that meets the requirements of COLREGs and good seamanship. The related quantitative rules, method and model refer to the previous work of the authors [17].

The feasible course alteration range ${\text{VO}}^{\prime}$ can be calculated in Step 6 and may consist of several divided sub-ranges. To a large extent, some sub-ranges may not meet the requirements of COLREGs and good seamanship. Hence, Step 8 is used to single out ${\text{VO}}^{\prime}$ with the constraint of COLREGs and good seamanship. Because the ship is an inertial body, every one-second update will be sufficient for the calculation of the overall algorithm. That is, ∆t = 1 s set in the diagram of Fig. 8.

Fig. 8

Flow chart of the feasible course alteration range algorithm

4 The optimal route in each sub-feasible course alteration range

4.1 Resuming normal navigation after collision avoidance

These sub-ranges provide the OS with many choices to take collision avoidance actions. They meet COLREGs and good seamanship, as described in Sect. 3.3. The OS will be collision-free when sailing along with the headings in these sub-ranges. To reach the destination as soon as possible, the OS will resume normal navigation at the appropriate time point to ensure safety after pass and clear all objects.

The following points define what constitutes a “resuming normal navigation”.

How to define the resuming normal navigation after collision avoidance, the following questions can be addressed.

• (1) The OS will resume the originally planned course as early as possible under the premise of safety.

• (2) The OS will return to the planned route as close possible, and the course used will be similar to the originally planned route.

Therefore, to resume “normal navigation” primarily involves choosing an appropriate opportunity in time when the OS alters course to the same course or to a course similar to the original course. The basic ideas for choosing this time point are as follows:

• (1) The OS will be collision-free after resuming normal navigation.

• (2) According to Rule 8 of COLREGs, the course alteration shall be large enough to be readily apparent to another vessel observing, and never be performed if misunderstandings expected.

4.2 Route planning and optimisation

Among all choices meeting the above requirements, there must be an optimal route. An optimal route means the OS will experience the shortest passage distance or time to the next waypoint. The smallest distance of deviation from the original route and the minimum course alteration amplitude are the goals. As introduced in Sect. 3.3, the OS will pass through either ahead or astern of a certain TS when any heading for course in the same sub-range is executed. Assuming the probability of the execution and the occurrence of misunderstanding is evenly distributed within a sub-range, the optimal or nearly optimal route could be easily determined by a simple choice model when the ship is navigating on the open sea areas where traffic is not highly congested and complicated.

According to the experience and knowledge of experts at sea, there are several patterns of route choice to pass and clear TSs and then resume normal navigation. Figure 9 illustrates that four types of routes are normally executed to avoid the TS and resume normal navigation for two typical encounter situations.

Fig. 9

Different routes during collision avoidance actions and resuming normal navigation

Route 1 shows that OS will take the minimum course alteration amplitude and continue straight-line sailing at point A. After passing the target, the OS begins to resume normal navigation at point B. B is the earliest time point for the OS to resume normal navigation. Route 2 shows the same passage as Route 1 at the beginning, but the OS will resume normal navigation sometime later (at point C), where TSs will pass safely after the OS resumes normal navigation. Route 3 shows that the OS will perform a larger course alteration amplitude than Route 1 and Route 2, and continue straight-line sailing at point D. The OS begins to resume normal navigation at point E. E is the earliest time point for the OS to resume normal navigation. Route 4 shows the same passage as Route 3 at the beginning, but the OS will resume normal navigation sometime later (at point F).

Among all the different types of routes above, the OS will experience the shortest passage and spend the least time when it executes collision avoidance actions along Route 1. For each sub feasible course alteration range, the minimum course alteration amplitude is already fixed. The crucial question, how to find an optimal route under these conditions, will change to find the earliest time point, i.e., the earliest time point for the OS to resume normal navigation and to ensure that all TSs pass outside of the domain of the OS. The simplest method is to search every time point at an appropriate interval after collision avoidance actions are completed. For instance, in Fig. 9, the searching process can start at point A and last until the earliest time point (B or the earliest time point after B) is found for which the OS domain is completely clear. The course control system will simulate the course alteration process before A and after B.

5 Case study and discussion

In recent years, the number of studies of different scenarios has been carried out by the authors, such as simulations of two ship encounter in different situations, and three ships or more. Moreover, the model was extended to the situation of static objects with different shapes [39]. To verify the mathematical models and methods presented in this study, an integrated and complicated case was simulated.

5.1 Settings

The initial position of the OS is (0,0) with heading 000° at speed 12 kn. Six TSs, as shown in Table 1, are sailing in the vicinity. Two static objects are set additionally to TSs. The possible course alteration range is set as $\left[-90^\circ \right.,\left.90^\circ \right]$. This case study follows the steps indicated in Sect. 3.3.2, considering COLREGs and good seamanship in the last step. All initial states of the TSs are shown in Table 1.

Table 1 Initial state of TSs and the OS

5.2 Results

The results of the case study are shown in Figs. 10 and 11, respectively.

Fig. 10

The feasible course alteration range

Fig. 11

The optimal route in sub-range 1

As shown in Fig. 10, the three feasible course alteration ranges are $\left[-64^\circ \right.,\left.-56^\circ \right]$, $\left[-17^\circ \right.,\left.-4^\circ \right]$, and $\left[6^\circ \right.,\left.12^\circ \right]$. Course alteration ranges 1 and 2 are the sub-range that meet COLREGs. The OS will be collision-free in the present situation if any course in these ranges is set by the course control system. However, if good seamanship is considered and there is no misunderstanding of target ship 2 and target ship 6, course alteration range 1 is the best choice. Thereafter, the optimal route in range 1 will be calculated. The result is shown in Fig. 11.

5.3 Discussion

Generally, the framework and case study of the collision avoidance mechanism shows success during multi-ship encounters in a complicated environment. The results are explicit to indicate compliance with COLREGs and the conformance of good seamanship. The automatic execution will be helpful to support safe navigation.

As shown in Sect. 3.3.2, the algorithm can be further improved to save the time of calculation. In this section, Step 8 will be placed before Step 1 to reduce the possible course alteration range. For instance, in a multi-ship encounter situation, the most dangerous TS is a stand-on vessel in crossing situations for the OS. Given that collision risk is already involved, the OS should alter course to the starboard side and remain clear of this TS. Collision avoidance actions in which the OS alters course to the port side will violate COLREGs. The calculations of sub-ranges requiring the OS to alter course to the port side will not be needed, and the total calculation is therefore simplified if Step 8 is be placed before Step 1. Hence, the possible course alteration range will be cut down as $\left[5^\circ \right.,\left.90^\circ \right]$. The new result for the same case is shown in Fig. 12. The feasible course alteration range is $\left[6^\circ \right.,\left.12^\circ \right]$. That is the same result as the previous algorithm, so the final optimal route is the same as Fig. 11, but the computation has been substantially reduced by 52.4%.

Fig. 12

The feasible course alteration range with the optimised algorithm

Along with the progress of intelligent ship and smart shipping, this study can be further developed and seamlessly connected to the unmanned vehicle. To outlook automatic collision avoidance in practice, the following research will be performed in the future:

• (1) A digital traffic environment, whose information can be read and executed by a computer programme and which is input via different sources, e.g., the ECDIS (electronic chart display and information system), the AIS, and the ARPA (automatic radar plotting aid), will be established. All necessary information should be treated with data fusion to enhance systemic reliability.

• (2) Automatic collision avoidance decisions with consideration of the TS manoeuvring, which will greatly influence the time of action taken by the OS.

• (3) Moreover, optimal path planning for heavy traffic situations or restricted water areas should be conducted after this study.

6 Conclusions

Automatic collision avoidance and route planning in multi-ship encounter situations is demanding for the current navigation support and will be the hard core of autonomous navigation. Collision avoidance mechanism is the relationship between the variations in the own ship (OS) velocity vector after nonlinear course altering motion and the collision avoidance result, i.e. course alteration. The aim of this study is to present methods for calculating feasible OS course alteration ranges based on the collision avoidance mechanism. Furthermore, the optimal route for multi-ship encounter situations is calculated.

• (1) The static collision avoidance mechanism is presented in accordance with the ship domain and VO theory.

• (2) The dynamic collision avoidance mechanism is based on the static one and OS manoeuvrings. A course control system combined with ship manoeuvring model (MMG Model) and the fuzzy adaptive PID controller is developed to predict the nonlinear variations of the kinematic status (position, velocity, heading, etc.) caused by the OS manoeuvrings. Finally, the dynamic ranges of course alteration for collision-free are proposed.

• (3) Finally, the route caused by the course alteration within the ranges is optimized to keep clear of all objects and resume the normal navigation.

Verified by the case study, COLREGs and good seamanship are fully considered, and the proposed methods to calculate the feasible course alteration range and optimal route are logical and conform to navigation experience. Since all the processes can be executed automatically by computer, the proposed methods are applicable to support ship navigation under multi-object environments on the open sea. In the future application, shallow water banks, islands and other obstructions in the complicated sea area can be transformed into static objects to build a digital traffic environment. The theories and methods presented in this paper can be extended for autonomous navigation.

7 Appendix 1: List of variables

See Table 2.

Table 2 Glossary of abbreviations and variables

8 Appendix 2: Prototype ship and simulation

The Prototype ship is the M/V HUAYANG DREAM, which is a Panamax size bulk carrier. Table 3 shows the ship’s particulars. The corresponding author served as the Captain of this ship from January 15, 2014, to July 28, 2014. A comparison of the turning cycles is shown in Figs. 13 and 14. A comparison of speed performance between the numerical model and the real ship is shown in Fig. 15.

Table 3 Ship’s particulars

Fig. 13

turning cycle (MMG model)

Fig. 14

Turning cycle (full scale test)

Fig. 15

Speed and RPM

While there were some differences between the real ship and MMG model, for open sea the accuracy of the model was deemed to be acceptable.