# Vessel Navigation Behavior Analysis and Multiple-Trajectory Prediction Model Based on AIS Data

Authors: He Ma; Yi Zuo; Tieshan Li
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

With the increasing application and utility of automatic identification systems (AISs), large volumes of AIS data are collected to record vessel navigation. In recent years, the prediction of vessel trajectories has become one of the hottest research issues. In contrast to existing studies, most researchers have focused on the single-trajectory prediction of vessels. This article proposes a multiple-trajectory prediction model and makes two main contributions. First, we propose a novel method of trajectory feature representation that uses a hierarchical clustering algorithm to analyze and extract the vessel navigation behavior for multiple trajectories. Compared with the classic methods, e.g., Douglas–Peucker (DP) and least-squares cubic spline curve approximation (LCSCA) algorithms, the mean loss of trajectory features extracted by our method is approximately 0.005, and it is reduced by 50% and 30% compared to the DP and LCSCA algorithms, respectively. Second, we design an integrated model for simultaneous prediction of multiple trajectories using the proposed features and employ the long short-term memory (LSTM)-based neural network and recurrent neural network (RNN) to pursue this time series task. Furthermore, the comparative experiments prove that the mean value and standard deviation of root mean squared error (RMSE) using the LSTM are 4% and 14% lower than those using the RNN, respectively.


---

## Body

## 1. Introduction

Since 2007, the International Maritime Organization requested that the international vessels over 300 and noninternational vessels over 500 tons must be attached by automatic identification system (AIS) transmitters and receivers [1]. The AIS has become one of the most important broadcast systems of vessel navigational message, e.g., longitude, latitude, course, and speed via VHF. The message of the AIS can not only be transmitted from ship to shore-based center but can also be exchanged between ships. Therefore, the AIS has been of great support for marine traffic tracking and management such as collision avoidance and risk evaluation [2–4]. With the wide use of the AIS, large volumes of AIS data are generated and stored. Simultaneously, it is increasingly becoming a challenging issue to efficiently utilize AIS data and provide vessel operators with more effective and convenient navigation services. Especially, the vessel trajectory information-based AIS data play a crucial role in the field of transportation studies for significant guidance of navigation behavior analyses [5–9].In recent years, the related studies can be mainly divided into three categories. In the first category, most studies focus on collision avoidance and accident analysis, and they use AIS data to determine the parameters in the ship collision avoidance model [2–4]. In the second category, the studies briefly used AIS data for navigation behavior analysis and classification, and several classification methods such as the k-nearest neighbor (KNN) algorithm and other new methods were used to classify the trajectory [5, 6]. Zhao and Shi focused on behavior analysis based on AIS data and proposed an improved Douglas–Peucker (DP) algorithm for compressing vessel trajectory data [7]. In the final category, scholars mostly focused on trajectory reconstruction- and prediction-based AIS data using regression analysis methods [8–10]. Several scholars also focus on state-of-the-art machine learning techniques for trajectory prediction [11]. Among the above research studies, trajectory prediction is the most key technique of vessel intelligent navigation systems, which can provide navigation guidance and support for vessel operators based on historical AIS data. However, the existing research studies mainly pursued one single trajectory prediction so that the model is lack of generalization ability, and a training process is required for each trajectory individually [5–11].To address this issue, this article proposed a multiple-trajectory prediction model. To realize predicting multiple trajectories, a novel trajectory representation method is proposed to be able to extract common features of multiple trajectories using a series of AIS data points. The proposed method is based on a hierarchical clustering approach [12, 13]. In this work, we use the Euclidean metric to measure the similarity between two points (clusters) using their longitude and latitude from AIS data and sequentially combine two points (clusters) using a greedy order of minimum distance between them. Using our method, multiple trajectories can be represented as common feature points with the same optimal number. Since the new trajectory is still a classic time series data, the article employs long short-term memory (LSTM)-based network and recurrent neural network (RNN) to train the prediction model based on the new features. In the first part of numerical experiments, we compare the proposed features with the traditional features extracted by DP and least-squares cubic spline curve approximation (LCSCA) algorithms. The loss of our features against the original trajectories is 0.005, which is reduced by 50% and 30% compared with the DP and LCSCA algorithms, respectively. In the second part of numerical experiments, we train the trajectory prediction models based on our features using the LSTM and RNN. The measures of root mean squared error (RMSE) is also used to estimate the performance of different prediction models. We found that the prediction models using both the LSTM and RNN can obtain the significantly low RMSE when the dimension of the proposed feature is set to 13. Especially, the model using the LSTM with the optimal parameters (activation function is relu, and dropout is 0.2) can obtain the minimum RMSE of 0.0009, which dramatically outperformed the models using the RNN. The experimental results also show that the mean value and standard deviation of RMSE using the LSTM are 4% and 14% lower than those using the RNN, respectively. Therefore, this article makes two main contributions to the field of trajectory prediction. Firstly, the proposed representation method can extract more approximate features to the original trajectories with fewer AIS points. Secondly, this work solved the main limitation of multiple trajectory prediction accounting for the common features extraction. The models based on our features show efficiency for trajectory prediction, and especially the prediction models using the LSTM.The remainder of this paper is organized as follows. Section2 introduces the literature review of navigation behavior analysis and trajectory prediction model. Section 3 describes the comparative experiments to evaluate the performance of the proposed trajectory representation method and trajectory prediction model. Finally, conclusions are presented in Section 4.


## 2. Materials and Methods

### 2.1. Literature Review

#### 2.1.1. Review of Trajectory Representation

The DP is a feature extraction algorithm that approximates the curve using a series of line segments. In the field of maritime engineering, the DP has been widely used for trajectory representation based on AIS data. Initially, the DP starts with a threshold to denote the maximum distance, and the simplification result of the trajectory can be obtained according to the following steps [14]:(a)
Draw a straight line from the beginning point to the ending point of the original trajectory(b)
Set this line as the initial simplification(c)
Calculate the distance of each point to the simplification line(d)
Consider the point with the maximum distance as the featured point(e)
Separate the simplification line into two line segments by the new point(f)
Repeat steps (c) to (e) until the distance of all the points to the simplification lines is smaller than the thresholdAn improved method that uses kernel-based sparse representation to iteratively obtain a salient feature cluster was proposed in [15, 16]. This method applied an approximate dependence analysis to further maintain complementarity, while eliminating redundancy among the features is selected by the nonlinear orthogonal matching pursuit.LCSCA is also an efficient method to represent trajectory using featured points [15]. When the number of the points of the original trajectory is N, the points can be arranged as T1=x1,y1,T2=x2,y2,…,TN=xN,yN in ascending order of time. The original trajectory can be described as(1)T=T1T2⋮TN=x1,y1x2,y2⋮⋮xN,yN.We set the number of representative points asp, the node vector as τ, and the parameter vector as l=0,l2,…,lN−1,lN. Node vector τ can be calculated as(2)τ=0,0,0,0︸1…4,1p−3,2p−3,3p−3,…,p−4p−3︸5…p,1,1,1,1︸p+1…p+4,lt=hthN=∑i=2txi−xi−12+yi−yi−12∑i=2Nxi−xi−12+yi−yi−12,t=2,3,…,N,lt∈0,1,Ki,1lt=1,ifτi<lt<τi+1,0,otherwise,(3)Ki,jlt=lt−τiτi+j−1−τiKi,j−1+τi+j−ltτi+j−τi+1Ki+1,j−1,where i=1,2,…,p and j=2,3,4. If the coordinates of all the representative points are denoted as T1′=x1′,y1′,T2′=x2′,y2′,…,Tp′=xp′,yp′, the representative points can form a matrix as(4)C=T1′T2′⋮Tp′=x1′y1′x2′y2′⋮⋮xp′yp′,C=ϕ∇T.The control points can be obtained according to equation (3), and j is chosen to be 4 for cubic splines. Thus,(5)ϕ=K1,4l1⋯Kp,4l1⋮⋱⋮K1,4lN⋯Kp,4lN,ϕ∇=ϕTϕ−1ϕT,where the matrix C of the representative points is the final result.


#### 2.1.2. Review of Trajectory Analysis

In this section, we review several related research on vessel trajectory analysis. They can be divided into two main categories as trajectory classification analysis and trajectory prediction analysis [17]. Trajectory classification is to establish classic models to classify the trajectories according to their attributes and characteristics. Liu et al. set categories based on the direction of historical trajectories and then applied the KNN method to recognize new trajectories owing to the right category, which was regarded as the future trends [5]. In [18–20], researchers focused on establishing a vessel trajectory classification model in combination with regression methods and statistical methods, such as logistic regression and probability estimation methods. These research studies included trajectory representation processes before the training classification model, which can not only dramatically save consuming time but also improve the accuracy of trajectory classification. Trajectory prediction analysis is another hot research topic in the field of vessel navigation behavior analysis, which mainly focus on trajectory reconstruction and approximation [21, 22]. Zhang et al. proposed a trajectory construction model based on three sections of a single trajectory [9]. They divided a trajectory into three sections based on the vessel navigation states, and then the spline model and linear regression model were applied to reconstruct the trajectories. Tang et al. applied historical trajectory to training LSTM models for prediction of the future position [11]. However, there is an absence of multiple trajectory prediction in the abovementioned studies.


### 2.2. Navigation Behavior Analysis and Trajectory Prediction Model

The purpose of this article is to implement simultaneous prediction for multiple trajectories using a common model. Since individual trajectory presents different lengths and also contains different numbers of points, it is a challenging issue to train prediction models based on different scaling data. Therefore, this article proposes an integrated framework consisting of two tasks. First, we propose a novel trajectory representation method to solve the data scaling problem, which can extract common features with the same number of points. Second, we employ the RNN and LSTM to solve the time series problem, which can train the models for simultaneous prediction based on the proposed features.


#### 2.2.1. The Proposed Method for Trajectory Representation

AIS data provides many attributes of trajectory, such as navigation time, longitude, latitude, and direction. In this article, longitude and latitude are considered as the typical attributes. If a vessel trajectoryT is given as equation (1), Ti denotes the position point of longitude and latitude as xi,yi. We use the Euclidean metric as the measure of the distance between two points in equations (6) and (7):(6)li=DisTi,Ti+1=xi−xi+12+yi−yi+12(7)S=l1,l2,…,ln−1,where li denotes the distance between Ti and Ti+1, and S denotes the set of all distances in the original trajectory. Then, the simplification process of the proposed method can be described as follows:(a)
Calculate the distanceli between each neighborhood point(b)
Save all the distanceli in S as the initial set(c)
Merge two points (clusters) with the minimumli into the same cluster as Ti′(d)
Recalculate the distance ofTi′ with both sides of neighborhood points (clusters)(e)
Update the setS with new distance li−1 and li(f)
Repeat steps (c) to (e) until the number of clusters is convergent tokThus, the original trajectory can be represented by a series of clusters, and we used the mean value of each cluster as the featured point (see Figure1).Figure 1
Illustration of feature extraction from the original trajectory.The number of the featured points of the representation trajectory is determined based on the loss from the original trajectory. The article uses the dynamic time warping (DTW) method to measure the similarity between two time series of datasets. Therefore, the warp path between the original trajectoryT and representation trajectory T′ can be described as W=w1,w2,…,wK, the distance can be described as DT,T′, and the distance DT,T′ is the loss of the trajectory representation [23].(8)DT,T′=min∑k=1KwkK.


#### 2.2.2. The Proposed Model for Multiple Trajectory Prediction

Both the RNN and LSTM are based on neural networks and widely used to pursue time series prediction. The LSTM can be considered as an improved type of the RNN, which has the ability of long-term memory. The proposed model of multiple-trajectory prediction is shown in Figure2. In the LSTM cell, the input gate uses the tanh function, the forgetting gate uses the sigmoid function, and the output gate also uses the sigmoid function. If the trajectory number is M, the memory module of the LSTM selectively remembers and forgets the input information, and its formula is as follows:(9)Ft=σWf×ht−1+Uf×Tt′+bfFigure 2
Illustration of the trajectory prediction model.Tt′ represents the representation trajectory and can be described as(10)Tt′=T1,1′⋮T1,t′…⋱…TM,1′⋮TM,t′,where TM,t′ denotes the t-th point of the M-th representation trajectory as input. Notation ht−1 is the output of the hidden layer at the (t−1) point. Notation σ is the sigmoid activation function, and notations Ft, Wf, Uf, and bf are the output, weight of Wf, weight of Tt′, and bias of the forgotten gate, respectively. The sigmoid layer determines the updated value as follows:(11)dt=σWi×ht−1+Ui×Tt′+biwhere notations Wi,Ui,bi denote the weight of ht−1, weight of Tt′, and bias of the input gate, respectively. The tanh layer provides a candidate vector for the cell and can be described as follows:(12)Ct˜=tanhWc×ht−1+Uc×Tt′+bcwhere notations Wc,Uc,bc denote the weight of ht−1, weight of Tt′, and bias, respectively. The output values of the forgotten gate and input gate update the cell state Ct can be described as follows:(13)Ct=Ct−1×Ft+Ct˜×dt.The final output uses the new cell state to output content:(14)Ot=σWo×ht−1+Uo×Tt′+bo,ht=Ot×tanhCt,where notations Wo,Uo,bo, and ht denote the weight of ht−1 , weight of Tt′ , bias, and the output of the hidden layer, respectively [24]. If the input is the (i−1) number points of M representation trajectories, the number of the point of the representation trajectory is K, and hi is the i number of points, the notation ht can be described as(15)ht=T1,2′⋮T1,t+1′…⋱…TM,2′⋮TM,t+1′=gT1,1′⋮T1,t′…⋱…TM,1'⋮TM,t′,t=1,3,…,K−1.Then, we use root mean squared error (RMSE) as the evaluation indicator of prediction models. Ifhi,t denotes the actual point t of the trajectory i and hi,t′ denotes the actual point t of this trajectory, the RMSE of the predicted value hi,t′ and the actual value hi,t can be calculated as follows:(16)RMSE=1M∑i=1Mxi,t−xi,t′2+yi,t−yi,t′2.where xi,t,yi,t denotes the coordinate of hi,t, and xi,t′,yi,t′ denotes the coordinate of hi,t′.


## 2.1. Literature Review

### 2.1.1. Review of Trajectory Representation

The DP is a feature extraction algorithm that approximates the curve using a series of line segments. In the field of maritime engineering, the DP has been widely used for trajectory representation based on AIS data. Initially, the DP starts with a threshold to denote the maximum distance, and the simplification result of the trajectory can be obtained according to the following steps [14]:(a)
Draw a straight line from the beginning point to the ending point of the original trajectory(b)
Set this line as the initial simplification(c)
Calculate the distance of each point to the simplification line(d)
Consider the point with the maximum distance as the featured point(e)
Separate the simplification line into two line segments by the new point(f)
Repeat steps (c) to (e) until the distance of all the points to the simplification lines is smaller than the thresholdAn improved method that uses kernel-based sparse representation to iteratively obtain a salient feature cluster was proposed in [15, 16]. This method applied an approximate dependence analysis to further maintain complementarity, while eliminating redundancy among the features is selected by the nonlinear orthogonal matching pursuit.LCSCA is also an efficient method to represent trajectory using featured points [15]. When the number of the points of the original trajectory is N, the points can be arranged as T1=x1,y1,T2=x2,y2,…,TN=xN,yN in ascending order of time. The original trajectory can be described as(1)T=T1T2⋮TN=x1,y1x2,y2⋮⋮xN,yN.We set the number of representative points asp, the node vector as τ, and the parameter vector as l=0,l2,…,lN−1,lN. Node vector τ can be calculated as(2)τ=0,0,0,0︸1…4,1p−3,2p−3,3p−3,…,p−4p−3︸5…p,1,1,1,1︸p+1…p+4,lt=hthN=∑i=2txi−xi−12+yi−yi−12∑i=2Nxi−xi−12+yi−yi−12,t=2,3,…,N,lt∈0,1,Ki,1lt=1,ifτi<lt<τi+1,0,otherwise,(3)Ki,jlt=lt−τiτi+j−1−τiKi,j−1+τi+j−ltτi+j−τi+1Ki+1,j−1,where i=1,2,…,p and j=2,3,4. If the coordinates of all the representative points are denoted as T1′=x1′,y1′,T2′=x2′,y2′,…,Tp′=xp′,yp′, the representative points can form a matrix as(4)C=T1′T2′⋮Tp′=x1′y1′x2′y2′⋮⋮xp′yp′,C=ϕ∇T.The control points can be obtained according to equation (3), and j is chosen to be 4 for cubic splines. Thus,(5)ϕ=K1,4l1⋯Kp,4l1⋮⋱⋮K1,4lN⋯Kp,4lN,ϕ∇=ϕTϕ−1ϕT,where the matrix C of the representative points is the final result.


### 2.1.2. Review of Trajectory Analysis

In this section, we review several related research on vessel trajectory analysis. They can be divided into two main categories as trajectory classification analysis and trajectory prediction analysis [17]. Trajectory classification is to establish classic models to classify the trajectories according to their attributes and characteristics. Liu et al. set categories based on the direction of historical trajectories and then applied the KNN method to recognize new trajectories owing to the right category, which was regarded as the future trends [5]. In [18–20], researchers focused on establishing a vessel trajectory classification model in combination with regression methods and statistical methods, such as logistic regression and probability estimation methods. These research studies included trajectory representation processes before the training classification model, which can not only dramatically save consuming time but also improve the accuracy of trajectory classification. Trajectory prediction analysis is another hot research topic in the field of vessel navigation behavior analysis, which mainly focus on trajectory reconstruction and approximation [21, 22]. Zhang et al. proposed a trajectory construction model based on three sections of a single trajectory [9]. They divided a trajectory into three sections based on the vessel navigation states, and then the spline model and linear regression model were applied to reconstruct the trajectories. Tang et al. applied historical trajectory to training LSTM models for prediction of the future position [11]. However, there is an absence of multiple trajectory prediction in the abovementioned studies.


## 2.1.1. Review of Trajectory Representation

The DP is a feature extraction algorithm that approximates the curve using a series of line segments. In the field of maritime engineering, the DP has been widely used for trajectory representation based on AIS data. Initially, the DP starts with a threshold to denote the maximum distance, and the simplification result of the trajectory can be obtained according to the following steps [14]:(a)
Draw a straight line from the beginning point to the ending point of the original trajectory(b)
Set this line as the initial simplification(c)
Calculate the distance of each point to the simplification line(d)
Consider the point with the maximum distance as the featured point(e)
Separate the simplification line into two line segments by the new point(f)
Repeat steps (c) to (e) until the distance of all the points to the simplification lines is smaller than the thresholdAn improved method that uses kernel-based sparse representation to iteratively obtain a salient feature cluster was proposed in [15, 16]. This method applied an approximate dependence analysis to further maintain complementarity, while eliminating redundancy among the features is selected by the nonlinear orthogonal matching pursuit.LCSCA is also an efficient method to represent trajectory using featured points [15]. When the number of the points of the original trajectory is N, the points can be arranged as T1=x1,y1,T2=x2,y2,…,TN=xN,yN in ascending order of time. The original trajectory can be described as(1)T=T1T2⋮TN=x1,y1x2,y2⋮⋮xN,yN.We set the number of representative points asp, the node vector as τ, and the parameter vector as l=0,l2,…,lN−1,lN. Node vector τ can be calculated as(2)τ=0,0,0,0︸1…4,1p−3,2p−3,3p−3,…,p−4p−3︸5…p,1,1,1,1︸p+1…p+4,lt=hthN=∑i=2txi−xi−12+yi−yi−12∑i=2Nxi−xi−12+yi−yi−12,t=2,3,…,N,lt∈0,1,Ki,1lt=1,ifτi<lt<τi+1,0,otherwise,(3)Ki,jlt=lt−τiτi+j−1−τiKi,j−1+τi+j−ltτi+j−τi+1Ki+1,j−1,where i=1,2,…,p and j=2,3,4. If the coordinates of all the representative points are denoted as T1′=x1′,y1′,T2′=x2′,y2′,…,Tp′=xp′,yp′, the representative points can form a matrix as(4)C=T1′T2′⋮Tp′=x1′y1′x2′y2′⋮⋮xp′yp′,C=ϕ∇T.The control points can be obtained according to equation (3), and j is chosen to be 4 for cubic splines. Thus,(5)ϕ=K1,4l1⋯Kp,4l1⋮⋱⋮K1,4lN⋯Kp,4lN,ϕ∇=ϕTϕ−1ϕT,where the matrix C of the representative points is the final result.


## 2.1.2. Review of Trajectory Analysis

In this section, we review several related research on vessel trajectory analysis. They can be divided into two main categories as trajectory classification analysis and trajectory prediction analysis [17]. Trajectory classification is to establish classic models to classify the trajectories according to their attributes and characteristics. Liu et al. set categories based on the direction of historical trajectories and then applied the KNN method to recognize new trajectories owing to the right category, which was regarded as the future trends [5]. In [18–20], researchers focused on establishing a vessel trajectory classification model in combination with regression methods and statistical methods, such as logistic regression and probability estimation methods. These research studies included trajectory representation processes before the training classification model, which can not only dramatically save consuming time but also improve the accuracy of trajectory classification. Trajectory prediction analysis is another hot research topic in the field of vessel navigation behavior analysis, which mainly focus on trajectory reconstruction and approximation [21, 22]. Zhang et al. proposed a trajectory construction model based on three sections of a single trajectory [9]. They divided a trajectory into three sections based on the vessel navigation states, and then the spline model and linear regression model were applied to reconstruct the trajectories. Tang et al. applied historical trajectory to training LSTM models for prediction of the future position [11]. However, there is an absence of multiple trajectory prediction in the abovementioned studies.


## 2.2. Navigation Behavior Analysis and Trajectory Prediction Model

The purpose of this article is to implement simultaneous prediction for multiple trajectories using a common model. Since individual trajectory presents different lengths and also contains different numbers of points, it is a challenging issue to train prediction models based on different scaling data. Therefore, this article proposes an integrated framework consisting of two tasks. First, we propose a novel trajectory representation method to solve the data scaling problem, which can extract common features with the same number of points. Second, we employ the RNN and LSTM to solve the time series problem, which can train the models for simultaneous prediction based on the proposed features.


### 2.2.1. The Proposed Method for Trajectory Representation

AIS data provides many attributes of trajectory, such as navigation time, longitude, latitude, and direction. In this article, longitude and latitude are considered as the typical attributes. If a vessel trajectoryT is given as equation (1), Ti denotes the position point of longitude and latitude as xi,yi. We use the Euclidean metric as the measure of the distance between two points in equations (6) and (7):(6)li=DisTi,Ti+1=xi−xi+12+yi−yi+12(7)S=l1,l2,…,ln−1,where li denotes the distance between Ti and Ti+1, and S denotes the set of all distances in the original trajectory. Then, the simplification process of the proposed method can be described as follows:(a)
Calculate the distanceli between each neighborhood point(b)
Save all the distanceli in S as the initial set(c)
Merge two points (clusters) with the minimumli into the same cluster as Ti′(d)
Recalculate the distance ofTi′ with both sides of neighborhood points (clusters)(e)
Update the setS with new distance li−1 and li(f)
Repeat steps (c) to (e) until the number of clusters is convergent tokThus, the original trajectory can be represented by a series of clusters, and we used the mean value of each cluster as the featured point (see Figure1).Figure 1
Illustration of feature extraction from the original trajectory.The number of the featured points of the representation trajectory is determined based on the loss from the original trajectory. The article uses the dynamic time warping (DTW) method to measure the similarity between two time series of datasets. Therefore, the warp path between the original trajectoryT and representation trajectory T′ can be described as W=w1,w2,…,wK, the distance can be described as DT,T′, and the distance DT,T′ is the loss of the trajectory representation [23].(8)DT,T′=min∑k=1KwkK.


### 2.2.2. The Proposed Model for Multiple Trajectory Prediction

Both the RNN and LSTM are based on neural networks and widely used to pursue time series prediction. The LSTM can be considered as an improved type of the RNN, which has the ability of long-term memory. The proposed model of multiple-trajectory prediction is shown in Figure2. In the LSTM cell, the input gate uses the tanh function, the forgetting gate uses the sigmoid function, and the output gate also uses the sigmoid function. If the trajectory number is M, the memory module of the LSTM selectively remembers and forgets the input information, and its formula is as follows:(9)Ft=σWf×ht−1+Uf×Tt′+bfFigure 2
Illustration of the trajectory prediction model.Tt′ represents the representation trajectory and can be described as(10)Tt′=T1,1′⋮T1,t′…⋱…TM,1′⋮TM,t′,where TM,t′ denotes the t-th point of the M-th representation trajectory as input. Notation ht−1 is the output of the hidden layer at the (t−1) point. Notation σ is the sigmoid activation function, and notations Ft, Wf, Uf, and bf are the output, weight of Wf, weight of Tt′, and bias of the forgotten gate, respectively. The sigmoid layer determines the updated value as follows:(11)dt=σWi×ht−1+Ui×Tt′+biwhere notations Wi,Ui,bi denote the weight of ht−1, weight of Tt′, and bias of the input gate, respectively. The tanh layer provides a candidate vector for the cell and can be described as follows:(12)Ct˜=tanhWc×ht−1+Uc×Tt′+bcwhere notations Wc,Uc,bc denote the weight of ht−1, weight of Tt′, and bias, respectively. The output values of the forgotten gate and input gate update the cell state Ct can be described as follows:(13)Ct=Ct−1×Ft+Ct˜×dt.The final output uses the new cell state to output content:(14)Ot=σWo×ht−1+Uo×Tt′+bo,ht=Ot×tanhCt,where notations Wo,Uo,bo, and ht denote the weight of ht−1 , weight of Tt′ , bias, and the output of the hidden layer, respectively [24]. If the input is the (i−1) number points of M representation trajectories, the number of the point of the representation trajectory is K, and hi is the i number of points, the notation ht can be described as(15)ht=T1,2′⋮T1,t+1′…⋱…TM,2′⋮TM,t+1′=gT1,1′⋮T1,t′…⋱…TM,1'⋮TM,t′,t=1,3,…,K−1.Then, we use root mean squared error (RMSE) as the evaluation indicator of prediction models. Ifhi,t denotes the actual point t of the trajectory i and hi,t′ denotes the actual point t of this trajectory, the RMSE of the predicted value hi,t′ and the actual value hi,t can be calculated as follows:(16)RMSE=1M∑i=1Mxi,t−xi,t′2+yi,t−yi,t′2.where xi,t,yi,t denotes the coordinate of hi,t, and xi,t′,yi,t′ denotes the coordinate of hi,t′.


## 2.2.1. The Proposed Method for Trajectory Representation

AIS data provides many attributes of trajectory, such as navigation time, longitude, latitude, and direction. In this article, longitude and latitude are considered as the typical attributes. If a vessel trajectoryT is given as equation (1), Ti denotes the position point of longitude and latitude as xi,yi. We use the Euclidean metric as the measure of the distance between two points in equations (6) and (7):(6)li=DisTi,Ti+1=xi−xi+12+yi−yi+12(7)S=l1,l2,…,ln−1,where li denotes the distance between Ti and Ti+1, and S denotes the set of all distances in the original trajectory. Then, the simplification process of the proposed method can be described as follows:(a)
Calculate the distanceli between each neighborhood point(b)
Save all the distanceli in S as the initial set(c)
Merge two points (clusters) with the minimumli into the same cluster as Ti′(d)
Recalculate the distance ofTi′ with both sides of neighborhood points (clusters)(e)
Update the setS with new distance li−1 and li(f)
Repeat steps (c) to (e) until the number of clusters is convergent tokThus, the original trajectory can be represented by a series of clusters, and we used the mean value of each cluster as the featured point (see Figure1).Figure 1
Illustration of feature extraction from the original trajectory.The number of the featured points of the representation trajectory is determined based on the loss from the original trajectory. The article uses the dynamic time warping (DTW) method to measure the similarity between two time series of datasets. Therefore, the warp path between the original trajectoryT and representation trajectory T′ can be described as W=w1,w2,…,wK, the distance can be described as DT,T′, and the distance DT,T′ is the loss of the trajectory representation [23].(8)DT,T′=min∑k=1KwkK.


## 2.2.2. The Proposed Model for Multiple Trajectory Prediction

Both the RNN and LSTM are based on neural networks and widely used to pursue time series prediction. The LSTM can be considered as an improved type of the RNN, which has the ability of long-term memory. The proposed model of multiple-trajectory prediction is shown in Figure2. In the LSTM cell, the input gate uses the tanh function, the forgetting gate uses the sigmoid function, and the output gate also uses the sigmoid function. If the trajectory number is M, the memory module of the LSTM selectively remembers and forgets the input information, and its formula is as follows:(9)Ft=σWf×ht−1+Uf×Tt′+bfFigure 2
Illustration of the trajectory prediction model.Tt′ represents the representation trajectory and can be described as(10)Tt′=T1,1′⋮T1,t′…⋱…TM,1′⋮TM,t′,where TM,t′ denotes the t-th point of the M-th representation trajectory as input. Notation ht−1 is the output of the hidden layer at the (t−1) point. Notation σ is the sigmoid activation function, and notations Ft, Wf, Uf, and bf are the output, weight of Wf, weight of Tt′, and bias of the forgotten gate, respectively. The sigmoid layer determines the updated value as follows:(11)dt=σWi×ht−1+Ui×Tt′+biwhere notations Wi,Ui,bi denote the weight of ht−1, weight of Tt′, and bias of the input gate, respectively. The tanh layer provides a candidate vector for the cell and can be described as follows:(12)Ct˜=tanhWc×ht−1+Uc×Tt′+bcwhere notations Wc,Uc,bc denote the weight of ht−1, weight of Tt′, and bias, respectively. The output values of the forgotten gate and input gate update the cell state Ct can be described as follows:(13)Ct=Ct−1×Ft+Ct˜×dt.The final output uses the new cell state to output content:(14)Ot=σWo×ht−1+Uo×Tt′+bo,ht=Ot×tanhCt,where notations Wo,Uo,bo, and ht denote the weight of ht−1 , weight of Tt′ , bias, and the output of the hidden layer, respectively [24]. If the input is the (i−1) number points of M representation trajectories, the number of the point of the representation trajectory is K, and hi is the i number of points, the notation ht can be described as(15)ht=T1,2′⋮T1,t+1′…⋱…TM,2′⋮TM,t+1′=gT1,1′⋮T1,t′…⋱…TM,1'⋮TM,t′,t=1,3,…,K−1.Then, we use root mean squared error (RMSE) as the evaluation indicator of prediction models. Ifhi,t denotes the actual point t of the trajectory i and hi,t′ denotes the actual point t of this trajectory, the RMSE of the predicted value hi,t′ and the actual value hi,t can be calculated as follows:(16)RMSE=1M∑i=1Mxi,t−xi,t′2+yi,t−yi,t′2.where xi,t,yi,t denotes the coordinate of hi,t, and xi,t′,yi,t′ denotes the coordinate of hi,t′.


## 3. Experiments and Results

### 3.1. Design of Experiments

In this article, the vessel trajectories were collected using AISs, and the location is Dalian port as shown Figure3. The dataset contains 33 vessels with 400 trajectories, and the frequency of points included in each trajectory is from 20 points to 380 points.Figure 3
Geographical location of research data.Firstly, we pursue the original trajectories to extract featured points with the proposed method, DP and LCSCA. The loss of each representation trajectory was calculated and compared with the DTW. The number of extracted points using the proposed method is optimized according to the loss decline rate of DTW. Secondly, we used 90% points of 400 representation trajectories as training data and the remainder 10% as testing data. The RNN and LSTM are used to learn the prediction models, and the comparative experiments for parameters adjustment were conducted to improve the prediction accuracy.


### 3.2. Comparison of Trajectory Representation

To measure the performance and effectiveness of the proposed method, the DP and LCSCA were used as the comparisons. Figure4 shows that the mean loss of all trajectories at different values of the simplified rate (the ratio of the number of points in the representation trajectory with the number of points in the original trajectory) for the three methods. It is found that the mean loss using our method is lower than that using the DP and LCSCA methods in all situations. When the simplified rate is lower than 0.14, the mean loss of the proposed method is almost 50% lower than that of DP and LCSCA methods. It is observed that the deviation of the proposed method is always lower than that of the other two methods.Figure 4
Mean loss of the proposed feature, DP, and LCSCA.Then, the optimal number of extracted points is discussed in Figure5. Figure 5 shows the line plots of the loss and loss decline rate changing with the number of representation points. It can be observed that the loss decline rate can be firstly obtained at the minimum value of 15% when the number of representation points is equal to 13. To reduce the complexity of the prediction model, we use 13-dimensional features as the representation trajectories.Figure 5
Mean loss and loss decline rate of the proposed feature with different numbers of representation points.


### 3.3. Comparison of Trajectory Prediction

According to parameter tuning, we chooserelu as the active function, 0.2 as dropout, and 100 as the epoch. The RNN and LSTM initially consider that the number of input is set to 80, and two hidden layers with the number of neurons are set to 80 and 40, respectively. From the third hidden layer, the number of neurons is set to half of the prior one. Table 1 shows the mean values (M.V.s), maximum values (Max.V.s), minimum values (Min.V.s), and standard deviation (S.D.) of prediction RMSE of 400 trajectories using the LSTM and RNN with different numbers of hidden layers, and the boxplot charts of the RNN and LSTM are drawn in Figures 6 and 7. Figure 6 shows that when the RNN contains five hidden layers, the prediction model shows the best performance. Simultaneously, Figure 7 shows that the model using the LSTM containing four hidden layers can obtain the best performance. We also found that M.V. and S.D. of RMSE of best models using the LSTM were 4% and 14% lower than those of the models using RNN as shown in Figure 8.Table 1
Results of the RNN and LSTM with different numbers of hidden layers (batch size = 1)
Hidden layerLSTMRNNM.V.Max.V.Min.V.S.D.M.V.Max.V.Min.V.S.D.10.02730.08210.00040.01600.02780.09000.00090.017620.02490.07160.00030.01170.02640.07980.00100.015930.02260.08320.00090.01250.02930.08310.00230.013640.02150.08580.00170.01140.02670.08970.00110.013250.02370.08990.00170.01350.02240.08710.00020.0132Figure 6
Box chart of RMSE of the RNN with different numbers of hidden layers.Figure 7
Box chart of RMSE of the LSTM with different numbers of hidden layers.Figure 8
Comparison of the M.V. and S.D. of the RNN and LSTM with different numbers of hidden layers.Then, we draw boxplot charts of RMSE values for the model using the LSTM with different batch sizes in Figure9 and summarize the numerical results in Table 2. However, the best Min.V., Max.V., and S.D. of RMSE can be obtained when the batch size equals 2. The minimum M.V. of RMSE can be dramatically improved when the batch size equals 4.Figure 9
Boxplot chart of RMSE using the LSTM with 4 hidden layers in different batch sizes.Table 2
Results of the LSTM with 4 hidden layers in different batch sizes.
Batch sizeM.V.Max.V.Min.V.S.D.10.02150.08580.00170.011420.02190.07750.00070.011330.02270.08790.00150.011440.02110.08800.00120.011950.02390.08880.00150.0134


## 3.1. Design of Experiments

In this article, the vessel trajectories were collected using AISs, and the location is Dalian port as shown Figure3. The dataset contains 33 vessels with 400 trajectories, and the frequency of points included in each trajectory is from 20 points to 380 points.Figure 3
Geographical location of research data.Firstly, we pursue the original trajectories to extract featured points with the proposed method, DP and LCSCA. The loss of each representation trajectory was calculated and compared with the DTW. The number of extracted points using the proposed method is optimized according to the loss decline rate of DTW. Secondly, we used 90% points of 400 representation trajectories as training data and the remainder 10% as testing data. The RNN and LSTM are used to learn the prediction models, and the comparative experiments for parameters adjustment were conducted to improve the prediction accuracy.


## 3.2. Comparison of Trajectory Representation

To measure the performance and effectiveness of the proposed method, the DP and LCSCA were used as the comparisons. Figure4 shows that the mean loss of all trajectories at different values of the simplified rate (the ratio of the number of points in the representation trajectory with the number of points in the original trajectory) for the three methods. It is found that the mean loss using our method is lower than that using the DP and LCSCA methods in all situations. When the simplified rate is lower than 0.14, the mean loss of the proposed method is almost 50% lower than that of DP and LCSCA methods. It is observed that the deviation of the proposed method is always lower than that of the other two methods.Figure 4
Mean loss of the proposed feature, DP, and LCSCA.Then, the optimal number of extracted points is discussed in Figure5. Figure 5 shows the line plots of the loss and loss decline rate changing with the number of representation points. It can be observed that the loss decline rate can be firstly obtained at the minimum value of 15% when the number of representation points is equal to 13. To reduce the complexity of the prediction model, we use 13-dimensional features as the representation trajectories.Figure 5
Mean loss and loss decline rate of the proposed feature with different numbers of representation points.


## 3.3. Comparison of Trajectory Prediction

According to parameter tuning, we chooserelu as the active function, 0.2 as dropout, and 100 as the epoch. The RNN and LSTM initially consider that the number of input is set to 80, and two hidden layers with the number of neurons are set to 80 and 40, respectively. From the third hidden layer, the number of neurons is set to half of the prior one. Table 1 shows the mean values (M.V.s), maximum values (Max.V.s), minimum values (Min.V.s), and standard deviation (S.D.) of prediction RMSE of 400 trajectories using the LSTM and RNN with different numbers of hidden layers, and the boxplot charts of the RNN and LSTM are drawn in Figures 6 and 7. Figure 6 shows that when the RNN contains five hidden layers, the prediction model shows the best performance. Simultaneously, Figure 7 shows that the model using the LSTM containing four hidden layers can obtain the best performance. We also found that M.V. and S.D. of RMSE of best models using the LSTM were 4% and 14% lower than those of the models using RNN as shown in Figure 8.Table 1
Results of the RNN and LSTM with different numbers of hidden layers (batch size = 1)
Hidden layerLSTMRNNM.V.Max.V.Min.V.S.D.M.V.Max.V.Min.V.S.D.10.02730.08210.00040.01600.02780.09000.00090.017620.02490.07160.00030.01170.02640.07980.00100.015930.02260.08320.00090.01250.02930.08310.00230.013640.02150.08580.00170.01140.02670.08970.00110.013250.02370.08990.00170.01350.02240.08710.00020.0132Figure 6
Box chart of RMSE of the RNN with different numbers of hidden layers.Figure 7
Box chart of RMSE of the LSTM with different numbers of hidden layers.Figure 8
Comparison of the M.V. and S.D. of the RNN and LSTM with different numbers of hidden layers.Then, we draw boxplot charts of RMSE values for the model using the LSTM with different batch sizes in Figure9 and summarize the numerical results in Table 2. However, the best Min.V., Max.V., and S.D. of RMSE can be obtained when the batch size equals 2. The minimum M.V. of RMSE can be dramatically improved when the batch size equals 4.Figure 9
Boxplot chart of RMSE using the LSTM with 4 hidden layers in different batch sizes.Table 2
Results of the LSTM with 4 hidden layers in different batch sizes.
Batch sizeM.V.Max.V.Min.V.S.D.10.02150.08580.00170.011420.02190.07750.00070.011330.02270.08790.00150.011440.02110.08800.00120.011950.02390.08880.00150.0134


## 4. Conclusions

In this article, a prediction model for multiple trajectories was demonstrated based on a novel trajectory representation method. The proposed method used a hierarchical clustering approach to extract the featured point from the original trajectory based on AIS data, and the common features of multiple trajectories can be obtained by a series of simplification line segments. Compared with traditional methods such as the DP and LCSCA, our method shows low loss from the original trajectory, and the lowest loss decline rate can be obtained at 13-dimensional features based on the measures of DTW. To investigate the performance of proposed features, we used a real-world case of the Dalian port and collected the AIS data containing 400 trajectories from 33 vessels. In the experiments, the LSTM and RNN are employed to learn the trajectory prediction models, and both the LSTM and RNN show high performance on multiple trajectory prediction. Especially, the LSTM can obtain the highest performance with the parameters fine-tuning.In the future work, we plan to improve our method in two parts. First, we will design an automatic process to combine the feature extraction and model construction, which can simultaneously obtain the optimal prediction model based on the optimal features. Second, based on the above automatic process, we will implement our model to real-time trajectory prediction in online mode of AISs.



---

*Source: 6622862-2022-01-15.xml*