Research on autonomous route generation method based on AIS ship trajectory big data and improved LSTM algorithm

Introduction

With the development of the global shipping economy, ships are gradually developing in the direction of large scale, high speed, and intelligence, and more attention has been paid to the safety and economy of ship navigation which depends to a large extent on the adoption of a correct and reasonable route. As the first priority of ship navigation planning, route planning design is an important and tedious task (Yao, 2019). The automatic identification system (AIS) of ship is a kind of navigation aid equipment and is used for maritime safety and communication between ships as well as between ships and shore. AIS can broadcast the dynamic information of ships such as ship position, ship speed, and heading to other ships and shore stations in the nearby waters in combination with the static information of ships such as ship name, call sign, and draft (Feng et al., 2021). The historical voyage big data of navigation ships can be obtained by collecting AIS data. Through the data mining of the historical trajectory of ships' navigation in a certain area, the navigation patterns of ships can be analyzed. Furthermore, based on this, reasonable routes can be recommended for ships sailing in this area (Zhang et al., 2015). How to use the AIS big data of ships to improve the intelligence of route planning design and finally realize the autonomous generation of the route is a challenging topic.

At present, the route generation technology can be mainly divided into two classes. One is that the relevant experts and technicians draw the route on the paper chart manually, and the other is to use the evolutionary algorithms to automatically generate the navigation route of the ship (Zeng and Ito, 2001; Shen et al., 2019). The route designed by evolutionary algorithms can greatly reduce the workload of the crew and enhance the intellectualization of ship operation. Moreover, evolutionary algorithms can be divided into two types, one is according to the sea depth, weather, wind direction, wind speed, and other factors, through computer simulation to find the optimal path algorithm (Gasparetto et al., 2015; Dai et al., 2019). The other is based on AIS big data combined with a deep learning algorithm to achieve autonomous route generation (Lv et al., 2018; Lazarowska, 2020). Compared with manual route drawing, the former reduces the complexity of route design but often falls into a local optimal solution. In contrast, deep learning algorithms have been widely used in image recognition, language processing, traffic flow prediction, and other fields, and the generation technology of vehicle driving recommended routes based on big data is also becoming mature (Arel et al., 2010; Islam et al., 2016; Zhou et al., 2017). Against this background, this study proposes a method to classify ship trajectory according to the navigation routes by adding an unsupervised clustering layer based on long short-term memory (LSTM) deep learning algorithm with the historical trajectory of ships as the dataset and finally realizing the autonomous generation of ship routes. The algorithm can not only make the route design more intelligent and convenient but can also improve the navigation safety to a certain extent.

The trajectory clustering algorithm is an unsupervised learning algorithm that can classify trajectories according to the similarity of the trajectories (Pauletic et al., 2019). According to the different measurement methods, the related studies are mainly divided into two categories, one is based on trajectory points, and the other is based on trajectory segments. In the research on clustering algorithm based on trajectory points, Morris and Trivedi (2009) compared various trajectory clustering algorithms and their characteristics on different datasets, but it has not been verified in practical applications. Piciarelli et al. (2005) proposed a real-time trajectory clustering algorithm based on video datasets, which can obtain valuable data from higher-level anomaly detection modules. Zhao et al. (2017) proposed a hierarchical clustering method and an adaptive statistical method to solve the problem of uneven distribution of ship trajectories, but the method in a more complex environment was not considered. The clustering method based on trajectory points can deal with large trajectory data, but it ignores the space-time correlation between points and is not sensitive to abnormal trajectory points. In contrast, in the research on clustering algorithm based on trajectory segment, Lee et al. (2007) proposed the trajectory-based Hausdorff distance method that calculates the distance between trajectory segments in terms of parallel distance, vertical distance, and angular distance, and its results are more accurate.

Lin and Su (2008) proposed a one-way distance method based on the spatial shape of a moving object trajectory that only pays attention to the similarity of trajectory space shape and ignores time, speed, direction, and other attributes. The clustering algorithm based on trajectory segment has a good consideration for the accuracy of the trajectory, but the time complexity is relatively high, which is not conducive to use when the data volume is large. From the two kinds of clustering algorithm, the current clustering algorithms cannot take into account both trajectory integrity and efficiency, which is very difficult to handle the huge AIS big data.

Long short-term memory artificial neural network is a kind of recurrent neural network (RNN), which is used to solve the gradient vanishing problem of RNN. Many scholars use LSTM to generate trajectories. Xing et al. (2019) divided the vehicles into different types according to their driving styles and predicted the trajectory errors at different driving times. However, it did not carry out the comparison of the accuracy of the generated trajectories with different lengths. Xue et al. (2020) used LSTM to predict pedestrian trajectory, but it has not been confirmed whether it was effective in complex scenarios. Kong et al. (2019) proposed a new RNN-based default logic for path planning with graph-based search algorithms and optimization methods among existing urban road planning methods. Lin et al. (2021) proposed STA-LSTM to improve the interpretability of vehicle trajectory prediction. The current research on LSTM trajectory generation mainly focuses on the improvement of the model, ignoring the influence of the accuracy of the trajectory dataset on the final prediction results. The trajectories of vehicles on roads are relatively neat, while the trajectories of ships at sea are sparse, and the trajectories of different ship types vary greatly. Therefore, how to reduce the trajectory generation error on the sea is an urgent problem to be solved.

According to the problems in the above research, this work makes the contributions as follows:

(1) Using the actual latitude and longitude to calculate the distance instead of the Euclidean distance in the clustering algorithm makes the clustering algorithm more accurate in dealing with ship trajectories to produce more accurate results.

(2) In the actual study, it is found that the sea surface paths are sparse and the complete route trajectories are more difficult to obtain. To address the problem of small trajectory samples, this study proposes a random dilution of high-density routes to obtain more samples.

(3) According to the AIS trajectory clustering problem, this work uses the k-means algorithm to cluster the target area. Then, a layer of unsupervised trajectory clustering layer is customized on top of the LSTM algorithm, and the adaptive DBSCAN clustering algorithm mentioned by Zhao et al. (2017) is fused into the unsupervised trajectory clustering layer. This study also widens the network width of the LSTM so that the LSTM can generate trajectories for multiple types of ships simultaneously. Moreover, this study compares the errors when generating trajectories of different lengths to prove the effectiveness of this study.

In this study, the western route with large navigable volume and complicated sea conditions in the Zhoushan sea area is selected as the research target area, and the specific route between Cezi Island and Liuheng Island in the western route is selected as the specific route planning target route, which has certain practical significance. The general arrangement of this study is as follows. The “Related principles” section introduces the relevant principles involved in study work and the improvement of the relevant principles. The “Production of datasets” section introduces the production process of the dataset. The “Route generation” section describes the experimental process and the comparison of the results of different models. The “Conclusion” section summarizes this experiment.

Related principles Clustering algorithm

(1) K-means algorithm

The k-means algorithm is a division-based clustering method that needs to specify the clusters (K-values) during clustering, the number of clusters will affect the final clustering effect, and cross-validation can be used to select an appropriate K-value for clustering unknown data (Nie et al., 2022). The K-means algorithm has the following main steps:

Step 1. Let the trajectory data be D = , the number of clusters is k, and the maximum number of iterations is N.

Step 2. The output cluster is C = .

Step 3. Initialize Ci= ∅, and choose suitable k points in D at random as the initial center of mass μ = (μ1,μ2,...,μk).

Step 4. Calculate the distance between each sample of D in the trajectory data and each centroid, and yj denotes any trajectory point within the cluster:

dist (xi,yj) = ||xi−μj||2, i = 1,2,...,n;j = 1,2,...,k.    (1)

Step 5. Assign the trajectory point xi into the nearest clusters according to the distance calculated in the previous step, and Cλi= Cλi⋃ is updated.

Step 6. Update the initial center of mass of each cluster:

μj′=1|Cj|∑x∈|Cj|x    (2)

Step 7. Repeat steps 4, 5, and 6 until the initial center of mass no longer changes.

(2)Adaptive DBSCAN

The Adaptive DBSCAN algorithm is a clustering algorithm that improves the DBSCAN algorithm. It improves the characteristics of the DBSCAN algorithm that requires manual input of parameters, introduces the concept of density threshold, and uses the KNN algorithm to determine the optimal parameters automatically. The specific steps are as follows:

Step 1. The density threshold is defined first, i.e.,

Density=MinPtsπ•Eps2    (3)

Step 2. MinPts is the specified minimum number of trajectory points and Eps is the specified radius. On the premise that the number of clusters in the clustering result is correct, the smaller the density threshold, the better the clustering effect. The following equation is used to calculate the distance between the points:

Dn×n = {Dist(i,j)|1≤i≤n,1≤j≤n}    (4)

where n is the number of trajectory points, and Dist(i, j) is the Euclidean distance between the two trajectory points. The elements in D are sorted in ascending order for each row. All data points in the kth column are the K-nearest neighbor distance vector Dk. After averaging, we can get Dk, which is calculated for all columns to obtain the list of Eps parameters:

DEps = {Dk|1≤K≤n}    (5)

Step 3. The definition of MinPts is as follows:

MinPts = 1n∑i=1nPi    (6)

where Pi is the number of Eps domain objects of the ith object, and n is the number of trajectory points.

Step 4. Input the parameters in DEps and the corresponding MinPts into the DBSCAN algorithm. The number of clusters N under different K values can be obtained. In addition, if the number of clusters N is unchanged for more than three consecutive times, the maximum K value corresponding to the number of clusters N is determined as the optimal K value, and then the Eps and MinPts values corresponding to the optimal K value are determined as the optimal parameters.

The distance calculated in formula (4) is Euclidean distance, which is not applicable to the distance of the trajectory points of ships but it uses the actual latitude and longitude instead. Let the latitude and longitude of point A and point B be (xi,yi) and (xj,yj), respectively, and the formula is as follows:

Dist(i,j) =R[cos(xi−xj)cosyicosyj+sinyisinyj]    (7)

where R is the radius of the Earth.

Improved LSTM algorithm

Long short-term memory is a special RNN, which is used to solve the problem of gradient vanishing and gradient exploding in traditional RNN. Compared with the ordinary RNN, LSTM solves the long-term dependence on historical data, which greatly improves the effect of neural network in solving regression problems (Zaremba et al., 2014). LSTM is also widely used in language recognition, text classification, stock forecasting, and other fields (Chakraborty et al., 2020). The structure of LSTM is shown in Figure 1.

www.frontiersin.org

Figure 1. Structure diagram of LSTM neuron.

In the figure, σ represents the sigmoid layer, whose values range is [0,1], where 0 means all forgotten and 1 means all remembered; tanh is the activation function; ht represents the hidden layer at moment t; Xt represents the input route trajectory at moment t; Ct represents the route trajectory information at moment t. The LSTM is mainly controlled by input gate, output gate, and forget gate for the cell, and the principle is as follows.

Forget gate:

ft = σ(Wf•[ht-1,xt]+bf)    (8)

Input gate:z

it = σ(Wi•[ht-1,xt]+bi)    (9) C˜t = tanh  (Wc•[ht-1,xt]+bc)    (10) Ct = ft•Ct-1+it•Ct~    (11)

Output gate:

Ot = σ (Wo[ht-1,xt]+bo)    (12) ht = Ot•tanh(Ct)    (13)

where Wf denotes the weight matrix in the forget gate, bf denotes the bias matrix in the forget gate, Ct~ denotes the candidate vector at moment t, it denotes the input route trajectory at moment t, Ot denotes the output at moment t, and ft denotes the forget information at moment t.

Long short-term memory is a chain structure; in the initial state, values of h0 and C0 are 0; and at this time, the history information is empty. In addition, when the input route trajectory information X1 passes through the first cell, ht−1 and Ct−1 are generated. In the next cell, ht−1 and xt are output through the ft of the sigmoid layer to decide which route information to forget. Then, the input gate generates it and Ct~ according to ht−1 and xt, and the current state Ct can be obtained by multiplying the two parts. The output gate outputs Ot through the sigmoid layer according to ht−1 and xt, and the final output ht can be obtained by multiplying Ot and the activation tanh(Ct). Then, output ht can be used as the input to the next cell and so on (Gers et al., 2000). During the operation of the LSTM, ht−1 represents the short-term memory, which is updated at each moment, while Ct−1 represents the long-term memory, which can save the route trajectory information for a certain time interval, but less than the long-term memory, so the LSTM is called the long- and short-term memory neural network (Huang et al., 2015). Equations (2-1) to (2-6) can be simplified as

[Ct~Otitft] = [tanhσσσ] (W[xtht-1]+b)    (14) Ct = ft•Ct-1+it•Ct~    (15) ht = Ot•tanh (Ct)    (16)

The improved LSTM adds a clustering layer on top of the LSTM. The input trajectories are not directly entered into the LSTM layer but are first classified through the clustering layer. The number of trajectories P for each class is counted according to the MMSI number, and the classes exceeding P are input into the LSTM layer. The improved LSTM is shown in Figure 2. In the figure, yt denotes the output route trajectory at moment t, and n denotes the length of the sequence.

www.frontiersin.org

Figure 2. Structure diagram of the improved LSTM.

The set of classified data is denoted as M = , and d is denoted as the class when Mi ≥ P. Then, Equation 9 should be

it = σ(Wi•[ht-1,dt]+bi)    (17) Evaluation of LSTM algorithm

In this study, two evaluation methods are used to evaluate the performance of the model.

(1) Average absolute error

MAE = 1N∑t-1N|y(t)-y^(t)|    (18)

(2) Root mean square error (RMSE)

R

留言 (0)

沒有登入
gif