Hypertron: Explicit Social-Temporal Hypergraph Framework for Multi-Agent Forecasting

1 Introduction

Human intention prediction is an instinctive ability. Taking pedestrian trajectories as an example, humans can predict others' future trajectories based on a priori experience and explicit features of other agents (e.g., location, sociality, time, speed, etc.) to socially make a proper trajectory strategy. However, building predictive models with such capability is challenging. Such models are often parameter redundant and lack interpretability. Therefore, a good forecasting method should effectively predict future trajectories based on the explicit social and temporal interactions among agents and their latent intentions within an acceptable inference time.

There are many existing methods for multi-agent trajectories prediction within scenes, ranging from recurrent neural network (RNN) [Lee et al., 2017; Ivanovic and Pavone, 2019] or attention mechanism [Giuliari et al., 2021; Yuan et al., 2021] to graph neural network (GNN) [Salzmann et al., 2020; Wang et al., 2021]. As shown in Fig 1, many of their interactions among agents are modeled implicitly, which introduce massive homogeneous learnable parameters. These methods have the following shortcomings in agents' interactions: 1) Homogeneous learning methods adopt a uniform representation to model interactions, which is poorly interpretable because it fails to consider rich semantic information. 2) One-to-one approachs calculate the relation between vertices, which can't simulate the relation among multiple vertices and introduce too much redundancy.

To tackle the aforementioned problems, we drive our research perspective to a hypergraph approach to model the relations among agents, which is explicit, heterogeneous, and lightweight as shown in Fig 1. We introduce a hypergraphbased explicit agents interaction method following a coarseto-fine paradigm, which learns relation among multiple agents simultaneously by heterogeneous hyperedges. Firstly, it constructs coarse temporal and social hypergraphs based on explicit relation among agents (e.g., location, sociality). Then, the coarse hypergraphs are optimized by the coarseto-fine hypergraph convolution (CFHconv) to incorporate the latent intentions of the agents. Finally, the trajectory features are further updated by the CFconv Interaction Module (CIM), which enables the interaction of agents in different dimensions.

Furthermore, we construct a human-understandable and lightweight framework, dubbed Hypertron, an explicit socialtemporal hypergraph framework for multi-agent forecasting. Hypertron stacks multiple layers of CIM to explicitly learn the relation among agents in the social and temporal dimensions and generate diverse and plausible trajectories.

To the best of our knowledge, we are the first to propose a hypergraph based framework for multi-agent forecasting, which is illustrated in Fig 2. Our main contributions are summarized as follows:

1. We introduce an interpretable and lightweight hypergraph-based trajectory prediction framework that generates diverse hypotheses to reflect plausible future trajectories.
2. We present a coarse-to-fine hypergraph construction strategy that can explicitly simulate the relation of multiagent trajectories with a sequence representation.
3. We design the CFHconv interaction module that stacks social- and temporal-CFHconv to model different dimensional interactions and incorporate latent intentions of agents.
4. We demonstrate that our framework achieves highly competitive results while saving over 60% parameters and reducing 30% inference time.

2 RelatedWork

Trajectory/Motion Forecasting. The trajectory sequence can be directly represented by sequential models such as RNN [Lee et al., 2017; Ivanovic and Pavone, 2019]. With the rise of powerful attention mechanism, these methods [Giuliari et al., 2021; Yuan et al., 2021] directly model the relation of all agents at any time, which introduce a lot of redundancy in the feature attending process. Graph-based models [Salzmann et al., 2020; Wang et al., 2021] construct relatively sparse edges, but it's hard to construct efficient and interpretable edges. Most of the above methods introduce too many redundant connections among all agents. Unlike the one-to-one modeling paradigm of prior works, our Hypertron models the high-order relation of agents efficiently with heterogeneous hyperedges.

Social Interaction Modeling. Methods for social interaction modeling mainly focus on the temporal and social dimensions. Sequential methods model the temporal features, and GNN are adopted as social models for agent's interaction[Wang et al., 2021]. However, temporal models and relation models only model the interaction implicitly, since all the edges and attention connections in those methods are homogeneous. Our method explicitly defines hyperedges in temporal and social dimensions for agents, thus the model can easily understand agents' interaction at any dimension.

Hypergraph Learning. An emerging research topic in complex networks is to extend graph to hypergraph [Feng et al., 2019; Ji et al., 2020]. It models high-order constraints among data and learns their correlation by connecting two or more vertices simultaneously. In sequence representation, researchers use hypergraphs for tasks like molecular optimization [Kajino, 2019], video object segmentation [Jiang et al., 2019], and traffic flow prediction [Yi and Park, 2020]. However, most methods adopt an implicit approach in modeling and updating the hypergraph. It is still a worthwhile question to consider how to explicitly construct the hypergraph and make it effective in learning the relation among vertices by giving explicit and heterogeneous definitions to the hyperedges.

3 Methods

3.1 ProblemFormulation

We formulate the multi-agent trajectory prediction problem as estimating future trajectory distributions of N (variable) agents based on their motions and the tracking history of all surrounding agents. We denote the current time step as t = 0, our goal is to learn the posterior distribution P(Y|X, I) of all N agents' future trajectories over T future time steps Y = (Y1 ,Y2 , ...,YT ). X = (X-H ,X-H+1 , ...,X0 ) denote all agent states' history at all H+1 observed time steps. And depending on the data, the optional conditional items I may contain the future planning of agents, semantic maps, etc.

3.2 Overview of the Hypertron

To tackle the stochasticity and multi-modality of agents' future behavior, we adopt the conditional variational autoencoders (CVAEs) inside of Hypertron. Our model learns the distribution of future trajectory Y conditioned on past trajectory X and contextual information I by introducing a stochastic latent variable Z. We reformulate future trajectory distribution as:

where p (Z|X, I) is the Gaussian prior distribution and p (Y|X, I, Z) is the conditional likelihood distribution. Since the integration over Z is intractable, we apply negative evidence lower bound (ELBO) Lelbo as one of our loss functions:

where q (Z|Y,X, I) is the posterior net to approximate the true posterior distribution of Z, and DKL(||) denotes the KLdivergence.

Hypertron can explicitly learn the semantic relation of agents in the social and temporal dimensions and predict the distribution of their future trajectories by stacking multiple layers of CIM-based encoders and decoders. Its overall CFHconv framework is shown in Fig 2, and we will introduce its modules as follows.

Figure 2: Overall architecture of the Hypertron. It comprises of three sub-networks: Past Encoder, Future Encoder, CVAEs, and Future Decoder. The flow via red paths are only available in the training.

Past Encoder. Past Encoder is used to encode the multiagent past observed sequence X. By feeding X into CIM, we get the explicit interactive past features CP . Then, we use a mean pooling layer across timesteps to get the mean past features ˜CP = mean(CP ). And fully connected layer (FC) is to map ˜CP to the gaussian parameters (µp, σp) of p (Z|X, I) = N (µp, Diag (σp)2 ). Temporal CFHconv CFHconv Interaction Module

Future Encoder. Similar to Past Encoder, Future Encoder feeds future observed sequence Y into the CIM to learn the semantic relation among multiple agents. Then we compute the mean past features ˜CF = mean(CF ) by the same methods as Past Encoder. And ˜CP and ˜CF are concatenated and fed into the FC to the gaussian parameters (µq, σq) of q (Z|Y, X, I) = N (µq , Diag (σq)2 ). Agent Encoder Social CFHconv Time Encoder Soft link processing Soft link processing

Future Decoder. Our future decoder is similar to other recursive network decoders in an autoregressive way. With one exception, we adopt an explicit regression approach and generate social and temporal hypergraphs of the current trajectories to predict the trajectories of the next timestep. The input sequence of decoder can be formed as Fi = ˆ Yi + Z, where ˆ Yi is the output ˆY of Future decoder at i-th timestep, ˆY0 is initialized from the XN and Z is the sample from past encoder (testing) or future encoder (training). And to approximate p (Y|Z,X, I) according to q (Z|Y,X, I), we minimize the mean squared error between the predicted trajectories and ground truth Y. And our loss is defined as : Hypergraph Construction Add Context I (Optional) FC

To generate more diverse and plausible trajectories after the training phase, we refer to [Yuan et al., 2021] and adopt the diversity sampling technique in DLow [Yuan and Kitani, 2020] to Hypertron.

Temporal CFHconv

3.3 CFHconv

Agent Encoder Social CFHconv Time Encoder Soft link processing Soft link processing To better model agents' social and temporal relation by explicit hypergraph, we propose coarse-to-fine hypergraph convolution (CFHconv), a coarse-to-fine paradigm (as shown in Fig 3). The mathematical formulation of the CFHconv to aggregate agents' information from input feature X and coarse hypergraph Hcoa is given as:

Hypergraph Construction Add Context I (Optional) FC Agent 1 Agent 2 Agent 3 Agent 4 where Xv is vertex feature learned from trajectory feature by a nonlinear feature transformation (instantiated as 1 ×1 convolution). Hconv is hypergraph convolution, A denotes the constructing function, and Fe is the hyperadge aggregation function. Different from the traditional hypergraph convolution, our module adopts a coarse-to-fine paradigm, and we further state the structure in three steps:

Step1 (Hyperedge feature calculation). Our aim is to optimize the coarse hypergraph by computing the fine-grained association between hyperedge features and vertex features. Therefore, the module constructs the hyperedge feature Xe from the vertex features with the coarse hypergraph. For simplicity, we implement Fe by a matrix multiplication with an embedding:

where ⊗ denotes matrix multiplication, We is a hyperedge embedding to be learned, that can be implemented by a nonlinear function (instation 1×1 convolution and ReLU(·)).

FC

Step2 (Fined hypergraph construction). Then, we calculate the correlation matrix Wh by hyperedge features and node features, and thus further optimize the coarse hypergraph by Wh to obtain the fined hypergraph Hf : Temporal CFHconv CFHconv Interaction Module

Agent Encoder

Social CFHconv

where ⊙ is element-wise multiplication, and softmax is used for normalization.

By this paradigm, our fined hypergraph can learn the explicit (distance calculation) and intrinsic (feature association) connections of agents in temporal and social dimensions. Soft link processing Soft link processing

Step3 (Hypergraph convolution module). Since fined hypergraph contains more relational information (distance and association weights) than the traditional hypergraph, we need to redesign the hypergraph convolution for it. dd Context I (Optional)

We define fined vertex ˜D and fined hyperedge degree ˜B as ˜Dii = ∑Kj=1 Hf(i, j), ˜Bjj = ∑Ni=1 Hf(i, j) = 1, respectively. Hf(i, j) denotes the corrlation between the j-th hyperedge to the i-th vertex. Fined vertex ˜D, fined hyperedge degree ˜B, and fined hypergraph Hf are used to calculate our hypergraph convolution. Hypergraph Construction

By following the transfer formulation in [Feng et al., 2019; Zhu et al., 2021], we design our hypergraph convolution module, and it can be generalized as:

where Θ is a trainable parameter and σ denotes an nonlinear activation function (implemented by ReLU(·)), and ˜Xe is the interaction feature. Since ˜B is an identity matrix, it is omitted in Eq 8.

Further, we use the residual connection to update the vertex features and aggregate the interaction feature ˜Xv. The calculation of the output features ˆXv can be formulated as:

By residual connection, our module can easily stack multiple layers and can be inserted into other model without breaking its initial behavior.

3.4 CFHconv InteractionModule

Our CFconv Interaction Module (CIM) is an interaction module based on CFHconv. As shown in Fig 4, it learns the interactions of different agents in temporal and social dimensions through fine-grained hypergraphs. For better applicability to the sequence representation task, CIM follows the encoder and decoder design of [Lee et al., 2017; Yuan et al., 2021]. Compared with the traditional hypergraph convolutional neural network, CFconv has two main types of differences: (1) It adopts an explicit modeling approach, thus the information interaction is more target-oriented, and the network is more lightweight. (2) It follows a coarse-to-fine modeling idea, which provides a more comprehensive interaction and updating process.

Trajectory Feature Extractor. Given N agents' trajectories over T times S = {Stpos }t=T t=1 with their associated scene

CFHconv Interaction Module

context I (e.g., semantic map information extracted by CNN networks), and Stpos is all agents' normalized positions at time t. Based on Stpos , the extractor estimates agents' velocities Stvel and accelerations Stacc to obtain variable trajectory features X = X1, X2, ..., XT , and Xt is defined as:

where St I is the current context, and FC is a fully connected layer that maps trajectory features to high-dimensional space.

Explicit Hypergraph Construction. Thanks to the property that hyperedge can contain multiple vertices, it can describe complex associations among multiple vertices more accurately by fewer hyperedges. We propose a humanunderstandable and machine-learnable hypergraph construction approach that can explicitly model the relation among agents in social and temporal dimensions: (1) Social dimension, we construct the social hypergraph Htsoc = {etn }n=N n=1 at the t step based on the Euclidean distances of all agents at time t, where etn denotes the relation between n-th agent and other agents. (2) Temporal dimension, the temporal hypergraph Hntem = {εtn }n=N n=1 of n-th agent is constructed by multiplying the Euclidean distance with a scaling factor based on the length of the time step, where εtn represents the relation of an agent at different times. Meanwhile, to let the hypergraph focus on more relevant vertex information, we design a soft link, a module that uses a threshold θ to filter the too-small correlation noise and normalize it by softmax function. The soft link processing is computed as:

where Hij denotes the correlation between the j-th hyperedge to the i-th vertex.

Agent/Time Encoding. Unlike other sequential representation networks, Hypertron feeds into all agents' temporal data in a fixed time period simultaneously. Therefore, before performing Social- and Temporal-CFHconv, we adopt positional encoding to add identity information to the data in social and time dimensions to inform each element's explicit criteria for CFHconv. For trajectory sequence X, we use sine and cosine functions to locate embedding:

where P i obs denote the i-th feature of Pobs and d is each dimension of embedding. And the positional encoding output ˆX is computed as ˆX = W2(W1X + Pobs), where W1,W2 is a learnable transformation function.

4 Experiments

Datasets. To evaluate our methods, we conduct experiments on three publicly examined datasets: The ETH/UCY datasets and the Stanford Drone Dataset. As in previous works, the experimental models predict the next 12 timesteps trajectories by observing trajectories of last 8 timesteps.

There are five subsets of real-world pedestrian trajectory prediction in ETH/UCY datasets, each of which contains complex pedestrian behavior, including multi-directional nonlinear trajectories, working together, standing and unpredictable movement to avoid collisions, etc. The multi-agent social scene trajectories with rich interactions are sampled by 0.4 second intervals.

The Stanford drone dataset (SSD) includes 20 top-down scenes of university scenes captured by drones. It is much larger than ETH/UCY and includes other objects like bicycles or cars in addition to pedestrians. And the frame rate is the same as for ETH/UCY.

Metrics. We employ minimum average displacement error (ADEK) and minimum final displacement error (FDEK) of K prediction samples ˆYk of each agent compared to the ground truth Yk: ADEK = 1 T minKk=1 ∑Tt=1 ‖ˆ yt,(k) n - ytn ‖2 , FDEK = minKk=1 ‖ˆ yt,(k) n - ytn ‖2 , where ˆ yt,(k) n denotes the future location of agent n at time t in the k-th sample and ytn is the corresponding ground truth.

Implementation Details. We train the Hypertron with Adam optimizer, and the initial learning rate is 0.001. The number of hyperedges in the social hypergraph is set to 32, and each hyperedge eis indicates the social correlation of the i-th agent with others. Similarly, the counterpart of the temporal hypergraph is set to 20, and each ejt indicates the temporal correlation of the agent in the j-th timestep with others.

4.1 Quantitative Evaluation

Accuracy. For fair comparisons, we do not use any semantic/visual information for ETH/UCY to compare with prior work, including S-GAN [Gupta et al., 2018], PECNet [Mangalam et al., 2020], STAR [Yu et al., 2020], Agentformer [Yuan et al., 2021] and Trajectron++ [Salzmann et al., 2020]. Tab 1 shows the results on all five subsets. We find that our method significantly improves state of the art (SOTA), where it outperforms other works on 1 and 4 out of 5 subsets in ADE20/FDE20, respectively. Especially, Hypertron achieves the lowest average FDE20 error of 0.34 on all subsets, outperforming the second best method (Trajectron++) by 17%. Notably, our method shows promising results on two higher crowd density subsets, ETH and University (Univ), illustrating that Hypertron can effectively interact among multiple agents in dense scenes by the social and temporal hypergraphs and generate accurate future trajectories.

We report the performance on SSD dataset in Tab 2 with Sophie [Sadeghian et al., 2019], PCCSNet [Sun et al., 2021], etc. Our model can obtain competitive results on SSD dataset, achieving only a lower accuracy than PCCSNet. We argue that our model does not extract enough contextual information and that a better extract approach should lead to improved performance. This result reflects that Hypertron can effectively achieve temporal and social interaction among agents and has strong robustness.

Efficiency. The number of parameters and the inference time are essential to model's applicability. We compare the parameters and inference time of Hypertron with other SOTA in Tab 3, including S-GAN, S-LSTM [Alahi et al., 2016], etc. To measure the inference time, we use a V100 GPU. Hypertron is very compact compared to previous work and achieves a better balance of size, inference time, and performance.

The results show that Hypertron can save over 60% parameters and reduce more than 30% inference time compared to AgentFormer. We analysis that our model can achieve better performance with acceptable inference time and parameters because our CIM uses hypergraphs to construct the relations among agents in social and temporal dimensions. It can achieve lightweight interactions while reducing the noise and useless computation from interaction redundancy.

Ablation Studies. We further conduct extensive ablation studies at ETH/UCY. The results are shown in Tab 4, and we find each component of our model plays a key role in improving performance. First, we use Social-CFHconv and Temporal-CFHconv separately instead of our final model to explore the effectiveness of our module. The results in a loss of at least 0.04/0.05 mADE20/mFDE20 score on the test set, showing that Social/Temporal-CFHConv can greatly improve our model by interacting in the social and temporal dimensions. Second, we replace Social/Temporal-CFHConv with Transformer [Vaswani et al., 2017] to further enhance the validation of our model performance. The performance drops at least 0.02/0.03 mADE20/mFDE20 score, indicating that our CFHConv has better interaction capabilities than Transformer. Our performance gains are attributed to our explicit hypergraph construction, it allows Hypertron to learn the specific meaning of each hyperedge and achieve target-oriented optimization of the model.

4.2 Qualitative Evaluation

Trajectory visualization. Fig 5 shows Hypertron's most likely predictions for some examples of ETH/UCY and SSD datasets. We find that Hypertron's predictions are consistent with these groups, resulting in lower error than other models. By comparing results on both datasets, although our model shows good performance, it still has relative errors in prediction due to the lack of additional contextual information (e.g., map, environment information). However, by adding additional information, the prediction results are more stable.

Visualization of coarse-to-fine hypergraph. We visualize some coarse-to-fine hypergraph as examples in Fig 6. Fig 6(a) is a social hypergraph at one timestep and Fig 6(b) is a temporal hypergraph for one agent's trajectory. We can find our hypergraphs can model both social and temporal dimensions very well. In the social dimension, with the social hypergraph, weights can be assigned based on the explicit distance among agents and their latent intentions. And with the temporal hypergraph, it can focus on the relevance and importance between different timesteps. It is worth noting that we explicitly focus on the distance information between different timesteps in the temporal hypergraph, so we can promisingly find that Hypertron can kindly handle the case of sharp turns by assigning a relatively higher weight to the closer vertices.

5 Conclusion

In this work, we present Hypertron, an explicit socialtemporal hypergraphs framework for multi-agent forecasting. It generates diverse and reasonable trajectories by stacking multiple explicit agent interaction modules to estimate the intentions of agents. The interaction module constructs coarse temporal and social hypergraphs based on explicit relation among agents (e.g., location, sociality). The coarse hypergraphs are optimized by the coarse-to-fine hypergraph convolution to incorporate the latent intentions of the agents. Extensive experiments on several challenging trajectory forecasting datasets with SOTA methods show that Hypertron achieves better performance with fewer parameters and inference time.

Acknowledgments

The work is supported by the National Natural Science Foundation of China under Grant 62171436 and 61725105.