# Non-Autoregressive Sparse Transformer Networks for Pedestrian Trajectory Prediction
## 3 Methods  
### Overview  
The goal of trajectory prediction aims to predict the future locations of all pedestrians in a scene. In fact, the future path of an agent depends on two factors, namely, historical trajectory, i.e., the temporal interaction, and the influence from neighbors, i.e., the spatial interaction. Therefore, both spatial and temporal features are the key information that should be considered for predicting trajectories.  
Our proposed Non-autoregressive Sparse Transformer (NaST) networks comprises three main components: a sparse spatial transformer encoder, sparse temporal transformer encoder, and a non-autoregressive transformer decoder. The transformer encoder and decoder comprise feed forward networks and multi-head attention modules as the original transformer [22]. The encoder architecture is built with a sparse strategy and is in charge of modeling social interaction and temporal dependency. The decoder makes inference in a non-autoregressive pattern to generate all the predicted locations in parallel. The overall NaST architecture is shown in Figure 1.  
Given a set of \(N\) pedestrians in a scene with their corresponding observed positions in \(T_{obs}\) steps, \(X^{i}_{t}=\left(x^{i}_{t},y^{i}_{t}\right)\) represents the location of pedestrian \(i\in\{1,\dots,N\}\) at time \(t\in\dots\dots\dots\), \(T_{obs}\}\). Therefore, the history observation trajectories of pedestrian \(i\) can be represented as \(X^{i}_{t},\dots,\dots,X^{i}_{T_{obs}}\), and the future corresponding positions that need to be predicted are \(\hat{Y}^{i}_{t},\ t\in\left\{T_{obs+1},\dots,T_{pred}\right\}\).  
Pedestrian future trajectory is highly related to historical trajectory and the influence of neighbors nearby. Previous works based on dense interaction model constructed super-fluous interactions and thus inevitably resulted in a considerable deviance from reality. The original transformer computes dense self-attention between a pedestrian with all neighbors. However, in a real scenario, a pedestrian is not influenced by all of the nearby neighbors. To find neighbors who are involved in interactions, we designed a sparse spatial transformer to model the social interactions. Due to the consistency of the trajectory in the temporal dimension, not all the temporal nodes are necessary for modeling temporal interactions, thus the temporal transformer is designed to find the most important time steps, which are helpful for predicting the future trajectory.  
In Figure 1, the input history observation sequences are first embedded by a fully connected layer and then sent to the transformer encoder. The transformer encoder comprises a sparse spatial transformer and a sparse temporal transformer, which model the spatial and temporal interaction, respectively. The output features of the sparse spatial and temporal transformers are merged by a fully connected layer to form a set of new features with spatio-temporal encodings. The transformer decoder receives the outputs of the encoder along with a query sequence. The results are then concatenated with random Gaussian noise and embedded by a fully connected layer to generate the predictions sequence \(\hat{Y}^{i}_{t},\ t\in\left\{T_{obs+1},\dots,T_{pred}\right\}\). We elaborate on our modular design for each part in the rest of the section.