Deep Learning in Unmanned Surface Vehicles Collision-Avoidance Pattern Based on AIS Big Data with Double GRU-RNN

Abstract

There is a collection of a large amount of automatic identification system (AIS) data that contains ship encounter information, but mining the collision avoidance knowledge from AIS big data and carrying out effective machine learning is a difficult problem in current maritime field. Herein, first the Douglas–Peucker (DP) algorithm was used to preprocess the AIS data. Then, based on the ship domain the risk of collision was identified. Finally, a double-gated recurrent unit neural network (GRU-RNN) was constructed to learn unmanned surface vehicle (USV) collision avoidance decision from the extracted data of successful encounters of ships. The double GRU-RNN was trained on the 2015 Tianjin Port AIS dataset to realize the effective learning of ship encounter data. The results indicated that the double GRU-RNN could effectively learn the collision avoidance pattern hidden in AIS big data, and generate corresponding ship collision-avoidance decisions for different maritime navigation states. This study contributes significantly to the increased efficiency and safety of sea operations. The proposed method could be potentially applied to USV technology and intelligence collision avoidance.

1. Introduction

With the development and the integration of the global economy, the marine world has become an important link for transportation and trade development in all countries in the world. However, the frequent occurrence of collisions at sea has caused not only great losses in terms of human lives and property but also has a wide coverage, posing a serious threat to marine ecology and the environment. These problems have gained increasing attention. In recent years, with the development of big data, artificial intelligence, cloud computing, and other technologies, the intelligence level of ships has continuously improved. Consequently, the development of unmanned ships has become an inevitable trend in future ship development. Due to their small size and intelligence, unmanned surface vehicles (USV) are often used to perform specific tasks, such as maritime rescue, marine surveying, and monitoring of dangerous goods. They have a wide range of applications worldwide. Although USV can serve to effectively reduce labor costs, the marine environment domain is complex, and therefore, to identify whether an USV can automatically avoid collisions is a prerequisite to successful completion of various tasks. As one of the core technologies used in USV, the automatic collision-avoidance technology includes not only a measure of the level of intelligence of unmanned ships but also the key to establish safe navigation of a USV in complex environments. Therefore, investigating the issue of collision-avoidance decision-making for unmanned ships has important practical significance to reduce or avoid maritime accidents.

In the maritime field, considering the large-scale popularization of AIS and the full coverage of shore-based equipment, the automatic identification system (AIS) big data is deemed as an effective data source. In 2018, the fleet online HiFleet used its more than 3000 shore-based AIS base stations and 58 AIS satellites to receive an average of 150 million ship position report data from 838,044 ships (MSSI numbers between 200 million and 899,999,999) worldwide, every day Figure 1 shows the 2018 global liquefied natural gas (LNG) AIS trajectory data.

A large amount of AIS data contains extensive ship information, which requires certain screening and mining. Therefore, it is important to provide data support with the aim of establishing subsequent ship collision-avoidance, ship safety navigation, and ship behavior prediction. The maturity of algorithms, such as machine learning and big-data mining, has inspired new solutions to the previously mentioned problems in the marine field. Researchers received a new opportunity to easily access and analyze AIS data, to improve the intelligence of USV.

Due to its easy access, multi-data integration, and other advantages, AIS has become a widely used big-data source in the field to perform prediction [1], clustering [2], reinforcement learning [3], pattern classification [4], etc.

Liu [5] focused on dynamic obstacle avoidance and considered the path-planning problem of a USV, using the ant colony algorithm (ACA) and the clustering algorithm (CA). Shi [6] introduced the concept of empirical mode decomposition (EMD) denoizing and Fermat’s spiral fitting, based on the AIS data. Lyu [7] combined the dynamic and static path planning approaches and proposed a set of real-time multi-ship adaptations for complex water automatic collision-avoidance decision-making and developing an effective path planning algorithm. Sun [8] suggested using 3D path planning for an autonomous underwater vehicle, (AUV) using a hierarchical deep Q-network combined with the prioritized experience replay. Pietrzykowski [9] realized a real-time implementation of an automotive collision mitigation system and evaluated the associated risk. Guo et al. [4] introduced deep reinforcement learning (DRL) to realize the intelligent route planning of unmanned ships in an unknown environment. Guardeño [10] focused on developing reactive static obstacle avoidance (SOA) methods, serving to increase the autonomy of USVs. Geng [11] developed velocity obstacle models, concerning both dynamic and static obstacles to represent a potential conflict-free region with regard to other objects. Xiu [12] implemented a maritime unmanned aerial vehicle (Mar-UAV) system, equipped with a high-resolution camera and an AIS. Azzeddine et al. [13] suggested considering an adaptive ship safety domain as a spatial risk function to identify both collision and grounding risks, based on motion and maneuverability conditions for all vessels.

The present study effectively combines the concepts of AIS and deep learning, to learn and solve the problem of USV’s maritime safety navigation and collision-avoidance. Figure 2 represents the overall framework of the proposed algorithm.

2. Materials and Methods

In this section, we first describe machine-learning training data preparation. In this study, we employed the Tianjin Port 2015 AIS trajectory dataset (Figure 3), as a source to specify the ship-encounter training data. In this study, extracting the successful cases of ship collision-avoidance from AIS big data could be divided into three steps—(a) ship AIS big data compression; (b) identification of the ship encounter situation data in historical data based on the ship domain; and (c) training data normalization. Data mining is used to extract training datasets that can be used to train a neural network. The preprocessing of training data could further improve the efficiency of the considered machine-learning technique, increase its pertinence, and solve the problem of blind learning.

2.1. AIS Big Data Compression Based on the Douglas–Peucker Algorithm

As the high-frequency broadcast of AIS data accumulates a large number of data items in a period, there is a large amount of redundant information while defining the trajectory of a ship. The huge amount of AIS data might cause a system to perform a large number of irrelevant repetitive calculations and require considerable computational resources during data analysis. There are only a limited number of points in a ship trajectory that can actually characterize it, accounting for only 8% of the overall dataset. Therefore, in this study, we applied the Douglas–Peucker algorithm to compress and preprocess the AIS big data of a ship, to reduce the amount of the AIS big data, and to increase the value of the overall training data, which was beneficial for improving the efficiency of machine learning and did not require executing operations repeatedly.

While digitizing an AIS trajectory, it is necessary to sample a motion trajectory curve of a ship, i.e., to select a limited number of points on a curve and turn it into a polyline so that it can maintain the original shape to a certain extent. In this way, the training volume of a neural network could be reduced, and the learning efficiency might be improved.

The Douglas–Peucker algorithm [14] includes five steps, defined as follows (Figure 4):

• Define a straight line (AB) between two points A and B at the beginning and end of the curve, corresponding to the chord of the curve.
• Obtain (C) on the curve with the largest distance from the straight line segment and calculate the distance (d) from AB.
• Compare the size of a distance using a predefined threshold. If it is less than the threshold, the straight line segment is regarded as an approximation of the curve, and the processing of the curve is completed.
• If the distance is greater than the threshold, use C to divide the curve into two segments (AC and BC) and perform steps 1–3.
• Upon completion of processing for all curves, a polyline formed by connecting each dividing point can be used as an approximation of a curve.

To facilitate the calculation and compression, we considered the recommended range of distance threshold selection for AIS data processing, under different scale charts (

Table 1. Recommended thresholds in different scales.

Scale	Recommended Threshold/m	Compression Ratio/%
<1:3,000,000	20	97
1:2,990,000~1:1,000,000	10~20	94~97
1:990,000~1:2,00,000	4~10	87~94
1:190,000~1:100,000	2~4	78~87
>1:100,000	0.2~2	36~78

) [15].

Figure 5 displays the AIS trajectory and the compressed ship position, together, to show the compression effect of the DP algorithm. The DP algorithm shown in Figure 5 could reduce the amount of AIS data and enhance the processing efficiency of subsequent data, while retaining the characteristics of the ship’s trajectory.

Figure 6 illustrates the comparison before and after the compression of the AIS data in the waters of Tianjin Port. The color bars of Figure 6 and Figure 7, represent the density frequency values of the ship’s key feature points.

2.2. Identification of the Risk of Collision Based on the Ship Domain

After compressing AIS data, the ship encounter matching screening was performed, and the ship encounter data were further extracted. A successful case of ship collision-avoidance was considered as a training sample in the proposed double GRU-RNN. The conventional method require the distance at Closest Point of Approach (DCPA) of the encounter between the two ships. Due to the difference in the positions of the other ships, a degree of danger, time to Closest Point of Approach (TCPA), was different. It was not sufficiently comprehensive to compare DCPA and TCPA alone, and therefore, in this study, we employed the shipping field as a method to identify ship encounters.

The ship field method was proposed by Fuji [16] et al. It implied defining an elliptical area in which the long axis was eight times of the length of a ship (a), and the short axis was 3.2 times of the length of the ship (b). This model could be described by an elliptical equation in a two-dimensional coordinated system. By calculating the value of lambda in a shipping area where the relative motion line of the other ship was tangent to the ship, whether the ship would encounter a collision risk, could be determined. Figure 8 represents a schematic diagram of the size change of the shipping area, with a step length of 0.1.

$$\{\begin{array}{l}a\prime =\lambda a\\ b\prime =\lambda b\end{array}$$

(1)

where a′ is the line of relative motion that is tangent to the long axis of the ellipse, b′ is the line of relative motion that is tangent to the short axis of the ellipse.

In this way, the risk of collision could be successfully quantified as a single value (λ), which was convenient for the calculation and screening of ship encounter data. Usually, two-dimensional coordinates can be used to investigate the movements of ships in the sea. In the surface coordinate system, the origin of a coordinate is a fixed point on a surface; the y-axis is north-oriented, and the x-axis is east-oriented. In the ship motion coordinate system, the center of a ship is the coordinate origin. The ship length direction is the y-axis, and the ship width direction is the x-axis. The relationship between these two systems is represented in Figure 9.

Transformation from the Earth’s surface coordinate system XOY to the ship motion coordinate system xoy is defined as follows:

$$\{\begin{array}{l}{x^{\prime }}_t=x_t\cos {\theta }_o+y_t\sin {\theta }_o-x_o\cos {\theta }_o-y_o\sin {\theta }_o\\ {y^{\prime }}_t=-x_t\sin {\theta }_o+y_t\cos {\theta }_o+x_o\sin {\theta }_o-y_o\cos {\theta }_o\end{array}$$

(2)

where a is the semi-axial length and b is the semi-axial width of the own ship domain, Vo is the speed of the own ship, Vt is the speed of the target ship, θo is the course of the own ship, and θt is the course of the target ship, (xo, yo) is the own ship’s coordinates in Earth’s surface coordinate system, (xt, yt) is the target ship coordinates in Earth’s surface coordinate system, (xt′, yt′) is the target ship coordinates in the own ship motion coordinate system.

$$\gamma =\alpha \text{-}C$$

(3)

$$\begin{array}{l}xx=s\times \sin (c)-S\times \sin (C)\\ yy=s\times \cos (c)-S\times \cos (C)\end{array}$$

(4)

$$\begin{array}{l}xt\prime =d\times \sin (\gamma )\\ yt\prime =d\times \cos (\gamma )\end{array}$$

(5)

$$\{\begin{array}{ll}\{\begin{array}{l}y=(yt\prime -xt\prime \times (yy/xx))/(1+0.16\times (yy/xx)2)\\ x=-(yy/xx)\times 0.16\times y\end{array}& ,xx\ne 0 \mathrm{and} yy\ne 0\\ \{\begin{array}{l}y=0\\ x=xt\prime \end{array}& ,xx=0 \mathrm{and} yy\ne 0\\ \{\begin{array}{l}y=0\\ x=yt\prime \end{array}& ,xx\ne 0 \mathrm{and} yy=0\\ \{\begin{array}{l}y=xt\prime \\ x=yt\prime \end{array}& ,xx=0 \mathrm{and} yy=0\end{array}$$

(6)

$$\lambda =\sqrt{{(y/(4\times L))}^2+{(x/(1.6\times L))}^2}$$

(7)

where S is the speed of the own ship; C is the course of the own ship; L is the captain of the own ship; s is the target speed; c is the target course, α is the target azimuth angle; d is the distance; γ is the side angle; xx, yy are the component vectors of the relative speed on the x-axis and y-axis; (x,y) is the tangent point coordinate of the ship domain.

The value of λ reflects how close the target ship is to the own ship (Figure 10). If λ > 1, the target ship did not enter its own spacecraft domain, and there was no risk of collision; however, if λ ≤ 1, and no evasive action was taken, the target ship entered its own ship domain, and there was a risk of collision. Ships must take corresponding actions in accordance with COLREG requirements to avoid collisions.

To facilitate the calculation and comprehensiveness of collision avoidance, we visualized the collision risk of ships based on the shipping field. Considering a 360° incoming ship, two ships encountered a full-scale heading difference (−180~180°) with 0.1° being the step size. We generated a 3D view of the collision risk of a ship, as represented in Figure 11. The collision risk diagram could be used to intuitively judge the encounter state and the degree of danger of a ship.

It can be seen from Figure 11 that X,Y is the relative position coordinate of the target ship, and the Z-axis represents the heading difference between the target ship and own ship. The color (λ) could be used to indicate the current tangency between the relative motion line of the other ship and the ship domain of the own ship. The darker the color, the higher the risk, and the smaller the lambda value.

The ship encounter data were extracted from the massive ship AIS trajectories, as shown in Figure 12.

2.3. Training Data Normalization

To facilitate machine learning, it was necessary to process the extracted AIS encounter data and apply standardized conversion. We set the first position of a ship as the origin of coordinates and set the course of the first position of a ship as 000. There were two steps to transform a location point, a relative position, and an angle in each batch of data. (a) Translation—the first position of the own ship in the training group was employed as the reference to perform coordinate translation. (b) Rotation transformation—the heading of the first position of the own ship was utilized as the reference to perform coordinate rotation transformation. Translation and rotation transformation are illustrated in Figure 13.

$$\{\begin{array}{l}{x}_0=O{x}_0\\ y_0=O{y}_0\\ h_0=O{h}_0\end{array}$$

(8)

$$\{\begin{array}{l}O{x}_i=O{x}_i-x_0\\ O{y}_i=O{y}_i-y_0\\ O{h}_i=O{h}_i-h_0\\ T{x}_i=T{x}_i-x_0\\ T{y}_i=T{y}_i-y_0\\ T{h}_i=T{h}_i-h_0\end{array}$$

(9)

$$\{\begin{array}{l}x\prime =\cos (h_0)\times x-\sin (h_0)\times y\\ y\prime =\cos (h_0)\times y+\sin (h_0)\times x\end{array}$$

(10)

2.4. Double GRU-RNN Model

In this section, we first present the structure of the proposed double-GRU-RNN deep learning model.

The RNN network introduces a directional loop, which can deal with the problems of correlation between inputs. Breaking the traditional neural network structure layer and the full connection between the layers, the transition state between each layer of nodes was no longer the traditional neural network model of input-hidden layer-output. AIS ship trajectory is a typical time-series data, and the RNN network has a high degree of fit for AIS data. In theory, RNN can process time-series data of any length.

There is no guarantee of a one-to-one correspondence between the other ships’ actions and the own ship. Under normal conditions, the trajectory feature points of a direction-maintaining ship is significantly smaller than those of a give-way ship. The output, the length of the input sequence, and the length of the output sequence cannot be predicted in advance, and therefore, we propose to develop two GRU-RNNs to learn collision-avoidance decisions of a USV. GRU-RNN_1 is employed as a neural network to process the navigation state of the target ship; GRU-RNN_2, as a prediction network for collision-avoidance decision making of a ship, can be used to effectively solve the problem of the unequal database length, and at the same time, adding a neural source into a GRU to solve the gradient mass problem caused by the long length of data. The structure of the proposed double GRU-RNN is illustrated in Figure 14.

The activation function of RNN also has a soft saturation using the tanh function. As its output is centered at 0, the convergence speed is faster than the sigmoid function. The function image is shown in Figure 15.

$$\tanh (x)=\frac{\sinh x}{\cosh x}=\frac{e^x-e^{-x}}{e^x+e^{-x}}=\frac{1-e^{-2x}}{1+e^{-2x}}$$

(11)

The input layer of ship behavior input data $\mathrm{I}\left(\mathrm{t}\right)$ can be expressed as:

$${\mathrm{I}\left(\mathrm{t}\right)=\{\mathrm{lon}}_1{,\mathrm{lat}}_1{,\mathrm{t}}_1{,\mathrm{lon}}_2{,\mathrm{lat}}_2{,\mathrm{t}}_2,\dots {,\mathrm{lon}}_{\mathrm{i}}{,\mathrm{lat}}_i{,\mathrm{t}}_i\}$$

(12)

ship position data of the output $\mathrm{O}\left(\mathrm{t}\right)$ layer is expressed as:

$${\mathrm{O}(\mathrm{t}+2)=\{\mathrm{lon}}_1{}^{\prime }{,\mathrm{lat}}_1{}^{\prime }{,\mathrm{t}}_1{}^{\prime }{,\mathrm{lon}}_2{}^{\prime }{,\mathrm{lat}}_2{}^{\prime }{,\mathrm{t}}_2{}^{\prime },\dots {,\mathrm{lon}}_j{}^{\prime }{,\mathrm{lat}}_{\mathrm{j}}{}^{\prime }{,\mathrm{t}}_j{}^{\prime }\}$$

(13)

For the loss function, we used the tensorflow function (tf.contrib.seq2seq.sequence_loss). The loss function applied in actual use was a softmax loss function.

$$L(W)=\frac{1}{N}{\displaystyle \sum _{i=1}^N{L}_i(f(x_i,W),y_i)+\lambda R(W)}$$

(14)

2.4.1. GRU Cell Structure

A GRU neural network [17] is a variant of a long short-term memory (LSTM). Both are defined based on an RNN neural network. However, a GRU neural network is an improvement of an RNN neural network that has a short-term memory function. During back propagation, there is a problem with the gradient disappearance. Therefore, the RNN neural network is not friendly in terms of updating layers with small gradients. The GRU neural network sets up two gates (update gate and reset gate). The GRU neural network has fewer tensors and fewer parameters than the LSTM neural network and is much faster than the LSTM neural network in speed. The GRU neural network replaces the hidden unit of an RNN with a GRU module unit. The GRU neural network algorithm is an algorithm proposed by Cho et al. in 2014 [18]. The GRU unit structure is represented in Figure 16.

In the GRU neural network algorithm, two gates were set, namely, the update gate and the reset gate. The reset gate was aimed to control the degree of ignorance of information in the previous stage; the function of the update gate was used to update the unit state in time and pass the hidden state and input state to the sigmoid function; the sigmoid function belonged to 0 or 1, and when the value was 0, it was discarded. When the value was 1, it was reserved. Using the GRU neural network algorithm, we could mitigate the problem of gradient disappearance [19]. The workflow of a GRU neural network was defined as follows:

Step 1: Solve the reset gate ($r_t$) and the candidate state ($\stackrel{-}{h_t}$):

$$r_t=\sigma (W_r{x}_t+U_r{h}_{t-1}+b_r)$$

(15)

$$\overline{h_t}=\tanh (W_r{x}_t+U_h(r_t\odot h_{t-1})+b_h)$$

(16)

Step 2: Solve the update gate ($z_t$) and the current state ($h_t$):

$$z_t=\sigma (W_z{x}_t+U_z{h}_{t-1}+b_z)$$

(17)

$$h_t=z_t\odot h_{t-1}+(1-z_t)\odot \overline{h_t}$$

(18)

$$h_t=z_t\odot h_{t-1}+(1-z_t)\circ \tanh (W_h{x}_t+U_h(r_t\circ h_{t-1})+b_h)$$

(19)

It could be seen that there were linear and nonlinear relationships between the current state ($h_t$) and the historical state ($h_{t-1}$). When the update gate ($z_t=0$), and the reset gate ($r_t=1$), the current state ($\stackrel{-}{h_t}$) was defined as below:

$$\stackrel{-}{h_t}=\tanh (W_h{x}_t+U_h{h}_{t-1}+b_h)$$

(20)

2.4.2. Double RNN Structure

(1) Target Ship State Handling

The variable-length trajectory feature points of other ships were directly input into GRU-RNN_1 for processing, and the semantic vector value C was obtained after completing the centralized processing as the input value of GRU-RNN_2 as follows:

$$C=q(h_1,h_2,h_3,\dots ,h_t)$$

(21)

where t represents the number of trajectory feature points in an input sequence. Then, we considered the output h_t+1 of the last hidden layer as the semantic vector C.

(2) Own Ship Collision-Avoidance Decision

Using C as the input value in GRU-RNN_2, we input the trajectory feature points of the collision-avoidance action undertaken by a ship in a predictive manner and used the input trajectory feature points as input. Finally, we aimed to obtain the complete avoidance trajectory feature point sequence of the ship Y₂, Y_t−1:

$$Y_t=\arg \max P(Y_t)={\displaystyle \coprod _{i=1}^{T}p(Y_t|\{Y_1,Y_2,Y_3,\dots ,Y_{t-1}\})}$$

(22)

As a result of the continuous evolution of RNN, the structure of neural networks becomes more difficult to fit complex data structures, simplifying input data preprocessing and making the input information more complete and without loss. We utilized the overall target ship trajectory key point sequence as an input and the overall own ship trajectory key point sequence as an output. GRU-RNN_1 handled the target ship sequence to obtain semantic vector C. GRU-RNN_2 was utilized to derive the corresponding avoidance decision sequence (Figure 17).

Concerning the two GRU-RNN networks, the one mainly completed the input of a time-series data sequence to generate a state vector, and the other one generated a time-series data sequence through the generated state vector. The two networks cooperated with each other to achieve better performance in learning ship collision-avoidance decision making.

3. Results

The AIS data used in this article was the full-year AIS data of the Tianjin Port in 2015, including the 22,349 ships occupying 8.3 GB of storage space, with the 1,511,504,900 trajectory points. The AIS data structure storage is shown in

Table 2. AIS data structure storage. MMSI—maritime mobile service identity.

MMSI	Heading/°	Course/°	Speed/Kn	Time	Lon/°	Lat/°
636015XXX	101	101.8	11.3	1440538896	117.911	38.95156
636015XXX	100	102.4	11.3	1440538986	117.9169	38.95053
636015XXX	100	101.5	11.3	1440539076	117.9229	38.94955
636015XXX	99	101.3	11.4	1440539154	117.9289	38.94861
636015XXX	100	101.3	11.3	1440539257	117.9348	38.94771
636015XXX	99	100.9	11.3	1440539346	117.9408	38.94683
636015XXX	99	101.2	11.3	1440539466	117.9487	38.94558
636015XXX	99	100	11.3	1440539598	117.9574	38.94425
636015XXX	99	100.4	11.3	1440539706	117.9646	38.94327
636015XXX	99	99.8	11.2	1440539826	117.9725	38.94218

.

This article used Win10 x64 operating system with Intel(R) Core i7-9700F CPU, RAM 16 GB. The Double GRU-RNN was implemented in Python in a machine-learning framework provided by Google TensorFlow. The overall structure of the network training automatically generated using TensorBoard is depicted in Figure 18.

The double GRU-RNN had two input values—(a) target ship trajectory, and (b) own ship decision, where the generated decision and own ship decision were the optimized input of backpropagation training. Figure 19 illustrates the ship encounter data filtered by the AIS big data, which were used as the training data for the double GRU-RNN.

The trained double GRU-RNN network could process the trajectory of target ships and specify corresponding collision-avoidance operations in the own ship. The collision-avoidance results are represented in Figure 20 and Figure 21.

4. Discussion

This research was aimed to provide a theoretical basis for designing innovative intelligent collision-avoidance systems for USV. In this paper, we proposed the double GRU-RNN to learn the effective ways of making appropriate collision-avoidance decisions, based on successful collision-avoidance case data. Using two GRU-RNN networks, we successfully processed own ship trajectory data and target ship trajectory data. The proposed method could freely process the trajectory data of different lengths, was deemed more flexible, and was capable of deriving more accurate ship collision-avoidance decisions. The proposed algorithm included big-data training and had a broad range of applications and high versatility to achieve timely strategy generation, timely response, and enhanced collision-avoidance security.