Graph-Based Spatial-Temporal Convolutional Network for Vehicle Trajectory Prediction in Autonomous Driving

Inspired by the topological structure of the graph, we model the interactions among vehicles as a spatial-temporal graph. The spatial-temporal graph is defined as $G=\{G_{t}|\forall t\in\{1,\cdots,T\}\}$, where $G_{t}$ is the spatial graph representing the spatial relations of vehicles at the time $t$. Supposing that there are $N$ vehicles in a scene, we define the spatial graph as $G_{t}=\{V_{t},E_{t}\}$, where $V_{t}=\{v_{t}^{n}|\forall n\in\{1,\cdots,N\}\}$ is the set of all vertices. Each vertex $v_{t}^{n}$ represents an individual vehicle in the scene, and the attribute of $v_{t}^{n}$ is the coordinate $(x_{t}^{n},y_{t}^{n})$. $E_{t}$ is the set of all edges, and each edge represents the mutual effects between vehicles.

Generally, a vehicle has different effects on other vehicles. For example, the sudden deceleration of a vehicle would cause close vehicles to slow down or change lanes, but have little influence on vehicles far away from it. Therefore, to distinguish the intensity of interactions between two vehicles, we consider that each edge in $E_{t}$ should be assigned to different weights. In this work, we introduce $A_{t}\in\mathbb{R}^{N\times N}$ as a weighted adjacency matrix whose entries represent how strong the interactions between two vehicles could be. Considering that two vehicles with closer distances have stronger effects on each other, we use the reciprocal of the distance to measure the weight between two vehicles so that closer vehicles have higher weights. Hence, $A_{t}$ can be written as,

where $d_{i,j}$ in $A_{t}$ denotes the distance between the vehicles $i$ and $j$ at the time $t$. A toy example about the generation of a spatial graph is given in Fig. 3, in which each vertex in the graph is corresponding to a vehicle and the reciprocal of distances represent the weights in the weighted adjacency matrix $A_{0}$. At each time $t$ in the past time horizon, we can construct a spatial graph $G_{t}$. By stacking $G_{1},\cdots,G_{T}$, we get the spatial-temporal graph $G$, which is the input of our network. In the spatial-temporal graph, we define $V\in\mathbb{R}^{C\times T\times N}$ as the stacked tensor of all $V_{t}$ in the past time horizon, and $C$ is set to be 2 to represent the two-dimensional coordinate $(x,y)$. Similarly, the adjacency matrix of $G$ is denoted as $A\in\mathbb{R}^{T\times N\times N}$, which is the stack of $A_{1},\cdots,A_{T}$.

The spatial-temporal graph contains raw information about dependencies among vehicles, so we should use well-designed networks to extract these dependencies from the graph. In the spatial dimension, a vehicle’s future trajectory is highly dependent on the motions of its nearby vehicles. To capture the spatial dependencies, existing works [31, 32] use the number of zeros in the grid to represent distances between vehicles, which is inefficient. Since GCN directly operates on the vertices of a graph and has shown its effectiveness to capture the spatial dependencies between one vertex and its neighbors [41], we introduce the spatial graph convolution in this work.

Extended from standard two dimensional convolution [42], the graph convolution operation is expressed as:

where $Z^{(l)}$ denotes the feature matrix of vertices in layer $l$. $f(\cdot)$ is an activation function, $\hat{A}_{t}=A_{t}+I$, $I\in\mathbb{R}^{N\times N}$ is the identity matrix, $\Lambda_{t}\in\mathbb{R}^{N\times N}$ is the diagonal node degree matrix of $\hat{A}_{t}$, $\textbf{W}^{(l)}$ is the parameters matrix of the layer $l$. The aim of computing $\Lambda_{t}^{-\frac{1}{2}}\hat{A}_{t}\Lambda_{t}^{-\frac{1}{2}}$ is to normalize the adjacency matrix, which can speed up the learning process of GCN [42].

As shown in Fig. 4, the graph convolution operations apply a weighted sum to the features of a target vehicle and its surrounding vehicles, and then pass the results to the next layer. The feature of the target vehicle is considered because the state of the target vehicle also impacts its future motions. Note that the shapes of features are the same before and after the graph convolution.

In a real scenario with imperfect sensors which, for example, result in missing or abnormal data, it is necessary to preprocess the raw data, where it is required to remove the abnormal data and infer the missing data. We have introduced a data preprocessing module to complete these tasks. With this module, the abnormal data can be detected and removed by using one of existing anomaly detection methods, and missing data can be inferred by cubic Hermite interpolation.

We set the autonomous vehicle’s horizon of sight as follows. The autonomous vehicles can observe the motions of vehicles within the range of $\pm$ 100 meters longitudinally and two adjacent lanes laterally.

We use a 32-channel convolutional layer with $1\times 1$ kernel size to increase the dimensions of spatial coordinates, which can improve the learning ability of the network [27].

Residual connections are used in this module. The kernel size is $3\times 3$, and the padding is set to be 1 to guarantee that the shape of features is not changed after the convolutions.

Both the encoder and decoder are one-layer GRUs. A linear layer is used to make sure the outputs of the decoder have the expected shape, and also dropout (with 0.5 probability) is applied to prevent overfittings.

Since the outputs of our network are the probability distributions, we train the network by minimizing the negative log-likelihood loss:

where $\mathbb{P}(x_{t}^{n},y_{t}^{n}|\hat{\mu}_{t}^{n},\hat{\sigma}_{t}^{n},\hat{\rho}_{t}^{n})$ denotes the likelihood of the ground truth position $(x_{t}^{n},y_{t}^{n})$ over the predicted probability distribution.

The GSTCN is trained on the NVIDIA GTX1080Ti GPU. The batch size is set to be 128, and we train the model for 250 epochs using Stochastic Gradient Descent (SGD) optimizer with an initial learning rate of 0.1. The learning rate is multiplied by 0.1 every 80 epochs to speed up the convergence of the loss.

We choose appropriate hyperparameters to improve the performance of our network. We first test how the numbers of layers in the spatial graph convolutional module and the TDE affect the performance. As shown in Fig. 7, the best model has one layer in the spatial graph convolutional module and five layers in the TDE. Then, we fix the layer number and vary the number of hidden units in GRU as the number from $\{16,32,64,100,128\}$. As shown in Table I, the model has the lowest RMSE values when the number of hidden units is set to be 32.

Our full model mainly consists of three modules. To verify the effectiveness of each module on vehicle trajectory prediction, we train three variants of our model with different modules: GSTCN without GCN, GSTCN without TDE and GSTCN without GRU. As shown in Table II, the removal of any module in GSTCN will cause an increase in RMSE, which indicates the effectiveness of each module. When removing GCN or TDE from our full model, the features sent to the GRU lack the extracted spatial dependencies or temporal dependencies. As a result, the GRU fails to integrate the correlation between the spatial dependencies and temporal dependencies and cannot reasonably generate future trajectories. If the GRU is removed, the weak correlation between the spatial and temporal dependencies cannot be strengthened. Only after both the spatial dependencies and temporal dependencies are sent to the trajectory prediction module, can our model achieve the best performance, which indicates that the GCN and TDE are complementary in our full model, and the GRU encoder-decoder can strengthen the correlation between spatial dependencies and temporal dependencies from the extracted features and generate more accurate future trajectories.

The proposed network can simultaneously predict all neighbor vehicles’ future trajectories based on their past trajectories. Therefore, it is necessary to analyze the prediction errors of vehicles at different locations. As shown in Fig. 8, we report the RMSE values for vehicles located in the middle, front, and rear of the scene.

We note that vehicles located in the middle of the scene have the lowest RMSE values for all prediction horizons, which is consistent with the intuition that vehicles located in the middle have more neighboring information as inputs than vehicles at the edge. An interesting phenomenon is that the prediction errors of vehicles located in the rear of the scene are always lower than those of the vehicles in the front of the scene. This is because drivers are more likely to be affected by the vehicles in front of them according to the driving experience. However, when predicting the trajectories of the vehicles in the front of the scene, we can only utilize the motion information of the vehicles behind them. Thus, the predictions of the GSTCN are consistent with intuition.

The weights in the adjacency matrix measure the intensities of interactions among vehicles, so we should appropriately mark the weights. In Section III-A, we have introduced the reciprocal of the distance between two vehicles to mark the weights based on prior knowledge. This means that the closer the distance between vehicles the stronger the mutual effects are. Therefore, to validate this prior knowledge has a positive influence on the performance of our model, we introduce two other ways to measure the weights: (1) we directly use the distances between two vehicles to mark the weights; (2) similar to existing works [39, 42], we set all elements in the adjacency matrix to ones as a baseline.

The RMSE values of different weighted adjacency matrices are listed in Table III. The model with the weighted adjacency matrices defined by the reciprocal of the distance outperforms others. Therefore, the reasonable usage of the prior knowledge can help improve the performance of the model. Note that all weighted adjacency matrices outperform the baseline, which demonstrates the effectiveness of weighted adjacency matrices. An interesting result is that although it is contrary to the intuition when marking the weights directly using the distances, the prediction errors are still lower than that of the baseline, which is partly due to the reverse learning ability of the deep-learning-based models.

In order to compare with the methods that only predict one vehicle’s future trajectory each time, we report the RMSE values of the vehicle located in the middle of the scene, as shown in the column of “GSTCN-ONE” in Table IV. It shows that the GSTCN-ONE achieves the lowest prediction errors for almost all prediction horizons, demonstrating the powerful ability of our GSTCN in capturing the spatial-temporal dependencies and inferring the future trajectories.

In Table IV, we can see that in the prediction horizon of one second, the previous state-of-the-art model GRIP has better performance than the GSTCN. However, the deterministic trajectories generated by the GRIP fail to describe the stochastic behaviors of human drivers, so our GSTCN outperforms the GRIP in long prediction horizons, and the average RMSE values are 7.45% lower than that of the GRIP. Both the GSTCN and the CS-LSTM predict the probability distributions over the future trajectories, but GSTCN outperforms CS-LSTM in all prediction horizons, which demonstrates that the GCN is more effective to capture the spatial dependencies than LSTM. In addition, we note that almost all deep-learning-based approaches have better performance than traditional and machine-learning-based methods (CV and C-VGMM+VIM). Among all deep-learning-based methods, the ones that use the information of surrounding vehicles outperform the ones that do not (i.e., V-LSTM). Therefore, it is crucial to consider the neighboring information when predicting the trajectories.

Among all baselines, only the MATF and the GRIP-ALL can simultaneously predict trajectories of all vehicles. Therefore, this paper compares the performance of the two methods with our GSTCN in the case of predicting trajectories of all vehicles. As shown in Table V, our network improves the prediction accuracies for all prediction horizons. For example, the GSTCN achieves 22.4% average accuracy improvement compared with the GRIP-ALL. In addition, although our model does not take the scene images as the additional inputs, it still outperforms the MATF that does. This is because MATF only considers the spatial relationships at one timestamp but ignores the spatial-temporal dependencies, which demonstrates that capturing the spatial-temporal dependencies is far more important than processing the scene images.

Model size and inference speed are two important performance factors to decide whether an algorithm can be deployed to autonomous vehicles. The small model size guarantees that the method can work well with limited hardware resources. The fast inference speed can guarantee that autonomous vehicles have enough time to make decisions based on predictions. Since only the MATF and the GRIP-ALL can simultaneously predict trajectories of all vehicles among all baselines, we compare model sizes and inference speeds of them, as listed in Table VI.

The GRIP-ALL was previously the smallest model with 496.3K parameters. The model size of GSTCN is only about one tenth of that of the GRIP-ALL. To make a fair comparison, the inference speeds of these models are tested on the NVIDIA GTX1080Ti GPU, and we compare the average time required for each model to predict the trajectory of one vehicle. These three model simultaneously predict trajectories of 120 vehicles each time. Our GSTCN spends an average of 0.044 ms to predict one vehicle’s trajectory, which is about 7.3 times faster than the previously fastest model (GRIP-ALL). We achieve these improvements because the backbones of the GSTCN are GCN and CNN, which overcome the limitations induced by the recurrent architecture of LSTM.

In a general case, the data collected by the sensor have some missing points, so we randomly select half of the sequences from the testing set, from which randomly delete 20% of the data points. Before these imperfect data are fed into our model, we use cubic Hermite interpolation to infer the value of missing points.

An extreme case is that a vehicle is totally undetected during a past time horizon, so it is impossible to infer reasonable data for the model. For this case, we randomly select a vehicle from the input and completely discard its trajectory data.

As shown in Table VII, we compare the RMSE for our model with imperfect and perfect data. We can see that the RMSE for imperfect data are greater than these for the perfect data, but the increase is acceptable, which demonstrates the robustness of our model and its potential for practical applications. In addition, when one nearby vehicle is totally undetected during the past time horizon, the RMSE increments in the long prediction horizon (3-5s) are much larger than these in case I, which indicates that the complete undetection of one vehicle has a greater impact on the accuracy of vehicle trajectory prediction than the partial undetection of several vehicles.