GRIN: Generative Relation and Intention Network for Multi-agent Trajectory Prediction
Year: 2021

Abstract:
Learning the distribution of future trajectories conditioned on the past is a crucial problem for understanding multi-agent systems. This is challenging because humans make decisions based on complex social relations and personal intents, resulting in highly complex uncertainties over trajectories. To address this problem, we propose a conditional deep generative model that combines advances in graph neural networks. The prior and recognition model encodes two types of latent codes for each agent: an inter-agent latent code to represent social relations and an intra-agent latent code to represent agent intentions. The decoder is carefully devised to leverage the codes in a disentangled way to predict multi-modal future trajectory distribution. Specifically, a graph attention network built upon inter-agent latent code is used to learn continuous pair-wise relations, and an agent’s motion is controlled by its latent intents and its observations of all other agents. Through experiments on both synthetic and real-world datasets, we show that our model outperforms previous work in multiple performance metrics. We also show that our model generates realistic multi-modal trajectories.

heading: 1 Introduction
text: Generative trajectory forecasting requires learning the distribution of future trajectories conditioned on the past. It can provide an important foundation of path planning and tracking in many domains [28, 1]. In a highly interactive multi-agent environment, such as team sports, each individual takes actions based on its intentions, relations with, and observation of other agents [7]. For example, an attacking basketball player acts based on his/her strategy along with observations of teammates and the defending team. Similarly, an experienced driver identifies potential dangers from observed actions and motions of other drivers, thereby planning ahead of time [27]. Notably, in many such real-world examples, intentions, relations, and interactions are all dynamic, hidden, and stochastic, leading to highly variable future trajectories.
We argue that to model uncertainty correctly we should account for factors that arise from both individual and social (i.e. relation) perspectives, and do so explicitly. That is to say, individual decision/intention and social relation/observation are inductive biases that should be explicitly ∗Work completed during internship at AWS Shanghai AI Labs. †Correspondence authors are Junchi Yan and Tong He.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
introduced into a model design. Existing works model either intention [15, 32] or relations [24, 3, 36], not both, lead to compromised performance under highly interactive and uncertain environments [22].
To better address the problems above, we propose Generative Relation and Intention Network (GRIN) that explicitly models uncertainties of both the intention and relations, the design comes with an added benefit of being more interpretable. Specifically, our contributions are:
1) We present GRIN, a conditional generative model for multi-agent trajectory prediction, trained by variational inference and learning [35];
2) We propose a disentangled design of the model architecture such that the uncertainty from the intention and relations are modelled separately;
3) We evaluate our model on both a deterministic synthetic dataset [18] and a highly stochastic real-world dataset [41] by single-path and distributional metrics, quantifying the ability to predict accurately while being aware of multiple possibilities. Our model consistently outperforms advanced baselines on all datasets and metrics tested, highlighting the critical advantage of generative modeling of intentions and relations.

heading: 2 Related Works
text: Our work is closely related to multi-agent trajectory prediction, relation discovery from trajectory data, and multi-modal prediction, which are discussed in below.

heading: 2.1 Multi-Agent Trajectory Prediction
text: Multi-agent trajectory prediction is an actively researched problem due to its broad applications in robot planning [34, 20], traffic prediction [24, 38, 4, 26], sport video analysis [5] and so on. In practical situations, two major observations challenge trajectory prediction: 1) the way agents interact with each other affects the future trajectories, and 2) given very similar past trajectories, the future paths of the same agents may still be very uncertain, producing diverse and multi-modal outcomes. Next, we survey existing works from these two perspectives in detail.

heading: 2.2 Relation Discovery
text: Relationship between agents can affect their behaviors through two mechanisms: the type or state of the relation and the communications among agents contingent on the relations. As such, modeling the interactions between agents using graphs and the message passing mechanism they afford becomes a natural choice. Ivanovic et al. [12] uses heuristics from spatial proximity to get the graph before making predictions. Most other work start from a fully connected graph, then learn the graph edges in a self-supervised way. Kosaraju et al. [19] run graph attention network [39] on the fully connected graph and use the attention weight to decide how much information to share between agents. Kamra et al. [14] developed a dedicated attention mechanism for trajectory prediction from the inductive bias of motion and intents. Instead of using soft-attention, neural relational inference (NRI) proposed by Kipf et al. [18] takes the form of a variational auto-encoder; the edges are modeled as independent, categorical posterior distributions produced by an encoder trained through a biased reparametrization gradient. Jiachen et al. [24] and Graber et al. [8] improved NRI by using graphs that evolve over time. Compared with [24], which is a error-based model with two-stage training pipeline, our model is probabilistic-based model with more customized end-to-end training procedure. [24, 8] compute discrete edge types, which have difficulty modeling continuously varying relationships.
In summary, most work can be considered as RNN-based where the RNN is combined with the graph structure to model both spatial, temporal and inter-agent relations.

heading: 2.3 Multi-modal Prediction
text: A distributional estimation of possible trajectories provides more information for downstream tasks, especially for those with risk-sensitive processes. Deep generative models are suitable for such tasks. Most existing works build on the generative adversarial network (GAN) [23, 21, 10] and variational auto-encoder (VAE) [11, 6, 18, 8]. Social-GAN [10] is an early attempt to address this issue. However, it only learns a single mode of behavior with high variance. Social-BiGAT [19] explicitly accounts
for the multi-modal nature of the prediction problem by forming a reversible transformation between each scene and its latent noise vector. For VAE-based methods, conditional-VAEs [35] provides an appropriate formulation of trajectory prediction, as the past trajectory can be considered as the conditioning variable. The works [11, 34, 33] explore a serials of work using CVAE-based methods. Beyond Gaussian likelihoods, [24] proposes to use a Gaussian mixture as the likelihood to generate multi-modal predictions, which may be helpful given limited flexibility of neural networks.
Previous works on autonomous driving [2, 25, 37] also use graph neural networks to learn the correlation of agents. However, for [37, 2], the relation and intention of agents are entangled into a single latent variable. In [25], it does not involve a probabilistic generative model design to handle multi-modality.
These recent works have mostly considered multi-modality and built mechanisms to handle interaction between agents. However, to our knowledge, none of them disentangle the multi-modality effects from the two sources: inter-agent and intra-agent (or within-agent), which can influence the trajectory in distinct ways. We address this point through a careful architecture design and thorough empirical validation in the rest of the paper.

heading: 3 Methods
text: We specify notations, describe the task, and introduce the model architecture and training strategy.
Notations In each scene, we are given N agents across T steps. Denote by X ∈ RN×T all the trajectory data in this scene, and xti the location of the i-th agent at the t-th step. Given Tobs ≤ T as the number of historic frames, we have the observation XP = X1:Tobs , and the task is to predict XF = X (Tobs+1):T based on the observation.
Our motivation is to model the uncertainty of future trajectory given the past and to disentangle the two effects from the intra-agent intention and inter-agent relations, both of which are unobserved. Thus, we model the data by conditional generative model with latent variables zA and zG that describe agent intention and relational graph, respectively. This model can be trained by maximizing the evidence lower bound (ELBO, [35]), which is usually used as a surrogate for the intractable log-likelihood. During training, when past and future trajectories are available, we infer the latents using an encoder given XP and XF and optimize the ELBO with SGD. During prediction, we do not require the encoder and predict the future trajectories using the generative model given XP . Our model, GRIN, is illustrated in Figure 1. We describe the details in the following subsections.

heading: 3.1 Encoder
text: The encoder computes an approximate posterior q(z|XP ,XF ) with samples z = [zA, zG] conditioned on XP and XF . To allow disentanglement between the two types of latents, we explore an inductive bias built into our decoder architecture described in Section 3.3.
To start, we concatenate XP and XF along the time dimension and use a recurrent neural network (RNN) to compute feature of the full-length trajectory of each agent:
HERNN = RNN([XP ,XF ]), (1)
where HERNN ∈ RN×Mh , where N is the the number of agents and Mh is the feature dimension. Next, we assume a complete graph G for the N agents, and further improve the feature via a graph convolutional network (GCN):
HEGCN = GCN(G,H E RNN), (2)
where HEGCN ∈ RN×Mh . Assuming z follows a multi-variate Gaussian distribution N (µ, Iσ), with the reparameterization trick [31, 16], we sample ∼ N (0, I), and obtain z = × σ + µ, where the µ and σ are predicted by Multi-Layer Perceptrons (MLP):
µE = Fµ(HEGCN) σE = Fσ(HEGCN) (3)
The encoder’s outputs are zA ∈ RN×MZ , zG ∈ RN×MZ where MZ is the dimension of zA, zG.

heading: 3.2 Prior
text: The prior p(z|XP ) characterize the conditional distribution of z given only XP . In our implementation, the prior shares the model weights with the encoder. In this case, the encoder and prior are only different in terms of the input data to the RNN in Eq 1. By weight-sharing, the same RNN sees inputs with different lengths, and the KL-divergence term in the loss enforces the encoder and decoder to extract similar information from the input. Therefore, the RNN is encouraged to learn to encode the same information from XP and [XP ,XF ]. Besides, weight-sharing reduces its memory cost.
HPRNN = RNN(XP )
HPGCN = GCN(G,H P RNN )
µP = Fµ(HPGCN)
σP = Fσ(HPGCN)
(4)
3.3 Decoder
The decoder p(XF |zA, zG,XP ) produces future trajectories conditioned on the random variable z and the past trajectory XP . Following [18], we assume that that latent z is a sufficient summary of the distance history and define the likelihood as p(Xt+1|z,X1:t) = p(Xt+1|z,Xt). Therefore, given z and Xt, the decoder can predict X̂t+1. For t > Tobs, the input to the decoder is its own prediction X̂t.
The decoder is built with a simple inductive bias that is nonetheless important for capturing inter-agent relations, which we describe now. In many practical situations, the relation between two agent largely depend on the agents themselves and is thus correlated. For example, for three particles A, B and C each with either positive or negative charge, if one knows that A attracts B, and B attracts C, then A must repels C. Thus, the posterior over the relations are highly correlated. Such a correlation over the relations can be more difficult to characterize, since dimensionality of relations scales as N2. Thus, we propose to model the relations as a function of each pair of agent, rather than independent as assumed in previous work, e.g. [18], which yields correlated uncertainty over the relations.
To incorporate this intuition, we assume a complete graph for the N agents, and apply a modified Graph Attention Network (GAT) module [39] to describe their pairwise relations via the attention mechanism. Specifically, we use zG to compute the attention weight on edges and update node features with observation Xt. This module is illustrated in Figure 2 which implements:
eij = 〈Fd(zG,i) · Fs(zG,j)〉 αij = softmaxj{eij}
(5)
where 〈·〉 is the dot product, Fs and Fd are two MLP layers for source (zG,j) and destination (zG,i) node features respectively, and αij is the edge attention weight for the later graph convolution
computation. Thus, the edges become correlated through the graph latents zG of each individual. By definition, the attention thus computed is not constrained to be symmetric but contains the set of symmetric relationships. When the true relationship is indeed symmetric, such as the force between charged particles, we expect this attention matrix to by almost symmetric.
Further, one agent may have its own intention that is usually private and not available to the others. The agent-specific latent zA models such private intentions and does not enter the GAT module. Altogether, it is likely that our model disentangles an agent’s own intention (zA) and the relations through (zG), which we carefully validate in experiments.
The rest of the decoder follows similar from previous work. Given αij and Xt, we perform one round of message passing to extract the feature for each agent:
hti = 1 N − 1 ∑ j αijFg([xti, x t j ]) (6)
Next, we incorporate hti with zA,i to predict the ∆x t+1 i = x t+1 i − xti. We assume ∆x̂ti follows a Gaussian distribution N (∆xti, σx), where σx is for the entire dataset. Then σx is estimated by a single learned parameter σ̂x, and the mean is predicted by:
∆x̂t+1i = Fx([h t i, zA,i]) (7)
The GAT module models the relationships among the agents given zG and their location Xt.

heading: 3.4 Training
text: For training, we sample z = [zA, zG] from the encoder, q(z|XP ,XF ), and then optimize the ELBO: ELBOz = −E[log(p(XF |z,XP ))] + KL[q(z|XP ,XF )||p(z|XP )]. (8)
Since our decoder predicts [∆x̂ti, σ̂x] for agent i at step t, and it follows a Gaussian distribution. We approximate the expectation with the sample mean:
− E[log(p(XF |z,XP ))] ≈ 1
Z T∑ t=Tobs+1 N∑ i=1 [n 2 log(2πσ̂2x) + ∑ (∆x̂ti −∆xti)2 2σ̂2x ] (9)
where Z is the normalization term, and n is the dimension of ∆xti. Since the outputs of prior and the encoder are Gaussian, the second term can be computed analytically:
KL[q(z|XP ,XF )||p(z|XP )] = KL[N (µE , IσE)||N (µP , IσP )]. (10)
Following [10], we sample multiple z’s for one batch, and only compute the gradient from the lowest ELBOz:
L = min z {ELBOz} (11)

heading: 3.5 Trajectory Generation
text: To generate future trajectories, we first sample z from the prior, p(z|XP ), and then roll out the prediction from the decoder for any t ≥ Tobs:
∆x̂t+1i = Decoder(z,X t)
x̂t+1i = x t i + ∆x̂ t+1 i
(12)
The first input of roll out is the ground truth observation XTobs . For t > Tobs, we use X̂t as the input.

heading: 4 Experiments
text: In this section, we analyze the performance of GRIN against several baselines on two datasets. First, we introduce the datasets, baselines, and the evaluation metrics. Next, we show quantitative results comparing GRIN with baselines and ablation study on GRIN. Finally, we conduct qualitative case-study of GRIN’s behavior on the trajectory prediction task.3
3Code and data are available at https://github.com/longyuanli/GRIN_NeurIPS21.

heading: 4.1 Datasets
text: Charged Dataset [18]. We experiment with a simulated deterministic systems: charged particles, which controlled by simple physics rules. In each scene, there are 5 charged particles. Each particle has either a positive or negative charge with equal probability. Particles with the same charge repel each other, and vise versa. We set T = 100 and Tobs = 80 for each scene. We generate 50K scenes for training, and 10K each for validation and test respectively.
NBA Dataset [41]. This dataset contains tracking data from the 2012-2013 NBA season, and is accessible in [30]. In this dataset, each trajectory contains the 2D positions of the basketball and the players from both sides. Each team is consisted of 5 players. We preprocess the data such that each scene has 50 frames and spans approximately 8 seconds of play, and the first 40 frames are historic, i.e. T = 50 and Tobs = 40.

heading: 4.2 Evaluation Metrics
text: The potential uncertainty and multi-modality in the trajectory datasets makes the evaluation difficult. Instead of just measuring the point-wise absolute match between prediction and ground truth, we check both point-wise accuracy and distributional distance by the following different metrics.
1) Average Displacement Error (ADE) and Final Displacement Error (FDE). Average Displacement Error is the L2 distance between the ground truth and predicted trajectories. Final Displacement Error measures the L2 distance between the ground truth final destination and predicted final destination. For stochastic models, we report the best-of-100 displacement error of each trajectory/destination.
2) Conditional Maximum Mean Discrepancy (MMD). MMD [9] is a non-parametric measure of distributional distance between two distributions. Here, our goal is to learn a conditional distribution of the future path given the past, so we used the conditional version defined in [13]. See Appendix for details.
3) Negative Log Likelihood (NLL). With the test dataset, we compute ELBO, an upper bound on the NLL, on the predicted trajectories. Since the computation of ELBO asks for a sample of the random variables for each trajectory, we compute 100 ELBO values and report the mean and the standard deviation. We only report this metric on models that are trained with ELBO.

heading: 4.3 Baselines
text: To make the comparison complete, we decouple the designs to several aspects and compare with the representatives. While there are methods that integrate tracking with a advanced perceptual backbone [19, 33], here we mainly validate our approach of modeling inter- and intra-agent uncertainty, while the integration with other components is also worth future investigation.
Instance Interaction. Some existing works take the form of RNN plus interaction module at each timestamp. Fuzzy Query Attention (FQA) [14] is a recent work following this paradigm, which models the inductive bias from relative motion, intent and interaction.
Inferred Latent Graph. Works in this paradigm take the form of a variational auto-encoder, infer the latent graph from past trajectory. Message passing on the decoder is conducted on the inferred graph. Representative works include Neural Relational Inference (NRI) [18] and its dynamic version Dynamic Neural Relational Inference (dNRI) [8].
Generative Model. Generative model is a suitable tool to handle multi-modality and uncertainty. One classic work following this line is Social-GAN [10], as it is a GAN-based method. It can be considered as a general building block, and can be extended by introducing visual input.
Implementation Details. We implement our model using PyTorch [29], which has BSD-style license. The graph neural network modules are implemented using DGL [40], which has Apache 2.0 license. We train the model with the Adam [17] optimizer with the learning rate of 0.001. For all datasets, we set the dimension of zG and zA to be 2, the hidden dimension of all MLPs in the encoder and decoder to be 128. The batch size is set to be 128 for charged particle dataset and 64 for NBA dataset. Following common practice in VAE training, we let the predicted variance σ̂x be a parameter that is trained along with all other parameters in the model. We estimate the total amount of computation is
in total around 500 hours on an AWS p3.8xlarge EC2 instance with 4 Nvidia V100 GPU. The full details on the architecture and baseline implementations are discussed in the Appendix.

heading: 4.4 Quantitative Evaluation
text: Baseline Comparison. We quantitatively compare our proposed model against the others. In Table 1, we compare on Charged and NBA datasets. Since there’s no multi-modality in Charged dataset, we only report ADE and FED. Since FQA is deterministic, and Social-GAN is not optimized via ELBO, we do not compute NLL for these two models. GRIN achieves the best or on par performance under all the settings. We run hypothesis test of MMD scores and the difference is statistically significant between our prediction and the predictions from dNRI, FQA and Social-GAN. Although the ADE and FDE performance of Social-GAN is similar to GRIN, their MMD is significantly less optimal than ours. This indicates GRIN learns a better distribution of future trajectory.
Disentanglement Ablation Study. We examine the quantitative impact of zG and zA in the model. We make zG or zA deterministic by only predicting the mean as a deterministic latent vector, and remove the KL penalty of this term. Under this setting, the baselines are not computing a valid ELBO thus we don’t report the NLL score. The experiments are conducted on NBA dataset, and the results are available in Table 2. Obviously, the deterministic model is less capable of making predictions in an uncertain environment. The two models with one fixed z both give compromised performance comparing to the full model. Especially for a deterministic zA, only sampling the zG the MMD is significantly larger than the full model. The results shows that having zG and zA together improves on both the discrepancy error and the distribution distance. We also provide perturbation experiments of zA and zG to show the disentanglement of latent space, which can be found in the Appendix.

heading: 4.5 Qualitative Analysis with Visualization
text: We illustrate the predicted trajectories for scenes for both datasets. The figures support that GRIN can predict trajectories accurately in the deterministic environment, and can also capture uncertainty in the stochastic environments. Note that we just illustrate a few number of examples due to space limit, and more can be found in Supplementary to show that the observations is general.
Interactive Scene in a Deterministic Environment. On Charged dataset, we manually design a scenario that some particles start with close trajectories, thus it is highly interactive. Moreover, although we don’t have neutral particles in the training and test environment, a neutral particle with no charge is inserted into the scene. The prediction from GRIN is illustrated in Figure 3. We observe
Full model
Fixed zA
Fixed zG
Ground Truth Generations
Figure 4: Samples of generated trajectories on NBA dataset. For each trajectory, the light solid line is the past trajectory, and the dotted line is the future trajectory. Attacking players are pink, defending players are blue, and the basketball is brown. The first column is the ground truth trajectories, and the following three are the generated samples. The first row shows the generated trajectories from the full model, that we sample from both zG and zA. The second row shows the generated trajectories from the model that only samples different zG with a fixed sample of zA, and the third contains the results from a fixed sample of zG and different samples of zA.
that for a closed pair of particles (1 and 2), our model accurately captures the attracting forces as illustrated in the attention matrix. Interestingly, for the neutral particle 0, the model only picks up a minor effect from particle 1, and it doesn’t impact the other particles either. This empirically proves that our attention module is capable to capture interpretable relationships among agents, and ignores the less relevant pairs.
Uncertainty and Multi-modality in Real-world Environment. We visually show the multimodality in the real-world NBA dataset. First, to show that our model is capable to capture the uncertainty, we illustrate a few scenarios where the prediction trajectories are highly diverged in Figure 4. To further inspect the effect from zG and zA separately, we sample zG repeatedly with one fixed random sample of zA and vise versa, then plot the trajectories under the same scenario. From the ground truth, we see that player 2 carries the ball in the past, and he passes the ball to player 3. From the generation in the first two rows, we see that player 2 could either pass the ball or carry it himself. In the third row, the model only predicts trajectories with a smaller variance. We argue that this case demonstrates that zG has a more significant impact on the uncertainty of trajectories. This observation aligns with the common sense of basketball, as it is highly interactive and players’ movements are mostly affected by the inter-agent relationships.

heading: 5 Conclusion and Discussions
text: oIn this paper, we present GRIN for multi-agent trajectory prediction. Our model achieves state-ofthe-art performance on synthetic and real-world datasets across multiple metrics. Moreover, GRIN explicitly disentangles the sources of future uncertainty in the decoder, and produces convincing interpretable outputs in real-world scenarios.

heading: 5.1 Outlook and Future Works
text: Based on this work, we aim at several meaningful directions as future works.
1) Vision-based Trajectory Prediction. GRIN takes trajectories as inputs directly. While for unstructured vision data which is an important application scenario for our approach, e.g. video, an end-to-end pipeline is often needed to perform tracking and extract inter- and intra-agent information from video data to feed into our model, as done in [19, 33].
2) Dynamic Trajectory Prediction. Real-world environment is highly interactive and dynamic. This can be done by extending our model to continuously update zA and zG as time rolls forward.
3) Sparse Relationship Modeling. For simplicity, we have used a fully connected graph to model agent interactions. Real-world environments often induce sparse connectivity, so connectivity can change over time. Leveraging sparsity dynamically can potentially improve efficiency and scalability.

heading: 5.2 Limitations
text: Our approach may still have limitations in modeling and predicting very complex multi-agent systems. Although it captures the correlations in the relations, we cannot guarantee that the relations are consistent with the rules of the context (e.g. laws of physics between binary charged particles). One can either build in a particular decoder to represent such constraints or use a surrogate model that learns and approximate the rules.

heading: 5.3 Potential Negative Social Impacts
text: Trajectory prediction can be privacy-sensitive when the targets are human individuals. Our model may further mine the underlying interactions and even relations from the observed behaviors which raise some concerns.

heading: Acknowledgement
text: Longyuan Li and Junchi Yan were partly supported by National Key Research and Development Program of China (2020AAA0107600), Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102), and NSFC (61972250, 72061127003).

Review summaries:
This paper proposes to model interactions together with intention using the conditional generative models. For this, the authors created a model to encode two sets of latent variables and provided how they can be used for trajectory prediction. The evaluation is conducted using three datasets (two in the main manuscript and one in the supplementary).  

This paper develops a multivariable multimodal trajectory prediction model titled GRIN which is based on a CVAE framework. Specifically, future trajectories are conditioned on two latent vectors: one (the “interaction” latent) which is intended to represent the interactions between all pairs of entities, and one (the “intent” latent) which is intended to represent the “intent” of each individual entity. These meanings are enforced by the model architecture, as the interaction latent is used to compute attention values which are used to aggregate hidden representations for all pairs of variables, while the intent latent only impacts the prediction of its corresponding entity. Experiments are run on a few trajectory prediction datasets; GRIN outperforms other approaches which model interactions using latent variables. 

This work proposes GRIN, an architecture that explicitly models the latent uncertainty of social and individual aspects of future prediction of multi-agent systems. The architecture is trained using a conditional variational inference framework, and uses graph attention networks to allow for social attention during the future generation stage. The architecture is evaluated on a Charged particles dataset, an NBA motion forecasting dataset and pedestrian datasets (appendix). Quantitative and qualitative results show that the proposed approach is better than the baselines, and showcases the utility of disentangling the latent space into social and individual components.