• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 1229-3431(Print)
ISSN : 2287-3341(Online)
Journal of the Korean Society of Marine Environment and Safety Vol.25 No.3 pp.259-268
DOI : https://doi.org/10.7837/kosomes.2019.25.3.259

# A Study on Intention Exchange-based Ship Collision Avoidance by Changing the Safety Domain

Donggyun Kim*
*Graduate School of Maritime Sciences, Kobe University, Japan
March 27, 2019 May 7, 2019 May 28, 2019

## Abstract

Even if only two ships are encountered, a collision may occur due to the mistaken judgment of the positional relationship. In other words, if an officer does not know a target ship’s intention, there is always a risk of collision. In this paper, the experiments are conducted to investigate how the intention affects the action of collision avoidance in cooperative and non-cooperative situations. In non-cooperative situation, each ship chooses a course that minimizes costs based on the current situation. That is, it always performs a selfish selection. In a cooperative situation, the information is exchanged with a target ship and a course is selected based on this information. Each ship uses the Distributed Stochastic Search Algorithm so that a next-intended course can be selected by a certain probability and determines the course. In the experimental method, four virtual ships are set up to analyze the action of collision avoidance. Then, using the actual AIS data of eight ships in the strait of Dover, I compared and analyzed the action of collision avoidance in cooperative and non-cooperative situations. As a result of the experiment, the ships showed smooth trajectories in the cooperative situation, but the ship in the non-cooperative situation made frequent big changes to avoid a collision. In the case of the experiment using four ships, there was no collision in the cooperative situation regardless of the size of the safety domain, but a collision occurred between the ships when the size of the safety domain increased in cases of non-cooperation. In the case of experiments using eight ships, it was found that there are optimal parameters for collision avoidance. Also, it was possible to grasp the variation of the sailing distance and the costs according to the combination of the parameters, and it was confirmed that the setting of the parameters can have a great influence on collision avoidance among ships.

## 1. Introduction

To prevent collision between ships, an alteration of course should be large enough to show the ship's intention clearly (COLREG, 1972). However, it is difficult to understand the situation of many other ships and anticipate the course of the other ship for collision avoidance. To prevent collision between ships, several methods are proposed when one-to-one or one-to-many ships are encountered (Szlapczynski, 2006;Tsou et al., 2010). In the existing method for preventing collisions, a target ship only navigates according to predetermined conditions and does not respond to the action of the own ship. However, in the actual navigation, the decision of the own ship affects the other ships and vice versa. For collision avoidance when multiple ships are encountered, several distributed algorithms are proposed (Kim et al., 2014;2015;2017). In these algorithms, a ship can find an optimal course by herself without any centralized system, such as a Vessel Traffic Service center. Each ship repeatedly communicates with each other in a way which allows a ship to detect a target ship within a certain area.

To investigate the effect of cooperative and non-cooperative situations on ship collision avoidance using a distributed algorithm, two kinds of experiments are carried out. Firstly, when four ships are encountered, the sailing distance and cost according to the safety domain in cooperative and non-cooperative situations are compared. Secondly, to demonstrate the influence of two situations on ship collision avoidance, the trajectories of all ships with AIS data are recorded and analyzed in the Strait of Dover. This paper is organized as follows: Chapter 2 provides related works on ship collision avoidance. Chapter 3 explains the distributed algorithm for ship collision avoidance. Chapter 4 presents experimental results that show the effect of cooperation with each other.

## 2. Related works

International Regulations for Preventing Collisions at Sea (COLREGs) is a representative method for preventing ship collisions. This stipulates the obligations of ships in accordance with the positional relationship between them and enables collision avoidance operations. However, when multiple ships meet at the same time, the officer may find it difficult to determine and remember the positional relationship with the other ships.

To prevent collision between ships, several methods are proposed, such as ship domain (Fujii and Tanaka, 1971;Goodwin, 1975;Szlapczynski, 2006), ant colony optimization (Tsou and Hsueh, 2010), genetic algorithm (Tsou et al., 2010), and distributed algorithm (Kim et al., 2014;2015;2017).

In ship domain, the own ship avoids collision by preventing the target ship from approaching within a certain distance, and various ship domains are then presented (Fujii and Tanaka, 1971; Goodwin, 1975). In ant colony algorithm, the ship searches for the optimal route by mimicking the way ants secrete pheromones when searching for food. The pheromone is updated by identifying the path the ants have passed. The ants probabilistically select the next path. Ants choose their path with a greater probability of short distance or a high amount of pheromone. If the calculation time exceeds the set time or exceeds the iteration count, the process ends. The genetic algorithm imitates the survival method of the gene, allowing the ship to navigate the safe route. Szlapczynski (2011) proposed a collision avoidance method using an evolutionary algorithm. When multiple ships are encountered, a collision avoidance method is proposed. The fitness function was set as the sum of the fitness of ship trajectories.

Kim et al. (2014;2015) proposed a method to prevent collision between ships using a Distributed Local Search Algorithm (DLSA) and a Distributed Tabu Search Algorithm (DTSA). A ship searches for the safest course by exchanging information with target ships. Kim et al. (2017) applied Distributed Stochastic Search (Zhang et al., 2002;2005) to reduce the number of messages generated in DLSA and DTSA. The ship chooses the next course according to probability. The precondition of the distributed algorithm is collision avoidance through cooperation with other ships. However, comparative analysis of how collision avoidance is different in a cooperative situation and an non-cooperative situation has not been carried out.

## 3. Distributed Algorithms for Ship Collision Avoidance

In this study, experiments are done using Distributed Stochastic Search Algorithm (DSSA) in cooperative and non-cooperative situations. In DSSA, each ship selects the next-intended course according to probability by exchanging information with other ships in the detection area. The next-intended course is the course that the ship is intended to go through and can be changed gradually through exchange of information with other ships. Furthermore, after applying the probability of choosing a course, the number of messages exchanged is reduced by changing multiple ship intentions simultaneously (Kim et al., 2017). In this section, I briefly describe DLSA for avoiding collision between ships in a distributed system and then describe DSSA. Algorithm 1 is the process by which each ship determines the next-intended course. Each step is repeated until there is no risk of collision. After the collision risk disappears, a ship proceeds to the next position along the next-intended course that is selected last. This process is repeated until a ship arrives at her destination, and the process ends.

A cost function that consists of two parts, namely, the sum of collision risk for the target ships and the relative angle between a candidate course and a destination, is defined as follows:

$C O S T s e l f c r s ≡ α ∑ j ∈ T a r g e t S h i p s C R s e l f c r s , j + θ d e s t − θ s e l f c r s 180 ∘$
(1)

where self and crs mean a own ship and candidate course, respectively.

Collision risk (CR) is defined as follows:

$C R s e l f c r s , j ≡ T i m e W i n d o w T C P A s e l f c r s , j if s e l f , w i l l c o n f l i c t 0 w i t h s h i p j , o t h e r w i s e$
(2)

where TimeWindow is the length of time for future position.

The longer the TimeWindow, the faster a ship react.

A ship tries to minimize the cost by

$i m p r o v e m e n t S e l f ≡ max c r s C O S T s e l f i n t e n t i o n s e l f − C O S T s e l f c r s$
(3)

where intention is the current selected course. That is, the improvement has the largest cost reduction.

A ship chooses the course that reduces risk to the most extent. The Improvement is used to determine priorities when changing courses through information exchange between ships. Equation (4) determines whether the course to the destination is within the ship's maximum maneuvering angle, and if there is a course for the destination, it is added as a candidate course.

$θ s e l f _ d e s t ≡ θ d e s t − θ h e a d i n g , if θ d e s t − θ h e a d i n g < 45 ∘ e m p t y , o t h e r w i s e$
(4)

where crs∈{-45, -40, ..., -5, 0, +5, ..., +40, +45}∪ {$θ s e l f _ d e s t$} and $θ s e l f c r s$ returns $θ ℏ e a d i n g + c r s$.

Fig. 1 shows the process using DLSA for collision avoidance. In Fig. 1(1), it is assumed that there is a collision risk in the center after t time if three ships keep their current course. Each ship sends ok? message to each other. The message contains the position information of the ship during time t. In Fig. 1(2), based on ok? message from target ships, the collision risk of the current course (equation (1)) is calculated. In the same way, the collision risk of the candidate course is calculated (Fig. 1(3)). The improvement calculated by equation (3) is exchanged with target ships (Fig. 1(4)). Each ship stores the improvement of each other in the improvement list (Fig. 1(5)). Ship C has greater improvement than ships A and B and can choose the next-intended course (Fig. 1(6)). Ships A, B, and C check the collision risk based on the exchanged information. If there is a collision risk, the above procedure is repeated (Fig. 1(1)). In DLSA, all ships are able to select a candidate course that would reduce the collision risk in the present condition. However, only one in a neighboring relationship can change course (ship C in Fig. 1(6)). This is to prevent infinite loops. If three or more ships change their next-intended course at the same time, the collision risk may increase or the calculation time may increase. For this reason, only one of the ships of the neighboring relationship is allowed to change course.

However, this way of limiting infinite loops results in many message exchanges. DSSA solves the problem of infinite loops by applying probabilities while time lowering the number of DLSA message exchanges. In DSSA, Figs. 4, 5, and 6 are omitted. Instead, a ship selects the next-intended course according to probability (Fig. 2). Fig. 3

A ship selects the new candidate course as the next-intended course with probability p or selects the existing next-intended course with probability 1-p. This method allows all ships to choose a new course at the same time and send information to target ships if the next-intended course is changed.

## 4. Comparison of Ship Collision Avoidance by DSSA in Cooperative/Non-Cooperative Situations

As shown in Fig. 3, it is assumed that four ships sail. Ship O(relationship between ship T3 and O: port to port, ship O and T1: ship O is the give-way ship and T1 is the stand-on ship) tries starboard alteration to avoid collision with ship T1, but assumes that there is not enough clearance due to ship T2. Ship T2 may determine that there is no collision risk, but ship O is likely to increase the collision risk of other ships, including the nearby ship T2, in order to reduce the collision risk. In other words, even if the current situation is considered safe, the collision risk can be increased if one ship does not cooperate with the other ship.

In this experiment, the effect of cooperative and non-cooperative situations on ship collision are analyzed. As shown in Fig. 1, in a cooperative situation, the ship avoids collision by exchanging information with other ships. In non-cooperative situations, however, all ships do not exchange information with other ships. After calculating the cost function, they select the course that can reduce the cost most.

Thus, two cases are prepared. First, cooperative and non-cooperative situations in a four-ship encounter are analyzed. Second, eight ships with AIS data are assumed to meet in the Strait of Dover to test the collision avoidance in cooperative and non-cooperative situations. All these experiments are done by MATLAB which is specialized for processing matrix operations and visualizes the ship's position using the built-in graphics.

### 4.1 Experiment of four ships in cooperative/non-cooperative situations

Experiments are carried out in consideration of three parameters that could affect ship collision: safety domain, detection range, and speed. The size of the safety domain may affect the size of the turn angle. The change of the speed may determine the timing of the encounter with the target ship and also affect the costs. Depending on the size of the detection range, the detection timing of the target ship is changed. This is an important matter for determining the timing of the collision action, therefore I set two values to check for the presence of the collision according to the change of the detection range. The parameters of the first experiment are shown in Table 1. The experiment consisted of 16 combinations of parameters.

Fig. 4 is a simulated scenario of a four-ship encounter in a non-cooperative situation. Each ship departs from the corner. The starting position of the target ship on the opposite corner is set as the destination of each ship, and all ships meet at the center. The solid line represents the trajectories of each ship as an example of the results of non-cooperative situations. The ship calculates the predicted position of the other ship based on the current information and selects the course with the greatest reduction of collision risk. This is called the greedy search method, in which the experiments lead to rapid changes for collision avoidance.

Fig. 5 is a simulated scenario when four ships meet in a cooperative situation. The experimental conditions are the same as those in the non-cooperative situation in Fig. 4. In cooperative situations, the trajectories of the four ships (solid line) were smooth trajectories with few abrupt changes compared with those in a non-cooperative situation. In this experiment, the sailing distance and cost are analyzed by combining various parameters in cooperative/non-cooperative situations. In all experiments, DR and SP mean detection range and speed, respectively. The non-coop and coop means non-cooperative and cooperative situations, respectively.

#### 4.1.1 Safety domain set at 0.5 nm

Fig. 6 shows the experimental result when the safety domain is 0.5 nm. The bar and line represent the sailing distance and cost, respectively.

In non-cooperative situations (blue bar), the sailing distance is not affected much by the change in the detection range, but the change in speed greatly affects the sailing distance. In the cooperative situation (gray bar), the sailing distance was not significantly affected by the detection range and speed.

Regarding costs (line), compared with non-cooperative situations, cooperative situations in all areas recorded higher values. In non-cooperative situations, each ship will attempt to proceed to its destination using a greedy research, and the costs ranged between 0.5 and 0.8. However, in a cooperative situation, the cost of every position includes the cost of the destination. These factors are considered the reasons why the cost in a cooperative situation is higher than the cost in a non-cooperative situation.

#### 4.1.2 Safety domain set at 1.0 nm

Fig. 7 shows the experimental results when the safety domain is 1 nm in a similar tendency of Fig. 6. In a non-cooperative situation, large change in speed is observed. It appears that the higher the speed, the longer the distance travelled to the next position. In addition, the greedy search method increases the ship’s movement.

In a cooperative situation, the sailing distance is affected by the size of the detection range. As the detection range increased, a ship steers for collision avoidance in advance, and a stable sailing distance is obtained compared with that in a non-cooperative situation.

#### 4.1.3 Safety domain set at 1.5 nm

Fig. 8 shows the experimental result with 1.5 nm of safety domain. Regarding sailing distance (bar), sailing distances were longer in all areas than those in cooperative cases. The sailing distances in the cooperative situations were constant. With regard to costs (line), cooperative situations showed higher costs than non-cooperative situations.

In Experiment 4.1.3, the sailing distance of non-cooperative ships was the largest in all areas, unlike the previous experiments. In the case of non-cooperative situations, it seemed that if the size of the safety domain exceeds a certain size, the number of possible approaches decreases and the sailing distance converges to a constant value.

#### 4.1.4 Safety domain set at 2.0 nm

Fig. 9 demonstrates the only experimental result when the safety domain is 2 nm in a cooperative situation. Ship collision occurred in all non-cooperative situations. The cooperation between ships is necessary when the ship’s safety domain is getting bigger.

Considering the sailing distance (bar), when the detection range and speed were 6 nm and 24 kts, respectively, the sailing distance was the longest. This appears to be because the DSSA finds solutions based on probabilities. When the size of detection range is small (DR = 6 nm), the size of the safety domain is large (SD = 2 nm) and the speed is fast (SP = 24 knots), the longest sailing distance recorded. That is, it is necessary to secure a sufficient detection range according to the change of the speed.

Regarding cost (line), the lowest cost was recorded when the detection range was 6 nm and the speed was 24 kts, which recorded the longest sailing distance. In other words, the distance appears to be longer but more secure. The increase in the distance travelled means a deviating route. This means that the possibility of encountering a target ship is decreasing. Therefore, it seems that the sailing distance increased but the costs decreased.

Fig. 10 is the result of classifying all experiments according to the size of the safety domain. In cooperative and non-cooperative situations, both sailing distance (bar) and cost (line) tended to increase as the size of the safety domain increases.

In the cooperative situation, when safety domain was 0.5, 1.0, 1.5, and 2.0 nm, respectively, the sailing distances tended to increase to 50.4, 50.7, 50.9, and 51.8 nm, respectively. The larger the value of safety domain, the larger the space for collision avoidance between ships. For the costs, when safety domain was 0.5, 1.0, 1.5, and 2.0 nm, respectively, the costs increased to 0.84, 2.16, 3.09, and 4.08, respectively. The increase in the size of the safety domain caused the increase of the sailing distance, and the cost increased as the sailing distance becomes longer.

In non-cooperative situations, when the safety domain was 0.5, 1.0, and 1.5 nm, respectively, the sailing distances were 51.6, 51.6, and 52.8nm. The sailing distance of non-cooperative situations were higher than the cooperative ones, and the collision occurred when the safety domain was 2 nm. When the safety domain was 0.5, 1.0, and 1.5 nm, respectively, the costs were 0.72, 1.75, and 2.50. The higher the value of the safety domain, the higher the cost.

### 4.2 Experiment of cooperative/non-cooperative situations using AIS data

To set up a situation where cooperation with target ships is required, such as Fig. 3, the AIS data of the ship of Dover Strait in Fig. 11 were used for the experiment. In Fig. 11, ships 2, 5, 7, and 8 are a group of ships navigating down, and ships 3 and 6 are a group of ships navigating up. Ships 1 and 4 are the ships that cross the route of the two ship groups. In other words, ships 1 and 4 affect the collision avoidance action of the other ships. Therefore, all ships should cooperate with each other in order to sail safely.

Fig. 11 shows the position, safety domain, detection range, speed, and course of eight ships with the AIS data. The black and red circles represent the size of the safety domain and detection range, respectively. The information of each ship is shown in Table 2.

The experiments are conducted with the combination of parameters in Table 2. Twelve cases of experiments are conducted in cooperative and non-cooperative situations, respectively.

Table 3 and 4 showed the sailing distance, costs, and collisions according to the combination of parameters in non-cooperative and cooperative situations. The collision is marked as No (no collision) or Yes (collision happened). The meaning of "-" in the sailing distance indicates that it cannot be measured due to a collision.

For the first experiments in Table 3, for example, the sailing distance and cost were 81.28 nm and 7.427, respectively when safety domain, detection range, and speed were 1 nm, 6 nm, and 12 knots, respectively. At this time, no collision occurred. The results of twelve experiments were tabulated in this way. Except for experiments 1 and 2, experimental results showed that, when the size of the safety domain increased in a non-cooperative situation, the collisions occurred in all areas. In other words, a change in the size of the safety domain in a non-cooperative situation implies that it can have a very large impact on the action for collision avoidance.

Table 4 showed the sailing distance, costs, and collisions according to the combination of parameters in a cooperative situation. The experimental results showed that collision occurred in 5 out of 12 experiments. For example, in experiments 5 and 6, each vessel had the same size of safety domain and detection range, but the collision occurred with the change of speed. In experiments 9, 10, 11, and 12 namely, in the case where the size of the safety domain is the largest, only one of the four experiments did not collide. If the size of the safety domain is large, the detection range should have sufficient area and the speed should be small to avoid collision. Also, as the size of the safety domain increases, the sailing distance tends to increase.

Based on the results of Table 3 and Table 4, mutual cooperation is crucial for collision avoidance, and it is important to set the optimal parameter values in a cooperative situation.

For the sake of a better understanding, the trajectories of the ships in cooperative and non-cooperative situations are indicated in Figs. 12 , 13 and 14. Fig. 12 and 14 showed the trajectories when each ship sailed at actual different speed. The initial value of the ship is shown in Table 5.

The "No. ship" means the number of each ship. Each individual ship has different speeds and sails from origin to destination.

Fig. 12 shows one of the result of collision avoidance in a non-cooperative situation. The trajectories of each ship are indicated by a solid black line. The turning angle of each ship showed a sharp shape.

Fig. 13 is the enlarged area of the black rectangle area in Fig. 12. There was a collision between ships 3 and 6. The safety domain of each ship was set to 2 nm. Two ships engaged in collision to maintain the safety domain, but they penetrated the safety domain of the target ship at a distance of 1.89 nm. In the early stage of the collision, both ships attempted to change at a small angle. However, as the distance became closer, they attempted a sudden change of direction diagonally, eventually invading the safety domain of the target ship.

Fig. 14 shows the experimental result of the ship in a cooperative situation in the Strait of Dover. No rapid change was found compared with that in a non-cooperative situation. Moreover, all ships arrived at their destination safely without invading the safety domain of the target ship.

## 5. Conclusion

In this paper, the effect of cooperative and non-cooperative situations on ship collision avoidance was analyzed. In the experiment of four ships under a cooperative situation, the sailing distance was stable. This means that it is possible to establish a stable route by exchanging information with the other ship. Costs were higher in a non-cooperative situation. This was because the cost function took into account the destination at every position.

In the experiment of four ships under a non-cooperative situation, the sailing distance appeared to be greatly influenced by the change in speed. In addition, when the size of the safety domain was larger than a certain level, collision occurs. In both cooperative and non-cooperative situations, as the size of the safety domain increased, both the sailing distance and cost increased.

In the second experiment, eight ships with AIS data met at the Strait of Dover to test the collision avoidance under cooperative and non-cooperative situations. Tables 3 and 4 showed the results of experiments by cooperative and non-cooperative ships using actual data. In Table 3, only ten out of twelve experiments had collisions. In Table 4, five out of twelve experiments had collisions. Experiments proven that cooperation is crucial for ship collision avoidance.

Experimental results showed that when the safety domain was 2 nm, collision occurred because of invasion of the ship's safety domain at a distance of 1.89 nm. The trajectories of each ship did not showed a frequent change in a cooperative situation than in a non-cooperative situation, and ship collision were not occurred.

In this paper, the safety domain, detection range, and speed are considered factors affecting the collision intention of the ship. However, preventing collision by considering the influence of external information and problems caused by information errors between ships in a distributed system should be taken into account.

## Figure

Procedure for ship collision avoidance by distributed algorithm.

Decision for next-intended course depending on probability.

Representative image of a multiple ships encounter.

Simulated trajectories of four ships in non-cooperative situation.

Simulated trajectories of four ships in a cooperative situation.

Sailing distance and cost when safety domain is 0.5 nm.

Sailing distance and cost when safety domain equals to 1 nm.

Sailing distance and cost when safety domain equals to 1.5 nm.

Sailing distance and cost when safety domain equals to 2.0 nm.

Sailing distance and cost depending on the size of the safety domain.

Eight ships in the Strait of Dover. (source: www.shipfinder.com)

Trajectories of eight ships in a non-cooperative situation.

Simulated trajectories when collision happened.

Trajectories of eight ships in a cooperative situation.

## Table

Procedure for Distributed Algorithm

Values for parameters of four ships

Variables for parameters of 12 ships

Sailing distance, cost, and collision depending on the parameters in non-cooperative situation

Sailing distance, cost, and collision depending on the parameters in cooperative situation

Variables of initial settings for eight ships in the Strait of Dover

## Reference

1. COLREG.(1972), Convention on the International Regulations for Preventing Collisions at Sea. International Maritime Organization, London.
2. Fuiji, Y. and K. Tanaka(1971), Traffic Capacity, The Journal of Navigation, Vol. 24, No. 4, pp. 543-552.
3. Goodwin, E. M. (1975), A Statistical Study of Ship Domains, The Journal of Navigation, Vol. 28, No. 3, pp. 328-344.
4. Kim, D. , K. Hirayama and G. Park(2014), Collision Avoidance Multiple-Ship Situations by Distributed Local Search. Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 18, No. 5, pp. 839-848.
5. Kim, D. , K. Hirayama and T. Okimoto(2015), Ship Collision Avoidance by Distributed Tabu Search, The International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 9, No. 1, pp. 23-29.
6. Kim, D. , K. Hirayama and T. Okimoto(2017), Distributed Stochastic Search Algorithm for Multi-ship Encounter Situations, The Journal of Navigation, Vol. 70, pp. 699-718.
7. Szlapczynski, R. (2006), A Unified Measure of Collision Risk derived from the Concept of a Ship Domain, The Journal of Navigation, Vol. 59, No. 3, pp. 477-490.
8. Tsou, M. and C. Hsueh(2010), The Study of Ship Collision Avoidance Route Planning by Ant Colony Algorithm, Journal of Marine Science and Technology, Vol. 18, No. 5, pp. 746-756.
9. Tsou, M. , S. Kao and C. Su(2010), Decision Support from Genetic Algorithms for Ship Collision Avoidance Route Planning and Alerts, The Journal of Navigation, Vol. 63, No. 1, pp. 167-182.
10. Zhang, W. , G. Wang and L. Wittenburg(2002), Distributed Stochastic Search for Constraint Satisfaction and Optimization: Parallelism, Phase Transitions and Performance: Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI-2002), pp, 53-59.
11. Zhang, W. , G. Wang, Z. Xing and L. Wittenburg(2005), Distributed Stochastic Search and Distributed Breakout: Properties, Comparison and Applications to Contraint Optimization Problems in Sensor Networks. Artificial Intelligence, Vol. 161, pp. 1-2, pp. 55-87.