A Study on Multi-ship Avoidance System for Unmanned Surface Vehicles Using the Quaternion Ship Domain and Collision Risk Index
Article information
Abstract
Collision avoidance is essential for the safe navigation of unmanned surface vehicles (USVs). This paper proposes a multi-ship collision avoidance algorithm that integrates the quaternion ship domain (QSD) and collision risk index (CRI) to assess collision risk and generate optimal avoidance trajectories. The algorithm was used to evaluate target ships (TS) using the CRI values, adapt the ship domain based on QSD, and use the velocity obstacle (VO) method to determine feasible avoidance paths while adhering to the International Regulations for Preventing Collisions at Sea (COLREGs). Through 14 simulation scenarios, including single-ship, two-ship, and multi-ship encounters with unexpected TS maneuvers, the results revealed the ability of the algorithm to maintain safe separation distances in complex maritime traffic. The CRI-based approach allows real-time risk assessment and adaptive timing, while QSD adjusts dynamically based on the ship speed and encounter conditions, minimizing unnecessary maneuvers. This integration of QSD, CRI, and VO ensures COLREGs-compliant navigation, efficient path deviation management, and enhanced safety, contributing to the development of intelligent USV navigation systems.
1. Introduction
Recently, with the development of automatic unmanned systems, research on developing algorithms for installing and operating unmanned systems in transportation, such as vehicles, aircraft, and ships, has been increasing. In the maritime field, efforts are being made to implement navigation automation through systems that assist crew members onboard or fully autonomous navigation systems in which the ship makes its own decisions and operates. Unmanned surface vehicles (USVs) have high utility in fields such as transportation, military work, and marine surveying because they can be operated regardless of crew fatigue. The International Maritime Organization (IMO) presented a development framework for autonomous shipping divided into four stages. The essential function required to reach the level of fully autonomous ships at stage 4 is collision avoidance against obstacles. Accurate calculations of the obstacle risk and movement are required for ships to recognize and avoid obstacles independently without human assistance. In addition, the avoidance points and directions of the ships must be determined. In particular, a more complex decision-making process is required when multiple ships are encountered at sea than when avoiding a single ship. Therefore, a function is required to determine the need for avoidance through quantitative risk assessment and effectively identify local paths for ships that require avoidance.
According to research by the European Maritime Safety Agency (EMSA), more than 80% of maritime traffic accidents are caused by human error (EMSA, 2022). Collision and grounding accidents account for approximately 85% of accidents, often resulting in casualties (Wróbel et al., 2017). Internationally, the IMO has announced the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) (IMO, 1972) to prevent maritime collisions. On the other hand, the number of accidents has not decreased because many factors require human judgment to avoid other ships and obstacles in the complex maritime environment around ports with high traffic. If an autonomous shipping system replaces human judgment, collisions, and contact accidents at sea caused by human error can be prevented, and casualties resulting from accidents can be minimized.
Various studies and algorithms for stable obstacle avoidance of USVs have been presented. Research has been conducted using the characteristics of maritime traffic and the knowledge and experience of ship operators. Moreover, various methods have been developed to avoid collisions, particularly considering the characteristics of ships that do not move forward, backward, or change direction immediately. The collision avoidance algorithm for USVs is divided mainly into collision risk assessments, ship safety domain development, and avoidance by predicting the trajectory of other ships.
Mitrofanov (1968) conducted early studies on collision risk assessments. The collision risk was calculated based on the speed and course of the other ship, but the ship operator was required to take avoidance actions directly. Kearon (1977) proposed a formula to calculate the collision risk using the sum of the distance to the closest point of approach (DCPA) and time to the closest point of approach (TCPA) multiplied by the weights. Lisowski (2001) and Szlapczynski (2006) proposed a method to evaluate the collision risk using the ship length, visibility, and safety domains. On the other hand, the judgment may be uncertain and ambiguous if a collision risk assessment is performed only from the perspective of a ship operator.
To solve this problem, Hwang (2002) proposed a method for calculating the collision risk index (CRI) by applying the fuzzy logic presented by Klir, and Yuan (1996) to an existing collision risk assessment method. Fuzzy logic methods can be used to express the continuously changing level of risk quantitatively because the collision risk of a ship continuously changes according to speed, encounter situation, and location. Chen et al. (2015) and Xie et al. (2019b) proposed methods for modeling the collision risk level using the fuzzy logic membership functions. Li and Pang (2013) and Abebe et al. (2021) evaluated methods to utilize the CRI for autonomous ships. Lee and Rhee (2001) proposed a method to infer the collision risk using a fuzzy method and generate an avoidance path using the A* algorithm. Hu et al. (2020) implemented a system to calculate and analyze the real-time CRI for multiple ships and make decisions on direction and speed changes to avoid collisions. The simulations were performed for multiple ships to verify their ability to make collision avoidance decisions. Namgung and Kim (2021) attempted to improve the accuracy of the CRI by proposing a model that can calculate the CRI based on actual ship operation data.
Goodwin (1975) defined the “ship domain” proposed by Fuji and Tanaka (1971) as “the surrounding effective waters which the navigator of a ship wants to keep clear of other ships or fixed objects.” Based on this concept, Goodwin (1975), Davis et al. (1980, 1982), Coldwell (1983), Jingsong et al. (1993), and Kijima and Furukawa (2001, 2003) proposed ship domains that were defined in different forms. Generally, research related to the ship domain has been conducted by verifying only the difference in domain size depending on the safety distance or by identifying an avoidance path using a simple fixed ship domain. Nevertheless, confirming its effectiveness by simply verifying the size and shape of the ship domain is problematic because how the shape of the ship domain affects the avoidance path of the ship cannot be determined. In addition, an unnecessarily large avoidance path may be identified if a fixed ship domain is used, and an appropriate avoidance path may not be created in scenarios such as multi-ship encounters. Accordingly, Wang (2010) estimated the spatial collision risk of ships by proposing a quaternion ship domain (QSD), whose size changes according to the maneuvering ability and speed of a ship; the reliability of the QSD was verified by simulating various encounter situations. Zhou et al. (2020) applied the dynamic navigation safety domain (DNSD) to an actual USV and confirmed that the safety space was maintained during navigation through a simulation. In addition, the effectiveness of the DNSD was verified through the results of a ship domain changing flexibly according to the encounter situations.
Wang et al. (2018) proposed an avoidance-path generation algorithm to generate obstacle avoidance paths that complies with the COLREGs using a local normal distribution-based trajectory and a route search-based algorithm. Based on a normal distribution, a collision avoidance trajectory that complied with the COLREGs was developed to extract waypoints, and the performance of the algorithm was verified through a simulation of a single ship. Kufoalor et al. (2018) proposed a method that enables efficient avoidance, albeit with relatively low safety, by selecting a value between the velocity vector for avoidance and the velocity vector for maintaining the present path according to a set coefficient. Shaobo et al. (2020) designed a modified velocity obstacle method for USVs and verified its avoidance performance for a single ship. Huang et al. (2019) proposed a generalized velocity obstacle method that considers the dynamic characteristics of ships. The velocity obstacle method was optimized and applied to ships, and its avoidance performance was verified for two other ships. Zhou et al. (2021) proposed a model that determines the collision risk level for multiple ships using the navigation safety domain and CRI to improve the collision avoidance decision-making accuracy of USVs. They conducted experiments to verify the proposed decision-making model for collision avoidance measures for multiple ships.
In addition, various complex algorithms have been proposed to optimize avoidance algorithms and improve the performance of autonomous ships. Wang et al. (2023) proposed an innovative hierarchical algorithm specifically designed for dynamic obstacle avoidance in USVs, with a strong focus on enhancing energy efficiency. The algorithm incorporated advanced path-planning techniques and a sophisticated control strategy to improve the operational efficiency and adaptability of USVs in dynamically changing maritime environments. By integrating these elements, the algorithm was developed to optimize the performance of USVs, making them more capable of handling complex scenarios while conserving energy. Kim et al. (2022) developed a predictive probability model enhanced by the Kalman filter to improve collision avoidance strategies for USVs. The model leverages the predictive capabilities of the Kalman filter to foresee potential collision scenarios, allowing for proactive adjustments in the vessel trajectory. This approach enhances the safety of USVs and contributes to smoother and more efficient navigational practices, minimizing the risk of accidents in densely populated maritime areas. Song et al. (2022) introduced an algorithm designed to classify the intentions of moving obstacles encountered by USVs into active and inactive categories. This distinction is crucial for implementing precise collision avoidance strategies because it allows the USV to apply different maneuvers based on the threat level of the obstacle. The algorithm uses machine learning techniques to analyze the motion patterns and predict the intentions, significantly enhancing the decision-making process and overall safety of unmanned maritime operations. Yu and Roh (2024) proposed a composite method combining the VO and A* algorithms to formulate a robust anti-collision path planning strategy for maritime autonomous surface ships. Integrating these two algorithms provided a highly effective solution for navigating through complex marine traffic scenarios, ensuring optimal path selection and collision avoidance. This method improved the navigational accuracy of autonomous ships and increased their operational safety in high-traffic maritime zones. Chun et al. (2024) developed a deep reinforcement learning-based method for collision avoidance that dynamically integrates path and speed control. This approach allows autonomous ships to adapt their navigation strategies in real time, responding to immediate environmental changes and potential hazards. The learning model has continuously evolved based on new data, enabling it to make increasingly accurate predictions and decisions and enhancing the ability of an autonomous ship to navigate safely and efficiently in unpredictable conditions. Seo et al. (2023) applied the CRI integrated with the A* pathfinding algorithm to enhance route planning for collision avoidance in maritime vessels. The method optimized route selection to minimize potential encounters and conflicts by quantifying the risk of collision and incorporating these data into the A* algorithm. This sophisticated approach improves the safety of maritime navigation and increases the efficiency of route planning processes, providing a valuable tool for maritime traffic management. As reported in the summarized studies, these innovative approaches are crucial for enhancing the navigational safety and operational efficiency of maritime autonomous surface ships. The field is witnessing significant advancements, from using sophisticated hierarchical algorithms that balance energy efficiency with dynamic obstacle avoidance to integrating advanced computational techniques such as the Kalman filter, deep reinforcement learning, and A* pathfinding.
In existing studies using the collision risk index (CRI), the threshold value was set arbitrarily, leading to avoidance times that did not adjust automatically based on the risk level of the target ship. Often, the velocity vector selected for avoidance was not attainable at the current point because the motion performance of the OS was not considered. In addition, previous research on the ship safety domain typically measured risk based on the shape of the ship domain or used a simple fixed safety area to identify avoidance routes. Despite this, evaluating risk based only on the shape of the ship domain does not effectively determine its impact on the avoidance path of OS, complicating the verification of its effectiveness. Moreover, using a fixed ship domain can lead to unnecessarily large avoidance routes and may fail to generate appropriate routes, particularly in scenarios involving multiple ship encounters.
The methods used in this study to address these challenges are as follows: First, the system determines the optimal avoidance time for all encountered ships instead of relying on predefined thresholds by integrating CRI as a parameter of the VO method and allowing the avoidance time to be calculated automatically based on the encounter situation. Second, selecting a velocity vector for collision avoidance considers the reachable velocity area determined by the motion performance of ships, ensuring that only the velocity is attainable by the OS. Third, the system can maintain a sufficient distance to avoid more hazardous ships and ensure a minimum safety distance when the OS is the stand-on ship by generating a ship domain that adjusts according to the speed of the OS and the position of the encountered TS. This approach prevents the problems associated with overly distant evasive maneuvers and potential collisions due to failing to maintain the required minimum safe distance.
Section 2 of this paper explains the methodology. It introduces the specification of the simulation target ship, classification methods for target ships, and calculations using the CRI, QSD, and VO methods. This section also details how each method was applied in this study. Section 3 describes the collision avoidance algorithm. It includes a description of the procedures performed by the OS to avoid TS using the CRI, QSD, and VO methods and discusses the algorithm for returning to the global path once avoidance is complete. Section 4 reports simulations and discussions under various conditions. Fourteen simulations were performed, including scenarios for single-ship avoidance, two-ship avoidance, three-ship avoidance, five ships avoiding each other, and one ship acting unexpectedly. The effectiveness of the algorithm was verified through these simulation results. Section 5 concludes the paper by summarizing the results of this study and outlining future works.
2. Methodology
2.1 Problem Definition
This study addresses two primary issues: avoiding collisions with three or more TS by adhering to the COLREGs rules regardless of the encounter situation and avoiding collisions when the TS makes an unexpected change in direction. Three main methods are used to address these issues: the CRI, QSD, and VO methods. The CRI is used to quantitatively assess the risk for all encountered ships, while the QSD establishes a definitive safety zone around the OS to ensure it remains at a minimum specified distance from any TS. The results from the CRI and QSD calculations help determine the dimensions of the collision cone in the VO method. Because this collision cone is generated for all TS, the OS can select a velocity vector that satisfies the conditions above, even when encountering multiple TS. The integration of CRI and VO enables the selection of the optimal speed vector to avoid multiple ships simultaneously, and the QSD ensures a safe distance from the TS, facilitating avoidance even when the TS exhibits unexpected maneuvers. This section describes the CRI, QSD, and VO methods proposed in previous studies for obstacle avoidance of USVs and explains how each method was applied. In this paper, the own ship is denoted as the OS, and the target ship is denoted as the TS.
2.2 Classification of the Encounter Situation
The encounter situation of a ship at sea is determined by the heading angle of the OS, the position of the TS, and the heading angle of the TS. If an encounter situation is classified only by the location of the TS, distinguishing between ships that may pose a risk to the OS and those that do not is difficult. Tam and Bucknall (2010) proposed a model that classifies the position of the TS based on the heading angle of the OS and classifies the encounter situation according to the heading angle of the TS at that position. The Tam and Bucknall model classifies the encounter situations by dividing the area around the OS into six areas according to the angle and then dividing it into six areas according to the heading angle of the TS. This model can define encounter situations accurately according to the position and heading angle of the TS. The model can clearly distinguish between ships requiring avoidance and those not because it classifies encounter situations based on the COLREGs.
This study used a modified version of this model. First, encounter situations classified as stay-on in the prior model were subdivided and defined as port-side crossing and safe. Second, overtaking, which was defined too broadly and made it difficult to determine the approach direction of other ships, was also changed to port-side and starboard-side crossings. Finally, among the TS located posterior to the OS, those not facing the OS or passing through the posterior OS were classified as safe. Fig. 1 presents a diagram of the classification model.
Modified encounter situation classification diagram based on Tam and Bucknall (Tam and Bucknall, 2010)
2.3 Collision Risk Index
When significant traffic around a port exists, ship operators often struggle to discern which ships are hazardous and to what extent. The CRI provides operators with quantitative risk indicators, enabling them to distinguish clearly between ships requiring avoidance and those not and to decide on the appropriate avoidance actions. In a typical encounter, the CRI is calculated using the relative motion parameters between the OS and TS. The essential parameters required for calculating the CRI include DCPA, TCPA, RD RB, and K. This section explains the calculations and membership functions for each parameter.
2.3.1 Geometric relationships
The position and heading angle of the TS are required to infer the risk of the TS.
Fig. 2 shows the geometric relationship between the OS and TS during sailing. (xo, yo), (xt, yt), θo, and θt are the position of the OS, position of the TS, heading angle of the OS, and heading angle of the TS, respectively. The RD, TB, and RB of the TS can be calculated using Eqs. (1)–(4).
Geometric relationship between two ships
The RC and RV can be calculated using the heading angles of the OS and TS, and the velocity of each vessel, as expressed in Eqs. (5) and (8). (
The parameters calculated above were substituted into Eqs. (10) and (11) to calculate the DCPA and TCPA.
Table 1 lists the meanings according to the signs of the DCPA and TCPA (Iperen, 2015).
Relationship between give-way ship and stand-on ship according to the sign of the DCPA and TCPA
2.3.2 Membership functions of the collision risk index
The continuously changing level of risk can be expressed quantitatively using the fuzzy logic method because the risk of ship collisions changes continuously depending on the speed, encounter situation, and position. An appropriate membership function was established for each parameter to apply the fuzzy logic. The membership functions for calculating the collision risk index are expressed as follows (Yan, 2002; Xu and Wang, 2014; Boudraa et al., 2010; Srivastava et al., 2011):
Eqs. (17)–(23) express the relevant parameters for calculating each membership function.
The result of each membership function is 0 when there is no collision risk and 1 when the collision risk is at maximum. All factors affect the collision risk. Hence, the final CRI is calculated by multiplying each parameter by its weight and then summing them. The CRI is defined by Eq. (24):
Weight value for each parameter of the CRI
2.4 Quaternion Ship Domain
The main aim of developing a ship domain is to obtain a minimum safety distance around the OS using variables including the specifications of the OS, and it can be considered a risk of collision if the TS invades the area. The ship domain should be included in the composition of the collision avoidance algorithm because it affects the risk assessment of the encountered TS, setting the minimum approach distance and identifying the optimal path. Depending on the definition method, the ship domain can be defined using an analytical method, a ship operator knowledge-based method, an experimental method, or a complex method that combines these. The domain can be classified as circular, elliptical, or polygonal, depending on the shape of the defined domain.
In this study, the QSD presented by Wang (2010) was used, based on the Kijima and Furukawa (2003) ship domain. The QSD is an analytical method whose form varies according to the approach direction of the TS and the size, tactical diameter, and advance of the OS. A safe distance optimized for the present encounter situation can be calculated using a ship domain whose size changes in this manner. The border of the QSD is defined using an elliptical Eq. using the radii of the fore, aft, port-side, and starboard-side directions of a ship, as expressed in Eq. (25).
Fig. 3 shows the positions of Rfore, Raft, Rstbd, and Rport, and each radius was calculated using Eq. (26).
Radius in each direction for the QSD calculation
2.5 Velocity Obstacle Method
Fiorini and Shiller (1998) proposed the velocity obstacle method. It is a method for avoiding collisions by creating a collision cone for the area in which a collision may occur and selecting a vector outside the collision cone, assuming that the speed and direction of the OS and TS are maintained. The velocity obstacle method is advantageous for avoiding multiple ships because it produces a collision cone for each ship. The set of collision cones, CCA,B is expressed using Eq. (28) when the OS Â and the TS
Collision cones for two ships
When the OS has many TS to consider, it is safe to avoid TS with a high risk of collision earlier than the other TS. The time horizon used in the velocity obstacle method refers to the time range selected based on the system dynamics, obstacle trajectories, and computation rate of avoidance maneuvers. The avoidance point is determined by forming a collision cone for the time range below the time horizon. The definition of velocity obstacle with the applied time horizon is expressed as Eq. (31).
Collision cones with the time horizon applied to two ships
In other words, a larger time horizon means a larger collision cone, and the collision-possible velocity vectors over a longer distance are considered. Conversely, the size of the collision cone decreases as the time horizon decreases, and only the collision-possible velocity vectors within a narrow range are considered. Avoidance will always begin at the same point if a fixed value is used, regardless of the encounter situation, because the time horizon affects the timing of collision avoidance.
Previous studies have typically set a threshold for the CRI and have the OS begin avoidance if the CRI is higher. On the other hand, unexpected behavior of the TS will be difficult to adapt to if the OS begins to avoid when the CRI is above the threshold. In addition, developing an avoidance path if the CRI of several TS suddenly increases will become difficult because the TS below the threshold is not considered in advance. In this paper, the CRI replaces the function of the time horizon to determine the optimal avoidance point for each ship at different risk levels. Therefore, the size of the collision cone increases as the CRI of the TS increases, enabling the OS to avoid collision from a distance, and the size of the collision cone decreases as the CRI decreases, enabling the OS to perform avoidance with minimal movement. Ultimately, this suggests that an appropriate avoidance point is determined for every ship encountered. An appropriate value was determined through a simulation because the user arbitrarily adjusted the time horizon in the velocity obstacle method. Next, a multiplier was applied such that the value of the CRI, calculated as a value between 0 and 1, had the same scale as the time horizon. The velocity obstacle with the applied CRI is expressed as Eq. (32).
2.6 Ship Specification for Simulation and Maneuvering Eqs. of Motion
The ship designated as the simulation target was the KASS (Korean Autonomous Surface Ship), the first design ship developed by KRISO. KASS features a twin-propeller, twin-rudder configuration with a center skeg at the stern. The scale ratio of the ship applied to the simulation is 11, and this ship was applied to the OS and TS. Table 3 lists the main specifications of the KASS.
Specifications of the model ship
The maneuvering Eqs. of motion for a ship was used to simulate the motion of the OS. These Eqs. are characterized by three degrees of freedom, detailed in Eq. (33): surge, sway, and yaw (Gertier and Hagen, 1967).
In Eq. (34), the terms multiplied in front of the acceleration and velocity terms are the hydrodynamic derivatives. Eq. (35) expressed the propeller force. The sway was canceled out, and only the surge and yaw remained because the designated ship had two propellers. In Eq. (35), ρ denotes the density of seawater; D stands for the diameter of the propeller; n indicates the rotation per second (RPS) of the propeller. KT is the thrust coefficient according to the propeller advance coefficient JP .
Eq. (36), which accounts for rudder force, was used because there are two rudders; here, δ refers to the rudder angle, and FN is the rudder pressure. The other terms are coefficients that must be obtained through experimentation.
The motion performance of the ship described in this section will be used to generate the reachable velocity vector region of the OS in Section 3.1.
3. Collision Avoidance Procedure
3.1 Velocity Vector Selection Procedure
The velocity vector a USV can select at a given point is determined by its performance. The velocity vector area the USV can reach must be considered when applying this to the algorithm. An algorithm is required to move toward the original waypoint when the avoidance action is complete. This section describes selecting a vector for avoidance in the reachable velocity (RV) area and the global path return method. The USV selects the velocity vector using the following process:
Generate an RV considering the present velocity and rudder angle of OS;
Exclude velocities matching the velocity obstacles from the generated RV;
Select a velocity vector that complies with COLREGs among the remaining velocities;
If no velocity in the RV matches the velocity obstacle, select the velocity to return to the global path.
3.1.1 Reachable velocity vector area
The velocity range that the OS can reach at present is determined by the maneuvering characteristics and thrust. The RV can be calculated by multiplying the acceleration range of the OS, which is determined by the thrust of the thruster, by the time ∆t. The set of RVs at time t, FA (t), is defined as Eq. (37).
Areas of RVs and RAVs produced by the OS
3.1.2 Returning to the global path
If the encounter situation of all ships is “Safe,” a line of sight (LOS) is developed from the present position of the OS to the waypoint the OS was following before collision avoidance. The OS then returns to the global path by selecting the velocity vector above the LOS from among the RVs. Fig. 7 presents this process.
Returning to the global path using a line of sight
3.2 Velocity Vector Selection Considering COLREGs
Avoiding a TS requires the OS to check the TS information first using the automatic identification system (AIS). This study assumed that all TS information is collected without omission at every timestep. Next, the encounter situation was classified based on the position and heading angle of the TS. If there is a ship whose encounter situation is unsafe, the OS calculates the CRI and QSD for that ship and produces a velocity obstacle based on these values. Subsequently, a velocity vector for avoidance is selected outside the velocity obstacle. The COLREGs must be considered when selecting a velocity vector. According to the COLREGs, the OS is a give-way ship in head-on, starboard-side crossing, and overtaking encounter situations. Therefore, it must avoid the starboard side. In port-side crossing and overtaken situations, the OS must maintain the current speed and heading angle because it is a stand-on ship. This is implemented by selecting the rightmost velocity vector from among the RAVs for the TS, which are classified as head-on, starboard-side crossing, and overtaking encounter situations. In a port-side crossing encounter, the OS is not obligated to avoid but to prevent a collision; it is set to turn largely to the starboard side and cross the front of the TS. COLREGs prohibit crossings in front of other ships. Nevertheless, in a situation in which the OS selects port-side avoidance that passes behind the TS, port-side avoidance is more dangerous than starboard-side avoidance because it can result in a head-on collision if the TS belatedly avoids the starboard side. This is shown in Fig. 8.
Dangerous scenarios that may result from port-side avoidance
When multiple ships are present, regardless of the encounter situation of each ship, the OS is set to select the rightmost speed vector among the calculated RAVs because avoiding the starboard side complies with the COLREGs. Fig. 9 presents the velocity vectors selected when three ships encountered each other.
Velocity vector selected for avoidance when encountering three ships
Any ship with an encounter situation that changes to Safe is excluded from the velocity obstacle calculation when the OS moves to the coordinates of the selected velocity vector. Once all encountered ships are classified as Safe, the OS returns to the global path. The entire process runs in real-time, ensuring precise avoidance and a rapid return to the original course. Fig. 10 shows one calculation cycle, which was performed 10 times per timestep to maintain accurate and responsive collision avoidance.
Flow chart of the collision avoidance procedure
4. Simulations and Discussion
The proposed algorithm was verified using simulations of single-ship encounters, multi-ship encounters, and the unexpected behavior of other ships. The calculation of one cycle of the algorithm was performed once every 1/10 second, and the simulation was conducted for 300 timesteps. Each simulation consisted of a scenario in which a collision would occur if avoidance were not performed; to evaluate only the avoidance performance of the OS, the TS was set to a scenario in which no avoidance was performed. Each Figure in the simulation results shows the positions and trajectories of the OS and TS at three timesteps: initial encounter, avoidance point, and after avoidance. The CRI graph showed the change trend up to the third step. A green ship and trajectory represented the OS, and the other colors represented the TS. In addition, the color of the ship domain produced around the OS and the color of the CRI graph were the same as that of the TS. A green dot at (0, 200) represents the waypoints of the OS.
4.1 Single-Ship Avoidance
Simulations were performed for head-on, starboard-side crossing, port-side crossing, and overtaking encounter situations to confirm the changes in avoidance paths and CRI when encountering a single ship. Table 4 lists the initial positions, goal positions, heading angles, and speeds of the OS and TS. Fig. 11 presents the simulation results for the four encounter situations.
Initial conditions of the OS and TS in single-ship encounter situations
Simulation results of a single-ship encounter
In each encounter situation, the OS avoided the starboard side of the TS according to the COLREGs, and for port-side crossing, it crossed in front of the TS with a gap equal to the safety area of the ship domain. Compared to the starboard-side crossing, the port-side crossing was performed in the direction where the TS was approaching. Therefore, the OS was confirmed to have been avoided by turning a longer distance through the trajectory. In all four encounter situations, the QSD exhibited a tendency for the radius to increase in the direction in which the TS approached, and while avoiding the TS, the optimal safety distance was calculated, and its shape was changed flexibly. The CRI exhibited a gradual increasing trend in all four cases, reached its maximum value because of the influence of the relative distance coefficient when it reached the CPA and tended to decrease rapidly from the moment the TCPA became zero. Hence, avoidance ended, and from this point onward, no velocity obstacles would be produced for the TS. In addition, the timing of avoidance and the QSD differed according to the encounter situation. Table 5 lists the distance to the TS at the avoidance starting point and CPA.
Minimum relative distance and max CRI in each encounter situation (1 ship)
Avoidance begins at the earliest for a head-on encounter with the highest risk, and avoidance begins last for an overtaking encounter where the TS does not approach directly. Avoidance begins at similar times in starboard-side and port-side crossing situations. According to the COLREGs, the OS is a stand-on ship when the TS approaches from the port side. Nevertheless, the CRI increased rapidly because the TS did not perform avoidance, resulting in the OS starting avoidance late compared to the starboard-side crossing situation.
The distance at the CPA also varied according to the encounter situation owing to the influence of the QSD. In head-on and overtaking situations, the distance at the CPA was similar when the directions of movement of the OS and TS were on the same vertical line. The distance at the CPA in the starboard-side crossing situation, where the TS was moving away, was greater than that at the port-side crossing, where the TS was approaching. In summary, under the influence of the QSD and CRI, the OS secured an optimized safety distance for each encounter, determined the avoidance starting point, and identified a local path. Nevertheless, even if a sufficient safety distance is secured, it is dangerous to cross forward to avoid a ship approaching from the port side. Therefore, this should be improved with another method in the future.
4.2 Multi-Ship Avoidance (Two TS)
This section presents the results of a simulation in which the OS encountered two TS. To set up a complex scenario, one TS was set in a head-on or overtaking encounter, and the other TS was set in a port-side or starboard-side encounter at 45°, which sailors generally consider to be the most dangerous. Table 6 lists the initial positions, heading angles, and speeds of each TS. The conditions for the OS are described in Section 4.1. Fig. 12 presents the simulation results for the four scenarios.
Initial conditions of TS1 and TS2 in multi-ship encounter situations
Simulation results of two-TS encounter
In scenarios (a) and (b), TS2 crossed the OS at 45° and 315° when encountering TS1, which was a head-on situation. In scenario (a), the OS encountered TS2 approaching from the port side while avoiding TS1. Therefore, the OS maintained the present path sufficiently long to secure a safe distance from approaching TS2, crossed in front of TS2, and returned to the global path. In scenario (b), the OS changed the heading angle to the starboard side once again because it encountered a starboard-side ship while avoiding TS1, avoiding TS2.
In scenarios (c) and (d), TS2 crossed the OS at 45° and 315° while the OS overtook TS1. In scenario (c), while the OS was overtaking TS1, TS2 approached from the port side. Similar to scenario (a), the OS crossed in front of TS2 while maintaining a safe distance. In scenario (d), while the OS overtook TS1, TS2 approached from the starboard side, and the OS passed behind TS2 without any additional action.
Table 7 lists the distance and maximum value of the CRI when the OS and each TS are closest. The minimum distance to the TS was 12 meters, ensuring a safety distance of six times the length of the hull. This maintains the optimal safe distance for all encountered TS, similar to when avoiding a single vessel. The maximum value of the CRI was approximately 0.9. This occurs because no separate threshold was set, and the minimum avoidance path was produced, resulting in a high CRI because of the short distance at the point of avoidance.
Minimum relative distance and max CRI in each encounter situation (two ships)
The OS avoided the starboard side in all four scenarios to comply with the COLREGs. Because the algorithm considers all ships simultaneously, it secures a safe distance regardless of the direction from which the TS approaches, selects the optimal velocity vector at each timestep, and identifies an avoidance trajectory that does not cause a collision. The trajectory was maintained if it was appropriate for avoiding the two TS simultaneously. The velocity vector to the right of the present trajectory was selected if an additional safe distance was required to avoid another TS.
4.3 Multi-ship Avoidance (Three TS)
This section presents the simulation results for a scenario in which three ships must be considered simultaneously. Each scenario was set randomly so that the OS encountered the TS continuously. Table 8 lists the initial conditions of each TS. This is a very complex scenario because the TS does not perform any avoidance action, and the OS must consider the TS simultaneously or avoid them sequentially. Fig. 13 presents the simulation results for each scenario.
Initial conditions of TS1, TS2, and TS3 in multi-ship encounter situations
Simulation results of a three-TS encounter
In scenario (a), the OS avoided TS3 on the starboard side and TS2 simultaneously and maintained the path to avoid TS1 approaching from the head-on direction. Subsequently, the OS exhibited a trajectory heading to the waypoint after all the collision risks disappeared. In the CRI, the risk of TS3, which was avoided the fastest, first decreased. The CRI reached its maximum value in the order of TS2 and TS1 and then decreased. In scenario (b), the OS avoided the starboard side to simultaneously avoid TS2 on the port side and TS3 on the starboard side and then changed course to the starboard side again to avoid TS1 in the head-on direction. Because TS2 was ahead while the OS was avoiding it, the OS selected a velocity vector heading toward the waypoint. The CRI of TS3, which was encountered the fastest, reached its maximum value first, and the maximum CRIs of TS1 and TS2, whose DCPA increased during avoidance, did not exceed 0.75. In scenario (c), the OS changed its heading angle significantly to the starboard side to overtake TS1 while avoiding TS2 approaching from the port side. Subsequently, the OS maintained the path to avoid TS3 coming from the starboard side and then selected a velocity vector heading toward the waypoint when the danger from TS3 disappeared. The CRI value of the closest, TS1, was the highest, but it decreased as the distance from TS1 increased to avoid TS2. The CRIs of TS2 and TS3 reached a maximum value in that order and decreased after avoidance. Even when the OS avoided the three ships, it always complied with the COLREGs and selected the safest path, regardless of the direction the TS was approaching.
Table 9 lists the distance and maximum value of the CRI when the OS and each TS are closest in the three-ship encounter scenario. Like encounters with two TS, the results confirmed that a safe distance exceeding 12 meters is consistently maintained. The maximum CRI value was calculated for the TS that approaches the closest, and the calculated value was approximately 0.7 for the TS that finished avoiding early.
Minimum relative distance and maximum CRI in each encounter situation (three ships)
Through two- and three-ship encounter simulations, the avoidance trajectory was confirmed when the OS encounters another ship during avoidance or when multiple TS must be considered simultaneously. Because the velocity obstacle method was used as an avoidance algorithm, the OS defined a collision cone for all non-safe ships and selected a velocity that did not overlap with it to identify an avoidance path where the QSD was not violated regardless of the number of ships. In addition, owing to the influence of the CRI, larger collision cones were produced for high-risk ships, and avoidance action was performed in advance. Therefore, even if the OS encountered another ship during avoidance, it was on a trajectory that moved minimally on the present path.
4.4 Multi-Ship Avoidance (Four TS)
Simulations were conducted by applying the proposed algorithm to five ships. Because the OS and the four TS converged at one point (0, 100) simultaneously, each ship aimed to avoid the other four. Fig. 14 shows the simulation results; the CRI and QSD were based on the OS.
Simulation results of five ships to which the algorithm was applied
In a scenario where all ships gathered at one point, they avoided the starboard side and headed to the waypoint without violating the domains of each ship. In this case, we confirmed that even when the proposed algorithm was applied to different ships, they maintained the COLREGs and avoided each other with minimal movement.
4.5 Unexpected Movement of the TS
In this section, the simulation results are presented to confirm the avoidance path of the OS when the TS moves in violation of the COLREGs in head-on and overtaking situations. Table 10 lists the initial conditions and turning points of the TS, and Fig. 15 presents the simulation results.
Initial conditions and turning point of the TS in each scenario
Simulation results of the unexpected movement of the TS
In scenario (a), the TS approaching from the starboard side ignored the already avoiding OS and changed its course to the port side. The QSD shape changed as the TS changed direction, and the OS changed course to the starboard side once more to avoid a head-on collision with the TS. In scenario (b), the TS changed direction to the starboard side while the OS overtook it. Because the TS intervened while the OS was already overtaking on the right, the OS adjusted its course slightly to the starboard side and had a trajectory passing in front of the TS. This is because, in this scenario, the port-side velocity vector could not be selected, and the speed of the TS was lower than that of the OS.
Table 11 lists the minimum proximity distance and maximum CRI when TS shows unexpected movement. The TS approached the minimum safe distance of 5m because it already changed direction and approached when the OS started avoidance action. The TS could be avoided by changing direction once more without collision because of this difference. Contrary to the previous sections, the CRI values exceed 0.95, indicating an imminent collision. Future research should enhance the algorithm so that changes in the TS’s trajectory can be detected in advance, allowing for preemptive actions.
Minimum relative distance and max CRI in each encounter situation (unexpected movement)
In such a scenario, if the TS changes direction without complying with the COLREGs during the avoidance or overtaking behavior of OS, an appropriate avoidance path can be determined because the avoidable velocity was newly calculated within the secured safety distance. In addition, a quick response is possible even if the CRI increases rapidly because the starting point of avoidance is not determined by the CRI threshold.
5. Results
The effectiveness of the proposed collision avoidance algorithm was evaluated through 14 simulation scenarios, including single-ship, two-ship, and multi-ship encounters, as well as unexpected maneuvering cases. The quantitative performance of the algorithm is summarized as follows:
-
(1) Avoidance success rate
The algorithm successfully avoided collisions in 100% of the 14 tested scenarios, complying with the COLREGs. Excluding unexpected movement of the TS, the minimum relative distance maintained between the OS and TS during avoidance was 11.0 m, ensuring a safety margin of at least six times the hull length of the ship. When the OS avoided three or more ships, the algorithm adjusted its path by selecting the rightmost velocity vector to ensure compliance with COLREGs.
-
(2) CRI and avoidance timing
The maximum CRI values varied between 0.615 and 0.978, depending on the encounter situation, indicating that the algorithm correctly prioritized high-risk targets. Avoidance initiation distances differed based on risk severity, with head-on encounters triggering avoidance at approximately 124.0 m while overtaking scenarios initiated at around 59.6 m.
-
(3) Maneuvering efficiency
The algorithm optimized the VO selection, ensuring that avoidance maneuvers did not result in excessive detours. The return-to-global-path mechanism successfully redirected the USV to its original route within an average of 3–5 timesteps after avoidance completion.
6. Conclusions
A multi-ship collision avoidance algorithm was designed for USVs, and its performance was validated through simulations under various encounter scenarios and TS configurations. The algorithm integrates QSD to maintain a safe distance around the OS, CRI to assess the risk posed by TS, and the VO method to generate optimal avoidance paths. The selection of velocity vectors for avoidance was designed to comply with COLREGs. The key conclusions from the simulations are as follows:
-
(1) Single-ship avoidance performance
Simulations of general encounters with a single TS confirmed that the OS consistently avoided the starboard side in accordance with COLREGs. In port-side crossing situations, the OS maintained a safe distance and executed avoidance by passing in front of the TS while adhering to the collision cone constraints from QSD and CRI. The distance at the CPA and the avoidance initiation point varied according to the assessed collision risk. Higher risk levels led to earlier avoidance maneuvers, ensuring the CPA distance matched the dynamically calculated ship domain size.
-
(2) Multi-ship avoidance performance
Simulations involving multiple TS showed that the algorithm successfully generated avoidance paths while maintaining COLREGs compliance, regardless of the number or direction of approaching ships. A dynamic ship domain was produced for each encountered TS, and velocity obstacles were updated accordingly, ensuring a safe separation distance was maintained. When applied to four or more TS simultaneously, the simulation results showed that all ships avoided each other with minimal movement because each TS adhered to COLREGs and adjusted its trajectory accordingly.
-
(3) Response to unexpected maneuvers
When a TS performed an unexpected maneuver, the algorithm selected the safest available velocity vector within the calculated ship domain, adjusting the avoidance path dynamically. If no valid velocity vector was available, the OS maintained its current course to minimize the risk of sudden, unsafe maneuvers.
-
(4) Computational efficiency and real-time performance
Because all calculations use mathematical formulae, the algorithm could perform up to 60 calculations per second for a single TS. Even when handling four TS simultaneously, the system maintained a real-time processing rate of 10 calculations per second, confirming its feasibility for practical autonomous navigation. Future improvements will focus on reducing the computational complexity to support more TS while maintaining real-time performance.
Through simulations of diverse encounter scenarios, the proposed algorithm illustrated effectiveness in waypoint tracking, local path generation, multi-ship collision avoidance, COLREGs compliance, and adaptive responses to unexpected maneuvers. Future research will extend collision avoidance validation to environments with port infrastructure and marine structures, and further optimization will be conducted based on different TS types and sizes.
Notes
Kwang-Jun Paik serves as a journal publication committee member for the Journal of Ocean Engineering and Technology, but he did not have a role in the decision to publish this article. There are no potential conflicts of interest relevant to this article.
This work was supported by the National Research Foundation of Korea (NRF) grant (No. 2022R1F1A1074865) funded by the Ministry of Science and ICT, Republic of Korea, and the Korea Institute of Marine Science and Technology Promotion (KIMST) grant (No. 20200615) funded by the Ministry of Oceans and Fisheries, Republic of Korea.