1. Introduction
1.1 Background
In recent years, the autonomous ship has gradually become a hot research topic around world. An autonomous ship involves a highly integrated development of ship navigation intelligence and informatisation. Antão and Guedes Soares (Reference Antão and Guedes Soares2008) pointed out that 75% to 96% of marine accidents and causalities result from some type of human error. An autonomous ship can help or replace an officer on watch (OOW) to make a series of navigation decisions, which can overcome errors caused by human factors and reduce the probability of marine accidents (Zhang et al., Reference Zhang, Montewka, Manderbacka, Kujala and Hirdaris2021a). At the same time, a shortage of 147,500 skilled seafarers is predicted by 2025 (Lušić et al., Reference Lušić, Bakota, Čorić and Skoko2019), and the high intelligence level of an autonomous ship can reduce the number of seafarers required. In addition, from the perspective of shipowners’ operating costs, an autonomous ship can save on seafarers’ wages and, at the same time, allows the conversion of the original seafarers’ cabins into cargo warehouses, thereby increasing the volume available for cargo transportation (Bakdi et al., Reference Bakdi, Glad and Vanem2021).
The autonomous navigation system (ANS) is the brain of a maritime autonomous surface ship (MASS) and plays a critical role throughout the system. ANS makes a series of navigation decisions in real time based on external information (Wang et al., Reference Wang, Wu, Zhang, Wu and Wang2020). Among them, collision avoidance is one of the primary tasks faced by an autonomous navigation system (Huang et al., Reference Huang, Chen, Chen, Negenborn and Van Gelder2020; Zhang et al., Reference Zhang, Conti, Le Sourne, Vassalos, Kujala, Lindroth and Hirdaris2021b). Ship collision avoidance is not a new topic. As early as the 1990s (Calvert, Reference Calvert1997), researchers proposed collision avoidance models for different scenarios. In the past few decades, the field of ship collision avoidance has emerged and accumulated rich research results (Tam et al., Reference Tam, Bucknall and Greig2009). However, most of the existing collision avoidance strategies follow the ‘proactive strategy’, that is, the design subject of the collision avoidance model undertakes almost all evasive actions. This will increase the cost of navigation and, at the same time, unilaterally formulating a collision avoidance strategy will become ‘wilful’, resulting in an uncoordinated situation during the collision avoidance process, which is not in line with the actual traffic conditions at sea. Under a real collision avoidance process, OOWs usually use a very high frequency (VHF) radio to confirm each other's intentions and coordinate evasive actions (Szlapczynski and Szlapczynska, Reference Szlapczynski and Szlapczynska2016). The lack of human involvement on the bridge of an autonomous ship creates challenges for the coordination of collision avoidance actions (Aylward et al., Reference Aylward, Weber, Lundh, MacKinnon and Dahlman2022; Zhang et al., Reference Zhang, Zhang, Fu, Kujala and Hirdaris2022a).
The development of MASS should be a gradual process, as it will make a difference in the degree of intelligence and autonomy of a ship (Pedersen et al., Reference Pedersen, Glomsrud, Ruud, Simonsen, Sandrib and Eriksen2020). In the future, each participant under the same collision avoidance scenario will show typical multi-modal characteristics: traditional ships, ships equipped with auxiliary decision-making systems, remote-controlled ships and autonomous ships coexisting at the same time (Ventikos et al., Reference Ventikos, Chmurski and Louzis2020). Under such mixed scenarios, different decision-making subjects have different perceptions of the current marine scene and different decision-making logic. At the same time, there is a strong interactive coupling between different decision-making units, the same target ship (TS) may be participating in other collision avoidance scenarios while forming an encounter situation with own ship (OS), which leaves a high degree of uncertainty of any TS's evasive action. Therefore, considering the particularity of mixed scenarios formed by ships with different autonomy levels, this paper attempts to propose a multi-ship collaborative collision avoidance strategy under mixed scenarios so as to further ensure the safety of an autonomous ship.
1.2 Related works
In this part, the related work is summarised into three aspects, including a general proactive ship collision avoidance method, a centralised ship collaborative collision avoidance method, and a distributed ship collaborative collision avoidance method.
(1) General proactive ship collision avoidance method.
A lot of valuable research has been carried out on autonomous ship collision avoidance decision-making. The concepts, techniques and key points of ship collision avoidance have been summarised in some literature reviews (Statheros et al., Reference Statheros, Howells and Maier2008; Tam et al., Reference Tam, Bucknall and Greig2009; Huang et al., Reference Huang, Chen, Chen, Negenborn and Van Gelder2020). With the continuous development of intelligent unmanned technology, the obstacle avoidance theory of unmanned systems gradually migrated to the marine field. Researchers have designed many new collision avoidance algorithms and achieved good results, such as the improved artificial potential field (APF) (Xue et al., Reference Xue, Clelland, Lee and Han2011; Lyu and Yin, Reference Lyu and Yin2019), the dynamic window (DW) (Wilthil et al., Reference Wilthil, Flåten, Brekke and Breivik2018), the modified model predictive control (MPC) (Johansen et al., Reference Johansen, Perez and Cristofaro2016; Xie et al., Reference Xie, Garofano, Chu and Negenborn2019) and the velocity obstacle method (Kuwata et al., Reference Kuwata, Wolf, Zarzhitsky and Huntsberger2013; Zhao et al., Reference Zhao, Li and Shi2016; Shaobo et al., Reference Shaobo, Yingjun and Lianbo2020). It is also worth noting that methods based on deep reinforcement learning have become popular in recent years (Shen et al., Reference Shen, Hashimoto, Matsuda, Taniguchi, Terada and Guo2019; Zhao and Roh, Reference Zhao and Roh2019), and also the analysis and processing method based on big data, such as the automatic identification system (AIS) (Zhang et al., Reference Zhang, Kujala and Hirdaris2022b, Reference Zhang, Liu, Hirdaris, Zhang and Tian2023). As mentioned above, the goal of the proactive ship collision avoidance method is to ensure ship safety as much as possible, so most algorithms do not consider the issue of coordination between ships, and they prefer to make decisions and take actions independently.
(1) Centralised ship collaborative collision avoidance method.
The centralised method means that all ships will be coordinated by a unified central station from a global perspective (Akdağ et al., Reference Akdağ, Solnør and Johansen2022a). The goal of this method is to find the global optimal solution. Notably, this type of approach is based on a strong assumption, namely all ships are subject to the control of the central station. The centralised method is more suitable for the scheduling of the vessel traffic service (VTS) centre. Multi-objective optimisation algorithms are more suitable for solving such problems. Tam and Bucknall (Reference Tam and Bucknall2013) developed a deterministic collision avoidance path planning algorithm to provide collision-free paths for all involved ships, assuming that all encountering ships are in a cooperative mode. Liu et al. (Reference Liu, Deng and Zhang2016) proposed a hybrid optimisation cultural algorithm (CA) based on the particle swarm optimisation and bacterial foraging algorithm. Szlapczynski and Szlapczynska (Reference Szlapczynski and Szlapczynska2012) presented a multi-ship trajectory planning method by using evolutionary algorithms. Li et al. (Reference Li, Liu and Negenborn2019a) proposed a rolling horizon optimisation approach for multiple ships from a global optimal perspective, with the aim to minimise the time costs and course angle alterations of the anti-collision operations. For multi-ship collision avoidance under mixed scenarios, we cannot guarantee that each ship with different thinking will implement the global optimal solution strictly. Because the global optimal is not the individual optimal, such a strategy is unrealistic to execute without strong constraints.
(1) Distributed ship coordinated collision avoidance method.
The distributed method allows for different intelligent agents calculating their own decisions at the same time. This decentralised approach makes the collaborative collision avoidance process no longer dependent on the central station and improves the robustness of the decision-making system. Zhang et al. (Reference Zhang, Zhang, Yan, Haugen and Soares2015) presented a distributed multi-ship collision avoidance decision support formulation under the Convention on the International Regulations for Preventing Collisions at Sea (COLREGS), in which all the involved ships in this algorithm can make a decision individually and obey the basic principles of the COLREGS. Kim et al. (Reference Kim, Hirayama and Okimoto2015) use a distributed local search algorithm (DLSA) and a distributed tabu search algorithm (DTSA) to find optimal courses for involved ships. Li et al. (Reference Li, Liu, Negenborn and Ma2019b) proposed a distributed coordination strategy to deal with the many-to-many ship collision avoidance problem, where an optimisation strategy is adopted to find the most efficient collision avoidance plan for ships, namely, the rudder angles that each ship should take, and the corresponding operation time for rudder steering. Wang et al. (Reference Wang, Wu, Zhang, Wu and Wang2020) proposed a novel scheme called ‘observation-inference-prediction-decision (OIPD)’. OIPD is used for the distributed multi-ship collision avoidance problem with consideration of the autonomous, dynamic nature of the real circumstance. Li et al. (Reference Li, Wang, Guan and Pan2020) used a distributed algorithm to communicate the entire collision avoidance trajectory information for each ship. Akdağ et al. (Reference Akdağ, Fossen and Johansen2022b) used the scenario-based model predictive control method to realise collaborative collision avoidance. The distributed method is still based on some assumptions that all decision-makers are intelligent agents with the same decision-making logic or the OS can know the trajectory of TSs in advance. For the mixed scenario, which is discussed above, the distributed method still has its own limitations.
1.3 Motivation and contributions
Based on the above discussions, most of the current multi-ship collision avoidance decision-making models are more inclined to actively avoid other TSs from the perspective of the OS. Under such a strategy, the OS always yields to other ships. This mode will not only cause greater off-course cost, but also uncoordinated collision avoidance scenarios, which will affect the safety of ship navigation. Moreover, these two typical multi-ship cooperative collision avoidance algorithms, namely ‘distributed’ and ‘centralised’, also have their own limitations. The distributed method requires all ships to adopt a consistent collision avoidance model, which is mainly suitable for scenarios such as the cluster control of multi-unmanned ship. The goal of the centralised method is to achieve the global optimal solution, requiring each ship to obey decision-making instructions, which is mainly used in centralised command and dispatch scenarios such as VTS. Autonomous ships that behave in a more human-like manner have always been the goal of researchers. At present, most ships that are in danger of collision need to communicate and coordinate through a VHF radio to ensure the consistent collision avoidance actions. Therefore, considering ‘collaborative’ in decision-making models will be one of the main research directions of collision avoidance algorithms in the future.
However, the mixed multi-ship collision avoidance scenario is different from the general scenario. There are different ships with different levels of autonomy under the same ‘mixed scenarios’, so that the OOWs on various ship bridge or the collision avoidance algorithms adopted in different ANS always have their own unique strategies, which brings challenges to multi-ship collaborative collision avoidance under mixed scenarios. The biggest feature of the mixed scenario is that each decision-making participant has a different collision avoidance logic. The key to realise collaborative collision avoidance between ships under a mixed scenario is how to make all participants reach a consensus on this collaborative collision avoidance strategy. The consensus-based collaborative collision avoidance strategy is not necessarily the global optimal solution, but it should be a binding and fair strategy that can prompt all ships to act according to the agreement.
Therefore, a collaborative collision avoidance strategy for autonomous ships under mixed scenarios is envisioned in this paper. Under this strategy, the cooperative objects and timing are determined, and then the cooperative network is constructed. Then, based on the cooperative game theory, the collision avoidance responsibilities of different ships under the same mixed scenario are evaluated, and the cooperative strategy is finally generated. Under this special mixed scenario, autonomous ships can not only generate collision avoidance decisions for themselves, but also can create some corresponding action expectations for other ships. This collaborative strategy can satisfy group rationality and individual rationality, and also can provide a basis for the negotiation between multi-ship collision avoidance.
1.4 Outlines
The structure of this paper is as follows. The methodology for making collaborative collision avoidance strategies is described in detail in Section 2. A case study (including two different scenarios) is shown in Section 3. Section 4 includes discussions on the performance of this strategy. Conclusions are summarised in Section 5.
2. Methodology and modelling
The framework of the model proposed in this paper is shown in Figure 1. According to the ships’ initial state information and COLREGS, the collision risk matrix and encounter situation matrix between ships can be calculated, and the collaborative collision avoidance network of this mixed scenario can be formed. After that, according to the cooperative game model, the collision avoidance responsibility of each ship is divided, and the collaborative decisions are calculated according to GRVO and delivered to each ship for execution.
Figure 1. A framework for collaborative collision avoidance decision-making method under mixed scenarios
2.1 Construction of collaborative collision avoidance network
Due to the different levels of ship autonomy, each ship under the mixed scenario has its own understanding of the current situation. To formulate a collaborative collision avoidance strategy between multi-modal ships at sea, it is first necessary to determine a relatively objective calculation method to identify the objects that need to be collaborative and the timing of collaboration in mixed scenarios, build a reasonable collaborative network, and improve the quality of collaboration. In other words, it is necessary to find ships that are currently related to each other in the space centred on the OS, and they may be directly related or indirectly related (through other ships). In this section, we propose a method for constructing a collaborative collision avoidance network under mixed scenarios, which is calculated by a double-matrix model, the collision risk matrix, and the encounter situation matrix. Ship collision risk creates connections between different ships, and the encounters define these connections. At the same time, according to the requirements of the relevant clauses of COLREGS (1972), collision risk is the prerequisite for the formation of the encounter situation, so the collision risk matrix is directly related to the encounter situation matrix (Wang et al., Reference Wang, Zhang and Zheng2021).
First, define $\xi$
as the scene composed of all ships within a radius of 12 nautical miles centred on the OS, as shown in Equation (1), the scene $\xi$
contains $n + 1$
ships in total:
To make $n + 1$
ships map to each other, the collision risk matrix $M_{\textrm{CR}}^\xi$
and the encounter situation matrix $M_{\textrm{ES}}^\xi$
are both constructed, each of which are $({n + 1} )\times ({n + 1} )$
symmetric matrices and the main diagonal elements are zero, as shown in Equations (2) and (3). The matrix elements $\textrm{CR}_a^b$
and $\textrm{ES}_a^b$
respectively represent the collision risk of ship b relative to ship a and the encounter situation between these two ships, where $M_{\textrm{ES}}^\xi$
is determined by $M_{\textrm{CR}}^\xi$
:
For the element $\textrm{CR}_a^b$
, there are many ways to calculate the collision risk between ships (Szlapczynski and Szlapczynska, Reference Szlapczynski and Szlapczynska2017; Chen et al., Reference Chen, Huang, Mou and Van Gelder2019). The most widely used methods are still based on the distance at closest point of approach (DCPA; unit, nautical miles) and the time to closest point of approach (TCPA; unit, minutes). This set of spatiotemporal parameters can objectively represent the risk and urgency of collision between two ships, so this paper calculates $\textrm{CR}_a^b$
based on these two index values.
For DCPA, what needs to be explained here is that the value range of the original calculation result $\textrm{DCP}{\textrm{A}^\ast }$
is equal to $({ - \infty , + \infty } )$
. The following $\textrm{DCPA}$
is the result of taking the absolute value of $\textrm{DCP}{\textrm{A}^\ast }$
. For $\textrm{DCP}{\textrm{A}^\ast }$
, its positive and negative values have different meanings: if the TS is on the left side of the OS, when the TS passes the bow of the OS, $\textrm{DCP}{\textrm{A}^\ast } < 0$
and when passing the stern of the OS, $\textrm{DCP}{\textrm{A}^\ast } > 0$
; if the TS is on the right side of the OS, when the TS passes the bow of the OS, $\textrm{DCP}{\textrm{A}^\ast } < 0$
and when passing the stern of the OS, $\textrm{DCP}{\textrm{A}^\ast } > 0$
.
This paper defines that there is no risk when $\textrm{DCPA} > 0.9$
, $\textrm{TCPA} > 20$
or $\textrm{TCPA} \le 0$
. In addition to this condition, the time risk function $f({\textrm{TCPA}} )$
and the space risk function $f({\textrm{DCPA}} )$
are constructed, as respectively shown in Equations (4) and (5). The calculation results of collision risk between two ships are obtained by weighting, as shown in Equation (6), where $\textrm{CR}_a^b \in [{0,1} ]$
.
For the element $\textrm{ES}_a^b$
, based on the requirements of relevant clauses from COLREGS, this paper further divides three typical encounter scenarios (head-on, overtaking and crossing) into 16 types. It can reflect the information between ships in a more detailed manner and assist in the formulation of collaborative strategies. The following scene divisions also need to satisfy two preconditions: (1) normal power-driven vessels while underway; (2) vessels in sight of each other. Refer to Figure 2 for symbols and schematic diagrams of encounter situations.
Figure 2. The division results of 16 encounter situations
To describe different encounter situations, define the bearing of ship b relative to ship a as $\theta _a^b$
, and the relative course between the two ships is $\varphi$
. Set the blue as ship a and the yellow as ship b. The descriptions on these 16 encounter situations are shown in Table 1.
Table 1. Definition of different encounter situations
As mentioned above, $M_{\textrm{ES}}^\xi$
is decided by $M_{\textrm{CR}}^\xi$
, so we define if the element $\textrm{CR}_a^b > 0.5$
in $M_{\textrm{CR}}^\xi$
, then $\textrm{ES}_a^b$
can be obtained by Table 1; otherwise, $\textrm{ES}_a^b = 0$
. According to these two matrices, $M_{\textrm{CR}}^\xi$
and $M_{\textrm{ES}}^\xi$
, we can build a cooperative collision avoidance topological network, and it follow these rules:
(1) under scenario $\xi$
, ships in danger of collision are reserved as nodes of the cooperative network;(2) when two ships are in danger of collision, use an edge to connect these two nodes;
(3) the connecting edge is directional and stores information about associated ship a and b, including $\textrm{CR}_a^b$
and $\textrm{ES}_a^b$.
According to the above methods, this paper gives an example based on one multi-ship encounter scenario ${\xi ^a}$
, as shown in Figures 3(a) and 3(b). It should be noted that although there is no direct connection between two ships in the network $\textrm{CR}_a^b = 0$
, since they have a common connection node, it is considered that there is an indirect connection between them, as shown in Figure 3, TS-2 and TS-3, they use the OS as the relay node.
Figure 3. A construction case for collaborative topological network. (a) Multi-ship encounter scenario ${\mathrm{\xi }^\textrm{a}}$
. (b) Collaborative network under scenario ${\mathrm{\xi }^\textrm{a}}$
2.2 Multi-ship cooperative game model
2.2.1 Description of multi-ship cooperative game
The cooperative game is an important branch of game theory, which means that in the process of the game, different players can reach a binding cooperation contract to form a coalition (Lisowski, Reference Lisowski2012). The benefits obtained by participants should not be less than the benefits obtained by independent individuals when they did not participate in the coalition. The essence of a cooperative game is to find a way to distribute benefits, promote cooperation among different participants and improve efficiency.
Multi-ship collaborative collision avoidance under mixed scenarios can be described and modelled with reference to cooperative game theory. As mentioned in Section 1.3, due to the different levels of autonomy and decision-making logic of each ship in the mixed scenario, the key for each ship to participate in this coalition to form a synergy is that the benefits of participating in the process of collision avoidance are greater than the benefits obtained by taking actions alone. In this paper, we convert the benefit distribution method of collaborative collision avoidance into the distribution problem of collision avoidance responsibility. By rationally distributing the avoidance responsibilities of all parties involved, each ship can obtain more benefits from the coalition, and promote the participation of ships with different decision logics to participate in this coordination, thereby forming a stable coalition.
Let the cooperative game formed by multi-ship cooperative collision avoidance be denoted as $G({N,\; \mu } )$
. According to the collaborative network constructed in Section 2.1, ships participating in the game are nodes in the network structure, and the set of game participants is denoted as N. Let $N = \{{{S_1},{S_2}, \ldots ,{S_n}} \}$
, n represents the number of ships participating in the current scenario and μ(N) is the total revenue of the grand coalition formed by this complete collaboration network. For any $P \subseteq N$
, we call $P = \{{{S_1},{S_2}, \ldots ,{S_p}} \}$
a sub-coalition in N, and its corresponding sub-coalition revenue is recorded as $\mu (P )$
. Let $R = \{{{r_1},{r_2}, \ldots ,{r_n}} \}$
be a solution of the cooperative game $G({N,\; \mu } )$
, then ${r_k}$
in the solution set is the collision avoidance responsibility of ship ${S_k}$
.
2.2.2 Sub-coalition separation
The benefit distribution of each ship in coalition N is related to the benefit of each ship in the participating sub-coalition P. Therefore, it is necessary to divide the cooperative network into sub-coalitions to clarify which sub-coalitions each ship is in. For n ships participating in the collaboration, the dimension interval of its sub-coalition is $[{1,n} ]$
, any node is directly or indirectly connected by connecting edges, and these nodes are considered to form a coalition. The sub-coalition is obtained by dividing the major coalition, and the connection line retains $\textrm{CR}_a^b$
and $\textrm{ES}_a^b$
between a and b.
Taking the collaborative network in Section 2.1 as an example, the major coalition $N = 5$
, so the sub-coalition dimension interval is $[{1,5} ]$
. The results are as follows:
one-dimensional coalition ${P^1}$
: {OS}, {TS-1}, {TS-2}, {TS-3}, {TS-4};two-dimensional coalition ${P^2}$
: {OS,TS-1}, {OS,TS-2}, {OS,TS-3}, {OS,TS-4}, {TS-1,TS-2}, {TS-1,TS-3}, {TS-1,TS-4}, {TS-3,TS-4};three-dimensional coalition ${P^3}$
: {OS,TS-1,TS-2}, {OS,TS-1,TS-3}, {OS,TS-1,TS-4}, {OS,TS-2,TS-3}, {OS,TS-2,TS-4}, {OS,TS-3,TS-4}, {TS-1,TS-2,TS-3}, {TS-1,TS-2,TS-4}; {TS-1,TS-3,TS-4};four-dimensional coalition ${P^4}$
: {OS,TS-1,TS-2,TS-3}, {OS,TS-1,TS-2,TS-4}, {OS,TS-1,TS-3,TS-4}, {OS,TS-2,TS-3,TS-4};five-dimensional coalition ${P^5}$
: {OS,TS-1,TS-2,TS-3,TS-4}.
2.2.3 Revenue function
Since a ship taking collision avoidance actions will deviate from the original route and disturb the normal navigation state, under the premise of ensuring the safety of navigation, OOWs prefer to use a small range of instructions at a suitable time. If an agreement is reached after negotiation with other ships, the OS's collision avoidance responsibility can be allocated, so that it does not need to afford 100% of the collision avoidance obligation, which is the main way for ships to participate in the coalition to obtain benefits. In addition, reaching an agreement to form a stable collaborative coalition can also ensure that each ship will take reasonable and effective evasive actions to achieve safe passing under mixed scenarios. In this section, we will give the description of the revenue function for sub-coalitions of different dimensions.
Define the benefit of the $k$
-th ship in the sub-coalition as $\lambda ({{S_k}} )$
, then for the $n$
-dimensional sub-coalition ${P^n}$
, its revenue function is shown in Equation (7). That is, the benefit of coalition is equal to the sum of the benefit of each ship in this coalition:
For one-dimensional coalition ${P^1}$
, since only one ship is included, it cannot gain any benefit from coalition, and the revenue function of it is $\mu ({{P^1}} )= 0$
.
For two-dimensional coalition ${P^2}$
, suppose a two-dimensional coalition $\{{s,t} \}$
includes ship s and ship t, then there is a collision risk $\textrm{CR}_s^t$
and encounter situations $\textrm{ES}_s^t$
and $\textrm{ES}_t^s$
obtained from Table 1. For a typical two-ship coalition, this paper defines that the benefit $\lambda$
obtained by one ship comes from the collision risk $\textrm{CR}_s^t$
that the other ship can share. This is because if a ship does not participate in coalition, since it does not know the intentions and actions of the other ship, in theory, it will have to bear all the obligation to clear the current collision risk. According to COLREGS, we can divide a two-dimensional coalition $\{{s,t} \}$
into the give-way and stand-on ships. For a head on situation, since both ships have the obligation to take actions, each bears 50% of $\textrm{CR}_s^t$
. For other situations, the give-way ship needs to undertake the collision avoidance obligation whether it participates or not, so the benefit is equal to 0. The stand-on ship can sail directly with full confidence due to the coordination of the give-way ship, so the benefit is the entire $\textrm{CR}_s^t$
. To sum up, the revenue function of two-dimensional coalition is the superposition of $\lambda (s )$
and $\lambda (t )$
, as shown in Equation (8):
For multidimensional coalition ${P^w}({w > 2} )$
, due to the increase in the number of ships, evasive actions taken by ships in different encounter situations will interact with each other, so this paper follows the strong domination property of COLREGS in the cooperative game model. Set multidimensional coalition ${P^w}$
as $\{{{k_1},{k_2}, \ldots ,{k_w}} \}$
, then the revenue function $\lambda (k )$
of each ship k in the multi-dimensional coalition is not only related to the collision risk $\textrm{CR}$
shared by another ship, but also related to the expectation of the other ships’ actions. The benefit of the latter mainly comes from the give-way ship defined in this mixed scenario. If the action of the stand-on ship is an assistant action (in this paper, assistant actions are related to the encounter situation between two ships: when an encounter situation belongs to head on or crossing, the same turning direction is an assistant action; when an encounter situation belongs to overtaking, the opposite turning direction is an assistant), it can be regarded as sharing collision avoidance responsibility of the give-way ship, which can reduce the range of evasive action taken by the give-way ship, so that the give-way ship can benefit from it.
Taking the three-ship coalition in Figure 4 as an example, it can be seen from Table 1 that $\textrm{ES}_{{k_1}}^{{k_2}} = \textrm{C}2$
and $\textrm{ES}_{{k_2}}^{{k_3}} = \textrm{C}2$
; therefore, ${k_2}$
is a stand-on ship relative to ${k_1}$
but also a give-way ship relative to ${k_3}$
. Considering $\textrm{ES}_{{k_1}}^{{k_3}} = \textrm{H}2$
, according to COLREGS, both ${k_2}$
and ${k_3}$
need to alter course to the right side. It is an assistant action relative to ${k_1}$
and ${k_2}$
, so ${k_1}$
and ${k_2}$
can turn the original dashed trajectories into solid lines, and the range of evasive actions is reduced, so ${k_1}$
and ${k_2}$
gain additional benefits.
Figure 4. Benefit to be obtained from expected evasive actions
Therefore, let $G = \{{{g_1},{g_2}, \ldots ,{g_v}} \}$
be the set of give-way ships under different encounter situations in coalition ${P^w}$
, then for any one of the ships ${g_i}$
, its corresponding stand-on ship is set as ${h_i}$
. Take this stand-on ship as the central node to obtain all connected edge information, including encounter situation set $\textrm{E}{\textrm{S}_{{h_i}}}$
and collision risk set $\textrm{C}{\textrm{R}_{{h_i}}}$
.
We can index $\textrm{E}{\textrm{S}_{{h_i}}}$
according to Table 2. Since the rules do not clearly stipulate the turning direction in an overtaking situation, the left steering is subject to the right steering. To determine whether ${h_i}$
takes an assistant action can be achieved by comparing with $\textrm{ES}_{{h_i}}^{{g_i}}$
. If not, the benefit of ${g_i}$
is equal to 0; if it does, the benefit of ${g_i}$
in the coalition can be calculated from Equation (9):
Table 2. Turning directions in different situations defined by COLREGS
Among them, δ is the tuning factor, which is determined by $\textrm{ES}_{{h_i}}^{{g_i}}$
, as shown in Table 3. A larger turning range that ${g_i}$
may take suggests a higher expected benefit of ${h_i}$
. In addition, $\textrm{CR}_{{h_i}}^{\textrm{max}}$
represents the maximum collision risk value among ships associated with ${g_i}$
. A greater collision risk will result in a greater range of assistant actions that will be taken by ${g_i}$
. Therefore, the total revenue of coalition ${P^w}$
from taking actions by other ships is the sum of all benefits from give-way ships. In addition, let the number of connected edges (in danger of collision with each other) of coalition $\{{{k_1},{k_2}, \ldots ,{k_w}} \}$
equal m. Then the benefit of coalition ${P^w}$
generated by the collision risk that can be shared by another ship under the current encounter situation is the sum of collision risks of those connection edges, so the final multi-dimensional coalition revenue function is shown in Equation (10):
Table 3. Tuning factors under different encounter situation (give way)
2.2.4 Assignment of collision avoidance responsibility
In the previous section, the benefit calculation methods from one-dimensional to multi-dimensional coalition were introduced. In a multi-ship cooperative coalition $N = \{{{S_1},{S_2}, \ldots ,{S_n}} \}$
, different participants obtain different benefits in this coalition, so it is unreasonable to evenly distribute the collision avoidance responsibility of each ship in this collaborative network when formulating a multi-ship collaborative collision avoidance strategy. The collision avoidance responsibility of each ship should be allocated proportionally according to the contribution of each ship to the total benefit $\mu$
of coalition N, and the contribution of each ship to the coalition is proportional to the distribution of benefits obtained by each ship in this coalition. Therefore, in the multi-ship cooperative collision avoidance strategy, the allocation of collision avoidance responsibility of each ship is directly related to the distribution of the coalition benefit. The collision avoidance responsibility allocation scheme that conforms to the above logic is more likely to be adopted and implemented by ships with different decision-making logic under mixed scenarios, and then promotes cooperation among multiple ships.
To calculate the solution $R = \{{{r_1},{r_2}, \ldots ,{r_n}} \}$
of a multi-ship cooperative game $G({N,\; \mu } )$
, this paper uses the Shapley value method (Shapley and Shubik, Reference Shapley and Shubik1954). The most important point of this method is that it reflects the contribution of all parties in the same coalition to the overall goal of cooperation and avoids egalitarianism in the process of benefits distribution. The benefit $\mu (i )$
distributed by the $i$
-th ship in the coalition N can be obtained by Equation (11):
According to the description in Section 2.2.1, P is a sub-coalition of N and p is the number of participants in the sub-coalition. By Equation (11), the benefit distribution of all participants in coalition N is obtained, then for the solution $R = \{{{r_1},{r_2}, \ldots ,{r_n}} \}$
, the collision avoidance responsibility ${r_i}$
of the $i$
-th ship is shown in Equation (12):
2.3 Calculation of collaborative collision avoidance strategy
When ships do not participate in the collaborative network under a mixed scenario, it is unclear whether other ships will take evasive action. Therefore, to ensure the safety of navigation, most ships take proactive actions, and the responsibility of each ship to bear is still 100%. Due to the construction of collaborative network, ships participating in the same coalition can share collision avoidance responsibility with each other. As mentioned in Section 2.2, the more benefits obtained by participating in the coalition will mean the greater the collision avoidance responsibility is shared. In this section, according to the final result $R = \{{{r_1},{r_2}, \ldots ,{r_n}} \}$
of the cooperative game model, we use the GRVO method to calculate the final strategy for multi-ship collaborative collision avoidance under mixed scenarios, and the strategy form is the steering angle of each ship.
For any ship ${S_i}$
in the coalition $N = \{{{S_1},{S_2}, \ldots ,{S_n}} \}$
, with this ship as the central node, we can obtain the set of ships in different encounter situations connected to it as $D = \{{{d_1},{d_2}, \ldots ,{d_m}} \}$
, and also the set of encounter situations $\textrm{E}{\textrm{S}_{{S_i}}}$
. For any ship ${d_j}$
in set D, the velocity obstacle (VO) (Van den Berg et al., Reference Van den Berg, Lin and Manocha2008) for ${S_i}$
induced by ${d_j}$
is the set of velocities that, if chosen from, will eventually lead to a dangerous situation between two ships. Let C represent the ship position, then $\textrm{RC} = {C_{{d_j}}} - {C_{{S_i}}}$
represents the relative position between these two ships, and let V represent the ship speed, then $\textrm{RV} = {V_{{S_i}}} - {V_{{d_j}}}$
represents the relative speed between these two ships. Now define a ray $\gamma$
that starts from the RC point and launches in the direction of $\textrm{RV}$
, then the position of this ray after time t is shown in Equation (13):
Define the safe encounter distance $\textrm{SD}$
between two ships to be positively correlated with ship distance $|{\textrm{RC}} |$
, as shown in Equation (14), units are in nautical miles. Then use the symbol $\psi$
to represent the circular area with ${d_j}$
as the centre and $\textrm{SD}$
as the radius. Therefore, the velocity obstacle $\textrm{V}{\textrm{O}_{{S_i}|{d_j}}}$
for ${S_i}$
induced by ${d_j}$
can be expressed as Equation (15):
The definition of $\textrm{V}{\textrm{O}_{{S_i}|{d_j}}}$
is based on the fact that ship ${S_i}$
bears 100% of the collision avoidance responsibility relative to ${d_j}$
. In other words, ${S_i}$
takes evasive action alone to ensure that these two ships pass at a safe distance $\textrm{SD}$
. However, in a multi-ship collaborative network under a mixed scenario, each ship is assigned with different collision avoidance responsibility according to the result $R = \{{{r_1},{r_2}, \ldots ,{r_n}} \}$
of the cooperative game. Let ${r_S}_i$
and ${r_d}_j$
be the collision avoidance responsibility of ${S_i}$
and ${d_j}$
assigned in a collaborative network, respectively, then the relative responsibility of ${S_i}$
relative to ${d_j}$
can be calculated by Equation (16):
Therefore, the original velocity obstacle $\textrm{V}{\textrm{O}_{{S_i}|{d_j}}}$
can be updated to $\textrm{GRV}{\textrm{O}_{{S_i}|{d_j}}}$
based on the definition of GRVO. Let the current velocity of ${S_i}$
be $V_{{S_i}}^\ast$
, then $\textrm{GRV}{\textrm{O}_{{S_i}|{d_j}}}$
can be expressed as Equation (17), and the schematic is shown in Figure 5 (with a responsibility of 50%):
Figure 5. Generalised reciprocal velocity obstacle
In addition, when situation $\textrm{ES}_{{S_i}}^{{d_j}}$
meets the conditions listed in Table 2, $V_{{S_i}}^\ast$
will also be constrained by the turning direction. Set the turning direction constraint imposed by ${d_j}$
on ${S_i}$
to be ${\sigma ^{{d_j}}}$
, then the functions for right turning constraint $\sigma _r^{{d_j}}$
and left turning constraint $\sigma _l^{{d_j}}$
can be shown in Equation (18). Here, ‘${\times}$
’ represents the vector cross product and $\varphi$
represents the relative course.
Therefore, for any ship ${d_j}$
in set D, ${S_i}$
can provide the relative velocity obstacle area $\textrm{GRV}{\textrm{O}_{{S_i}|{d_j}}}$
and turning constraint ${\sigma ^{{d_j}}}$
. Let the velocity vector corresponding to ${S_i}$
at different turning angles $\varepsilon$
be $V_{{S_i}}^{{\varepsilon ^\ast }}$
, then the initial collision avoidance decision ${\varepsilon _{{S_i}}}$
of ship ${S_i}$
in the cooperative collision avoidance coalition N can be calculated by Equation (19):
The initial decision ${\varepsilon _{{S_i}}}$
of ${S_i}$
in coalition N can meet the requirements in most scenarios, considering that the definition of Table 2 above is in accordance with the requirement of ‘left turning obeys right turning’. So, for the decision ${\varepsilon _{{S_i}}}$
, if ship ${d_j}$
is regarded as the overtaken ship, and the decision of ${S_i}$
relative to this ship under collision avoidance responsibility $r_{{S_i}}^\ast$
is to turn right, then the assistant action that ${d_j}$
is expected to share is to turn left. However, the final decision of ${d_j}$
may be a right turn in the global situation. Therefore, for each ship $d_o^j$
in the subset ${D_o}$
formed by the overtaken ships from set D, it is necessary to review the initial decision ${\varepsilon _{{S_i}}}$
. If none of ${\varepsilon _{{S_i}}}$
is located in each ship's velocity obstacle area $\textrm{GRV}{\textrm{O}_{{S_i}|d_o^j}}$
in the set ${D_o}$
, then ${\varepsilon _{{S_i}}}$
is feasible; if not, let the new velocity be $V_{{d_j}}^\ast$
, which corresponds to the decision of ship $d_o^j$
in the coalition, then calculate the new velocity obstacle area $\textrm{GRV}{\textrm{O}_{{S_i}|{d_j}}}$
and get the updated final decision ${O_{{S_i}}}$
.
In summary, for the collaborative collision avoidance coalition $N = \{{{S_1},{S_2}, \ldots ,{S_n}} \}$
under a mixed scenario, the final solution of the cooperative collision avoidance strategy is obtained as $O = \{{{O_{{S_1}}},{O_{{S_2}}}, \ldots ,{O_{{S_n}}}} \}$
.
3. Case study
In this section, we designed two scenarios: one is a three-ship encounter situation and the second is a five-ship encounter situation. We tested the above models in a simulation environment to verify the effectiveness of multi-ship cooperative collision avoidance strategies.
3.1 Scenario I
The initial parameters of each ship under this scenario are shown in Table 4, where the ship position is a relative coordinate with $({0,0} )$
as the centre point. According to the collaborative network construction method proposed in Section 2.1, the collision risk matrix and the encounter situation matrix among these three ships are shown in Tables 5 and 6, respectively. According to the above information, we can get a topological network of cooperative collision avoidance between ships under this scenario, as shown in Figure 6. It can be seen that these three ships in this scenario are all connected to each other, and the decision of any ship will have an impact on the other ships.
Table 4. Initial state parameters of each ship in Scenario I
Table 5. Collision risk matrix of Scenario I
Table 6. Encounter situation matrix of Scenario I
Figure 6. A collaborative topology network for Scenario I
According to this network, we can get the sub-coalitions with different dimensions and their benefits, as shown in Table 7. At the same time, according to the Shapley value method, the allocation ratio of collision avoidance responsibility of each ship under this scenario and the final collaborative decision of each ship can be obtained, and the results are shown in Table 8.
Table 7. Sub-coalitions of Scenario I and their benefits
Table 8. Collision avoidance responsibility and collaborative decision for each ship under Scenario I
We assume that each ship forms a cooperative network at the position in Table 4, and the global collision avoidance responsibility assigned to each ship under this mixed scenario also reaches an agreement at this moment, that is, all three ships will take evasive actions at these coordinates in Table 4 at the same time. The final results of the simulation verification of this model in the first scenario are shown in Figure 7(a)–7(f). Figure 7 records the whole process of each ship's collision avoidance decision and the trajectory of each ship under Scenario I. The starting point of each ship is set at the position 720 s before the coordinates in Table 4, and the end point of each ship is a point on the extension line of the starting point of each ship along the ship course. To reflect the ship's manoeuvrability characteristics, we set the steering rate of each ship to 2°/10 s during the whole simulation test. In addition, we have also simplified the strategy for resuming voyages after each ship has finished evasive action, that is, if any ship meets the condition of $\textrm{TCPA} < 0$
with other ships that have been in danger of collision, then this ship ends evasion and navigates to the destination (returns to the original route). The DCPA values relative to each other when these ships take evasive action are shown in Table 9.
Figure 7. Collision avoidance trajectory of each ship under Scenario I. (a) T = 500 s. (b) T = 1000 s. (c) T = 1500 s. (d) T = 2000 s. (e) T = 2500 s. (f) T = 3433 s (Reach Destination)
Table 9. DCPA relative to other ships under Scenario I
In addition, the relative distances with other ships during the whole process are shown in Figure 8(a)–8(c). It can be seen from the figure that although each ship imposes a steering rate, the relative distance between these ships is within the range of the safe encounter distance, which can improve the collision avoidance efficiency and effectiveness.
Figure 8. Change of relative distance between ships under Scenario I. (a) Ship1. (b) Ship2. (c) Ship3
3.2 Scenario II
Scenario II is a more complex mixed situation, including a total of 5 ships, and the initial state parameters of each ship are shown in Table 10. The collision risk matrix and the encounter situation matrix calculated by this model, according to the information in Table 10, are shown in Tables 11 and 12, respectively. According to the above information, the topological collaborative network formed by these ships in Scenario II can be obtained, as shown in Figure 8.
Table 10. Initial state parameters of each ship in Scenario II
Table 11. Collision risk matrix of Scenario II
Table 12. Encounter situation matrix of Scenario II
It can be seen from Figure 9, the five-ship coalition can be divided into 28 sub-coalitions according to different dimensions (one-dimensional to five-dimensional), and the benefit of each sub-coalition is shown in Table 13. According to Table 13, the global collision avoidance responsibility of each ship assigned by this model and the final multi-ship cooperative collision avoidance strategy under this mixed scenario can be calculated as shown in Table 14.
Figure 9. A collaborative topology network for Scenario II
Table 13. Sub-coalitions of Scenario II and their benefits
Table 14. Collision avoidance responsibility and collaborative decision for each ship under Scenario II
Consistent with the settings in Scenario I, we assume that each ship forms a cooperative network at the positions in Table 10, and at the same time, these five ships under this mixed scenario reach an agreement on the global collision avoidance responsibility assigned by this model. The final results of model simulation verification are shown in Figure 10(a)–10(f). This figure records the entire process of each ship's collision avoidance decision and the navigation trajectory. The DCPA values relative to each other when these ships take evasive action are shown in Table 15.
Figure 10. Collision avoidance trajectory of each ship under Scenario II. (a) T = 500s. (b) T = 1000s. (c) T = 1500s. (d) T = 2000s. (e) T = 2500s. (f) T = 3946s (Reach Destination)
Table 15. DCPA relative to other ships under Scenario II
At the same time, we also recorded the relative distances between ships in this scenario, as shown in Figure 11(a)–11(e), respectively. According to the distance change curve, it can be known that the cooperative collision avoidance strategy generated by this model can make ships safely pass and clear.
Figure 11. Change of relative distance between ships under Scenario II. (a) Ship1. (b) Ship2. (c) Ship3. (d) Ship4. (e) Ship5
4. Discussion
Aiming at the mixed scenario where ships with multiple autonomous levels coexist at the same time, the collaborative collision avoidance model proposed in this paper tries to solve this problem by rationally assigning the collision avoidance responsibility of each ship. Through the model verification in Section 3, this collaborative collision avoidance strategy under mixed scenarios proposed in this paper has the following advantages.
First, the most obvious benefit of the cooperative collision avoidance strategy is that the range of collision avoidance actions taken by each ship is reduced. According to the experience of collision avoidance at sea, on the premise that the evasive action can be clearly identified, a smaller range of evasive actions will mean the less deviation from the original route and the less cost generated by evasive actions. Many OOWs tend to take appropriate (smaller angle) evasive decisions on the premise of ensuring safety. To illustrate this point, the velocity obstacle method is also used, and the safe encounter distance defined in Section 2.3 is also adopted. The decisions taken by each ship participating in the cooperation and not participating in the cooperation in Scenarios I and II are compared. The results are respectively shown in Tables 16 and 17. The direct reason for the reduction in the decision's range is that the ship's independent collision avoidance responsibility is shared by other ships.
Table 16. Comparison of decisions before and after collaboration (Scenario I)
Table 17. Comparison of decisions before and after collaboration (Scenario II)
Second, a collaborative strategy is a deterministic decision. Compared with the proactive collision avoidance decision-making models introduced in Section 1.2, the collaborative collision avoidance strategy assigns different decisions to each ship in a multi-ship encounter situation from a global perspective, which makes the future actions of each ship in the scenario determined, reducing the potential collision risk due to the uncertainty of those behaviours taken by other ships. At the same time, this deterministic strategy makes each ship reduce the number of collision avoidance actions. From the experimental results in Section 3, each ship takes only one evasive action, which improves the efficiency of ship collision avoidance.
Third, the collaborative strategy formed through the cooperative game model is suitable for the mixed scenario involving ships with different autonomy levels. Under such a scenario, the decision-making logic of each ship is different, and it is difficult to establish objective constraints to define the collision avoidance action of each ship or to force each ship to form a coalition. However, the collision avoidance responsibility assigned to each ship through the cooperative game model can satisfy both ‘collective rationality’ and ‘individual rationality’, which can improve the rationality of responsibility assignment and encourage each ship to accept coordination to form a stable coalition.
The multi-ship collision avoidance strategy proposed in this paper provides the possibility to realise collaborative collision avoidance between ships in mixed scenarios. This strategy is essentially a centralised collaborative collision avoidance method. However, for mixed navigation scenarios where ships of different autonomy levels coexist in open waters, it is difficult to determine a centralised and coordinated cooperative control unit. Therefore, considering the practical application of this strategy in the future, the calculation of the collaborative collision avoidance strategy proposed in this paper will be based on the distributed calculation method. This strategy will aim to promote collaborative collision avoidance between ships, and as an advantageous strategy, it will become the basis for collaborative interaction between ships. The specific collaborative process is shown in Figure 12. Under the mixed scenario, one ship (Ship-1) generates a collaborative collision avoidance strategy according to this paper, which not only includes the strategy that the OS plans to adopt, but also includes the action expectations for other ships, then broadcasts the strategy to other ships in the collaborative network and the other ships will give feedback after receiving this strategy. Since this strategy is based on cooperative game theory, it will have a high probability of promoting coordination among multiple ships. This model will imitate the scene of collision avoidance coordination between OOWs through a VHF radio. At the same time, in terms of future ship cooperative data communication, the VHF data exchange system (VDES), as an enhanced and upgraded version of AIS in the field of water mobile services, will provide technical support for inter-ship collaboration under mixed scenarios.
Figure 12. Multi-ship cooperative interaction mechanism
In future research work, we will try to explore the architecture of collaborative interaction between ships based on this collaborative strategy, focusing on the interactive dynamic feedback mechanism and the optimisation theory of collaborative strategies, so as to provide new ideas for multi-ship collision avoidance under mixed scenarios.
5. Conclusion
With the continuous improvement of ship intelligence, the level of autonomous operation is also rising. For traditional ship collision avoidance, different OOWs can coordinate with each other through a VHF radio to achieve safe passing. For the mixed marine scenarios, where ships with different levels of autonomy coexist, the traditional coordination method is not effective, so it is necessary to study a multi-vessel collaborative collision avoidance strategy suitable for this mixed scenario. Considering the above, the collaborative objects and timings of the mixed scenario are determined first, which is by calculating a double matrix (collision risk matrix and encounter situation matrix) and forming a collaborative network. After that, according to the cooperative game theory, based on collective rationality and individual rationality, the assignment of collision avoidance responsibility of each ship under the mixed scenario is obtained, and the final collaborative strategy is calculated according to GRVO. The verification of two complex cases shows that the model proposed in this paper can effectively solve the problem of multi-vessel collaborative collision avoidance under mixed scenarios. It can enable ships with different decision-making logic to pass at a safe encounter distance, which has certain reference significance for the multi-ship collaborative collision avoidance problem under the coexistence of ships with different autonomous levels in the future.
Acknowledgments
The research presented in this paper is supported by the Liao Ning Revitalization Talents Program (No. XLYC1902071); Cultivation Program for the Excellent Doctoral Dissertation of Dalian Maritime University (0143210263); China Scholarship Council (CSC).
