1. Introduction

Maritime transportation is one of the most important industries in the world, contributing up to 90% of the world trade volume, each ship is a great asset and an essential link in the operation of global maritime transportation. Therefore, ensuring safety throughout the routes of the ship is always on top priority and developed by scientists every day. In which, ship collision is a major type of accident at sea that usually results in significant financial loss, fatalities, and environmental pollution. Thus, assessing of the risk of ship collision is considered the main factor to ensure safe navigation and relevant collision risk mitigations have been the main research focuses in decades.

Multi-vessel collision risk assessment for maritime traffic surveillance is a key technique to ensure maritime traffic and transportation safety and security. Typically, surveillance operators have to search and predict emerging conflict situations from many sailing vessels within a large sea area. Early detection of such risk situations provides critical time to take appropriate action, possibly before a disaster occurs. This paper proposes a real-time multi-vessel collision assessment framework by using Automatic Identification System (AIS) data to detect and rank potential vessel collision risk index by combining a distance clustering process named hierarchical cluster analysis (HCA) for detecting clusters of encounter vessels.

In the previous research, Rong Zhen has introduced a method that used a spatial clustering process named DBSCAN (Zhen et al., 2017) using the clustering algorithm proposed by Martin Ester at al. (1996) is quite complex to enforcement. For practical considerations, there are three major disadvantages DBSCAN method has to face: Firstly, the time complexity is mostly governed by the number of regionQuery invocations, DBSCAN visits each point of the database possibly multiple times lead to prolongation of execution time. Moreover, the position of objects changes continuously in the survey area over time. Secondly, if the data and scale are not well understood and have a clear basis, choosing a meaningful distance threshold ε can be difficult. And DBSCAN is not taking advantage of the available distance data between objects in the survey area, especially identifying the cluster of two vessels close to each other.

On the other hand, using real data from AIS means reducing wasting time when evaluating because of continuity. Therefore, to solve the above problems, in this paper, the author used the HCA solution to cluster vessels with highly simple, faster and take advantage of distance data in comparison with DBSCAN. This paper is organized into five sections as below.

2. Case study

2.1 Risk assessment

Normally, a risk assessment is the combined effort of identifying and analyzing potential (future) events that may negatively impact individuals, assets, and/or the environment (i.e. risk analysis); and making judgments "on the tolerability of the risk based on a risk analysis" while considering influencing factors (i.e. risk evaluation).

To assess the safety level quantitatively and take actions to reduce the possibility of collision in monitored waters, a variety of researchers have published work that assesses risk in various ways. Bearing in mind the type of methods and their objectives, the studies published can be categorized approximately into three broad groups (Li et al., 2012;Zhang et al., 2016):

In the study of risk modeling and risk analysis, the maritime risk can be measured by a variety of methods, such as the product of probabilities and consequences, three or more levels of state indicators and fuzzy, probit regression model, dynamic ship domain and collision judgment model (Kim. and Kim, 2018), quantitative (Koo, 2018;Jeon and Jung, 2018). The research on maritime accidents analysis is a crucial aspect of assessing and improving safety at sea. There are several research works focusing on maritime accident analysis with the results of the theoretical models were compared with actual accident statistics. To assess marine risks from accident data, large amounts of maritime traffic accident data accumulated across many years and contexts should be gathered and analyzed. However, data that contains maritime accidents are rare; therefore, the non-accident data is frequently utilized by researchers to obtain safety levels in the traffic. In the analysis of encounter and near miss situation between vessels, certain maritime traffic risk indexes that correlate the position, speed, and course of the vessels would always be defined and modeled. Then, the risk index can be applied to assess the risk values in the maritime surveyed sea area.

2.2 The AIS data and its application

The AIS system was introduced in the International Convention for the Safety of Life at Sea (SOLAS) amendment, which stated that all vessels over 300 Gross Tonnages (GT) engaged in international voyages, all cargo vessels over 500 GT and all passenger vessels are required to be equipped with AIS from 31 December 2004. Through the installation of AIS receivers in the base station and satellite, substantial AIS information is stored and accumulated by the maritime traffic authority and research group. The AIS transmits ship-related data that can be divided into three groups: dynamic data, static data and voyage-related data (Aarsæther and Moan, 2009).

Vessel Traffic Service (VTS) is vital for ensuring safe and smooth maritime traffic in designated areas. With the rapid development of technologies and the extensive implementation of AIS, a lot of data are available to support the decision-making processes in VTS. Besides the original purpose of identification and collision avoidance between ships at sea, the AIS data serve as an important input and source for maritime traffic risk assessment, and indeed, as an input for research in this area.

The DCPA and TCPA values was used to calculates and ranking the dynamic collision risk and developed by the basic risk, relative multipliers of TCPA and DCPA which are calculated from the AIS data by considering the distance between two ships, the relative speed of the ships, and the difference between the headings of the ships.

2.3 Collision risk index

For the purpose of maritime traffic surveillance in real time, the authors adopt the collision risk index from the research of ship collision avoidance presented in Chen et al. (2015) and situations of near miss between vessels were assessed and investigated in Zhang et al. (2015). The CRI is defined in the notation of the International Regulations for Preventing Collisions at Sea (COLREGS), evaluates the probability and severity of a vessel colliding with other vessels around it. This is an important criterion to rank the risk from other ships, giving the ship officers the time and extent to take evasive actions. Moreover, the CRI index is usually quantified for automated ship collision avoidance, and it has three significant characteristics: ambiguity, uncertainty, and instantaneity. The CRI is impacted by the DCPA, TCPA, distance from the threatening vessel (D), relative bearing (B) and the ratio of speed (K). Based on the factors above, the CRI can be calculated using the combination of DCPA and TCPA. However, the logic for the modeling of CRI is based on the application of automated vessel collision avoidance; the CRI is calculated from the perspective of the own ship to the ships surrounded. The obtained CRI is the basis for the own ship to assess the risk and take intelligent evasive actions of anti-collision.

When assessing the collision risk values in the whole monitored sea area, maritime traffic surveillance systems should determine the CRI between all the vessels that sail within the spatial sea area; however, such a process can be very computationally expensive. On the other hand, real-time data collect from VTS stations always ready, fully and particularly. Moreover, such risk values should be presented to the operators of the surveillance systems in an understandable and comprehensible manner. This is the challenge to presenting an efficient and computationally inexpensive method for assessing collision risk within large surveillance.

3. Theoretical framework

3.1 Framework

To assess and detect vessels at risk of collision from a huge number of sailing vessels within a large sea area, the authors designed an analytical framework illustrated that processes AIS data collected from the maritime surveyed area in real-time (support from VTS stations). Firstly, a hierarchical diagram to extract vessels positioned close to each other and marked, then combine with the preliminary assessment to filter out safe vessels these did not closely located vessels around them. Next step, the DCPA and TCPA are calculated for the couples of closely positioned vessels in encounter clusters. Finally, the collision risk index is estimated in real-time following the proposed function that is described in Figure 1.

3.2 Hierarchical method

When multiple ships operate within the scope of a VTS surveillance system, need an essential solution for operator assistance to propose the list and ranking collision risk of the ships that can be easily monitored, alerted and have solutions to help those ships navigate safer as reduce CRI index also.

A collision occurs when vessels reach standard conditions such as speed, time, and especially distance close enough to happen. To detect the vessel encounter situation from large number of vessels sailing within large sea area automatically, the author used the hierarchical method.

Hierarchical clustering also called hierarchical cluster analysis or HCA is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:

As the HCA program is illustrated in Fig. 2, the distance value (D) will decide where the cut-line is and the number of clusters we have, it is pretty clear that the HCA meets the requirement of detection of encounter vessels and filtration of safer vessels.

When applying HCA, the applicant's mission is to decide the value of distance D that shows the number of object clusters based on the safety of maneuvering in that situation. In the nautical, the distance between vessels is usually calculated from the AIS data using the Euclidean distance method or Mercator method. Because of the limitation of paper, we do not re-introduce those solutions here. After applying HCA, we can get the clusters of encounter vessels named C₁ to C_n (n is the total number of clusters obtained by HCA).

3.3 Preliminary assessment in clusters

Before assessing the collision risk in each cluster of vessels, the important and necessary is preliminary assessment the collision possibility in clusters by using individual vessel AIS records data combine with the assumptions and coefficients present by the applicant and formula below:

Where u_i is the average speed for vessel i, lat_t1, lat_t2, long_t1, long_t2 are the longitude and latitude coordinates of vessel i at time t2 and t1 before. t2 and t1 are the maximum and minimum time relates to collision risk and bases on the set of applicants.

It would be pointed out that all the motionless vessels (vessels with speed lower than 0.1 knots) do not affect the collision risk in shipping routes. After obtaining the time mean speed for all the ships of clusters, clusters with motionless vessels would be easy to dismiss.

Secondly, assessment bases on the correlation courses and position between vessels in each cluster. For a cluster, the own vessel has a correlation position and course that never cross the other over time (courses are not crossing in forward by correlation position), which means this cluster is safe. In detail, we can easily compare correlation position between two vessels at current time and t time before by using relative Euclidean distance formula, ignore the curvature of the earth:

Where d₀, d_t is the relative distance between two vessels a and b at present and t time before, lat_a0, long_a0, lat_at, long_at is latitude and longitude of vessel a at current time and t time sequent and similarly with b0, bt.

Then, if d₀ ≤ d_t, that means possible collision risk, do the detailed assessment in the following steps.

3.4 Calculation of DCPA, TCPA and CRI in each cluster

For two vessel A, B in each cluster with the correlative position (lat_a, long_a), (lat_b, long_b). The distance between vessels can be obtained:

With the related values can be calculated below:

The relative speed (S_r) and relative course (C_r) are calculated as shown below:

Then, the DCPA and TCPA can be calculated following (Li and Pang, 2013):

Where Dist is the distance between the target vessel to own vessel, the Bearing is the bearing of the target vessel measured from own vessel. The unit of DCPA is nautical miles (NM), and the unit of TCPA is minutes (mins).

The value of CRI is from 0 to 1 in the traditional automated vessel collision avoidance system. The DCPA and TCPA are the most important factors in assessing the risk of collision between vessels in a practical scenario. CRI based on the DCPA and TCPA respectively by a negative exponential function following the recommendations presented in Mou et al. (2010). The mathematical expression of the relation ship between CRI and DCPA, TCPA is expressed below:

Where a and b are the adjusted coefficients that can be estimated according to the opinions of maritime experts and officers on watch in the vessel traffic system.

The combined CRI based on CRI_d and CRI_t is calculated following by:

The parameters α and β are the weight of CRI_d and CRI_t, the sum of α and β is 1, and their value can be set according to the specific characteristics of the maritime traffic application.

The above mathematical model is applied to every cluster of vessels, the CRI of each vessel threatened by the other vessels in the same cluster is obtained. Hence, the CRI matrix of each encounter vessel clustered can be ranked, the vessels with the high collision risk index in the clusters are filtered and highlighted to the operator on watch in the vessel traffic surveillance center. Thus, the operator can give instructions to these vessels and coordinate the risk situation between them, relieving intense risk situations between vessels within the large surveillance sea area.

4. Experimental results

In order to illustrate the effectiveness of the proposed framework, the author carried out an experiment in the port of Korea under the range of Mokpo’s VTS (Fig. 3, 4).

4.1 Input parameters D for identifying encounter vessels

As mentioned in section 3.2, D is an important initial parameter input to HCA process, this parameter will decide the number of vessel clusters. This means these clusters have a high risk of collision, must be assessed and act proactively in the situation of collision. The D parameter is decided by operators based on the actual surveillance area, regular state, the maneuverability of the ships and changed many times for optimal reasons. In this study, the author defines the distance for the encounter vessel as 2.5 nm after some empirical specification of radius tests in which the ranges from 1 nm to 5 nm and the reason of necessary preparation for avoidance collision situations of vessels in survey area. There are 11 clusters of encounter vessels generated when D is specified as 2.5 nm as presented in Fig. 4. and Table 2. The existence of other vessels may influence the own vessel behavior or trajectory, so the encounter situation between vessels has been estimated considering this factor.

The CRI ranges from 0 to 1, the coefficient a and b in Eqs. (14) and (15) are used for quantifying the exponential relationship between CRI and DCPA, TCPA respectively. Based on the study of research works of R.Zhen et al. (2017) regarding automated vessel collision avoidance methods, the author assumed an exponential relationship between CRI and DCPA, TCPA respectively, and the correlated a and b are calculated from the assumptions shown in Table 1.

After calculating the coefficients for Eqs. (14) and (15), the relation can be plotted as shown below. As seen in Figs. 5 the CRI decreases non-linearly with increasing values of DCPA and TCPA, thus the mathematical estimation of CRI_d and CRI_t fit our assumptions. In order to assess the CRI from the influence of spatial and temporal features of threatening vessels, the comprehensive CRI is computed by the sum of weighted CRI_d and CRI_t. The spatial and temporal features have the same impact on the CRI. So α and β in Eq. (16) are 0.5. Finally, the combined CRI change with DCPA and TCPA is shown in Fig. 6.

4.2 Identification and assessment of clusters

1) Preliminary assessment

After receiving the real-time data and entering the parameter D = 2.5 nm into the HCA system, the results obtained at the time of study in Mokpo water surveillance area had 13 clusters of vessels close together with the indicators as Table 2 and Fig. 4. The preliminary assessment has shown that 5 clusters have the impossible to collision because of passed each other or course, velocities and distance responses the safety conditions through determination methods as mentioned in section 3.3.

2) Assessment of encounter vessels clusters

It is clear that, based on the standard of distance, the closer ships lead to a higher risk of collision. In addition, the higher correlation speed between two ships, the faster collision could happen. As data are shown in Table 2, after through the preliminary assessment, the closest distance between vessels in clusters is cluster no.7 with 0.69 nm, and the cluster with the highest correlation speed is also cluster no.7. Therefore, it can be quickly concluded that cluster of vessels no.7 has highest risk of collision. To concrete the collision risk assessment of all clusters, the CRI quantification and ranking has required.

4.3 Quantification and ranking of CRI

For each cluster of encounter vessels, we calculate CRI index following Eq. (16). The collision risk index can be identified through the CRI threshold set from the related research literature and maritime experts’ opinions collected. In some automated collision avoidance research literature (Bi, 2000;Zhao et al., 2016, R.Zhen et al., 2017), 0.5 is the criteria for the vessel taking evasive anti-collision actions. Based on the existed references and suggestions from operators in the maritime traffic service center, the author set the threshold as 0.5. The high CRI pairs of vessels whose CRI are more than 0.5 would be identified and ranked, the direction of the blue arrow is the heading of each vessel, the situation between high CRI vessels could be identified through the direction of the vessel. The results can be seen in Table 3.

There are six couples of vessels identified with a red triangle in the eleven clusters, according to their high CRI threshold. Then, the encounter situation of each couple of vessels can be obtained based on the difference of COG value and definition of encounter situation in the COLREGS in Naeem et al. (2012). The specific information about CRI values, rankings and type of encounter situation are described in Table 3.

It is clear to recognize that the no. 7 vessels cluster has a high risk of collision, exceeds the safety threshold, requires immediate and appropriate emergency avoidance action to ensure the safety of the ship. The remaining clusters also have a very high collision risk index, which should be carefully monitored and notified controllers to have ready for responding or actively maneuvers to avoid collision. The results described above illustrate the feasibility and effectiveness of our proposed framework of real-time multi-vessel collision risk assessment for maritime traffic surveillance. As the AIS data is updated in real-time, the clustering process and collision risk index calculation should be processed in real-time as well. This framework can be easily implemented in practical maritime traffic surveillance applications.

5. Discussion and conclusion

The above experiment has shown that the results of the study are consistent with the reality, convenient for officers and operators to predict in advance of vessel clusters in collision situations.

As mention in the introduction section, in comparison with the DBSCAN method R. Zhen et al. (2017), this method is simple and easier to implement because the data exploited and compared directly from the AIS, especially easy for operators when evaluate the appropriate parameter D. The selection of the input parameter D is very important for classifying the closest pair of vessels at high collision risk. Moreover, the flexible change of D parameter leads to optimally in assessing the risk of collisions of vessels close together. It also contributes significantly to reducing the cost of safety assessment. Obviously, the collision occurs or not, apart from the distance factor as the HCA method mentioned, it also depends on many factors such as vessels speed, currents, and traffic density in the survey water area, weather conditions,… but it can be said that this is the simple and most optimal method to quickly classify a cluster of ships with a high risk of collision. On the other hand, a flexible change of D parameter contributes to the elimination of additional external factors that affect the purpose of the study to assess the collision risk in practical maritime traffic surveillance applications.

An objective challenge is the selection of the DCPA and TCPA limits, requiring operators to have experience in handling because these factors are intimately tied to the maneuvering possibility of the ships within the scope of investigation area combined with consideration of the impact external conditions. If these indicators too high, it can cause the ship controllers to stress in unnecessary situations or it is difficult to cause a collision. On the contrary, these indicators are too low, making the ship controllers subjective in being ready for avoidance maneuvers, leading to unpredictable consequences.

In addition, the discontinuous AIS data affect to the results of this method, requiring continuous evaluation measures as soon as data is received from the AIS and repeated frequently to bring the optimal results. It is hard to apply in heavy traffic areas such as channels, creeks, and wharves. In the next studies, we will endeavor to overcome these limitations, incorporate external elements into the CRI assessment to provide more accurate assessment results.