summaries: This paper presents a method for dynamic relational inference for multi-agent trajectory prediction. The method extends the neural relational inference (NRI) (Kipf et al., 2018) by changing the static relations between agents to dynamic relations. This equates to inferring time-varying latent variables $z_t^{ij}$ as opposed to learning time-independent latent variables $z^{ij}$. The paper conducts experiments on physics simulations and basketball trajectories to show the superiority of the proposed method against different variants of NRI. The authors propose a novel Relational Inference system that learns to predict the graph structure underlying the data as well as the updated state of the system. Relational reasoning has received considerable attention in recent year. Predicting the graph structure underlying a system from data in a dynamic way is an great next step, which could help alleviate some of the scalability issue currently afflicting these methods. This paper builds on Kipf et al. (2018)’s Neural Relational Inference. In particular, this work introduces a latent variable model which treats the interactions (i.e. relations) between different agents as dynamic and time-varying. As in NRI, the interaction variable between any two agents is conditioned on the history of those agents’ states. An agent’s future state is conditioned on its history of states as well as its interaction variables with other agents.
abstractText: Unsupervised learning of interactions from multi-agent trajectories has broad applications in physics, vision and robotics. However, existing neural relational inference works are limited to static relations. In this paper, we consider a more general setting of dynamic relational inference where interactions change over time. We propose DYnamic multi-Agent Relational Inference (DYARI) model, a deep generative model that can reason about dynamic relations. Using a simulated physics system, we study various dynamic relation scenarios, including periodic and additive dynamics. We perform comprehensive study on the trade-off between dynamic and inference period, the impact of training scheme, and model architecture on dynamic relational inference accuracy. We also showcase an application of our model to infer coordination and competition patterns from real-world multi-agent basketball trajectories.
authors.name: Thomas Kipf
authors.name: Ethan Fetaya
authors.name: Kuan-Chieh Wang
authors.name: Max Welling
authors.name: Richard Zemel
references.authors: Alexandre Alahi Kratarth Goel Vignesh Ramanathan Alexandre Robicquet Li Fei-Fei Silvio Savarese
references.title: Social lstm: Human trajectory prediction in crowded spaces
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Stefano V Albrecht Peter Stone
references.title: Autonomous agents modelling other agents: A comprehensive survey and open problems
references.venue: Artificial Intelligence,
references.authors: Ferran Alet Erica Weng Tomás Lozano-Pérez Leslie Pack Kaelbling
references.title: Neural relational inference with fast modular meta-learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Peter Battaglia Razvan Pascanu Matthew Lai Danilo Jimenez Rezende
references.title: Interaction networks for learning about objects, relations and physics
references.venue: In Advances in neural information processing systems,
references.authors: Samy Bengio Oriol Vinyals Navdeep Jaitly Noam Shazeer
references.title: Scheduled sampling for sequence prediction with recurrent neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Steffen Bickel Michael Brückner Tobias Scheffer
references.title: Discriminative learning under covariate shift
references.venue: Journal of Machine Learning Research,
references.authors: Tian Qi Chen Yulia Rubanova Jesse Bettencourt David K Duvenaud
references.title: Neural ordinary differential equations
references.venue: In Advances in neural information processing systems,
references.authors: Kyunghyun Cho Bart Van Merriënboer Caglar Gulcehre Dzmitry Bahdanau Fethi Bougares Holger Schwenk Yoshua Bengio
references.title: Learning phrase representations using rnn encoder-decoder for statistical machine translation
references.venue: arXiv preprint arXiv:1406.1078,
references.authors: Junyoung Chung Kyle Kastner Laurent Dinh Kratarth Goel Aaron C Courville Yoshua Bengio
references.title: A recurrent latent variable model for sequential data
references.venue: In Advances in neural information processing systems,
references.authors: Marco Fraccaro Søren Kaae Sønderby Ulrich Paquet Ole Winther
references.title: Sequential neural models with stochastic layers
references.venue: In Advances in neural information processing systems,
references.authors: Lise Getoor Nir Friedman Daphne Koller Avi Pfeffer
references.title: Learning probabilistic relational models
references.venue: In Relational data mining,
references.authors: Palash Goyal Emilio Ferrara
references.title: Graph embedding techniques, applications, and performance: A survey
references.venue: Knowledge-Based Systems,
references.authors: Colin Graber Alexander Schwing
references.title: Dynamic neural relational inference
references.venue: Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Roger Grosse Ruslan R Salakhutdinov William T Freeman Joshua B Tenenbaum
references.title: Exploiting compositionality to explore a large space of model structures
references.venue: arXiv preprint arXiv:1210.4856,
references.authors: Aditya Grover Maruan Al-Shedivat Jayesh K Gupta Yura Burda Harrison Edwards
references.title: Learning policy representations in multiagent systems
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Irina Higgins Loic Matthey Arka Pal Christopher Burgess Xavier Glorot Matthew Botvinick Shakir Mohamed Alexander Lerchner
references.title: beta-vae: Learning basic visual concepts with a constrained variational framework
references.authors: Jonathan Ho Stefano Ermon
references.title: Generative adversarial imitation learning
references.venue: In Advances in neural information processing systems,
references.authors: Chin-Wei Huang David Krueger Alexandre Lacoste Aaron Courville
references.title: Neural autoregressive flows
references.venue: In International Conference on Machine Learning,
references.authors: Max Jaderberg Wojciech M Czarnecki Iain Dunning Luke Marris Guy Lever Antonio Garcia Castaneda Charles Beattie Neil C Rabinowitz Ari S Morcos Avraham Ruderman
references.title: Humanlevel performance in 3d multiplayer games with population-based reinforcement learning
references.authors: Eric Jang Shixiang Gu Ben Poole
references.title: Categorical reparametrization with gumble-softmax
references.venue: In International Conference on Learning Representations (ICLR 2017). OpenReview
references.authors: Charles Kemp Joshua B Tenenbaum
references.title: The discovery of structural form
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: arXiv preprint arXiv:1412.6980,
references.authors: Diederik P Kingma Max Welling
references.title: Auto-encoding variational bayes
references.venue: arXiv preprint arXiv:1312.6114,
references.authors: Thomas Kipf Ethan Fetaya Kuan-Chieh Wang Max Welling Richard Zemel
references.title: Neural relational inference for interacting systems
references.venue: In International Conference on Machine Learning,
references.authors: Daphne Koller Nir Friedman Sašo Džeroski Charles Sutton Andrew McCallum Avi Pfeffer Pieter Abbeel Ming-Fai Wong David Heckerman Chris Meek
references.title: Introduction to statistical relational learning
references.venue: MIT press,
references.authors: Tjalling C Koopmans Olav Reiersol
references.title: The identification of structural characteristics
references.venue: The Annals of Mathematical Statistics,
references.authors: Rahul G Krishnan Uri Shalit David Sontag
references.title: Structured inference networks for nonlinear state space models
references.venue: In Thirty-first aaai conference on artificial intelligence,
references.authors: Hoang M Le Yisong Yue Peter Carr Patrick Lucey
references.title: Coordinated multi-agent imitation learning
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Shiyang Li Xiaoyong Jin Yao Xuan Xiyou Zhou Wenhu Chen Yu-Xiang Wang Xifeng Yan
references.title: Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Yunzhu Li Jiajun Wu Russ Tedrake Joshua B Tenenbaum Antonio Torralba
references.title: Learning particle dynamics for manipulating rigid bodies, deformable objects, and fluids
references.venue: arXiv preprint arXiv:1810.01566,
references.authors: Yukai Liu Rose Yu Stephan Zheng Eric Zhan Yisong Yue
references.title: Naomi: Non-autoregressive multiresolution sequence imputation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Christos Louizos Uri Shalit Joris M Mooij David Sontag Richard Zemel Max Welling
references.title: Causal effect inference with deep latent-variable models
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ryan Lowe Yi I Wu Aviv Tamar Jean Harb OpenAI Pieter Abbeel Igor Mordatch
references.title: Multi-agent actor-critic for mixed cooperative-competitive environments
references.venue: In Advances in neural information processing systems,
references.authors: Sindy Löwe David Madras Richard Zemel Max Welling
references.title: Amortized causal discovery: Learning to infer causal graphs from time-series data
references.venue: arXiv preprint arXiv:2006.10833,
references.authors: Sarthak Mittal Alex Lamb Anirudh Goyal Vikram Voleti Murray Shanahan Guillaume Lajoie Michael Mozer Yoshua Bengio
references.title: Learning to combine top-down and bottom-up signals in recurrent neural networks with attention over modules
references.venue: arXiv preprint arXiv:2006.16981,
references.authors: Damian Mrowca Chengxu Zhuang Elias Wang Nick Haber Li F Fei-Fei Josh Tenenbaum Daniel L Yamins
references.title: Flexible neural representation for physics prediction
references.venue: In Advances in neural information processing systems,
references.authors: Syama Sundar Rangapuram Matthias W Seeger Jan Gasthaus Lorenzo Stella Yuyang Wang Tim Januschowski
references.title: Deep state space models for time series forecasting
references.venue: In Advances in neural information processing systems,
references.authors: Alvaro Sanchez-Gonzalez Jonathan Godwin Tobias Pfaff Rex Ying Jure Leskovec Peter W Battaglia
references.title: Learning to simulate complex physics with graph networks
references.venue: arXiv preprint arXiv:2002.09405,
references.authors: Adam Santoro David Raposo David G Barrett Mateusz Malinowski Razvan Pascanu Peter Battaglia Timothy Lillicrap
references.title: A simple neural network module for relational reasoning
references.venue: In Advances in neural information processing systems,
references.authors: Michael Shum Max Kleiman-Weiner Michael L Littman Joshua B Tenenbaum
references.title: Theory of minds: Understanding behavior in groups through inverse planning
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Jiaming Song Hongyu Ren Dorsa Sadigh Stefano Ermon
references.title: Multi-agent generative adversarial imitation learning
references.venue: In Advances in neural information processing systems,
references.authors: Sainbayar Sukhbaatar Rob Fergus
references.title: Learning multiagent communication with backpropagation
references.venue: In Advances in neural information processing systems,
references.authors: Andrea Tacchetti H Francis Song Pedro AM Mediano Vinicius Zambaldi Neil C Rabinowitz Thore Graepel Matthew Botvinick Peter W Battaglia
references.title: Relational forward models for multi-agent learning
references.venue: International Conference on Learning Representations (ICLR
references.authors: Ronald J Williams David Zipser
references.title: A learning algorithm for continually running fully recurrent neural networks
references.venue: Neural computation,
references.authors: Zonghan Wu Shirui Pan Fengwen Chen Guodong Long Chengqi Zhang Philip S Yu
references.title: A comprehensive survey on graph neural networks
references.authors: Jinsung Yoon Daniel Jarrett Mihaela van der Schaar
references.title: Time-series generative adversarial networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Hengshuang Zhao Jianping Shi Xiaojuan Qi Xiaogang Wang Jiaya Jia
references.title: Pyramid scene parsing network
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
sections.text: DYNAMIC RELATIONAL INFERENCE IN MULTI-AGENT TRAJECTORIES
  Anonymous authors Paper under double-blind review
  ABSTRACT
  Unsupervised learning of interactions from multi-agent trajectories has broad applications in physics, vision and robotics. However, existing neural relational inference works are limited to static relations. In this paper, we consider a more general setting of dynamic relational inference where interactions change over time. We propose DYnamic multi-Agent Relational Inference (DYARI) model, a deep generative model that can reason about dynamic relations. Using a simulated physics system, we study various dynamic relation scenarios, including periodic and additive dynamics. We perform comprehensive study on the trade-off between dynamic and inference period, the impact of training scheme, and model architecture on dynamic relational inference accuracy. We also showcase an application of our model to infer coordination and competition patterns from real-world multi-agent basketball trajectories.
sections.heading: 1 INTRODUCTION
sections.text: Particles, friends, and teams are multi-agent relations at different scales. Learning multi-agent interactions is essential to our understanding of the structures and dynamics underlying many systems. Practical examples include understanding social dynamics among pedestrians (Alahi et al., 2016), learning communication protocols in traffic (Sukhbaatar et al., 2016; Lowe et al., 2017) and predicting physical interactions of particles (Mrowca et al., 2018; Li et al., 2018; Sanchez-Gonzalez et al., 2020). Most existing work on modeling relations assume the interactions are observed and train the models with supervised learning. For multi-agent trajectories, the interactions are hidden and thus need to be inferred from data in an unsupervised fashion. While one could impose an interaction graph structure (Battaglia et al., 2016), it is difficult to find the correct structure as the search space is very large (Grosse et al., 2012). The search task is computationally expensive and the resulting model can potentially suffer from the model misspecification issue (Koopmans & Reiersol, 1950). Neural Relational Inference for Interacting Systems
  Thomas Kipf * 1 Ethan Fetaya * 2 3 Kuan-Chieh Wang 2 3 Max Welling 1 4 Richard Zemel 2 3 4
  Abstract
  Interacting systems are prevalent in nature, from dynamical systems in physics to complex societal dynamics. The interplay of components can give rise to complex behavior, which can often be explained using a simple model of the system’s constituent parts. In this work, we introduce the neural relational inference (NRI) model: an unsupervised model that learns to infer interactions while simultaneously learning the dynamics purely from observational data. Our model takes the form of a variational auto-encoder, in which the latent code represents the underlying interaction graph and the reconstruction is based on graph neural networks. In experiments on simulated physical systems, we show that our NRI model can accurately recover ground-truth interactions in an unsupervised manner. We further demonstrate that we can find an interpretable structure and predict complex dynamics in real motion capture and sports tracking data.
  1. Introduction A wide range of dynamical systems in physics, biology, sports, and other areas can be seen as groups of interacting components, giving rise to complex dynamics at the level of individual constituents and in the system as a whole. Modeling these type of dynamics is challenging: often, we only have access to individual trajectories, without knowledge of the underlying interactions or dynamical model.
  As a motivating example, let us take the movement of basketball players on the court. It is clear that the dynamics of a single basketball player are influenced by the other players, and observing these dynamics as a human, we are
  *Equal contribution 1University of Amsterdam, Amsterdam, The Netherlands 2University of Toronto, Toronto, Canada 3Vector Institute, Toronto, Canada 4Canadian Institute for Advanced Research, Toronto, Canada. Correspondence to: Thomas Kipf <t.n.kipf@uva.nl>.
  Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s).
  Observed dynamics Interaction graph
  Figure 1. Physical simulation of 2D particles coupled by invisible
  springs (left) according to a latent interaction graph (right). In this
  example, solid lines between two particle nodes denote connections
  via springs whereas dashed lines denote the absence of a coupling.
  In general, multiple, directed edge types – each with a different associated relation – are possible.
  able to reason about the different types of interactions that might arise, e.g. defending a player or setting a screen for a teammate. It might be feasible, though tedious, to manually annotate certain interactions given a task of interest. It is more promising to learn the underlying interactions, perhaps shared across many tasks, in an unsupervised fashion.
  Recently there has been a considerable amount of work on learning the dynamical model of interacting systems using implicit interaction models (Sukhbaatar et al., 2016; Guttenberg et al., 2016; Santoro et al., 2017; Watters et al., 2017; Hoshen, 2017; van Steenkiste et al., 2018). These models can be seen as graph neural networks (GNNs) that send messages over the fully-connected graph, where the interactions are modeled implicitly by the message passing function (Sukhbaatar et al., 2016; Guttenberg et al., 2016; Santoro et al., 2017; Watters et al., 2017) or with the help of an attention mechanism (Hoshen, 2017; van Steenkiste et al., 2018).
  In this work, we address the problem of inferring an explicit interaction structure while simultaneously learning the dynamical model of the interacting system in an unsupervised way. Our neural relational inference (NRI) model learns the dynamics with a GNN over a discrete latent graph, and we perform inference over these latent variables. The inferred edge types correspond to a clustering of the interactions. Using a probabilistic model allows us to incorporate prior beliefs about the graph structure, such as sparsity, in a principled manner.
  ar X
  iv :1
  80 2.
  04 68
  7v 2
  [s ta
  t.M L]
  6 Ju
  n 20
  18
  Figure 1: Neural R lational I ference for learning th interaction graph. Picture taken from (Kipf et al., 2018)
  Relational inference aims to discover hidden interactions from data and has been studied for decades. Statistical relational learning are based on probabilistic graphical models such as probabilistic relational model (Kemp & Tenenbaum, 2008; Getoor et al., 2001; Koller et al., 2007; Shum et al., 2019). However, these methods may require significant feature engineering and high computational costs. Recently, Battaglia et al. (2016); Santoro et al. (2017) propose to reason about relations using graph neural networks but still requires supervision. One exception is Neural Relational Inf rence (NRI) (Kipf et al., 2018), a flexible deep generative mo el that can infer pot ntial relations in an unsupervised fashi n. As shown in Figure 1, NRI simul-
  taneously learns the dynamics from multi-agent trajectories and infers their re ations. In particular, NRI builds upon variational auto-encoder (VAE) (Kingma & Welling, 2013) and introduces latent variables to represent the hidden relations. Despite its flexibility, a major limiting factor of NRI is that it assumes the relations among the agents are static. Th t is, two agents ar either interacting or n t interacting regardless of their states at different time steps, which is rath r restrictive.
  1
  In this paper, we study a more realistic setting: dynamic relational inference. For example, in game plays, players can coordinate and compete dynamically depending on the strategy. We propose a novel deep generative model, which we call DYnamic multi-Agent Relational Inference (DYARI). DYARI encodes trajectory interactions at different time steps. It utilizes deep temporal CNN models with pyramid pooling to extract rich representations from the interactions. DYARI infers the relations for each sub-sequence dynamically and jointly decode a sequence of relations.
  As relational inference is unsupervised, we use simulated dynamics physics systems as ground truth for validation. We find that the performance of the static NRI model deteriorates significantly with shorter output trajectories, making it unsuitable for dynamic relational inference. In contrast, DYARI is able to accurate infer the hidden relations with various dynamics scenarios. We also perform extensive ablative study to understand the effect of inference period, training schemes and model architecture. Finally, We showcase our DYARI model on real-world basketball trajectories.
  In summary, our contributions include:
  • We tackle the challenging problem of unsupervised learning of hidden dynamic relations given multi-agent trajectories. • We develop a novel deep generative model called DYARI to handle time-varying interactions
  and predict a sequence of hidden relations in an end-to-end fashion. • We demonstrate the effectiveness our method on both the simulated physics dynamics and
  real-world basketball game play datasets.
sections.heading: 2 RELATED WORK
sections.text: Deep sequence models Deep sequence models include both deterministic models (Alahi et al., 2016; Li et al., 2019; Mittal et al., 2020) and stochastic models (Chung et al., 2015; Fraccaro et al., 2016; Krishnan et al., 2017; Rangapuram et al., 2018; Chen et al., 2018; Huang et al., 2018; Yoon et al., 2019). For GAN-like models, (Yoon et al., 2019) combine adversarial training and a supervised learning objective for time series forecasting. Liu et al. (2019) propose a non-autoregressive model for sequence generation. Compared with GANs, VAE-type models can provide explicit inference and are preferable for our purpose. For instance, Chung et al. (2015) introduces stochastic layers in recurrent neural networks to model speech and hand-writing. Rangapuram et al. (2018) parameterizes a linear state-space model for probabilistic time series forecasting. Chen et al. (2018); Huang et al. (2018) combine normalizing flows with autoregressive models. However, all existing models only model the temporal latent states for individual sequences rather than their interactions.
  Relational inference Graph neural networks (GNNs) seek to learn representations over relational data, see several recent surveys on GNNs and the references therein, e.g. (Wu et al., 2019; Goyal & Ferrara, 2018). Unfortunately, most existing work assume the graph structure is observed and train with supervised learning. In contrast, relational inference aims to discover the hidden interactions and is unsupervised. Earlier work in relational reasoning (Koller et al., 2007) use probabilistic graphical models, but requires significant feature engineering. The seminal work of NRI (Kipf et al., 2018) use neural networks to reason in dynamic physical systems. Alet et al. (2019) reformulates NRI as meta-learning and proposes simulated annealing to search for graph structures. Relational inference is also posed as Granger causal inference for sequences (Louizos et al., 2017; Löwe et al., 2020). Nevertheless, all existing work are limited to static relations while we focus on dynamic relations.
  Multi-agent learning Multi-agent trajectories arises frequently in reinforcement learning (RL) and imitation learning (IL) (Albrecht & Stone, 2018; Jaderberg et al., 2019). Modeling agent interactions given dynamic observations from the environment remains a central topic. In the RL setting, for example, Sukhbaatar et al. (2016) models the control policy in a fully cooperative multi-agent setting and applies a GNN to represent the communications. Le et al. (2017) models the agents coordination as a latent variable for imitation learning. Song et al. (2018) generalizes GAIL (Ho & Ermon, 2016) to multi-agent through a shared generator. However, these coordination models only capture the global interactions implicitly without the explicit graph structure. Tacchetti et al. (2019) combines GNN with a forward dynamics model to model multi-agent coordination but also requires supervision. Grover et al. (2018) directly models the episodes of interaction data with GNs for learning multiagent policies. Our method instantiates the multi-agent imitation learning framework, but focuses on relational inference. Our approach is also applicable to dynamic modeling in model-based RL.
sections.heading: 3 DYNAMIC MULTI-AGENT RELATIONAL INFERENCE
sections.text: Given a collection of multi-agent trajectories, we aim to reason about their hidden relations over time. First we describe the underlying probabilistic inference problem.
sections.heading: 3.1 PROBABILISTIC INFERENCE FORMULATION
sections.text: For each agent i ∈ {1, · · · , N}, define its state (coordinates) as xt ∈ RD. A trajectory τ (i) = (x1, x2, · · · , xT ) is a sequence of states that are sampled from a policy. Given trajectories from N agents {τ (i)}Ni=1, dynamic relational inference aims to infer the pairwise interactions of N agents at every time step. Mathematically speaking, the joint distribution of the trajectories can be written as:
  p(τ (1), · · · , τ (N)) = T∏ t=1 p(xt+1|xt, · · · ,x1) (1)
  where p(xt+1|xt, · · · ,x1) represents the state transition dynamics. We use the bold form xt := (x (1) t , · · · , x(N)t ) to indicate the concatenation of all agents observations and x<t := (x1, · · · ,xt).
  We introduce latent variables z(ij)t to denote the interactions between agent i and j at time t. To make the problem tractable, we restrict z(ij)t to be categorical, representing discrete interactions such as coordination or competition. We assume that the dynamics model can be decomposed into the individual dynamics, in conjunction with the pairwise
  interaction. This substantially reduces the dimensionality of the distribution and simplifies learning. Therefore, we can rewrite the transition dynamics as:
  p(xt+1|x<t) ≈ ∫ z N∏ i=1 p(x (i) t+1|x (i) <t, z (ij) t ) N∏ i=1 N∏ j=1,j 6=i p(z (ij) t |x(i)<t, x(j)<t )dz (2)
  Here each p(x(i)t+1|x (i) <t) captures the state transition dynamics of a single agent. p(z (ij) t |x(i)<t, x(j)<t ) represents the latent interactions between two agents. Figure 2 visualizes the graphical model representation for three agents over t number of time steps. The shaded nodes represent observed variables and the unshaded nodes are latent variables. Dynamic relational inference is to estimate distributions of the hidden variables {z(ij)t } at different time steps.
sections.heading: 3.2 DYNAMIC MULTIAGENT RELATIONAL INFERENCE (DYARI)
sections.text: We propose a deep generative model: Dynamic multi-Agent Relational Inference (DYARI). Given the trajectories (x1, · · · ,xT ) of all agents, DYARI first concatenates the trajectories based on a fully connected graph. The concatenated trajectories are used as interaction features for the encoder. Then we sample the sequence of relations from the encoded hidden states. Finally, we generate the future trajectory predictions conditioned on the sampled relations. Figure 3 visualizes the overall architecture of our model which encodes and decodes multi-agent trajectories. The bottom cut-out diagram shows the architecture of our encoder.
  Encoder. A key ingredient of DYARI is an encoder that is inspired by PSPNet (Zhao et al., 2017) to learn rich representations of trajectories at different scales. In particular, we define a residual block as a two-layer CNN with residual connections (He et al., 2016). Our encoder has four modules: feature extraction, pyramid pooling, an aggregation module, and an interpolation module.
  • Feature extraction: the feature extraction module consists of multiple residual blocks interleaved with pooling layers to extract rich temporal features. • Pyramid pooling: the pyramid pooling module learns multi-scale temporal representations from
  the extracted features. First, the output of the feature extraction module is downsampled by 2x
  and 5x through average pooling. Then, the downsampled features are passed through two residual blocks and finally upsampled by 2x and 5x to generate features which are of the same size as the input. The representations learned at 2x and 5x resolutions are concatenated with the input to generate composite multi-scale features.
  • Aggregation module: a 1-D convolution that aggregates the multi-scale features. • Interpolation module: it average-pools the aggregated features corresponding to the dynamic
  period. Then the outputs are upsampled through nearest neighbours interpolation to obtain the hidden presentations for the relations.
  Sampling. We utilize variational inference (Kingma & Welling, 2013) to sample the latent variables from hidden representations. Specifically, assume the interaction posterior z(ij)t to be categorical:
  qφ(z (ij) t |x<t) ∼ Cat(p1, · · · , pk)
  Using the Gumbel-Max trick (Jang et al., 2017), we can reparameterize the categorical distribution as: z (ij) t = Softmax(h (ij) t + g (ij) t ). Here h (ij) t is the hidden states of the encoder and g (ij) t is a random Gumbel vector. Note that a defining feature of DYARI is that the latent variable z(ij)t is time-dependent, requiring fine-grained modeling. Our encoder ensures that the learned representations are expressive enough to capture such complex dynamics.
  Decoder. Given the sampled latent variables, the decoder generates the prediction auto-regressively following a Gaussian distribution:
  p(x (i) t+1|x<t, z (ij) t ) = N (x(i)t+1|µ (i) t+1, σ 2I) (3) µit+1 = fdec( ∑ j 6=i ∑ k z (ij) t,k uk; θ), uk = f k mlp(x (i) t , x (j) t ) (4)
  Here the output x(i)t+1 is reparameterized by a Gaussian distribution with mean µ (i) t+1 and a fixed standard deviation σ2. The mean vector µ(i)t+1 of agent i is computed by aggregating the hidden states of all other agents. We use a separate MLP to encode the previous inputs into different type of edges in a k-dimensional one-hot vector z(ij)t . To generate long-term predictions using the model in Eqn. (4), we can also incorporate the predictions from the previous time step. The decoder architecture is the same as in NRI at a given time step, which consists of message passing GNN operations, followed by a GRU (Cho et al., 2014) decoder.
  Inference. At every time step t, we learn a different distribution for the hidden relation z(ij)t . We assume a uniform prior for pθ(zt) and use ELBO as the optimization objective:
  LELBO = E[log pθ(x<T |z<T )]− βdKL[qφ(z<T |x<T )||pθ(z<T )]] (5)
  = − N∑ i=1 T∑ t=1 (µ (i) t − x(i)t )2 2σ2 + β N∑ i,j T∑ t=1 H(qφ(z (ij) t |xt))
  where the mean vector µ(i)t is parameterized by the decoder. H is the entropy function and β balances the two terms in ELBO (Higgins et al., 2016).
sections.heading: 4 EXPERIMENTS
sections.text: We conduct extensive experiments on simulated physics dynamics and real-world basketball trajectories. The majority of our experiments are based on the physics simulation in the Spring environment. This is ideal for model verification and ablative study as we know the ground truth relations.
  4.1 PHYSICS SIMULATIONS
  Data Generation The Spring environment (Kipf et al., 2018) simulates the movements of a group of particles connected by a spring in a box. The hidden relation is whether there is a spring connecting the two particles. To simulate dynamic relations, we generate the trajectories by removing and adding back the springs following certain patterns. Figure 4 visualizes the trajectories resulting from such dynamic relations. Starting from the bottom, the two-particle trajectories appear as straight lines and bend in the middle due to the spring force, and return to straight lines after the removal of the spring.
  We define the number of time steps between the change of relations as the dynamic period. The primary challenges for dynamic relation inference arise along two dimensions:
  1. The shorter the dynamic period, the more frequent the relation changes. Hence, it becomes more difficult to infer relations with shorter dynamic period.
  2. If the dynamic period itself also changes, then the task becomes much harder because the model also needs to adapt to the unknown period in the changing relations. Note that the way relations change in the trajectories must follow certain pattern and not be completely random. Otherwise it would be impossible to learn anything meaningful.
  We experiment with two types of dynamic relations: periodic dynamics and additive dynamics. For periodic dynamics, we generate the trajectories by periodically removing and adding back the springs. We investigate the model performance by generating data with different frequencies of periodicity. For additive dynamics, we assume the dynamic period is increasing arithmetically. Each trajectory is of length 50 and the decoding length is 40, see details of the generated dataset in Appendix.
  Baselines and Setup We consider several baselines for comparison: (1) NRI (static): unsupervised NRI with an encoder trained using the entire trajectory and infer repeatedly over time. This corresponds to NRI (learned) in (Kipf et al., 2018). (2) NRI (adaptive): NRI (static) with an encoder trained over sub-trajectories. The encoding length corresponds exactly to the dynamic period of the dataset. We use the NRI (static) decoder to predict the entire trajectory in an auto-regressive fashion. (3) Interaction Networks (IN) (Battaglia et al., 2016): a supervised GNN model which uses the ground truth relations to predict future trajectories. We include this supervised learning model as the “gold standard” for our inference tasks. It is important to note here that (Graber & Schwing, 2020) also propose a model, dNRI, for this problem but the focus of their work is trajectory prediction whereas we focus on unsupervised relational inference. In our experiments with their model, we observed a relational inference accuracy of 0.505 on our periodic data with dynamic period 20. On the other hand, the same model gives an accuracy of 0.66 on the 3-particle synthetic data presented in their paper. Therefore, dNRI is unable to infer relations in an unsupervised setting.
  In practice, we do not know the dynamic period beforehand. Therefore, how often we infer the relations is a difficult choice: rare inference would miss the time steps where relations change while predicting too frequently introduces more latent variables and complicates the inference. To investigate this trade-off, we define inference period as the number of time steps between two
  predicted relations. Unless otherwise noted, the inference period in our experiments is the same as the dynamic period. All the models are trained to predict the sequence in an auto-regressive fashion: the prediction of the current time step is fed as the input to the next time step. We use Adam (Kingma & Ba, 2014) optimizer with learning rate 5e−4 and weight decay 1e−4 and train for 300 epochs.
sections.heading: 4.1.1 PATHOLOGICAL CASES OF NEURAL RELATIONAL INFERENCE
sections.text: It is known that latent variable models suffer from the problem of identifiability (Koopmans & Reiersol, 1950), which means certain parameters, in principle, cannot be estimated consistently. NRI infers correlation-like relations between trajectories which highly depend on the length of the time lag. To test this hypothesis, we follow the exact same setting as Kipf et al. (2018) to infer the interaction graph. Instead of decoding 50 time steps, we vary the length of input and output sequence.
  Table 1 summarizes the inference accuracy with different sequence length in the encoder and decoder. We can see that the performance of NRI deteriorates drastically with shorter training sequences, simply increasing the capacity of the encoder (NRI++) does not help. One plausible explanation is that NRI is learning correlation-like interactions. Shorter decoding sequences carry less information about correlations, making it harder to learn. Meanwhile, we also observed that using auto-regressive can achieve better inference accuracy compared to teacher forcing. The pathological cases highlight the issue of NRI for dynamic relational inference. If the interactions change frequently every few time steps, repeatedly applying NRI to different time steps would suffer from short decoding sequences. Therefore, having a model that can jointly infer a sequence of relations is critical.
sections.heading: 4.1.2 DYNAMIC RELATIONAL INFERENCE COMPARISON
sections.text: We compare the performance of different models for dynamic relational inference tasks.
  Periodic dynamics In the periodic scenario, the dynamic period is fixed. We generate four datasets with a dynamic period of 40, 20, 8, 4 to simulate relational dynamics with increasing frequency. Table. 2 columns “40, 20, 8, 4” show the trajectory prediction mean square error (MSE) and interaction inference accuracy comparison of different methods.
  We can see that all methods can achieve almost perfect predictions of the trajectories with very low MSE. However, there is a sharp difference in relational inference accuracy. NRI (static) is incapable of learning dynamic interactions. NRI(adaptive) can learn but has lower accuracy due to short decoding sequences. With a more expressive encoder and joint decoding, DYARI is able to reach higher accuracy. When the dynamic period is very small at 4, even DYARI struggles slightly, suggesting the fundamental difficulty with frequently changing dynamics.
  Additive Dynamics In the additive scenario, we allow the dynamic period itself to increase arithmetically. We increase the dynamic period in steps of 4 starting from a dynamic period of 4 timesteps. In a sequence of 40 timesteps, this implies that the relations (spring connection) get flipped at timesteps 4, 12 and 24. We use four NRI(static) models, each trained separately with 4, 8, 12 and 16 encoding timesteps. We combine the ensemble model predictions into NRI(adaptive). Table. 2 “Add” columns show the performance comparison. Similar to the periodic scenario, DYARI outperforms the baselines in this challenging task as well. Note that NRI(adaptive) is a close competitor w.r.t inference accuracy, but it is a four model ensemble and takes a long time to train.
sections.heading: 4.1.3 ABLATIVE STUDY
sections.text: We perform ablative study to further validate our experiment design and understand the behavior of DYARI. In particular, we study the trade-off between dynamic and inference period, the effect of training scheme, as well as the ablative study of model architecture design.
  Table 3: Inference accuracy for different combinations of dynamic and inference periods with DYARI.
  Dynamic Period 40 8 4
  Inference Period
  40 0.99 0.50 0.50 8 0.88 0.80 0.50 4 0.80 0.76 0.74
  Dynamic vs. Inference Period. To understand the relations between dynamic and inference period, we repeat the periodic scenario experiments by varying both dynamic and inference period in 40, 8, 4 time steps.
  In Table 3, we observe that dynamic relational inference reaches the highest accuracy when the inference period matches the dynamic period. If the inference period is longer than the dynamic period, the model can miss the changes in the relations and completely fails to perform inference. Meanwhile, if the inference period is shorter than the dynamic period, the model still can learn but suffers from low accuracy. This is potentially due to the extra uncertainty introduced by estimating more latent variables.
  Decoder Training Scheme Another fundamental challenge in sequence prediction is covariate shift (Bickel et al., 2009) – a mismatch between distribution in training and testing – due to sequential dependency. Common solutions to mitigate covariate shift include teacher forcing (Williams & Zipser, 1989) and scheduled sampling (Bengio et al., 2015). However, all these work are focused the prediction of observed sequence while our sequence predictions are on the latent variables. It is not evident that covariate shift exists in this setting. We demonstrate the empirical evidence for the effect of different training schemes on the accuracy of relational inference.
  Quite surprisingly, we found that auto-regressive training is most effective for dynamic relations inference. Figure. 5 summarizes the difference in learning curve between using teacher forcing and auto-regressive for different dynamic periods. We also include a version of scheduled sampling (hybrid): in the first 30 time-steps, we train the model with teacher forcing and then switch to auto-regressive in the last 10 time-steps. We observe that while teacher forcing converges faster, it
  leads to lower accuracy. This observation is consistent across different dynamic periods. Therefore, auto-regressive training is preferred for dynamic relation inference.
sections.heading: 4.2 REAL-WORLD BASKETBALL DATA EXPERIMENTS
sections.text: To showcase the practical value of dynamic relational inference, we apply DYARI to a real-world basketball trajectory dataset. The goal of the experiment is to extract meaningful “hidden” relations in competitive basketball plays. The basketball dataset contains trajectories for 10 players in a game. As the ground-truth relations are unknown, we use the trajectory prediction MSE and negative ELBO as in-direct measures for the dynamic relational inference performance. We assume there are two types of hidden relations: coordination and competition. We defer the details of the dataset and training setup to the Appendix.
  We report performance comparisons for different inference periods. As shown in Table 4, we observe lower MSE loss and negative ELBO with shorter inference period. Intuitively, the interactions in the real world may change constantly, thus shorter inference period can capture the dynamics better. DYARI outperforms the baselines in trajectory prediction MSE and negative ELBO loss. Notice that NRI(adaptive) is using encoder and decoder that are trained separately and this results in a high negative ELBO loss on the test set. Fig. 6 visualizes a sample trajectory of 10 basketball players with inferred relations from DYARI over different time steps. We separate coordination and competition interactions in different rows. In Fig. 6, Kobe Bryant is moving along with three-point line and guarded by a defender. We can see clear attention drawn to the specific players throughout the play. See Appendix for other inferred relations.
sections.heading: 5 CONCLUSION
sections.text: We investigate unsupervised learning of dynamic relations in multi-agent trajectories. We propose a novel deep generative model: Dynamic multi-Agent Relational Inference (DYARI) to infer changing relations over time. We conduct extensive experiments using a simulated physics system to study the performance of DYARI in handling various dynamic relations. We perform ablative study to understand the effect of dynamic and inference period, training scheme and model design choice. Compared with static NRI and its variant, our DYARI model demonstrates significant improvement in simulated physics systems as well as in a real-world basketball trajectory dataset.
sections.heading: A MODEL IMPLEMENTATION DETAILS
sections.text: In this section, we include some details about the model implementation, especially the encoder part. Our encoder is analogical to ResNet CNNs (He et al., 2016) used in the field of image recognition, where the task can be abstracted to be a classification problem on 1D dimension. Meanwhile, inspired by PSPNet used in visual scene semantic parsing (Zhao et al., 2017), we add additional 2 global feature extractors to combine the whole-sequence (global) features and the sub-sequence (local) features.
  for DYARI, each residual block shown in Fig. 3 consists of 4 skip connections structure.
sections.heading: B EXPERIMENTAL DETAILS
sections.text: Particle dataset In general, we use the same pre-processing in NRI. Each raw simulated trajectory has length of 5000 and we sample with frequency of 100 so that each sample has length of 50 in our dataset. Correspondingly, the value of dynamic period/inference period matches the length of sample in our dataset. For instance, dynamic period = 10 means that the in the raw trajectory, the state of a node changes every 1000 time steps. In addition, The value of trajectories are all normalized to range of [0, 1] and the evaluation is done on the same range as well.
  Basketball dataset details The basketball dataset consists of trajectory from 30 teams. The raw trajectory is captured with frequency of 25 ms. For our experiment, we sample the trajectory with frequency of 50 ms for more evident player movements. We use a inference period that matches the length of sample. For instance, inference period = 10 means that our model produce prediction every 500 ms. The resulting dataset include 50,000 training samples, 10,000 validations samples and 10,000 test samples.
  We normalize the values of the trajectories to range [0,1] and train all the models in an auto-regressive fashion. We use the same training set up as in physics simulation experiments with a batch size of 64.
sections.heading: C ADDITIONAL EXPERIMENTS
sections.text: Stochastic dynamics In order to make the problem even harder and to unify all the previous settings, we generate a dataset where the edge types are flipped randomly with a probability p after each dynamic period of 4 timesteps. The static data generation corresponds to p = 0 and the periodic dynamics corresponds to p = 1. Table 5 shows the MSE and inference accuracy of NRI, DYARI and Interaction Networks on the stochastic dataset for flipping probabilities p = 0.8 and p = 0.9.
  The Effect of Average Pooling We perform an ablation study where we remove the average pooling corresponding to the inference period in the interpolation module to study the effect of this average pooling on the results. We find that without average pooling, inference accuracy decreases from 0.92 to 0.59 (as shown in Table 6) for inference period at 20. Here we drop the average pooling corresponding to the inference periods and directly interpolate to the sequence length. This shows that intermediate average pooling is critical for the relational inference performance.
  Additional Inferred Relations in Basketball Trajectories We set the number of relations in Basketball dataset as two. In Sec 4.2, we visualized one of the inferred relations. Table 8 visualizes the second relations. Notice that the first relation captures focus on the rightmost red player while here the relation captures focus on the leftmost red player.
title: Neural Relational Inference for Interacting Systems