Grouptron: Dynamic Multi-Scale Graph Convolutional Networks for Group-Aware Dense Crowd Trajectory Forecasting

One of the pioneering works of human trajectory forecasting is the Social Force model [8], which applies Newtonian forces to model human motion. Similar methods with strong priors have also been proposed [9]; yet, most of them rely on hand-crafted energy potential, such as relative distances and rules, to model human motion.

Recently, machine learning methods have been applied to the problem of human trajectory forecasting to obtain models with better performance. One line of work is to formulate this problem as a deterministic time-series regression problem and then solve it using, e.g., Gaussian Process Regression (GPR) [10], inverse reinforcement learning (IRL) [11], and recurrent neural networks (RNNs) [1, 12, 13].

However, the issue of these deterministic regressors is that human behavior is rarely deterministic or unimodal. Hence, generative approaches have become the state-of-the-art trajectory forecasting methods, due to recent advancements in deep generative models [14, 15] and their ability of generating distributions of potential future trajectories (instead of a single future trajectory). Most of these methods use a recurrent neural network architecture with a latent variable model, such as a conditional variational auto-encoder (CVAE) [2, 16, 17, 18], or a generative adversarial network (GAN) [19, 20, 21, 22, 23] to encode multi-modality. Compared to previous work, we not only consider multi-modality from the perspective of a single agent, but also from the group level; we take into account the phenomenon that people usually move in groups. We show that our group-aware prediction has better understanding of the scenes and achieves better forecasting performance.

Of the methods mentioned above, RNN-based methods have achieved better performance. However, recurrent architectures are parameter inefficient and expensive in training [24]. Besides, to handle spatial context, RNN-based methods need additional structures. Most of them use graph models to encode neighboring pedestrians’ information since the topology of graphs is a natural way to represent interactions between pedestrians. Graph convolutional networks (GCN) introduced in [25] is more suitable for dealing with non-Euclidean data. The Social-BiGAT [20] introduces a graph attention network [26] to model social interactions. GraphSAGE [27] aggregates nodes and fuses adjacent nodes in different orders to extract node embeddings. To capture both the spatial and temporal information, Spatio-Temporal Graph Convolutional Networks (STGCN) extends the spatial GCN to spatio-temporal GCN for skeleton-based action recognition [28]. STGCN is adapted by Social-STGNN [29] for trajectory forecasting, where trajectories are modeled by graphs with edges representing social interactions and weighted by the distances between pedestrians. A development related to our paper is dynamic multi-scale GNN (DMGNN) [30], which proposes a multi-scale graph to model human body relations and extract features at multiple scales for motion prediction. There are two kinds of sub-graphs in the multi-scale graph: (i) single-scale graphs, which connect body components at the same scales, and (ii) cross-scale graphs, which form cross-scale connections among body components. Based on the multi-scale graphs, a multi-scale graph computational unit is proposed to extract and fuse features across multiple scales. Motivated by this work, we adopt the multi-scale graph strategy for dense crowd forecasting which includes scene-level graphs, group-level graphs, and individual-level graphs.

People moving in groups (such as friends, family members, etc.) is a common phenomenon and people in each group tend to exhibit similar motion patterns. Motivated by this phenomenon, group-aware methods [31] consider the possibility of human agents being in groups or formations to have more correlated motions than independent ones. They therefore can also model reactions of agents to the moving groups. Human agents can be assigned to different groups by clustering trajectories with similar motion patterns based on methods such as $k$-means clustering [32], support vector clustering [33], coherent filtering [34], and spectral clustering methods [35].

We aim to predict the trajectory distributions of a time-varying $N(t)$ number of pedestrians $P_{N(t)}$. At time step $t$, given the 2-D position $\mathbf{s}\in\mathbb{R}^{2}$ of each pedestrian and their previous trajectories of $T$ time steps $\mathbf{T}\in\mathbb{R}^{T\times 2}$, our goal is to predict the distributions of their trajectories in the next $F$ future time steps, $y=\mathbf{T}_{1,..,N(t)}^{t:t+F}\in\mathbb{R}^{N(t)\times F\times 2}$. We denote the distributions as $p(y\mid x)$. The performance of the predictions is evaluated by standard distance-based metrics on benchmark datasets: the average displacement error (ADE) and the final displacement error (FDE).

Rooted in the CVAE architecture in Trajectron++ [2], we design a more expressive multi-scale scene encoding structure, which actively takes into consideration the group-level and scene-level information for better representation of crowded scenes where groups of pedestrians are present. Concretely, we leverage spatio-temporal graphs for each level to model information and interactions at the corresponding level. We refer to our model as Grouptron. Our model is illustrated in Fig. 2. In this subsection, we provide an overview of the architecture, and in Section III-C, we elaborate on the details of the Grouptron model.

At the individual level, we construct spatio-temporal graphs for individual pedestrians. The graph is centered at the node whose trajectory we want to predict. We call it the “current node”. Long short term memory (LSTM) networks [36] are used to encode this graph. We group the pedestrians with the agglomerative clustering algorithm based on Hausdorff distances [35]. STGCN is used to encode dynamics within the groups.

At the scene level, spatio-temporal graphs are created to model dynamics among pedestrian groups and are encoded using a different STGCN. Lastly, the information across different scales is combined. A decoder is then used to obtain trajectory predictions and the model can output the most possible trajectory or the predicted trajectory distributions.

Together with the latent variable $z$, $E_{multi}$ is passed to the decoder that is a Gated Recurrent Unit (GRU) [37] with 128 dimensions. The output from the GRU decoder is then fed into dynamics integration modules as control actions to output the predicted trajectory distributions, or the single most-likley trajectory, depending on the task.

We adopt the following objective function for the overall CVAE model:

where $I_{q}$ is the mutual information between x and z under the distribution $q_{\phi}(\mathbf{x}|z)$. We follow the process given in [38] to compute $I_{q}$. We approximate $q_{\phi}\left(z|\mathbf{x}_{i},\mathbf{y}_{i}\right)$ with $p_{\theta}\left(z|\mathbf{x}_{i}\right)$, and obtain the unconditioned latent distribution by summing out $\mathbf{x}_{i}$ over the batch.

The model is trained on two publicly available datasets that are benchmarks in the field: The ETH [39], with subsets named ETH and HOTEL, and the UCY [40] datasets, with subsets named ZARA1, ZARA2, and UNIV. The trajectories are sampled at $0.4$ seconds intervals. The model observes 8 time steps, which corresponds to 3.2 seconds, and predicts the next 12 time steps, which corresponds to 4.8 seconds.

To further evaluate and demonstrate Grouptron’s performance in densely populated scenarios, we create UNIV-N test sets, where $N$ is the minimum number of people present simultaneously at each time step in the test sets. Each UNIV-N test set contains all time steps that have at least $N$ people in the scene simultaneously from the original UNIV test set. In this way, we created test sets UNIV-40, UNIV-45, and UNIV-50 and, at each time step, there are at least 40, 45, and 50 people in the scene at the same time. These test sets are far more challenging than the original UNIV test set because of the more complex and dynamic interactions at different scales. We train the models on the original UNIV training set and evaluate the models on the UNIV-40, UNIV-45, and UNIV-50 test sets.

As in prior work [1, 2, 41] and more, we used the following metrics to evaluate our model:

The Grouptron model is implemented using PyTorch. The model is trained using an Intel I7 CPU and NVIDIA GTX 1080 Ti GPUs for 100 epochs. The batch size is 256. For the HOTEL, UNIV, ZARA1, and ZARA2 datasets, the output dimension for the group-level and scene level encoders are 16. For the ETH dataset, we set the output dimension of the group-level and scene-level encoders to be 8. This is because the ETH test set contains only 2 timesteps with at least 5 people in the scene, out of the total 1161 timesteps. In comparison, the training set contains 1910 timesteps, out of 4976 in total, with at least 5 people. Thus, to help the model learn generalizable representations in this case, we decrease the output dimension of the STGCNs to 8. The learning rate is set to $0.001$ initially and decayed exponentially every epoch with a decay rate of 0.9999. The model is trained using Adam gradient descent and gradients are clipped at $1.0$.

In Fig. 3, it is shown that the groups created by the agglomerative clustering method are very close to the natural definition of pedestrian groups. We can see that pedestrians 5 and 6 are travelling in a highly correlated fashion and pedestrians 1, 2, 3, and 4’s trajectories are highly similar as well. In both cases, the clustering algorithm is able to correctly cluster these pedestrians into their corresponding groups. This shows that by using agglomerative clustering based on Hausdorff distances, Grouptron is able to successfully generate naturally defined groups. To quantitatively evaluate the groups generated by the algorithm, we selected 10 random time steps from the ETH training dataset. We invited 10 human volunteers to label groups for the time steps and used the agglomerative clustering method described in Section III-C to generate group clusters, respectively. For both human-generated groups and algorithm-generated groups, the number of groups to be formed is computed using Equation 1. We then compute the average Sørensen–Dice coefficient between human-generated and algorithm-generated groups. That is, we use

where $T$ is the number of timesteps, $H$ is the total number of human annotators, $G_{a,t}$ is the grouping created by the agglomerative clustering method for time step $t$, $G_{h,t}$ is the grouping created by humans for time step $t$, and $|G_{h}\cap G_{a}|$ measures how many of the groups by humans and the algorithm are exactly the same. The Average Dice coefficient between human annotators and the algorithm is 0.72. The higher the Dice coefficient, the more similar are the groups created by the agglomerative clustering method and human annotators. Thus, The average Dice Coefficient of 0.72 indicates the groups output by agglomerative clustering method are really similar to human-generated ones.

We compare Grouptron’s performance with state-of-the-art methods and common baselines in the field in terms of the FDE and ADE metrics, and the results are shown in Table I. Overall, Grouptron outperforms all state-of-the-art methods with considerable decrease in displacement errors. Since Grouptron is built on Trajectron++, we also compare the FDE and ADE values of Grouptron and Trajectron++. We find that Grouptron outperforms Trajectron++ on all 5 datasets by considerable margins. Particularly, on the ETH dataset, Grouptron achieves an FDE of 1.56m, which is 7.1% better than the FDE value of 1.68m by Trajectron++. Furthermore, Grouptron achieves an FDE of 0.97m on the UNIV dataset. This is 9.3% reduction in FDE error when compared with the FDE value of 1.07m by Trajectron++ on the same dataset.

Moreover, we compare Grouptron’s performance with Trajectron++’s in dense crowds with the UNIV-N datasets in Table II. Overall, Grouptron outperforms Trajectron++ on all the UNIV-N test sets by enormous margins. In particular, Grouptron achieves an FDE of 1.04m and ADE of 0.40m on the UNIV-45 test set, which contains all timesteps from the original UNIV test set that have at least 45 pedestrians in the scene at the same time. This is 16.1% in FDE improvement when compared with the FDE value of Trajectron++ and 13.0% in ADE improvement when compared with the ADE value of Trajectron++ on the same test set.

Furthermore, we notice that the state-of-the-art method, Trajectron++, performs substantially worse as the number of pedestrians in the scene increases. Specifically, Trajectron++’s FDE increases from 1.07m to 1.25m as the minimum number of pedestrians in the scene increases from 1 to 50. In contrast, Grouptron’s FDE remains relatively stable as the number of pedestrians increases. This shows that Grouptron performs much better and is more robust in densely populated scenarios.

Fig. 4 shows Grouptron’s most likely predictions for some examples of the UNIV dataset. Fig. 4a shows two pedestrian groups crossing paths. We can see that Grouptron’s predictions are consistent with the groups. Furthermore, it accurately predicts when and where the two groups’ trajectories intersect. Fig. 4b shows a case where pedestrians are forming groups and merging paths. Grouptron again successfully predicts the formation of this group. Fig. 4c and Fig. 4d show Grouptron’s performance in densely populated scenes with more than 40 pedestrians. Even in these extremely challenging scenarios for state-of-the-art methods, Grouptron still produces predictions of high quality and the predictions are consistent with pedestrian groups. Furthermore, we can see that even when pedestrian groups are crossing paths or influencing each other, Grouptron successfully predicts these highly dynamic and complex scenarios.

In Fig. 5, we compare Grouptron’s distributions of 20 most likely predictions with those of Trajectron++’s. Comparing Fig. 5a with 5b and 5c with 5d shows that Grouptron’s predictions for the pedestrians of interest reflect the interactions within pedestrian groups more accurately. Furthermore, Grouptron’s prediction distributions have much smaller ranges, indicating that it is much more confident with prediction outcomes.