Local Route Planning for Collision Avoidance of Maritime Autonomous Surface Ships in Compliance with COLREGs Rules

Abstract

A maritime autonomous surface ship (MASS) ensures safety and effectiveness during navigation using its ability to prevent collisions with a nearby target ship (TS). This avoids the loss of human life and property. Therefore, collision avoidance of MASSs has been actively researched recently. However, previous studies did not consider all factors crucial to collision avoidance in compliance with the International Regulations for Preventing Collisions at Sea (COLREGs) Rules 5, 7, 8, and 13–17. In this study, a local route-planning algorithm that takes collision-avoidance actions in compliance with COLREGs Rules using a fuzzy inference system based on near-collision (FIS-NC), ship domain (SD), and velocity obstacle (VO) is proposed. FIS-NC is used to infer the collision risk index (CRI) and determine the time point for collision avoidance. Following this, I extended the VO using the SD to secure the minimum safe distance between the MASS and the TS when they pass each other. Unlike previous methods, the proposed algorithm can be used to perform safe and efficient navigation in terms of near-collision accidents, inferred CRI, and deviation from the course angle route by taking collision-avoidance actions in compliance with COLREGs Rules 5, 7, 8, and 13–17.

1. Introduction

The Korea Maritime Safety Tribunal (KMST) has found that approximately 85% of marine accidents are caused by human error [1]. This finding indicates that removing human involvement may be beneficial for maritime safety. For example, a maritime autonomous surface ship (MASS) could improve maritime safety. Therefore, MASSs with various degrees of autonomy (ranging from one to four) are being developed for maritime transportation [2].

One of the most critical features of a MASS is its ability to prevent collisions with nearby obstacles during navigation. This is because collisions can cause structural hazards, loss of human life and property, and ocean pollution due to oil and cargo spills. Nonetheless, over the past five years, approximately 95% of all collisions in South Korea [1] occurred as a result of a failure to comply with the International Regulations for Preventing Collisions at Sea (COLREGs) [3]. Therefore, route planning with collision avoidance in compliance with COLREGs is essential to prevent the collision of a fully autonomous MASS.

In this regard, route planning can be global or local [4]. In global route planning, a MASS finds all spaces where obstacles exist on a given map in advance to choose an obstacle-free route. By contrast, in local route planning, a MASS generates a collision-free route in real time by dynamically responding to the environment, including to obstacles. Specifically in local route planning, unlike in global route planning, the MASS can deviate from its planned route or change its speed and must, therefore, comply with COLREGs to avoid all obstacles safely unless exceptional circumstances occur.

“A Guide to the Collision Avoidance Rules” [5] comprehensively examines the core COLREGs Rules through various precedents and expert discussions. In keeping with this guide, a collision avoidance process on the basis of COLREGs Rules 5, 7, 8, and 13–17 was proposed, as shown in Figure A1. First, in accordance with Rule 5, a vessel shall perform appropriate observations to ensure that the present situation and collision risk are fully assessed using all available means appropriate to the given circumstances and conditions. Second, in accordance with Rule 7, the collision risk shall be identified by considering radar plotting or equivalent systematic observations as well as the compass bearing change of an approaching vessel. Third, in accordance with Rules 13–15, the encounter type shall be determined if a collision risk exists. Finally, if a vessel is subject to Rule 16 for determining an encounter type, Rule 8 shall be followed early to avoid collision with the target ship (TS) at a safe distance through course and/or speed alterations. However, for a stand-on vessel, in accordance with Rule 17, a collision risk is determined to exist in accordance with Rule 7. If the actions of a give-way vessel eliminate the collision risk, the present course and speed shall be maintained; otherwise, a collision-avoidance action in accordance with Rule 8 shall be taken.

Table A1. Comparison and analysis of representative local route-planning algorithms.

Algorithm	Reference	Rule 5	Rule 7		Rule 13	Rule 14	Rule 15	Rule 16	Rule 17	Rule 8
			Available Means							Alteration of Course	Alteration of Speed	Safe Distance	Avoiding Multi-Vessels
			Radar Plotting	Changing of Compass Bearing
Genetic algorithm (GA)	[24]	√	√	-	√	√	√	√	-	√	-	√	-
Evolutionary algorithm	[25]	√	√	-	√	√	√	√	√	√	-	√	√
Fuzzy logic	[26]	√	√	-	√	√	√	√	-	√	√	√	-
Fuzzy logic + A*	[23]	√	√	-	√	√	√	√	√	√	-	√	√
Ant colony optimization (ACO)	[27]	√	√	-	√	√	√	√	√	√	-	√	√
Multi-objective particle swarm optimization (PSO)	[28]	√	√	-	√	√	√	√	-	√	-	√	√
Velocity obstacle (VO)	[7]	√	√	-	√	√	√	√	-	√	√	√	√
Optimal reciprocal collision avoidance (ORCA)	[6]	√	√	-	√	√	√	√	√	√	√	√	√
Dynamic reciprocal VO	[8]	√	√	-	√	√	√	√	-	√	√	√	√
Nonlinear VO	[9]	√	√	-	√	√	√	√	-	√	√	√	√
Generalized VO	[10]	√	√	-	√	√	√	√	-	√	√	√	√
Nonlinear VO for stand-on vessels	[11]	√	√	-	√	√	√	-	√	√	√	√	√
Artificial potential field (APF)	[29]	√	√	-	√	√	√	√	-	√	-	√	√
COLREGs-constrained APF	[30]	√	√	-	√	√	√	√	-	√	-	√	√
Deep reinforcement learning	[31]	√	√	-	√	√	√	√	√	√	-	√	√
Deep Q-learning	[32]	√	√	-	√	√	√	√	√	√	-	√	√

lists representative local route-planning algorithms for the MASS in avoiding collisions. It was identified whether these algorithms comply with COLREGs Rules for collision avoidance as proposed [5]. All algorithms were found not to comply with the compass bearing change of an approaching vessel in accordance with Rule 7. The algorithm presented by [6] satisfied all Rules except Rule 7. However, there are two significant issues. First, if the stand-on vessel is the cause of constant collision risk, a collision-avoidance action in accordance with Rule 17 can be taken; however, the time point for this collision avoidance was not defined. Second, assuming the lengths of the MASS and TS to be the diameter, the velocity obstacle (VO) [6,7,8,9,10,11] combines the radii of the MASS and TS to formulate a circle for creating a cone-shaped danger zone. However, because this circle is smaller than the ship domain (SD), where no TS exists for preventing collision, the collision-avoidance action is taken with a collision risk always existing with no minimum safe distance being secured. In this light, in the present study, a local route-planning algorithm was developed based on the situational awareness (SA) model [12] using a fuzzy inference system based on near-collision (FIS-NC) [13], SD, and VO to ensure that a MASS complies with all essential collision-avoidance requirements based on the COLREGs Rules proposed [5] and also solves the problems of existing algorithms analyzed herein.

The remainder of this paper is organized as follows. Section 2 presents the necessary theoretical background. Section 3 uses the SA model to discuss the local route-planning algorithm based on FIS-NC, SD, and VO for collision avoidance in compliance with the COLREGs Rules. Section 4 presents MATLAB computational simulation results and the discussions. Finally, Section 5 presents the conclusions of this study.

2. Theoretical Background

2.1. Closest Point of Approach

The closest point of approach (CPA) is the point where the MASS is closest to the TS at any time. Let the coordinate, course, and velocity of the MASS be $(x_{o,}{y}_o)$, ${\varphi }_o$, and $V_o$, respectively, and those of the TS be $(x_{t,}{y}_t)$, ${\varphi }_t$, and $V_t$, respectively. Then, the time until the CPA and the distance between the MASS and TS at the CPA are calculated using an automatic radar plotting aid (ARPA) and an automatic identification system (AIS) equipped in all cargo vessels, as follows:

$$D_r=\sqrt{{(x_t-x_o)}^2+{(y_t-y_o)}^2}$$

(1)

$$V_r=V_o\times \sqrt{1+{\left(\frac{V_t}{V_o}\right)}^2-2\times \frac{V_t}{V_o}\times \cos ({\varphi }_o-{\varphi }_t)}$$

(2)

$${\varphi }_r={\cos }^{-1}\times \left(\frac{V_o-V_t\times \cos ({\varphi }_o-{\varphi }_t)}{V_r}\right)$$

(3)

$$T_{CPA}=D_r\times \cos \left({\varphi }_r-{\alpha }_t-\pi \right)/V_r$$

(4)

$$D_{CPA}=D_r\times \sin \left({\varphi }_r-{\alpha }_t-\pi \right)$$

(5)

where $D_r$ is the relative distance between the MASS and the TS, $V_r$ the relative velocity, ${\varphi }_r$ the relative course, ${\alpha }_t$ the azimuth of the TS, and ${\alpha }_r$ the relative bearing. T_CPA is the time to the CPA, and D_CPA is the distance between the MASS and the TS at that time. T_CPA can be zero, positive, or negative, and D_CPA can only be zero or positive. The closer both T_CPA and D_CPA are to zero, the higher the collision risk. A negative T_CPA means that the D_CPA has already passed, that is, the vessels are moving away from each other after the closest state. Figure 1 shows an illustration of the CPA.

Following this, the variance of compass degree (VCD) [14] is calculated as

$$VC{D}_i=\left|{\alpha }_{r_i}-{\alpha }_{r_{i-1}}\right|$$

(6)

where $i$ is the current time. At this point in time, the collision risk is high when VCD approaches 0.

2.2. FIS-NC

In fuzzy logic, fuzzy IF-THEN rules are used to formulate conditional statements. Figure 2 shows the inference process of the FIS-NC proposed by [13].

In the first step, inputs including D_CPA, T_CPA, VCD, and $D_r$ were collected using ARPA and AIS, and the degree to which these inputs belong to each of the appropriate fuzzy sets was determined. In the second step, the fuzzified inputs were applied to the antecedents of fuzzy rules. This result was then applied to the consequent membership function ($f$). In the third step, aggregation was performed to unify the outputs of all rules. In the last step, the input for the defuzzification process was the aggregated output fuzzy set, and the output was calculated as the collision risk index (CRI) using the weighted average function ($\widehat{f}$).

CRI ranged from 0.00 to 1.00 [13], and the time point for collision avoidance was as follows: the give-way vessel shall take a collision-avoidance action for CRI ≥ 0.01, and the stand-on vessel shall take a collision-avoidance action for CRI ≥ 0.33.

2.3. SD

The SD is a generalized safe distance area that requires the maintenance of a situation without a TS or an obstacle. This concept was introduced for preventing collisions. However, because various SDs can exist, the size and shape of the SD must be selected in keeping with what is most suitable for vessel operation [15]. After analyzing the size and shape of SDs based on AIS sea traffic data for 4 years [16], the most suitable ones for vessel operation were found to be those where the long diameter proposed by [17] was equal to a long radius of 4$L$ and short radius of 1.6$L$ (where $L$ is the vessel length). The elliptical SD proposed by [17] is shown in Figure 3 and given by Equations (7)–(11).

The elliptical SD of the MASS parallel to the x-axis at position $(x_o,y_o)$ is calculated as

$$\frac{{(x-x_o)}^2}{{(a_o\times L_o)}^2}+\frac{{(y-y_o)}^2}{{(b_o\times L_o)}^2}=1$$

(7)

where $L_o$ is the length of the MASS, and $a_o$ and $b_o$ are the long and short radii, respectively.

The location of the elliptical SD may change depending on the route of the MASS. Therefore, an elliptical SD rotation consistent with the MASS’s course is required. In Equation (7), the coordinates $(x,y)$ are rotated to $(x’,y’)$ to match the angle ${\varphi }_o$ between the long radius $a_o$ and the $y$-axis. Equations (8) and (9) provide the changed coordinates of the elliptical SD:

$$x’=x\times \cos {\theta }_o-y\times \sin {\theta }_o$$

(8)

$$y’=x\times \sin {\theta }_o+y\times \cos {\theta }_o$$

(9)

In these equations, the angle of intersection (${\theta }_o$) in the heading direction of the MASS for the long radius $a_o$ and x-axis is determined using the angle ${\varphi }_o$, as shown in Equation (10). The coordinates $(x,y)$ in Equation (7) are substituted with the coordinates $(x’,y’)$ to obtain the rotated elliptical SD, as given by Equation (11).

$${\theta }_o=\{\begin{array}{cc}\left|{90}^{\circ }-{\varphi }_o\right|& i{f}_{}{\varphi }_o\le {180}^{\circ }\\ \left|{270}^{\circ }-{\varphi }_o\right|& i{f}_{}{\varphi }_o>{180}^{\circ }\end{array}$$

(10)

$$\frac{{(x’-x_o)}^2}{{(a_o\times L_o)}^2}+\frac{{(y’-y_o)}^2}{{(b_o\times L_o)}^2}=1$$

(11)

However, the SD proposed by [17] had a static shape and size regardless of the change in vessel velocity. Therefore, Namgung and Kim [13] theoretically analyzed the SD proposed by [17] and [18] to obtain an SD using the length and speed of the MASS as parameters. They calculated the long radius $a_o$ and short radius $b_o$ of the SD using Equations (12) and (13), respectively, for each 0.1 $\mathrm{kt}$ velocity change.

$$a_o=\{\begin{array}{cc}\frac{8L_o-\left(\frac{(V_{10\mathrm{kt}}-V_o)\times 0.06}{0.1\mathrm{kt}}\right)}{2}& i{f}_{}{V}_o\le V_{10kt}\\ \frac{8L_o+\left(\frac{(V_o-V_{10\mathrm{kt}})\times 0.06}{0.1\mathrm{kt}}\right)}{2}& i{f}_{}{V}_o>V_{10kt}\end{array}$$

(12)

$$b_o=\{\begin{array}{cc}\frac{3.2L_o-\left(\frac{(V_{10\mathrm{kt}}-V_o)\times 0.028}{0.1\mathrm{kt}}\right)}{2}& i{f}_{}{V}_o\le V_{10kt}\\ \frac{3.2L_o+\left(\frac{(V_o-V_{10\mathrm{kt}})\times 0.028}{0.1\mathrm{kt}}\right)}{2}& i{f}_{}{V}_o>V_{10kt}\end{array}$$

(13)

where $V_{10\mathrm{kt}}$ is 10 $\mathrm{kt}$.

2.4. VO

The VO [19] for a vessel is the set of velocities for which it will collide with another vessel (i.e., obstacle) at some time in the future as long as both vessels keep a constant velocity. The VO collision-avoidance method aims to determine velocities that should be avoided to prevent any future collisions.

The VO for an ‘O’-shaped MASS [7] with respect to a ‘T’-shaped TS is given as

$$V{O}_T^O(V_t)=\left\{V_o|\lambda (P_o,V_o-V_t)\cap (T\oplus -O)\ne \varnothing \right\}$$

(14)

where $P_o$ is the position vector of the MASS, and $V_o$ and $V_t$ are the velocity of the MASS and TS, respectively. A ray starting at $P$ and going in the $V$-direction is expressed as

$$\lambda (P,V)=\left\{P+\tau V|\tau \ge 0\right\}$$

(15)

where $\tau$ is time.

Equation (14) uses the following set operation:

$$\mathit{Minkowski}\mathit{sum}:O\oplus T=\left\{o+t|o\in O,t\in T\right\}$$

(16)

$$\mathit{Reflection}\mathit{sum}:-O=\left\{-o|o\in O\right\}$$

By assuming that that both the MASS and the TS are circular, Equation (14) can be simplified as

$$V{O}_T^O(V_t)=\left\{V_o|\lambda (P_o,V_o-V_t)\in D(P_{ot},r_{ot})\right\}$$

(17)

where $D(P_{ot},r_{ot})$ is a circle with center $P_{ot}$ and radius $r_{ot}$. At this time, $r_{ot}$ is aggregated with the radius $r_o$ of $L_o$ and the radius $r_t$ of the TS length $L_t$ as

$$r_{ot}=\frac{L_o}{2}+\frac{L_t}{2}$$

(18)

The VO for a vessel with a TS present is represented by a cone-shaped danger zone in the velocity space (i.e., VO cone), as shown in Figure 4.

As long as the vessel maintains a velocity outside the VO cone and assuming that the velocity vectors are constant over time, it will not collide with the TS. At this time, a TS close to the MASS will produce a wide cone whereas one that is further away will produce a narrower cone.

The velocity space can be divided into four different regions $V{O}_{O|T}$, $V_1$, $V_2$, and $V_3$, where

$$V_1=\left\{V_o|V_o\notin V{O}_T^O(V_t)\cup V_3\wedge \left[P_{ot}\times (V_o-V_t)\right]<0\right\}$$

(19)

$$V_2=\left\{V_o|V_o\notin V_1\cup V_3\cup V{O}_T^O(V_t)\right\}$$

(20)

$$V_3=\left\{V_o|P_{ot}•(V_o-V_t)<0\right\}$$

(21)

If a velocity within $V{O}_{O|T}$ is chosen, the MASS will collide with the TS at some time in the future. If velocity of $V_1$, $V_2$, or $V_3$ is chosen, the MASS will pass the TS on the port or starboard side, or it will move away from the TS.

3. Local Route Planning Using Collision Avoidance in Compliance with COLREGs Rules

3.1. Determination of Encounter Type

The collision-avoidance actions for the give-way and stand-on vessels are determined for overtaking, head-on, and crossing situations according to COLREGs Rules 13–17, as shown in Figure 5 and Figure 6.

• Overtaking: For an overtaking situation, the vessel being overtaken should keep a steady speed and course. COLREGs Rule 13 allows the overtaking vessel to pass the other vessel on either side, as shown in Figure 6a.
• Head-on situation: For a head-on situation, both vessels should take collision-avoidance actions by changing their course to the starboard, as shown in Figure 6b.
• Crossing situation: When crossing from either port or starboard, the vessel which has the other vessel on its starboard side is considered the give-way vessel, and it should alter its course so that it passes behind the other vessel. The other vessel should keep a steady speed and course, as shown in Figure 6c.

However, because COLREGs Rules 13–15 only determine encounter types using ${\alpha }_r$ on the sector, as shown in Figure 6, unnecessary actions may be taken by a TS that does not approach the MASS.

Therefore, [20,21,22] determined encounter types using ${\alpha }_r$, ${\varphi }_o$, and ${\varphi }_t$.

Table 1. Existing methods for determination of encounter types.

Division	[20]	[21]	[22]
Parameter	${\alpha }_r$$,{\varphi }_o$$,{\varphi }_t$	${\alpha }_r$$,{\varphi }_o$$,{\varphi }_t$$,{\varphi }_e$	${\alpha }_r$$,{\varphi }_o$$,{\varphi }_t$
Sector	6	6	4
Encounter type	Head-on Overtaking Stand-on Safe Give-way	Head-on Crossing (give-way) Crossing (quarter lee give-way) Crossing (stand-on) Crossing (quarter lee stand-on) Overtaking Being overtaken	Head-on Overtaking Crossing
Head-on range	${337.5}^{\circ }\le {\alpha }_r\le {22.5}^{\circ }$	${348.75}^{\circ }\le {\alpha }_r\le {11.25}^{\circ }$	${355}^{\circ }\le {\alpha }_r\le {005}^{\circ }$
Interpretation type	Figure	Figure	IF-THEN

shows a comparative analysis of these methods.

Here, ${\varphi }_e$ is the encounter angle, as shown in Figure 7 and given by Equation (22). If ${\varphi }_e$ is negative, 360° is added in Equation (22).

$${\varphi }_e={\varphi }_t-{\varphi }_o-\pi$$

(22)

Existing methods have their own characteristics, as listed in

Table 2. Characteristics of existing methods.

Characteristics	[20]	[21]	[22]
(a) Does a safe sector exist to avoid taking an unnecessary action?	Yes	No	No
(b) Are both the overtaking vessel and the vessel being overtaken classified as the overtaking vessel?	Yes	No	Yes
(c) Are a give-way vessel and a stand-on vessel classified as the overtaking vessel in a crossing (quarter lee) situation?	Yes	No	Yes
(d) Can the MASS understand the present interpretation type?	No	No	Yes

. In the present study, the encounter type was determined by combining these characteristics based on the method proposed by [21], as shown in

Table 3. Determination method of encounter type.

Division	Characteristic
Parameter	${\alpha }_r$$,{\varphi }_o$$,{\varphi }_t$$,{\varphi }_e$
Sector	6
Encounter type	Head-on Crossing (give-way) Crossing (quarterlee give-way) Crossing (stand-on) Crossing (quarterlee stand-on) Overtaking Being overtaken Safe
Head-on range	${348.75}^{\circ }\le {\alpha }_r\le {11.25}^{\circ }$
Interpretation type	Figure, IF-THEN

. This is because the determination of the encounter type in overtaking and crossing situations can be distinguished by the circumstances, as shown in Table 2 (b) and (c).

Figure 8 shows the determination of the encounter type based on Table 3. A sector is divided into six parts, with the range of sector angles being $\left\{{11.25}^{\circ },{67.5}^{\circ },{112.5}^{\circ },{247.5}^{\circ },{292.5}^{\circ },{348.75}^{\circ }\right\}$. The circle in each sector indicates the encounter type determined by ${\varphi }_e$.

Algorithm 1 shows the determination of the encounter type between the MASS and the TS based on Figure 8. This process can largely be divided into two parts. First, if a collision risk exists, the MASS shall identify where the TS is located in the sector using ${\alpha }_r$. Second, the encounter type between the MASS and the TS is determined by ${\varphi }_e$ in the identified sector.

Algorithm 1. Determination of Encounter Type Between MASS and TS.

Input: ${\alpha }_r$, ${\varphi }_e$ Output: Encounter type $E_r$ 1  while collision risk exists 2    if TS is in ‘Sector Ⅰ’ determined with ${\alpha }_r$ then 3      if (${\varphi }_e{}_{}{\ge }_{}{348.75}^{\circ }$) and (${360}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) or (${\varphi }_e{}_{}{\ge }_{}{000}^{\circ }$) and (${11.25}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 4      decide $E_r$ ← head-on situation of MASS 5      else if (${\varphi }_e{}_{}{>}_{}{11.25}^{\circ }$) and (${112.5}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 6      decide $E_r$ ← crossing situation (give-way) of MASS 7      else if (${\varphi }_e{}_{}{\ge }_{}{112.5}^{\circ }$) and (${247.5}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 8      decide $E_r$ ← overtaking situation (overtaking) of MASS 9      else if (${\varphi }_e{}_{}{>}_{}{247.5}^{\circ }$) and (${348.75}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 10      decide $E_r$ ← crossing situation (stand-on) of MASS 11   else if TS is in ‘Sector Ⅱ’ determined with ${\alpha }_r$ then 12      if (${\varphi }_e{}_{}{>}_{}{11.25}^{\circ }$) and (${112.5}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 13      decide $E_r$ ← crossing situation (give-way) of MASS 14      else if (${\varphi }_e{}_{}{\ge }_{}{112.5}^{\circ }$) and (${180}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 15      decide $E_r$ ← overtaking situation (overtaking) of MASS 16      else if (${\varphi }_e{}_{}{>}_{}{180}^{\circ }$) and (${360}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) or (${\varphi }_e{}_{}{\ge }_{}{000}^{\circ }$) and (${11.25}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 17      decide $E_r$ ← safe (keep a steady speed and course) of MASS 18   else if TS is in ‘Sector Ⅲ’ determined with ${\alpha }_r$ then 19      if (${\varphi }_e{}_{}{>}_{}{11.25}^{\circ }$) and (${135}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 20      decide $E_r$ ← crossing situation (give-way) of MASS 21      else if (${\varphi }_e{}_{}{>}_{}{135}^{\circ }$) and (${180}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 22      decide $E_r$ ← crossing situation (quarter lee give-way) of MASS 23      else if (${\varphi }_e{}_{}{\ge }_{}{180}^{\circ }$) and (${360}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) or (${\varphi }_e{}_{}{\ge }_{}{000}^{\circ }$) and (${11.25}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 24      decide $E_r$ ← safe (keep a steady speed and course) of MASS 25   else if TS is in ‘Sector Ⅳ’ determined with ${\alpha }_r$ then 26      else if (${\varphi }_e{}_{}{\ge }_{}{112.5}^{\circ }$) and (${247.5}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 27      decide $E_r$ ← overtaking situation (being overtaken) of MASS 28      else if (${\varphi }_e{}_{}{>}_{}{247.5}^{\circ }$) and (${360}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) or (${\varphi }_e{}_{}{\ge }_{}{000}^{\circ }$) and (${112.5}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 29      decide $E_r$ ← safe (keep a steady speed and course) of MASS 30   else if TS is in ‘Sector Ⅴ’ determined with ${\alpha }_r$ then 31      if (${\varphi }_e{}_{}{>}_{}{180}^{\circ }$) and (${225}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 32      decide $E_r$ ← crossing situation (quarter lee stand-on) of MASS 33      else if (${\varphi }_e{}_{}{\ge }_{}{225}^{\circ }$) and (${348.75}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 34      decide $E_r$ ← crossing situation (stand-on) of MASS 35      else if (${\varphi }_e{}_{}{\ge }_{}{348.75}^{\circ }$) and (${360}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) or (${\varphi }_e{}_{}{\ge }_{}{000}^{\circ }$) and (${180}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 36      decide $E_r$ ← safe (keep a steady speed and course) of MASS 37   else if TS is in ‘Sector Ⅵ’ determined with ${\alpha }_r$ then 38      else if (${\varphi }_e{}_{}{>}_{}{247.5}^{\circ }$) and (${348.75}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 39      decide $E_r$ ← crossing situation (stand-on) of MASS 40      else if (${\varphi }_e{}_{}{\ge }_{}{180}^{\circ }$) and (${247.5}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) then 41      decide $E_r$ ← overtaking situation (overtaking) of MASS 42      else if (${\varphi }_e{}_{}{\ge }_{}{348.75}^{\circ }$) and (${360}^{\circ }{}_{}{\ge }_{}{\varphi }_e$) or (${\varphi }_e{}_{}{\ge }_{}{000}^{\circ }$) and (${180}^{\circ }{}_{}{>}_{}{\varphi }_e$) then 43      decide $E_r$ ← safe (keep a steady speed and course) of MASS 44   end 45  end

3.2. Collision-Avoidance Action Based on VO Using SD

According to the encounter type, the collision-avoidance action using $V{O}_T^O(V_t)$ based on $r_{ot}$ can be expressed as shown in Figure 9.

In this figure, the beige-shaded area is the cone-shaped danger zone of $V{O}_T^O(V_t)$.

Figure 10 shows a comparison of the size of the SD proposed by [13] and the size of the circle using $r_{ot}$, with both the MASS and the TS sail at 10 $\mathrm{kt}$.

At this time, to represent a cone-shaped danger zone, the sizes of the SDs of the MASS and TS were added as shown in Equation (23):

$$\{\begin{array}{c}{A}_{ot}=(a_o+a_t)\times 2=(L_o+L_t)\times 8\\ B_{ot}=(b_o+b_t)\times 2=(L_o+L_t)\times 3.2\end{array}$$

(23)

where $a_t$ and $b_t$ are the long radius and short radius of the TS, respectively, and $A_{ot}$ and $B_{ot}$ are the long radius and short radius of the added SD of the MASS and TS.

The size comparison indicated that the $r_{ot}$-based circle was $1/8$ times the long diameter and $1/3.2$ times the short diameter of the added SD of the MASS and TS. In other words, VO using the $r_{ot}$-based circle always causes a collision-avoidance action with a collision risk with no minimum safe distance being secured. Thus, a minimum safe distance was secured by creating $V{O}_T^O(V_t)$ based on the $S{D}_{ot}$ using Equation (23) instead of $r_{ot}$, as shown in Equation (24) and Figure 11.

$$SDV{O}_T^O(V_t)=\left\{V_o|\lambda (P_o,V_o-V_t)\in D(P_{ot},S{D}_{ot})\right\}$$

(24)

3.3. Development of Local Route-Planning Algorithm

SA [12] can be defined as the detection of continuous changes to the surrounding environment, the understanding of what is happening, and the prediction of what will happen in the near future based on the current state—it focuses on the selection, processing, transmission, and utilization of information from a changing environment. Reference [12] proposed the following three-step approach for the SA:

• Perception (Level 1 SA): The first step in achieving SA is to perceive the status, attributes, and dynamics of relevant elements in the environment. Specifically, Level 1 SA involves monitoring, cue detection, and simple recognition processes which lead to an awareness of multiple situational elements (e.g., objects, events, people, systems, environmental factors) and their current states (e.g., locations, conditions, modes, actions).
• Comprehension (Level 2 SA): The next step in achieving SA involves synthesizing disjointed Level 1 SA elements through pattern recognition, interpretation, and evaluation processes. Level 2 SA involves integrating this information to understand how it will impact upon the individual’s goals and objectives.
• Projection (Level 3 SA): The third step in achieving SA is projecting the future actions of the elements in the environment. Level 3 SA involves extrapolating information about the status and dynamics of the elements and comprehension of the situation (Levels 1 and 2 SA) forward in time to determine how it will affect future states of the operational environment.

Figure 12 shows the local route-planning procedure of the MASS based on SA.

In the perception step, the D_CPA, T_CPA, VCD, and $D_r$ between the MASS and the TS were collected using ARPA and AIS. In the comprehension step, if T_CPA is 0 or more, and the CRI inferred using FIS-NC is 0.01 or more, the MASS determines the encounter type based on Algorithm 1. In the projection step, a collision-avoidance action is taken with $SDV{O}_T^O(V_t)$ in head-on, crossing (give-way, including quarter lee give-way), and overtaking (overtaking) situations. In particular, if the inferred CRI in the crossing situation (stand-on, including quarter lee stand-on) is less than 0.33, the MASS keeps a steady speed and course; however, if it is 0.33 or more, the MASS takes a collision-avoidance action with $SDV{O}_T^O(V_t)$. In all other cases, the MASS keeps a steady speed and course.

As a result, the local route-planning algorithm for the MASS was developed as follows (Algorithm 2):

Algorithm 2. Local Route Planning.

Input: $T_{CPA}$, $CRI$, $E_r$, $P_o$, $P_{ot}$, $V_o$, $V_t$, $S{D}_{ot}$ Output: $SDV{O}_T^O(V_t)$ 1 Initialize $SDV{O}_T^O(V_t)=\varnothing$ ← keep a steady speed and course 2    while $T_{CPA}{}_{}{\ge }_{}0$ and $CR{I}_{}{\ge }_{}0.01$ do 3      if $E_r$ ← head-on situation of MASS ║ crossing situation (give-way) of MASS ║ crossing situation (quarter lee give-way) of MASS then 4      $SDV{O}_T^O(V_t)=\left\{V_o|\lambda (P_o,V_o-V_t)\in D(P_{ot},S{D}_{ot})\right\}$ 5      choose $V_2=\left\{V_o|V_o\notin V_1\cup V_3\cup SDV{O}_T^O(V_t)\right\}$ ← alter course to starboard 6      else if $E_r$ ← crossing situation (stand-on) of MASS ║ crossing situation (quarter lee stand-on) of MASS then 7      if $CR{I}_{}{\ge }_{}0.33$ then 8      $SDV{O}_T^O(V_t)=\left\{V_o|\lambda (P_o,V_o-V_t)\in D(P_{ot},S{D}_{ot})\right\}$ 9      choose $V_2=\left\{V_o|V_o\notin V_1\cup V_3\cup SDV{O}_T^O(V_t)\right\}$ ← alter course to starboard 10      else 11      $SDV{O}_T^O(V_t)=\varnothing$ ← keep a steady speed and course 12      end 13    else, if $E_r$ ← overtaking situation (overtaking) of MASS then 14      $SDV{O}_T^O(V_t)=\left\{V_o|\lambda (P_o,V_o-V_t)\in D(P_{ot},S{D}_{ot})\right\}$ 15      choose $V_1=\left\{V_o|V_o\notin SDV{O}_T^O(V_t)\cup V_3\wedge \left[P_{ot}\times (V_o-V_t)\right]<0\right\}$ ← alter course to port ║ $V_2=\left\{V_o|V_o\notin V_1\cup V_3\cup SDV{O}_T^O(V_t)\right\}$ ← alter course to starboard 16    else if $E_r$ ← overtaking situation (being overtaken) of MASS ║ safe situation of MASS then 17    $SDV{O}_T^O(V_t)=\varnothing$ ← keep a steady speed and course 18    end 19   end 20  end

4. Results and Discussion

4.1. Simulation Results

The performance of the local route-planning algorithm developed in Section 3.3 is validated for the collision avoidance of the MASS. This algorithm is referred to as SDVO + FIS-NC because it takes a collision-avoidance action based on the FIS-NC and $SDV{O}_T^O(V_t)$. First, SDVO + FIS-NC and existing local route-planning algorithms were applied and compared in each encounter type for a single vessel. Two existing algorithms were selected for this purpose: the A^* exploration-based local route-planning algorithm using the FIS [23] and the VO-based local route-planning algorithm using fuzzy comprehension evaluation (VO + FCE) [6] for taking collision-avoidance actions at a suitable time point based on fuzzy logic. Second, whether the MASS with SDVO + FIS-NC properly took collision-avoidance actions in more complex encounter types with multiple vessels was analyzed. At this point, the time of return to the way point after the collision-avoidance action was regarded as being when the negative TCPA occurred.

4.1.1. Avoiding Single Vessel

The head-on, crossing (give-way and stand-on), and overtaking encounter types with a single vessel were tested.

Table 4. Initial conditions of mass and TS for single encounter type.

${\mathit{E}}_{\mathit{r}}$	Vessel	$\mathit{\varphi }$	$\mathit{V}$	${\mathit{D}}_{\mathit{r}}$	$\mathit{L}$
Head-on	MASS	000°	10 $\mathrm{kt}$	8 $\mathrm{nm}$	172 m
	TS	180°	10 $\mathrm{kt}$	8 $\mathrm{nm}$	172 m
Crossing (give-way)	MASS	000°	10 $\mathrm{kt}$	5.1 $\mathrm{nm}$	172 m
	TS	270°	10 $\mathrm{kt}$	5.1 $\mathrm{nm}$	172 m
Crossing (stand-on)	MASS	000°	10 $\mathrm{kt}$	5.1 $\mathrm{nm}$	172 m
	TS	090°	10 $\mathrm{kt}$	5.1 $\mathrm{nm}$	172 m
Overtaking	MASS	000°	10 $\mathrm{kt}$	3 $\mathrm{nm}$	172 m
	TS	000°	5 $\mathrm{kt}$	3 $\mathrm{nm}$	172 m

shows the initial conditions of the MASS and TS.

Figure 13, Figure 14, Figure 15 and Figure 16 show that the MASS takes collision-avoidance actions upon approaching the TS by applying FIS, VO + FCE, and SDVO + FIS-NC in the different encounter types according to Table 4. The MASS applied each local route-planning algorithm to the generated local route in real time by determining the time point for collision avoidance according to the CRI, encounter type, and collision-avoidance action. The time point for collision avoidance with VO + FCE was not defined for crossing (stand-on), and therefore, it is excluded in Figure 15.

Table 5. Response distance and course angle when CRI is equaled or exceeded.

${\mathit{E}}_{\mathit{r}}$	Algorithm	Criteria CRI	${\mathit{D}}_{\mathit{r}}$	Response Distance	Course Angle
Head-on	FIS	0.60	$2.6\mathrm{nm}$	$2.64\mathrm{nm}$	050.3°
	VO + FCE	0.50	$3.5\mathrm{nm}$	$2.11\mathrm{nm}$	010.5°
	SDVO + FIS-NC	0.01	$3.5\mathrm{nm}$	$2.11\mathrm{nm}$	011.5°
Crossing (give-way)	FIS	0.60	$2.1\mathrm{nm}$	$2.31\mathrm{nm}$	066.7°
	VO + FCE	0.50	$1.7\mathrm{nm}$	$2.55\mathrm{nm}$	026.1°
	SDVO + FIS-NC	0.01	$3.1\mathrm{nm}$	$1.81\mathrm{nm}$	027.3°
Crossing (stand-on)	FIS	0.80	$0.8\mathrm{nm}$	$3.59\mathrm{nm}$	015.1°
	SDVO + FIS-NC	0.33	$2.1\mathrm{nm}$	$2.72\mathrm{nm}$	019.2°
Overtaking	FIS	0.60	$1.4\mathrm{nm}$	$2.38\mathrm{nm}$	030.8°
	VO + FCE	0.50	$1.4\mathrm{nm}$	$1.95\mathrm{nm}$	008.4°
	SDVO + FIS-NC	0.01	$2.7\mathrm{nm}$	$0.31\mathrm{nm}$	006.1°

shows the margin $D_r$, response distance, and course angle for collision avoidance at the coordinates when the criteria CRI of each algorithm were equaled or exceeded for give-way and stand-on vessels according to the encounter type. At this time, the response distance and course angle for the collision avoidance begin from 0 at coordinates $x,y$.

Table 6. Distance, course angle to way point, and margin $D_r$ at the return timing.

${\mathit{E}}_{\mathit{r}}$	Algorithm	${\mathit{D}}_{\mathit{r}}$	Distance to the Way Point	Course Angle to the Way Point
Head-on	FIS	0.66 $\mathrm{nm}$	3.53 $\mathrm{nm}$	047.6°
	VO + FCE	0.28 $\mathrm{nm}$	4.01 $\mathrm{nm}$	008.9°
	SDVO + FIS-NC	0.33 $\mathrm{nm}$	4.00 $\mathrm{nm}$	009.8°
Crossing (give-way)	FIS	0.49 $\mathrm{nm}$	2.63 $\mathrm{nm}$	066.1°
	VO + FCE	0.29 $\mathrm{nm}$	3.60 $\mathrm{nm}$	023.6°
	SDVO + FIS-NC	0.33 $\mathrm{nm}$	3.61 $\mathrm{nm}$	023.3°
Crossing (stand-on)	FIS	0.22 $\mathrm{nm}$	4.02 $\mathrm{nm}$	013.6°
	SDVO + FIS-NC	0.35 $\mathrm{nm}$	3.97 $\mathrm{nm}$	016.1°
Overtaking	FIS	0.74 $\mathrm{nm}$	4.51 $\mathrm{nm}$	024.8°
	VO + FCE	0.21 $\mathrm{nm}$	4.61 $\mathrm{nm}$	006.5°
	SDVO + FIS-NC	0.23 $\mathrm{nm}$	4.62 $\mathrm{nm}$	004.2°

shows the margin ($D_r$), distance, and course angle to the way point at the return timing after the collision-avoidance action between the MASS and the TS in each encounter type.

Table 7. Deviation from original route.

${\mathit{E}}_{\mathit{r}}$	Distance of Original Route	FIS	VO + FCE	SDVO + FIS-NC
Head-on	$8\mathrm{nm}$	$8.27\mathrm{nm}$	$8.03\mathrm{nm}$	$8.04\mathrm{nm}$
Crossing (give-way)	$8\mathrm{nm}$	$8.28\mathrm{nm}$	$8.03\mathrm{nm}$	$8.04\mathrm{nm}$
Crossing (stand-on)	$8\mathrm{nm}$	$8.05\mathrm{nm}$	-	$8.06\mathrm{nm}$
Overtaking	$8\mathrm{nm}$	$8.19\mathrm{nm}$	$8.01\mathrm{nm}$	$8.01\mathrm{nm}$

shows the deviation from the original route in each encounter type.

4.1.2. Avoiding Multiple Vessels

The head-on, crossing (give-way and stand-on), and overtaking encounter types with multiple vessels were tested for TSs approaching the MASS, as shown in

Table 8. Initial condition of multiple vessels for collision avoidance.

Vessel	$\mathit{\varphi }$	$\mathit{V}$	${\mathit{D}}_{\mathit{r}}$	$\mathit{L}$	${\mathit{E}}_{\mathit{r}}$	Criteria
MASS	000°	$10\mathrm{kts}$	-	$172$ m	-	Algorithm 2
TS 1	000°	$5\mathrm{kts}$	$1.5$ nm	$172$ m	Overtaking (being overtaking)	DCPA = 0 and TCPA ≤ 6 min
TS 2	315°	$12\mathrm{kts}$	$3.9\mathrm{nm}$	$172$ m	Crossing (quarter lee give-way)	DCPA = 0 and TCPA ≤ 2 min
TS 3	045°	$10\mathrm{kts}$	$3.9\mathrm{nm}$	$172$ m	Crossing (stand-on)	DCPA = 0 and TCPA ≤ 2 min
TS 4	270°	$7\mathrm{kts}$	$7.1\mathrm{nm}$	$172$ m	Crossing (give-way)	DCPA = 0 and TCPA ≤ 4 min
TS 5	090°	$10\mathrm{kts}$	$7.1\mathrm{nm}$	$86$ m	Crossing (stand-on)	DCPA = 0 and TCPA ≤ 6 min
TS 6	225°	$10\mathrm{kts}$	$9.2\mathrm{nm}$	$86$ m	Crossing (give-way)	DCPA = 0 and TCPA ≤ 2 min
TS 7	135°	$10\mathrm{kts}$	$9.2\mathrm{nm}$	$172$ m	Crossing (Stand-on)	DCPA = 0 and TCPA ≤ 2 min
TS 8	180°	$10\mathrm{kts}$	$10\mathrm{nm}$	$172$ m	Head-on	DCPA = 0 and TCPA ≤ 2 min

. All TSs were set up to take collision-avoidance actions using the VO [7] with D_CPA and T_CPA.

The MASS using SDVO + FIS-NC took collision-avoidance actions in an encounter type with multiple vessels, as shown in Figure 17.

Initially, the MASS analyzed whether T_CPA is 0 or more, and the CRI inferred using FIS-NC was 0.01 or more. TS1 was confirmed to be applied. This encounter type was considered an overtaking situation. The MASS was the overtaking vessel, and TS1 was the vessel being overtaken. Then, the MASS overtook TS1 by turning to starboard. After overtaking, because the T_CPA and CRI of TS3 and TS5 were 0 or more and 0.01 or more, respectively, the MASS determined the encounter type and collision-avoidance action. This encounter type was considered a crossing situation. The MASS was the stand-on vessel, and TS3 and TS5 were give-way vessels. Nonetheless, TS3 and TS5 did not take early collision-avoidance actions. Thus, the MASS kept a steady speed and course when the CRI was less than 0.33 and then turned to starboard when it was 0.33 or more. After the collision avoidance of TS3 and TS5, the MASS identified that the T_CPA and CRI of TS4 were 0 or more and 0.01 or more, respectively, and this encounter type was considered a crossing situation. The MASS was the give-way vessel and TS4 was the stand-on vessel. Therefore, the MASS took an early collision-avoidance action by turning to starboard immediately to return to its original route.

4.2. Discussion

The simulation results showed that SDVO + FIS-NC could avoid the TS according to COLREGs Rules 5, 7, 8, and 13–17, via Algorithms 1 and 2. In this section, the quality of the local route created by SDVO + FIS-NC is discussed in terms of safety and effectiveness during navigation.

First, a comparative analysis was conducted on the safety and effectiveness during navigation of a MASS and a single TS based on the results of each local route-planning algorithm. Safety was verified using the overlapped SD and inferred CRI. Effectiveness was verified using the course angle and deviation from the original route.

Figure 18, Figure 19, Figure 20 and Figure 21 show comparative results from the beginning of collision avoidance with the TS to the return to the original route.

Figure 18, Figure 19, and Figure 21 show the MASS as the give-way vessel, and Figure 20 shows the MASS as the stand-on vessel. Figure 18a–c, Figure 19a–c, Figure 20a–b, and a–c show whether the SD [13] applied to both vessels is overlapped. In this paper, an overlapped domain indicates a near-collision accident involving passing each other in a closed state with no minimum safe distance [15]. As a result of applying the SD to both vessels, FIS resulted in a near-collision accident in the crossing situation (stand-on vessel), and VO + FCE resulted in a near-collision accident in all encounter types. However, SDVO + FIS-NC did not result in a near-collision accident in any encounter type. Figure 18d, Figure 19d, Figure 20c, and Figure 21d show the changes in the inferred CRI. In spite of the gentle decrease in numerical changes in the input variables, the CRI inferred from the FIS increased and decreased, and the CRI inferred from the VO + FCE increased steeply. In contrast, the CRI inferred from the SDVO + FIS-NC increased gently according to a numerical change in the input variables, because the VCD did not change appreciably with respect to the collision-avoidance action. In particular, the VCD of the SDVO-FIS-NC was appropriately utilized in terms of the response distance for collision avoidance, as shown in Table 5, because the response distance of SDVO + FIS-NC was faster than those of FIS and VO + FCE. Figure 18e, Figure 19e, Figure 20d, and Figure 21e show the course angles for collision avoidance, and Figure 18f, Figure 19f, Figure 20e, and Figure 21f show the deviation from the original route. At this time, the value of deviation from the original route was identified as shown in Table 7. For the give-way vessel, the local route-planning algorithms with the most deviation from the course angle and route were FIS, SDVO + FIS-NC, and VO + FCE in order. For the stand-on vessel, SDVO + FIS-NC deviated slightly more from the course angle and route than FIS to prevent a near-collision accident.

Therefore, the results of local route-planning algorithms for taking safe and effective collision-avoidance actions between a MASS and a single TS during navigation can be summarized as follows. SDVO + FIS-NC took collision-avoidance action by minimizing the deviation from the course angle and original route, with no near-collision accident occurring for both the give-way and the stand-on vessels. This is because this algorithm created $V{O}_T^O(V_t)$ based on $S{D}_{ot}$. This result confirmed that SDVO + FIS-NC achieved safe and effective navigation.

Next, the safety and effectiveness of SDVO + FIS-NC during navigation between the MASS and multiple TSs were analyzed. SDVO + FIS-NC took a collision-avoidance action to the extent that no near-collision accident occurred and the vessel also did not deviate significantly from the original route, as shown in Figure 22. This result confirmed that SDVO + FIS-NC can take safe and effective collision-avoidance actions during navigation between the MASS and multiple TSs.

Accordingly, SDVO + FIS-NC can not only reduce the navigation distance and time, but also prevent near-collision accidents in heavy traffic or confined water, because the deviation from the original route is minimized.

5. Conclusions

To operate a MASS at sea, a new route must be planned in real time to avoid collisions with a TS by taking collision-avoidance actions in compliance with COLREGs Rules. Therefore, a local route-planning algorithm based on FIS-NC, SD, and VO was developed based on the SA model. This algorithm consists of perception, comprehension, and projection steps. In the perception step, data pertaining to the navigation between the MASS and the TS were collected using AIS and ARPA. In the comprehension step, if T_CPA was 0 or more and the CRI inferred using FIS-NC was 0.01 or more via the information collected in the perception step, the MASS determined the give-way and stand-on vessels according to the encounter type. In the projection step, local route planning was carried out using $SDV{O}_T^O(V_t)$ when a collision-avoidance action was required. For validating the performance of the developed SDVO + FIS-NC local route-planning algorithm, the following process was carried out. First, SDVO + FIS-NC and existing local route-planning algorithms, namely, the A^* exploration-based local route-planning algorithm using FIS and the VO + FCE, were applied and compared for each encounter type with a single vessel. As a result, only SDVO + FIS-NC took collision-avoidance action by minimizing deviations from the course angle and original route, and no near-collision accident occurred. Next, the collision-avoidance action of SDVO + FIS-NC was analyzed between the MASS and approaching multiple TSs. As a result, SDVO + FIS-NC took systematic collision-avoidance actions using T_CPA, CRI, and $SDV{O}_T^O(V_t)$ to the extent that no near-collision accident occurred, and the vessel did not deviate significantly from the original route. Thus, SDVO + FIS-NC is expected to not only reduce the distance and time of navigation owing to minimal differences in the original route but also prevent near-collision accidents in heavy traffic or confined water. This study is the first step toward the development of a local route-planning algorithm that can take collision-avoidance actions compliant with COLREGs Rules for a MASS. Future studies will focus on using SDVO + FIS-NC to take collision-avoidance actions in consideration of vessel dynamics, speed changes of the TS, and environmental conditions (e.g., wind, waves, and currents).