# GroupNet: Multiscale Hypergraph Neural Networks for
Trajectory Prediction with Relational Reasoning

Chenxin Xu1, Maosen Li1, Zhenyang Ni1, Ya Zhang1,2, Siheng
Chen1,2111Corresponding author.
1Shanghai Jiao Tong University, 2Shanghai AI Laboratory
<EMAIL_ADDRESS>
###### Abstract

Demystifying the interactions among multiple agents from their past
trajectories is fundamental to precise and interpretable trajectory
prediction. However, previous works only consider pair-wise interactions with
limited relational reasoning. To promote more comprehensive interaction
modeling for relational reasoning, we propose GroupNet, a multiscale
hypergraph neural network, which is novel in terms of both interaction
capturing and representation learning. From the aspect of interaction
capturing, we propose a trainable multiscale hypergraph to capture both pair-
wise and group-wise interactions at multiple group sizes. From the aspect of
interaction representation learning, we propose a three-element format that
can be learnt end-to-end and explicitly reason some relational factors
including the interaction strength and category. We apply GroupNet into both
CVAE-based prediction system and previous state-of-the-art prediction systems
for predicting socially plausible trajectories with relational reasoning. To
validate the ability of relational reasoning, we experiment with synthetic
physics simulations to reflect the ability to capture group behaviors, reason
interaction strength and interaction category. To validate the effectiveness
of prediction, we conduct extensive experiments on three real-world trajectory
prediction datasets, including NBA, SDD and ETH-UCY; and we show that with
GroupNet, the CVAE-based prediction system outperforms state-of-the-art
methods. We also show that adding GroupNet will further improve the
performance of previous state-of-the-art prediction systems.

††footnotetext: Code is available at: https://github.com/MediaBrain-
SJTU/GroupNet

##  1 Introduction

Multi-agent trajectory prediction aims to predict future trajectories of
agents conditioned on past movements. This task is not only critical to
numerous real-world applications, such as autonomous driving and human
behavior understanding, but also serves as a foundation to bridge the
knowledge of the past and the action for the future. At least three factors
would affect each agent’s dynamics: ego momentum, instantaneous intent, and
social influence from the other agents. The first factor has been well studied
[36]; the second factor is unpredictable; and the third factor is an emerging
research topic and the focus of this work. To demystify the social influence,
we need to model and reason the interactions among agents based on their past
spatio-temporal states, potentially leading to precise and interpretable
trajectory prediction.

Figure 1: GroupNet captures both pair-wise and group-wise interactions among
multiple agents from their trajectories and infers the interaction category
and strength for each interaction group.

Many works have tried to model the interactions through social operations [1,
13, 43], graph-based modeling [18, 15, 14, 23] and attention mechanism [38,
33, 27]. Although these methods have greatly improved the empirical
performances of trajectory prediction, they underestimate the significance of
relational reasoning. Some previous works, such as NRI [17] and Evolvegraph
[23], took a step forward towards explicit relational reasoning; however, they
still have limitation from two aspects. First, only pair-wise interactions are
modeled. In many scenarios, such as on a basketball court, a group of players
execute a defensive strategy cooperatively; in the ocean, a school of fish
coordinate their movements to evade predators, reflecting collective
behaviors. While this kind of group-wise interaction is common, they have
rarely been modeled. Second, only interaction categories are explicitly
reasoned by the current methods, while the intensity level of the agent
interaction cannot be reflected.

To further promote more comprehensive relational reasoning in trajectory
prediction, this work puts efforts on two aspects: interaction capturing and
interaction representation learning. To capture more interactions, we propose
a multiscale hypergraph, which consists of a series of hypergraphs to model
group-wise interactions with multiple group sizes. Instead of using
handcrafted designs, we learn such a multiscale hypergraph topology in a data-
driven manner. To learn the interaction embedding, we propose a three-element
representation format: the neural interaction strength, the neural interaction
category and the per-category function, which can reflect the interaction
strength and category in an interactive group. Based on neural message passing
over the multiscale hypergraph, we merge this three-element interaction
embedding in the representation learning process.

Overall, we integrate these two designs and propose GroupNet, a multiscale
hypergraph neural network, to capture social interactions for better
trajectory prediction. The proposed GroupNet has two significant advantages:
1) _strong ability of relational reasoning_. Through extensive synthetic
physics experiments, we validate that GroupNet is able to capture group
behaviors, infer interaction strength and interaction category during
trajectory prediction without any relation supervision; and 2) _strong ability
of plug-and-play._ As a general and comprehensive social modeling module,
GroupNet can be easily plugged in a prediction framework and improve its
previous performance. For example, based on a straightforward CVAE-based
framework, GroupNet significantly improves the prediction performance, leading
to competitive or leading results on three real-world prediction benchmarks.
Furthermore, for those current state-of-the-art prediction models, NMMP [14]
on NBA dataset, PECNet [27] on SDD dataset and Trajectron++ [34] on ETH-UCY
datasets, GroupNet brings significant benefit and lifts their results to even
better performances on each dataset. The main contributions of this paper are
summarized as follow:

$\bullet$ We propose GroupNet, a novel multiscale hypergraph neural network to
model complex social influences for better trajectory prediction. GroupNet can
capture both pair-wise and group-wise interactions at various group sizes and
reflect interaction strength and interaction category.

$\bullet$ We validate the relational-reasoning ability of GroupNet via
extensive synthetic simulations and show that GroupNet can capture group
behaviors, interaction strength and interaction category in an unsupervised
setting; see Section 6.2.

$\bullet$ With GroupNet, a simple CVAE-based framework achieves competitive
performances on three real-world prediction benchmarks. We also show many
state-of-the-art prediction systems can be significantly improved by replacing
their social modules with GroupNet; see Section 6.3.

##  2 Related Works

Trajectory prediction. Traditional approaches use hand-crafted rules and
energy potentials [2, 19, 28, 30, 40, 41]. For complex scenes, sequence-to-
sequence models [36, 1] are leveraged to encode trajectories individually.
Recent works model the interactions to predict more social-plausible
trajectories. [7, 8, 46, 3, 6] use a spatial-centric mechanism to represent
trajectories and consider the spatial interaction. [1, 13, 43] use a social
mechanism to aggregate neighboring actors and broadcasts to each actor for
neighboring information diffusion. Besides, attention mechanism [38, 33, 27,
45, 37] and transformer structure [11, 44] are used to capture agents’ spatial
and temporal dependencies. Graph-based methods [42, 18, 15, 14, 23, 29, 24,
10] are proposed to explicitly model the interaction between actors through
non-grid structures. However, previous methods only focus on modeling the
pair-wise interaction, ignoring the group behavior’s influence on agents. In
this work, we extend the graph-based mechanism from ordinary graphs to
multiscale hypergraphs to capture group behaviors at different sizes, thereby
modeling agent interactions more comprehensively.

Relational reasoning. In multi-agent systems, only the trajectories of
individual agents are available without knowledge of the underlying relations,
thus it is challenging to explicitly infer agents’ interaction and make
relational reasoning. Some works attempt to infer the interaction between
agents. NRI [17] infers a latent interaction graph via an autoencoder model.
RAIN [22] also infers an interaction graph using reinforcement learning to
select edges. EvolveGraph [23] and dNRI [12] consider a evolve mechanism and
learn a dynamic interaction graph. Our work also tries on relational reasoning
but the main differences are: i) we capture more interactions including both
group-wise interaction and pair-wise interaction, comparing to only inferring
pair-wise relationship on previous methods; and ii) we infer both interaction
category and interaction strength while previous works only consider the
interaction category.

##  3 Problem Formulation

The task of trajectory prediction with relational reasoning is to predict
future trajectories of multiple agents and infer interaction relationship
given past trajectories. Mathematically, let
$\mathbb{X}^{-}\in\mathbb{R}^{N\times T_{\rm p}\times 2}$ and
$\mathbb{X}^{+}\in\mathbb{R}^{N\times T_{\rm f}\times 2}$ be the past and
future trajectories of all the $N$ agents in the scene. Let
$\mathbf{X}^{-}_{i}=\mathbb{X}^{-}_{i,:,:}=[\mathbf{x}^{-T_{\rm
p}+1}_{i},\mathbf{x}^{-T_{\rm
p}+2}_{i},\cdots,\mathbf{x}^{0}_{i}]\in\mathbb{R}^{T_{\rm p}\times 2}$ and
$\mathbf{X}^{+}_{i}=\mathbb{X}^{+}_{i,:,:}=[\mathbf{x}^{1}_{i},\mathbf{x}^{2}_{i},\cdots,\mathbf{x}^{T_{\rm
f}}_{i}]\in\mathbb{R}^{T_{\rm f}\times 2}$ be the past and future trajectories
of the $i$th agent, where $\mathbf{x}_{i}^{t}\in\mathbb{R}^{2}$ is the 2D
coordinate at time $t$. Our goal is to learn a prediction model $g(\cdot)$, so
that the predicted future trajectories
$\widehat{\mathbb{X}}^{+}=g(\mathbb{X}^{-})$ are as close to the ground-truth
future trajectories $\mathbb{X}^{+}$ as possible. When a prediction model
$g(\cdot)$ is capable to infer social influences among the agents without any
ground-truth supervision about interaction category or strength, this
supplementary task is called  _unsupervised relational reasoning_.

Figure 2: The architecture of GroupNet. GroupNet has two stages: multiscale
hypergraph topology inference and multiscale hypergraph neural message
passing, where we infer the hypergraph topologies and capture the agent
patterns with their interaction, respectively. In multiscale hypergraph neural
message passing, we model the interaction as three elements to reflect
physical intuition and interpretation.

##  4 GroupNet

The core of GroupNet is to learn a multiscale hypergraph whose node is the
agent and hyperedge is the interaction; and then, leverage this multiscale
hypergraph to learn agent and interaction embedding.

###  4.1 Multiscale hypergraph topology inference

To comprehensively model group-wise interactions at multiple scales, we
consider inferring a multiscale hypergraph from agent dynamics to reflect
interactions at various group sizes; see Figure 2. Mathematically, let
$\mathcal{V}=\\{v_{1},v_{2},\cdots,v_{N}\\}$ be a set of agents and
$\mathcal{G}=\\{\mathcal{G}^{(0)},\mathcal{G}^{(1)},...\mathcal{G}^{(S)}\\}$
be a multiscale hypergraph showing the agent connections. At any scale $s$,
$\mathcal{G}^{(s)}=(\mathcal{V},\mathcal{E}^{(s)})$ has the hyperedge set
$\mathcal{E}^{(s)}=\\{e^{(s)}_{1},e^{(s)}_{2},\cdots,e^{(s)}_{M_{s}}\\}$ to
represent group-wise relations with $M_{s}$ hyperedges, each of which links a
number of agents to represent the common relations. A larger $s$ indicates a
larger scale of agent groups. Notably,
$\mathcal{G}^{(0)}=(\mathcal{V},\mathcal{E}^{(0)})$ is a specific hypergraph
whose edges model the finest pair-wise agent connections. The topology of each
$\mathcal{G}^{(s)}$ can be represented as an incidence matrix
$\mathbf{H}^{(s)}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{E}^{(s)}|}$ where
$\mathbf{H}^{(s)}_{i,j}=1$ if the $i$th node is included in the $j$th
hyperedge, otherwise $\mathbf{H}^{(s)}_{i,j}=0$.

Affinity modeling. The trajectory interactions are in a stealth mode and
nontrivial to capture since there are no explicitly predefined graph topology
for relation description. To infer a multiscale hypergraph, we construct
hyperedges by grouping agents that have highly correlated trajectories, whose
correlations could be measured by mapping the trajectories as a high-
dimensional feature vector. Concretely, the trajectory embedding of the $i$th
agent is
$\mathbf{q}_{i}=f_{\mathrm{Q}}({\mathbf{X}^{-}_{i}})\in\mathbb{R}^{d},$ where
$f_{\mathrm{Q}}(\cdot)$ can be a MLP. We then compute an affinity matrix
$\mathbf{A}\in\mathbb{R}^{N\times N}$ to reflect the correlation of any two
agents. The $(i,j)$th element of $\mathbf{A}$ is:

$\mathbf{A}_{i,j}\ =\
\mathbf{q}_{i}^{\top}\mathbf{q}_{j}/(\|\mathbf{q}_{i}\|_{2}\|\mathbf{q}_{j}\|_{2}),$
(1)

which represents the relational weight of the $i$th agent and the $j$th agent
reflecting the correlation between two agents. We normalize the embeddings to
ensure the trajectory representations to carry unit energy for stable relation
estimation.

Hyperedge forming. Given the affinity matrix, we then form hyperedges at
various scales. At the $0$th scale, we consider pair-wise connections. Each
node connects the nodes that have the largest affinity scores with it, leading
to $M_{0}$ edges in the incident matrix $\mathbf{H}^{(0)}$. For the other
scales, we consider group-wise connections. Intuitively, agents in a group
should have high correlation with each other. We thus find the groups of nodes
by looking for high-density submatrices in the affinity matrix $\mathbf{A}$.
We first assign a sequence of increasing group sizes
$\\{K^{(s)}\\}_{s=1}^{S}$; and then, for each node, we find a highly
correlated group at any scale $s$, leading to $K^{(s)}$ groups/hyperedges in
each scale. Mathematically, let the $i$th hyperedge $e^{(s)}_{i}$ at the $s$th
scale be the one associated with the $i$th node $v_{i}$. This hyperedge is
obtained by solving the following optimization problem of searching a
$K^{(s)}\times K^{(s)}$ submatrix:

$\displaystyle
e^{(s)}_{i}=\arg\mathop{\operatorname{max}}\limits_{\Omega\subseteq\mathcal{V}}\left\|\mathbf{A}_{\Omega,\Omega}\right\|_{\mathrm{1},\mathrm{1}},$
(2)
$\displaystyle\mathrm{s.t.}\;|\Omega|=K^{(s)},~{}v_{i}\in\Omega,~{}i=1,\dots,N,$

where the entrywise matrix norm $\|\cdot\|_{\mathrm{1},\mathrm{1}}$ denotes
the sum of the absolute values of all elements. The objective finds the most
correlated agents and links them together to consider the group behaviors. The
first constraint limits the group size and the second requires the
participance of the $i$th node. In this way, we could form at least one
hyperedge that belongs to each node at each scale. To solve the optimization
(2), when the total number of agents is small, we could adopt an enumeration
algorithm to search for the optimum solution; otherwise, we employ a greedy
algorithm approximation that first selects $v_{i}$ and then adds new nodes of
maximum affinity value with $v_{i}$ at each move sequentially.

The incidence matrices for a multiscale hypergraph are thus
$\\{\mathbf{H}^{(0)}\in\mathbb{R}^{N\times
NK^{(0)}},\\{\mathbf{H}^{(s)}\in\mathbb{R}^{N\times N}\\}_{s=1}^{S}\\}$, where
$\mathbf{H}^{(0)}$ includes $NK^{(0)}$ edges to consider the pair-wise
interactions and $\mathbf{H}^{(s)}(s\geq 1)$ includes $N$ hyperedges to
reflect the group-wise interactions within $K^{(s)}$ agents. Different from
the common multiscale graph whose node numbers vary from scales [25, 9], our
multiscale hypergraph has fixed node numbers, yet different hyperedge sizes on
various scales. Note that all the edges and hyperedges are selected based on
the same affinity matrix. This design brings two benefits: i) it is
computationally efficient to search for high-order relationships from a single
matrix; and ii) it makes the training of the affinity matrix more stable and
informative through back-propagation.

Compared to [17, 14, 23], our topology inference method is novel from two
aspects. First, our method actively infers a graph structure through learning;
while many previous methods directly adopt a fixed fully-connected topology.
Second, our method models both pair-wise and group-wise connections at
multiple scales; while the previous methods only model the pair-wise
connections at a single scale.

###  4.2 Multiscale hypergraph neural message passing

To learn the patterns of agents trajectories given the inferred multiscale
hypergraph, we customize a multiscale hypergraph neural message passing method
obtaining the embeddings of agents and interactions iteratively through node-
to-hyperedge and hyperedge-to-node, see Figure 2. Specifically, we first
initialize the agent embedding from trajectory of each agent; that is, at any
scale, for the $i$th agent, $v_{i}$, its initial embedding is
$\mathbf{v}_{i}=\mathbf{q}_{i}\in\mathbb{R}^{d}$ (see Sec. 4.1). At each
scale, in the node-to-hyperedge phase, groups of agent embeddings are
aggregated to get the interaction embeddings. In the hyperedge-to-node phase,
each agent embedding is updated according to associated interaction
embeddings. We execute the node-to-hyperedge and hyperedge-to-node for several
iterations. We finally obtain the representation of each agent by fusing its
embeddings across all the scales.

Node-to-hyperedge phase. To promote a representation for relational reasoning,
we exhibit an interaction embedding with three elements: neural interaction
strength, representing the intensity of the interaction, neural interaction
category, reflecting agents interaction category, and per-category function,
modeling how interaction process of this category works. At each scale of
hypergraph, for the $i$th hyperedge, $e_{i}$, its interaction embedding is
obtained through

$\mathbf{e}_{i}=r_{i}\sum\limits_{\ell=1}^{L}c_{i,\ell}\mathcal{F}_{\ell}\Big{(}\sum\limits_{v_{j}\in
e_{i}}\mathbf{v}_{j}\Big{)}\in\mathbb{R}^{d},$ (3)

where $r_{i}$ is its neural interaction strength. $c_{i,\ell}$, the $\ell$th
element of a category vector ${\bf c}_{i}\in[0,1]^{L}$, denotes the
probability of the $\ell$th neural interaction category within $L$ possible
categories. For each category, we assign a learnable category function
$\mathcal{F}_{\ell}(\cdot)$ implemented by MLPs. Each of these three elements
is trainable in an end-to-end framework.

To obtain the neural interaction strength $r_{i}$, and neural interaction
category ${\bf c}_{i}$, we leverage a collective embedding that is a hidden
state to reflect the overall information of agents in a group. For hypergraph
at any scale, the collective embedding of $e_{i}$ is obtained by the weighted
sum of all the agent embedding associated with the hyperedge $e_{i}$; that is,
$\mathbf{z}_{i}=\sum\limits_{v_{j}\in e_{i}}w_{j}\mathbf{v}_{j}$, where
$w_{j}=\mathcal{F}_{\rm w}\Big{(}\mathbf{v}_{j},\sum\limits_{v_{m}\in
e_{i}}\mathbf{v}_{m}\Big{)},$ with $\mathcal{F}_{\rm w}(\cdot)$ implemented by
an MLP. The weight $w_{j}$ reflects the contribution of the $j$th node to the
$i$th group. We then use the collective embedding to infer the neural
interaction strength, $r_{i}$, and the neural interaction category, ${\bf
c}_{i}$; that is,

$r_{i}=\sigma\left(\mathcal{F}_{\rm
r}(\mathbf{z}_{i})\right),~{}~{}\mathbf{c}_{i}=\mathrm{softmax}\left((\mathcal{F}_{\rm
c}(\mathbf{z}_{i})+\mathbf{g})/{\tau}\right),$

where $\sigma(\cdot)$ is a sigmoid function to constrain the strength values,
$\mathbf{g}$ is a vector whose elements are i.i.d. sampled from
$\mathrm{Gumbel}(0,1)$ distribution and $\tau$ is the temperature controlling
the smoothness of type distribution. We use the Gumbel softmax to make a
continuous approximation of the discrete distribution following [26].
$\mathcal{F}_{\rm r}(\cdot)$ and $\mathcal{F}_{\rm c}(\cdot)$ are modeled by
MLPs. The inference of the neural interaction strength, neural interaction
category and per-category function considers the group behavior through the
shared collective embedding.

Figure 3: The architecture of the trajectory prediction system. The system
consists of two processes: the encoding process (orange part) and the decoding
process (blue part). Encoding process obtains the hidden representation for
each agent. Decoding process aims to both predict the future trajectory and
reconstruct the past trajectory given the hidden representation and past
trajectory of each agent.

Hyperedge-to-node phase. Given the interaction embeddings learnt from groups
of agents, we then update each agent embedding by considering all the
associated interactions. For any scale of hypergraph, let
$\mathcal{E}_{i}=\\{e_{j}|v_{i}\in e_{j}\\}$ be the set of hyperedges
associated with the $i$th node $v_{i}$. The embedding of the $i$th agent in
the next iteration is updated as

$\mathbf{v}_{i}\leftarrow f_{\rm
v}\big{(}\big{[}\mathbf{v}_{i},\sum\limits_{e_{j}\in\mathcal{E}_{i}}\mathbf{e}_{j}\big{]}\big{)}\in\mathbb{R}^{d},$

where $f_{\rm v}(\cdot)$ is a trainable MLP; $[\cdot,\cdot]$ denotes the
embedding concatenation of one node and the associated hyperedges to absorb
the influence from interactions to an agent.

At any scale $s$, we repeat the node-to-hyperedge and hyperedge-to-node phases
for several times and obtain the embedding of the $i$th node,
$\mathbf{v}_{i}^{(s)}$. In this way, we compute the embeddings of the $i$th
node, $\mathbf{v}_{i}^{(0)},\mathbf{v}_{i}^{(1)}\dots,\mathbf{v}_{i}^{(S)}$,
across $S$ scales in parallel. Note that the trainable layers in various
scales are NOT shared. We finally concatenate the agent embedding across all
the scales to obtain the comprehensive agents’ embedding, formulated as
$\mathbf{v}_{i}=[\mathbf{v}^{(0)}_{i},\mathbf{v}^{(1)}_{i},\cdots,\mathbf{v}^{(S)}_{i}]\in\mathbb{R}^{d(S+1)}$.

Compared to previous methods NRI [17], dNRI [12], and EvolveGraph [23], which
achieve relational reasoning using neural message passing, the proposed
hypergraph neural message passing is novel from three aspects. First, previous
[17, 12, 23] adopt neural message passing on ordinary graphs; while we
consider neural message passing on a series of hypergraphs, promoting more
comprehensive information propagation and aggregation. Second, previous [17,
12, 23] only infer the interaction category; while our method can infer both
interaction category and strength through a three-element representation
format. Third, the interaction category inferred by previous [17, 12, 23] is
the final output after message passing; while the interaction category and
strength inferred by our method are the intermediate features that involve in
neural message passing. Our design not only promotes relational reasoning in
neural message passing, but also improves the prediction performance.

##  5 Prediction System with GroupNet

We apply GroupNet into a basic multi-agent trajectory prediction system based
on the CVAE framework [35] to handle the stochasticity of each agent’s
behavior. Let $\log p(\mathbb{X}^{+}\mid\mathbb{X}^{-})$ be the log-likelihood
of future trajectories $\mathbb{X}^{+}$ conditioned on the past trajectories
$\mathbb{X}^{-}$. The corresponding evidence lower bound (ELBO) is:

$\displaystyle\operatorname{log}p(\mathbb{X}^{+}\mid\mathbb{X}^{-})\geq$
$\displaystyle\;\mathbb{E}_{q(\mathbf{Z}\mid\mathbb{X}^{+},\mathbb{X}^{-})}\operatorname{log}p(\mathbb{X}^{+}\mid\mathbf{Z},\mathbb{X}^{-})$
$\displaystyle-\operatorname{KL}(q(\mathbf{Z}\mid\mathbb{X}^{+},\mathbb{X}^{-})\|p(\mathbf{Z}\mid\mathbb{X}^{-})),$

where $\mathbf{Z}\in\mathbb{R}^{N\times d_{z}}$ is the latent codes
corresponding to all the agents; $p(\mathbf{Z}|\mathbb{X}^{-})$ is the
conditional prior of $\mathbf{Z}$, which is set to be a Gaussian distribution.
Here we implement $q(\mathbf{Z}|\mathbb{X}^{+},\mathbb{X}^{-})$ by an encoding
process for embedding learning, and implement
$p(\mathbb{X}^{+}|\mathbf{Z},\mathbb{X}^{-})$ by a decoding process that
predicts the future $\mathbb{X}^{+}$. The system is sketched in Figure 3.

Encoding process. The encoding process aims to generate the Gaussian
parameters of the approximate posterior distribution. Mathematically, the
Gaussian parameters generation of the approximate posterior distribution and
the conditional prior distribution is given by:

$\displaystyle\mathbf{V}^{+}\ =\
\mathcal{M}_{\mathrm{f}}(\mathbb{X}^{+}),\quad\mathbf{V}^{-}=\mathcal{M}_{\mathrm{p}}(\mathbb{X}^{-}),$
$\displaystyle\bm{\mu}_{q}=\mathcal{F}_{\mathrm{\mu}}([\mathbf{V}^{+},\mathbf{V}^{-}]),\quad\bm{\sigma}_{q}=\mathcal{F}_{\mathrm{\sigma}}([\mathbf{V}^{+},\mathbf{V}^{-}]),$

where $\mathcal{M}_{\mathrm{f}}(\cdot)$ and $\mathcal{M}_{\mathrm{p}}(\cdot)$
is aforementioned GroupNet to get future agent embedding $\mathbf{V}^{+}$ and
past agent embedding $\mathbf{V}^{-}$. $\bm{\mu}_{q}$, $\bm{\sigma}_{q}$ are
the mean and variation of the approximate posterior distribution.
$\mathcal{F}_{\mathrm{\mu}}(\cdot)$, $\mathcal{F}_{\mathrm{\sigma}}(\cdot)$
are MLPs. We sample latent code of possible future trajectories
$\mathbf{Z}\sim\mathcal{N}(\bm{\mu}_{q},\operatorname{Diag}(\bm{\sigma}_{q}^{2}))$.
In the testing phase, we sample $\mathbf{Z}$ from the prior distribution
$\mathcal{N}(0,\lambda\mathbf{I})$, where $\lambda$ is a hyperparameter. We
concatenate the latent code $\mathbf{Z}$ with the embedding of agent past
trajectories $\mathbf{V}^{\mathrm{-}}$ as the output of encoding process:
$\mathbf{V}^{\mathrm{out}}=[\mathbf{Z},\mathbf{V}^{\mathrm{-}}]$.

Decoding process. We apply a residual decoder similar with [5] which takes
both the output embedding of the encoding process and past trajectories as
input. The residual decoder aims to both predict the future trajectories and
reconstruct the past trajectories, which avoids input information loss. The
residual decoder consists of two decoding blocks with the same structure.
Mathematically, the calculation of the two blocks
$\mathcal{F}_{Block1}(\cdot)$, $\mathcal{F}_{Block2}(\cdot)$ are:

$\displaystyle\widehat{\mathbb{X}}^{+}_{1},\widehat{\mathbb{X}}^{-}_{1}=\mathcal{F}_{Block1}(\mathbf{V}^{out},\mathbb{X}^{-}),$
$\displaystyle\widehat{\mathbb{X}}^{+}_{2},\widehat{\mathbb{X}}^{-}_{2}=\mathcal{F}_{Block2}(\mathbf{V}^{out},\mathbb{X}^{-}-\widehat{\mathbb{X}}^{-}_{1}),$

where $\widehat{\mathbb{X}}^{+}_{1}$, $\widehat{\mathbb{X}}^{+}_{2}$ and
$\widehat{\mathbb{X}}^{-}_{1}$, $\widehat{\mathbb{X}}^{-}_{2}$ are predicted
future trajectories and reconstructed past trajectories of two blocks. Each
block consists of a GRU encoder to encode the sequence and two MLPs as the
output header. The final prediction of future trajectories
$\widehat{\mathbb{X}}^{+}$ and reconstruction of past trajectories
$\widehat{\mathbb{X}}^{-}$ is the sum of two decoding blocks:

$\displaystyle\widehat{\mathbb{X}}^{+}=\widehat{\mathbb{X}}^{+}_{1}+\widehat{\mathbb{X}}^{+}_{2},\quad\widehat{\mathbb{X}}^{-}=\widehat{\mathbb{X}}^{-}_{1}+\widehat{\mathbb{X}}^{-}_{2}.$

Loss function. To train the prediction system, we minimize an overall loss
function formed by an evidence lower bound loss, a past trajectory
reconstruction loss and a variety loss in Social-GAN [13] to optimize the
“best” prediction:

$\displaystyle\mathcal{L}_{\mathrm{elbo}}=\alpha\|\widehat{\mathbb{X}}^{+}-\mathbb{X}^{+}\|_{2}^{2}+\beta\operatorname{KL}(\mathcal{N}(\bm{\mu}_{q},\operatorname{Diag}(\bm{\sigma}_{q}^{2})\|\mathcal{N}(0,\lambda\mathbf{I})),$
$\displaystyle\mathcal{L}_{\mathrm{rec}}=\gamma\|\widehat{\mathbb{X}}^{-}-\mathbb{X}^{-}\|_{2}^{2},\mathcal{L}_{\mathrm{variety}}=\mathop{min}\limits_{k}\|\widehat{\mathbb{X}}^{+(k)}-\mathbb{X}^{+}\|_{2}^{2},$
$\displaystyle\mathcal{L}=\mathcal{L}_{\mathrm{elbo}}+\mathcal{L}_{\mathrm{rec}}+\mathcal{L}_{\mathrm{variety}},$

where $\alpha$, $\beta$ and $\gamma$ are hyperparameters to control the
weights, $\|\cdot\|_{2}$ denotes the $\ell_{2}$ norm and
$\operatorname{KL}(\cdot||\cdot)$ denotes the KL divergence. In the variety
loss, we predict multiple times and $\widehat{\mathbb{X}}^{+(k)}$ denotes
$k$th prediction results.

##  6 Experiments and Analysis

###  6.1 Experimental setup

Datasets. We evaluate our method on both physical simulation datasets and
three real-world public datasets: the NBA SportVU Dataset (NBA), the ETH-UCY
Dataset [31, 21], and the Stanford Drone Dataset (SDD) [32]. For the physical
simulation datasets, since the ground truth of the interaction relationship
can be accessed, we evaluate the ability of relational reasoning of our
GroupNet. For the real-world datasets we evaluate the effectiveness of our
proposed GroupNet. More details of datasets are introduced in Appendix.

Metrics. Following [23, 1, 20], we use $\mathrm{minADE}_{K}$ and
$\mathrm{minFDE}_{K}$ as evaluation metrics. $\mathrm{minADE}_{K}$ is the
minimum among $K$ average distances of the $K$ predicted trajectories to the
ground-truths in terms of the whole trajectories; $\mathrm{minFDE}_{K}$ shows
the minimum distance among $K$ predicted endpoints to the ground-truth
endpoints.

Implementation details. In our model, all the MLPs have 3 layers with the ReLU
activation function. The latent code dimension $d_{z}$ is 32. In the loss
function, we set $\alpha,\beta,\gamma$ to 1.0 and the variance of the prior
distribution $\lambda=1.0$. We consider all other agent at the $0$th scale.
For NBA dataset, we set the scale to 2,5,11 players. For ETH dataset, we set
the group scales to the half and the full of agents number and for SDD dataset
to full of agent number in less than 100 pixels distance. To train the model,
we apply Adam optimizer [16] with learning rate $10^{-4}$ and decay every 10
epochs. See more details in Appendix.

###  6.2 Validation on relational reasoning

Ability to capture group behaviors. We consider six particles forming two
scales of groups: the Y-shape light bar and the spring; see Figure 4 (a) for
an example. During the prediction process, GroupNet aims to find the group
belongingness. Figure 4 (b) shows the learnt affinity matrix in (1), where a
darker color denotes higher affinity, which is revealed between the particles
connected by the light bar or spring. Figure 4 (c) illustrates the inferred
(hyper)edges and their interaction categories (the category number is set to
be 2). We see that i) the edge of spring and the hyperedge of light bar are
inferred on our multiscale hypergraph
$\\{\mathcal{G}^{(0)},\mathcal{G}^{(1)}\\}$. ii) the spring and light bar have
different interaction categories from other hyperedges, indicating that we
effectively capture these two group interactions.

((a))

((b))

((c))

Figure 4: Visualization of learnt group behavior. (a) The particle
trajectories containing a three-group with a light bar, a two-group with a
spring and an individual particle. (b) The heatmap of the learnt affinity
matrix via affinity modeling. (c) The multiscale hypergraph topology via
hyperedge forming and the interaction category vector of each hyperedge. The
red box represents the three-group and two-group we inferred.

((a))

((b))

((c))

Figure 5: Trajectory samples under three interaction categories. Table 1: Comparison of accuracy (mean $\pm$ std in %) of on interaction category recognition. | Corr.(path) | Corr.(LSTM) | NRI | Ours | Supervised
---|---|---|---|---|---
2-types |  78.3$\pm$0.0 |  75.3$\pm$2.5 |  89.7$\pm$3.5 |  99.3$\pm$0.3 |  99.5$\pm$0.2
3-types | – | – |  64.9$\pm$2.3 |  90.3$\pm$0.9 |  98.7$\pm$0.7

Ability to reason interaction category. We consider three particles forming
one group with three possible interaction categories: free, spring and light
bar. Figure 5 gives examples of each interaction type. We compare the neural
interaction category in (3) with the ground-truth category to achieve
interaction recognition and report the recognition accuracy. This category
recognition is unsupervised because the model only accesses the trajectories
of particles without any prior information about the three types of
interaction. We compare our method with three baselines [17] which consider
only pair-wise interactions and an upper bound. To adapt them to group-wise
actions, we use a majority vote for all pair-wise edges. The upper bound
‘Supervised’ represents using the ground-truth category to train the neural
interaction category. Table 1 reports the recognition accuracy on 2-type (only
free and light bar type) and 3-type recognition tasks, which are averaged over
5 independent runs. ‘–’ represents not applicable. We see that i) our method
significantly outperforms three baselines, as we model the group interaction
while NRI only considers pair-wise interaction; and ii) our method achieves
similar performance to the upper bound, reflecting that our method is capable
to reason the interaction category in an unsupervised manner.

Table 2: minADE20 / minFDE20 (meters) of trajectory prediction (NBA dataset).
$*$ denotes that NMMP is the previous best model on this dataset. With
GroupNet, NMMP works even much better. Simple CVAE with GroupNet achieves the
current best result.

Time |  Social -LSTM[1] |  Social -GAN[13] |  Social- STGCNN[29] |  STGAT [15] |  NRI [17] |  STAR [44] |  PECNet [27] |  NMMP* [14] |  GroupNet +NMMP |  CVAE |  GroupNet +CVAE
---|---|---|---|---|---|---|---|---|---|---|---
1.0s | 0.45/0.67 | 0.46/0.65 | 0.36/0.50 | 0.38/0.55 | 0.45/0.64 | 0.43/0.65 | 0.51/0.76 | 0.38/0.54 | 0.38/0.54 | 0.37/0.52 |  0.34/0.48
2.0s | 0.88/1.53 | 0.85/1.36 | 0.75/0.99 | 0.73/1.18 | 0.84/1.44 | 0.77/1.28 | 0.96/1.69 | 0.70/1.11 | 0.69/1.08 | 0.67/1.06 |  0.62/0.95
3.0s | 1.33/2.38 | 1.24/1.98 | 1.15/1.79 | 1.07/1.74 | 1.24/2.18 | 1.00/1.55 | 1.41/2.52 | 1.01/1.61 | 0.98/1.47 | 0.96/1.51 |  0.87/1.31
4.0s | 1.79/3.16 | 1.62/2.51 | 1.59/2.37 | 1.41/2.22 | 1.62/2.84 | 1.26/2.04 | 1.83/3.41 | 1.33/2.05 | 1.25/1.80 | 1.25/1.96 |  1.13/1.69

Table 3: minADE20 / minFDE20 (pixels) of trajectory prediction (SDD dataset).
$*$ denotes that PECNet is the previous best model on this dataset. With
GroupNet, PECNet works even better. Simple CVAE with GroupNet achieves the
current best ADE result.

Time |  Social- LSTM[1] |  Social -GAN[13] |  SOPHIE [33] |  Trajectron++ [34] |  NMMP[14] |  EvolveGraph [23] |  CF-VAE [4] |  PECNet* [27] |  GroupNet +PECNet | CVAE |  GroupNet +CVAE
---|---|---|---|---|---|---|---|---|---|---|---
4.8s | 31.19/56.97 | 27.23/41.44 | 16.27/29.38 | 19.30/32.70 | 14.67/26.72 | 13.90/22.90 | 12.60/22.30 | 9.96/15.88 |  9.65/15.34 | 10.22/18.18 |  9.31/16.11

Table 4: minADE20 / minFDE20 (meters) of trajectory prediction (ETH-UCY
dataset). $*$ denotes that Trajectron++ is the previous best model on this
dataset. With GroupNet, Trajectron++ works even better. Simple CVAE with
GroupNet achieves comparable results.

Subset |  Social- LSTM[1] |  Social- Attention[38] |  Social- GAN[13] |  SOPHIE [33] |  STGAT [15] | NMMP[14] | STAR[44] |  PECNet [27] |  Trajectron++* [34] |  GroupNet +Trajectron++ | CVAE |  GroupNet +CVAE
---|---|---|---|---|---|---|---|---|---|---|---|---
ETH | 1.09/2.35 | 1.39/2.39 | 0.87/1.62 | 0.70/1.43 | 0.65/1.12 | 0.61/1.08 |  0.36/0.65 | 0.54/0.87 | 0.39/0.83 | 0.38/0.74 | 0.47/0.80 | 0.46/0.73
HOTEL | 0.79/1.76 | 2.51/2.91 | 0.67/1.37 | 0.76/1.67 | 0.35/0.66 | 0.33/0.63 | 0.17/0.36 | 0.18/0.24 | 0.12/0.21 |  0.11/0.20 | 0.17/0.31 | 0.15/0.25
UNIV | 0.67/1.40 | 1.25/2.54 | 0.76/1.52 | 0.54/1.24 | 0.52/1.10 | 0.52/1.11 | 0.31/0.62 | 0.35/0.60 | 0.20/0.44 |  0.19/0.40 | 0.28/0.52 | 0.26/0.49
ZARA1 | 0.47/1.00 | 1.01/2.17 | 0.35/0.68 | 0.30/0.63 | 0.34/0.69 | 0.32/0.66 | 0.26/0.55 | 0.22/0.39 | 0.15/0.33 |  0.14/0.32 | 0.25/0.49 | 0.21/0.39
ZARA2 | 0.56/1.17 | 0.88/1.75 | 0.42/0.84 | 0.38/0.78 | 0.29/0.60 | 0.43/0.85 | 0.22/0.46 | 0.17/0.30 |  0.11/0.25 |  0.11/0.25 | 0.21/0.40 | 0.17/0.33
AVG | 0.72/1.54 | 1.41/2.35 | 0.61/1.21 | 0.54/1.15 | 0.43/0.83 | 0.41/0.82 | 0.26/0.53 | 0.29/0.48 |  0.19/0.41 |  0.19/0.38 | 0.28/0.50 | 0.25/0.44

Ability to reason interaction strength. We consider the movement of two
charged particles which interact via Coulomb forces. Figure 6 shows two
examples of particle trajectories. A stronger repulsion the moving particle
receives leading to a higher interaction strength. During the prediction we
aim to validate whether the neural interaction strength in (3) can reflect the
amount of charge without any direct supervision. Figure 6 (c) shows the
relations between the learnt interaction strength ($x$-axis) and charge on the
fixed particle ($y$-axis). We see that the neural interaction strength has a
proportional relationship with the amount of charge, reflecting our model is
capable to implicitly capture the interaction strength in an unsupervised
manner.

((a))

((b))

((c))

Figure 6: Particles’ trajectories and the curve of neural interaction strength
with particle’s electric charge.

###  6.3 Validation on effectiveness

NBA dataset. We predict the future 10 timestamps (4.0s) based on the
historical 5 timestamps (2.0s). Table 2 shows the comparison with nine state-
of-the-art methods. We see that i) GroupNet with CVAE framework achieves a
significant improvement over the state-of-the-art methods: the
$\mathrm{minADE_{20}}$ and $\mathrm{minFDE_{20}}$ at 4.0s is reduced by
$15.0\%/17.6\%$ comparing to the best baseline method (NMMP). The improvement
over previous methods increases with timestamps, since the proposed multiscale
hypergraph can capture more comprehensive interaction patterns and ii) We add
GroupNet into previous the state-of-the-art method and replace its encoder
(GroupNet+NMMP). Our GroupNet improve its performance by reducing
$\mathrm{minADE_{20}}/\mathrm{minFDE_{20}}$ at 4.0s by $6.0\%/12.2\%$.

SDD dataset. Table 3 compares the proposed method with nine state-of-the-art
methods. We see that i) GroupNet with CVAE framework achieves state-of-the-art
performance and reduces the $\mathrm{minADE_{20}}$ by $6.5\%$ comparing to
PECNet. ii) We add GroupNet into the previous best framework and replace its
Social Pooling encoder (GroupNet+PECNet). Our GroupNet is capable to improve
its performance by reducing $\mathrm{minADE_{20}}/\mathrm{minFDE_{20}}$ by
$3.1\%/3.4\%$.

ETH-UCY dataset. Table 4 compares the proposed method with nine state-of-the-
art methods and the ‘AVG’ means the averaged result over 5 subsets. We see
that i) GroupNet with CVAE framework outperforms most of previous methods and
achieves closing performance with the state-of-the-art method (Trajectron++);
and ii) We add GroupNet into previous the state-of-the-art method and replace
its encoder (GroupNet+Trajectron++). Our GroupNet is capable to improve its
performance by reducing $\mathrm{minFDE_{20}}$ by $7.3\%$ and reaches a new
state-of-the-art performance.

((a))

((b))

((c))

Figure 7: Qualitative results on the NBA dataset. We plot the best trajectory
among 20 predictions for the state-of-the-art method (NMMP), GroupNet with the
CVAE framework (Ours) and ground truth (GT). The red/blue color represents
players of two teams and the green color represents the basketball. Light
color represents the past trajectory.

Discussion. We see that previously, NMMP, PECNet and Trajctron++ are the best
models on NBA, SDD and ETH-UCY datasets, respectively, and no single method
achieves the best performances across all three datasets.  _Here we analyze
that this phenomenon may result from the inherence of the datasets._ In SDD,
there are relatively smooth trajectories and simple interactions among agents.
Hence, once a specific destination is given, the predictions tend to be
straightforward. This enables PECNet that emphasize accurate destinations
prediction to achieve good results. Opposite to SDD, the NBA dataset entails
much more complex agent interactions. Methods that pay more attention to
interaction modeling would suit NBA setting well. For example, NMMP and STAR
achieve leading performances on NBA. Lastly, ETH-UCY contains five subsets,
each of which varies from each other. This matches Trajectron++ that
incorporates multi-modal decoders to promote generalization.

Under this circumstance, our GroupNet shows commendable consistency: across
all the datasets and methods, _once GroupNet is plugged in to a prediction
system, the performance can be significantly and consistently lifted up._ This
reflects the robustness and generalization of our method.

Table 5: Ablation studies of different feature extraction modules on the NBA dataset. We report minADE20 / minFDE20 (meters).  Module | Prediction time
---|---
$\mathcal{M_{\mathrm{p}}}$ & $\mathcal{M_{\mathrm{f}}}$ | 1.0s | 2.0s | 3.0s | 4.0s
MLP | 0.37/0.52 | 0.67/1.06 | 0.96/1.51 | 1.25/1.96
NMMP | 0.35/0.49 | 0.63/0.97 | 0.90/1.36 | 1.17/1.76
ATT | 0.35/0.50 | 0.63/0.97 | 0.90/1.35 | 1.16/1.74
GroupNet |  0.34/0.48 |  0.62/0.95 |  0.87/1.31 |  1.13/1.69

Qualitative results. Figure 7 compares the predicted trajectories of NMMP,
GroupNet with the CVAE framework (Ours) and ground-truth (GT) trajectories on
NBA dataset. We see that i) our method produces more precise predictions than
previous state-of-the art method NMMP; and ii) for the scenes of fierce
confrontation between two teams (the second row), our method has a larger
improvement. This is because the proposed method captures more comprehensive
interactions among players in complicated scenes.

Table 6: minADE20 / minFDE20 (meters) of different group scales on NBA dataset. | Prediction time
---|---
Scale | 1.0s | 2.0s | 3.0s | 4.0s
1 | 0.37/0.52 | 0.67/1.05 | 0.97/1.50 | 1.27/1.95
1,2 | 0.35/0.49 | 0.63/0.97 | 0.89/1.35 | 1.16/1.75
1,2,5 | 0.35/0.49 | 0.62/0.95 | 0.88/1.32 | 1.14/1.71
1,2,5,11 | 0.34/0.48 | 0.62/0.95 | 0.87/1.31 | 1.13/1.69
1,2,3,5,11 | 0.34/0.48 | 0.62/0.94 | 0.87/1.31 | 1.13/1.70

###  6.4 Ablation studies

Effects of GroupNet in the system. We perform extensive ablation studies on
the NBA dataset to investigate the contribution of the key technical component
GroupNet;see Table 5. We apply three other feature extraction modules. The
‘MLP’ means that we use a multi-layer perceptron. The ‘ATT’ amd ‘NMMP’ means
that using the non-local attention mechanism in [39] and using the graph
neural message passing in [14] which models the pair-wise interactions between
two agents. We see that the proposed GroupNet leads to superior performance
comparing to the multi-layer perceptron, the attention mechanism and the
graph-based mechanism.

Effects of multiple scales. Table 6 presents the effect of multiple scales in
the GroupNet on the CVAE framework on the NBA dataset. We see that i) The
performance increases at first when choosing more scales. ii) The performance
becomes stable when having sufficient scales.

##  7 Conclusion

This paper proposes GroupNet, which promotes a more comprehensive interaction
modeling from two aspects: i) designing a multiscale hypergraph to capture
both pair-wise and group-wise interactions; and ii) designing a three-element
representation format of interaction embedding, including neural interaction
strength, category and per-category function. We apply the proposed GroupNet
as a key component to a CVAE-based prediction system and previous systems.
Experiments on synthetic physics simulations and real-world datasets reveal
the ability of relational reasoning and the effectiveness of GoupNet.

Limitation and future work. In this work, the agent number is relatively small
and the time window is relatively short due to the attribute of datasets. In
the future, we will extend the network into more complex interacting systems
and explore the long-term prediction task containing a time-varying number of
agents with an adaptive GNN.

## Acknowledgements

This research is partially supported by the National Key R&D Program of China
under Grant 2021ZD0112801, National Natural Science Foundation of China under
Grant 62171276, the Science and Technology Commission of Shanghai Municipal
under Grant 21511100900 and CCF-DiDi GAIA Research Collaboration Plan 202112.

## References

  * [1] Alexandre Alahi, Kratarth Goel, Vignesh Ramanathan, Alexandre Robicquet, Li Fei-Fei, and Silvio Savarese.  Social lstm: Human trajectory prediction in crowded spaces.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 961–971, 2016.
  * [2] Gianluca Antonini, Michel Bierlaire, and Mats Weber.  Discrete choice models of pedestrian walking behavior.  Transportation Research Part B: Methodological, 40(8):667–687, 2006\.
  * [3] Mayank Bansal, Alex Krizhevsky, and Abhijit Ogale.  Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst.  arXiv preprint arXiv:1812.03079, 2018.
  * [4] Apratim Bhattacharyya, Michael Hanselmann, Mario Fritz, Bernt Schiele, and Christoph-Nikolas Straehle.  Conditional flow variational autoencoders for structured sequence prediction.  arXiv preprint arXiv:1908.09008, 2019.
  * [5] Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Conguri Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, et al.  Spectral temporal graph neural network for multivariate time-series forecasting.  arXiv preprint arXiv:2103.07719, 2021.
  * [6] Sergio Casas, Wenjie Luo, and Raquel Urtasun.  Intentnet: Learning to predict intention from raw sensor data.  In Conference on Robot Learning, pages 947–956. PMLR, 2018.
  * [7] Fang-Chieh Chou, Tsung-Han Lin, Henggang Cui, Vladan Radosavljevic, Thi Nguyen, Tzu-Kuo Huang, Matthew Niedoba, Jeff Schneider, and Nemanja Djuric.  Predicting motion of vulnerable road users using high-definition maps and efficient convnets.  In 2020 IEEE Intelligent Vehicles Symposium (IV), pages 1655–1662. IEEE, 2018.
  * [8] Nachiket Deo and Mohan M Trivedi.  Convolutional social pooling for vehicle trajectory prediction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 1468–1476, 2018.
  * [9] Hongyang Gao and Shuiwang Ji.  Graph u-nets.  In international conference on machine learning, pages 2083–2092. PMLR, 2019.
  * [10] Jiyang Gao, Chen Sun, Hang Zhao, Yi Shen, Dragomir Anguelov, Congcong Li, and Cordelia Schmid.  Vectornet: Encoding hd maps and agent dynamics from vectorized representation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11525–11533, 2020.
  * [11] Francesco Giuliari, Irtiza Hasan, Marco Cristani, and Fabio Galasso.  Transformer networks for trajectory forecasting.  In 2020 25th International Conference on Pattern Recognition (ICPR), pages 10335–10342. IEEE, 2021.
  * [12] Colin Graber and Alexander G Schwing.  Dynamic neural relational inference.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8513–8522, 2020.
  * [13] Agrim Gupta, Justin Johnson, Li Fei-Fei, Silvio Savarese, and Alexandre Alahi.  Social gan: Socially acceptable trajectories with generative adversarial networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2255–2264, 2018.
  * [14] Yue Hu, Siheng Chen, Ya Zhang, and Xiao Gu.  Collaborative motion prediction via neural motion message passing.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6319–6328, 2020.
  * [15] Yingfan Huang, Huikun Bi, Zhaoxin Li, Tianlu Mao, and Zhaoqi Wang.  Stgat: Modeling spatial-temporal interactions for human trajectory prediction.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6272–6281, 2019.
  * [16] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [17] Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel.  Neural relational inference for interacting systems.  In International Conference on Machine Learning, pages 2688–2697. PMLR, 2018.
  * [18] Vineet Kosaraju, Amir Sadeghian, Roberto Martín-Martín, Ian Reid, S Hamid Rezatofighi, and Silvio Savarese.  Social-bigat: Multimodal trajectory forecasting using bicycle-gan and graph attention networks.  arXiv preprint arXiv:1907.03395, 2019.
  * [19] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang.  Trajectory clustering: a partition-and-group framework.  In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 593–604, 2007.
  * [20] Namhoon Lee, Wongun Choi, Paul Vernaza, Christopher B Choy, Philip HS Torr, and Manmohan Chandraker.  Desire: Distant future prediction in dynamic scenes with interacting agents.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 336–345, 2017.
  * [21] Alon Lerner, Yiorgos Chrysanthou, and Dani Lischinski.  Crowds by example.  In Computer graphics forum, volume 26, pages 655–664. Wiley Online Library, 2007.
  * [22] Jiachen Li, Fan Yang, Hengbo Ma, Srikanth Malla, Masayoshi Tomizuka, and Chiho Choi.  Rain: Reinforced hybrid attention inference network for motion forecasting.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16096–16106, 2021.
  * [23] Jiachen Li, Fan Yang, Masayoshi Tomizuka, and Chiho Choi.  Evolvegraph: Multi-agent trajectory prediction with dynamic relational reasoning.  Proceedings of the Neural Information Processing Systems (NeurIPS), 2020.
  * [24] Maosen Li, Siheng Chen, Yanning Shen, Genjia Liu, Ivor W Tsang, and Ya Zhang.  Online multi-agent forecasting with interpretable collaborative graph neural network.  arXiv preprint arXiv:2107.00894, 2021.
  * [25] Maosen Li, Siheng Chen, Yangheng Zhao, Ya Zhang, Yanfeng Wang, and Qi Tian.  Dynamic multiscale graph neural networks for 3d skeleton based human motion prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 214–223, 2020.
  * [26] Chris J Maddison, Andriy Mnih, and Yee Whye Teh.  The concrete distribution: A continuous relaxation of discrete random variables.  arXiv preprint arXiv:1611.00712, 2016.
  * [27] Karttikeya Mangalam, Harshayu Girase, Shreyas Agarwal, Kuan-Hui Lee, Ehsan Adeli, Jitendra Malik, and Adrien Gaidon.  It is not the journey but the destination: Endpoint conditioned trajectory prediction.  In European Conference on Computer Vision, pages 759–776. Springer, 2020.
  * [28] Ramin Mehran, Alexis Oyama, and Mubarak Shah.  Abnormal crowd behavior detection using social force model.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 935–942. IEEE, 2009.
  * [29] Abduallah Mohamed, Kun Qian, Mohamed Elhoseiny, and Christian Claudel.  Social-stgcnn: A social spatio-temporal graph convolutional neural network for human trajectory prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14424–14432, 2020.
  * [30] Brendan Morris and Mohan Trivedi.  Learning trajectory patterns by clustering: Experimental studies and comparative evaluation.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 312–319. IEEE, 2009.
  * [31] Stefano Pellegrini, Andreas Ess, Konrad Schindler, and Luc Van Gool.  You’ll never walk alone: Modeling social behavior for multi-target tracking.  In 2009 IEEE 12th International Conference on Computer Vision, pages 261–268. IEEE, 2009.
  * [32] Alexandre Robicquet, Amir Sadeghian, Alexandre Alahi, and Silvio Savarese.  Learning social etiquette: Human trajectory understanding in crowded scenes.  In European conference on computer vision, pages 549–565. Springer, 2016.
  * [33] Amir Sadeghian, Vineet Kosaraju, Ali Sadeghian, Noriaki Hirose, Hamid Rezatofighi, and Silvio Savarese.  Sophie: An attentive gan for predicting paths compliant to social and physical constraints.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1349–1358, 2019.
  * [34] Tim Salzmann, Boris Ivanovic, Punarjay Chakravarty, and Marco Pavone.  Trajectron++: Multi-agent generative trajectory forecasting with heterogeneous data for control.  2020\.
  * [35] Kihyuk Sohn, Honglak Lee, and Xinchen Yan.  Learning structured output representation using deep conditional generative models.  Advances in neural information processing systems, 28:3483–3491, 2015.
  * [36] Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  Sequence to sequence learning with neural networks.  arXiv preprint arXiv:1409.3215, 2014.
  * [37] Bohan Tang, Yiqi Zhong, Ulrich Neumann, Gang Wang, Ya Zhang, and Siheng Chen.  Collaborative uncertainty in multi-agent trajectory forecasting.  Advances in Neural Information Processing Systems, 34, 2021.
  * [38] Anirudh Vemula, Katharina Muelling, and Jean Oh.  Social attention: Modeling attention in human crowds.  In 2018 IEEE international Conference on Robotics and Automation (ICRA), pages 4601–4607. IEEE, 2018.
  * [39] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7794–7803, 2018.
  * [40] Xiaogang Wang, Keng Teck Ma, Gee-Wah Ng, and W Eric L Grimson.  Trajectory analysis and semantic region modeling using nonparametric hierarchical bayesian models.  International journal of computer vision, 95(3):287–312, 2011.
  * [41] Xiaogang Wang, Xiaoxu Ma, and W Eric L Grimson.  Unsupervised activity perception in crowded and complicated scenes using hierarchical bayesian models.  IEEE Transactions on pattern analysis and machine intelligence, 31(3):539–555, 2008.
  * [42] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang.  Connecting the dots: Multivariate time series forecasting with graph neural networks.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 753–763, 2020.
  * [43] Yanyu Xu, Zhixin Piao, and Shenghua Gao.  Encoding crowd interaction with deep neural network for pedestrian trajectory prediction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5275–5284, 2018.
  * [44] Cunjun Yu, Xiao Ma, Jiawei Ren, Haiyu Zhao, and Shuai Yi.  Spatio-temporal graph transformer networks for pedestrian trajectory prediction.  In European Conference on Computer Vision, pages 507–523. Springer, 2020.
  * [45] Ye Yuan, Xinshuo Weng, Yanglan Ou, and Kris M Kitani.  Agentformer: Agent-aware transformers for socio-temporal multi-agent forecasting.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9813–9823, 2021.
  * [46] Tianyang Zhao, Yifei Xu, Mathew Monfort, Wongun Choi, Chris Baker, Yibiao Zhao, Yizhou Wang, and Ying Nian Wu.  Multi-agent tensor fusion for contextual trajectory prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12126–12134, 2019.


# The Impact of Strategies and Information
in Model Checking for Multi-Agent Systems

Vadim Malvone LTCI, Télécom Paris, Institut Polytechnique de Paris,
Palaiseau, France<EMAIL_ADDRESS>
###### Abstract

System correctness is one of the most crucial and challenging objectives in
software and hardware systems. With the increasing evolution of connected and
distributed systems, ensuring their correctness requires the use of formal
verification for multi-agent systems. In this paper, we present a summary of
certain results on model checking for multi-agent systems that derive from the
selection of strategies and information for agents. Additionally, we discuss
some open directions for future research.

##  1 Introduction

The problem of assuring systems correctness is particularly felt in hardware
and software design, especially in safety-critical scenarios. When we talk
about a safety-critical system, we mean the one in which failure is not an
option. To face this problem, several methodologies have been proposed. Among
these, Model Checking (MC) [12, 11] results to be very useful. This approach
provides a formal-based methodology to model systems, to specify properties
via temporal logics, and to verify that a system satisfies a given
specification.

Notably, first applications of model checking just concerned closed systems,
which are characterized by the fact that their behavior is completely
determined by their internal states. Unfortunately, model checking techniques
developed to handle closed systems turn out to be quite useless in practice,
as most of the systems are open and are characterized by an ongoing
interaction with other systems. To overcome this problem, model checking has
been extended to Multi-Agent Systems (MAS). In the latter context, temporal
logics have been extended to temporal logics for the strategic reasoning such
as Alternating-time Temporal Logic (ATL) [3] and Strategy Logic (SL) [22].

Given the logics under exam, there are two key aspects in MAS to determine the
model checking complexity: the type of strategies and the agents’ information.
A strategy is a generic conditional plan that prescribes an action at each
step of the MAS. There are two main classes of strategies: _memoryless_ and
_memoryfull_. In the former case, agents choose an action by considering only
the current state, while in the latter case, agents choose an action by
considering the full history of the MAS. Regarding information, we distinguish
between _perfect_ and _imperfect_ information MAS. The former corresponds to a
basic setting in which every agent has full knowledge about the MAS. However,
real-life scenarios often involve situations where agents must act without
having all relevant information at hand. In computer science, these situations
occur, for example, when some variables of a system are internal/private and
not visible to an external environment. In MAS models, imperfect information
is usually modeled by setting an indistinguishability relation over the states
of the MAS. This feature deeply impacts on the MC complexity. For example, ATL
and SL become undecidable in the context of imperfect information and
memoryfull strategies [13].

In this paper, we present a review of results on model checking for multi-
agent systems concerning strategy classes and agent visibility, and explore
potential directions for future research.

### Outline

In Section 2, we recall the definition of concurrent game structures and the
syntax of ATL and SL. Then, in Section 3, we review the main classes of
strategies and the concept of information. In Section 4, we revisit the model
checking complexities for the aforementioned contexts. Finally, we conclude by
providing some future directions in Section 5.

##  2 Model and logics for MAS

In this section, we recall the definition of a formal model for MAS and the
syntax of two well-known logics for strategic reasoning: ATL and SL.

We start by recalling the definition of concurrent game structures [3].

###### Definition 1

Given sets $Ag$ of agents and $AP$ of atoms, a _concurrent game structure
(CGS)_ is a tuple $M=\langle S,s_{0},\\{Act_{i}\\}_{i\in
Ag},\allowbreak\\{\sim_{i}\\}_{i\in Ag},d,\delta,V\rangle$ such that:

  * •

$S$ is a finite, non-empty set of states, with initial state $s_{0}\in S$.

  * •

For every $i\in Ag$, $Act_{i}$ is a finite, non-empty set of actions.

Let $Act=\bigcup_{i\in Ag}Act_{i}$ be the set of all actions, and
$ACT=\prod_{i\in Ag}Act_{i}$ the set of all joint actions, i.e., tuples of
actions.

  * •

For every $i\in Ag$, $\sim_{i}$ is a relation of indistinguishability between
states, that is, an equivalence relation on $S$. Given states $s,s^{\prime}\in
S$, $s\sim_{i}s^{\prime}$ iff $s$ and $s^{\prime}$ are said to be
observationally indistinguishable for agent $i$.

  * •

The protocol function $d:Ag\times S\rightarrow(2^{Act}\setminus\emptyset)$
defines the availability of actions so that for every $i\in Ag$, $s\in S$, (i)
$d(i,s)\subseteq Act_{i}$ and (ii) $s\sim_{i}s^{\prime}$ implies
$d(i,s)=d(i,s^{\prime})$.

  * •

The transition function $\delta:S\times ACT\to S$ assigns a successor state
$s^{\prime}=\delta(s,\vec{\alpha})$ to each state $s\in S$, for every joint
action $\vec{\alpha}\in ACT$ such that $a_{i}\in d(i,s)$ for every $i\in Ag$,
that is, $\vec{\alpha}$ is enabled at $s$.

  * •

$V:S\times AP\rightarrow\\{\top,\bot\\}$ is a two-valued labelling function.

According to Def. 1, a CGS describes the interactions of a group $Ag$ of
agents, starting from the initial state $s_{0}\in S$, following the transition
function $\delta$. The latter is constrained by the availability of actions to
agents, as specified by the protocol function $d$. A history $h\in S^{+}$ is a
finite (non-empty) sequence of states.

Now, we recall the syntax of Alternating-time Temporal Logic [3].

######  Definition 2 ($ATL^{*}$)

The state ($\varphi$) and path ($\psi$) formulas in ATL∗ are defined as
follows, where $p\in AP$ and $\Gamma\subseteq Ag$:

$\displaystyle\varphi$ $\displaystyle::=$ $\displaystyle
p\mid\neg\varphi\mid\varphi\land\varphi\mid{\langle\\!\langle\Gamma\rangle\\!\rangle}\psi$
$\displaystyle\psi$ $\displaystyle::=$
$\displaystyle\varphi\mid\neg\psi\mid\psi\land\psi\mid X\psi\mid(\psi
U\psi)\mid(\varphi R\varphi)$

Formulas in ATL∗ are all and only the state formulas.

ATL extends Computation Tree Logic (CTL) [10] in which the existential $E$ and
the universal $A$ path quantifiers are replaced with strategic modalities of
the form ${\langle\\!\langle\Gamma\rangle\\!\rangle}$ and
${[\\![\Gamma]\\!]}$, where $\Gamma$ is a set of agents. A formula
${\langle\\!\langle\Gamma\rangle\\!\rangle}\psi$ is read as _“the agents in
coalition $\Gamma$ have a strategy to achieve $\psi$”_. The meaning of
temporal operators next $X$ and until $U$ is standard [12]. Operators
unavoidable ${[\\![\Gamma]\\!]}$, release $R$, finally $F$, and globally $G$
can be introduced as usual.

The formulas in the ATL fragment of ATL∗ are obtained from Def. 2 by
restricting path formulas $\psi$ to the temporal operators.

To conclude this section, we recall the syntax of Strategy Logic [22].

######  Definition 3 (SL Syntax)

Given the set $AP$ of atoms, variables $Var$, and agents $Ag$, the formal
syntax of SL is defined as follows, where $p\in AP$, $x\in Var$, and $a\in
Ag$:

$\displaystyle\varphi$ $\displaystyle::=$ $\displaystyle
p\mid\neg\varphi\mid\varphi\wedge\varphi\mid\varphi\vee\varphi\mid
X\varphi\mid\varphi\>U\varphi\mid\varphi\,R\,\varphi\mid\exists\>\\!{x}\varphi\mid\forall\>\\!\\!{x}\varphi\mid(a,x)\varphi$

SL syntactically extends Linear-time Temporal Logic (LTL) [24] with two
_strategy quantifiers_ , the existential $\exists\>\\!{x}$ and universal
$\forall\>\\!\\!{x}$, along with an _agent binding_ $(a,x)$, where $a$ is an
agent and $x$ a variable. Intuitively, these additional elements can be
respectively interpreted as _“there exists a strategy $x$”_, _“for all
strategies $x$”_, and _“bind agent $a$ to the strategy associated with the
variable $x$”_.

##  3 Classes of Strategies and Information

In this section, we recall some definitions of strategies and of agents’
information.

In Definition 1, we have defined an indistinguishability relation for each
agent involved in the model. When every $\sim_{i}$ is the identity relation,
i.e., $s\sim_{i}s^{\prime}$ iff $s=s^{\prime}$, we obtain a CGS with _perfect
information_ [3]. When the latter is not true, we assume that every agent $i$
has _imperfect information_ about the exact state of the system. That is, in
any state $s$, $i$ considers all states $s^{\prime}$ that are
indistinguishable for $i$ from $s$ to be epistemically possible [14]. The
indistinguishability relations are extended to histories in a synchronous,
pointwise way, i.e., histories $h,h^{\prime}\in S^{+}$ are indistinguishable
for agent $i\in Ag$, or $h\sim_{i}h^{\prime}$, iff (i) $|h|=|h^{\prime}|$ and
(ii) for all $j\leq|h|$, $h_{j}\sim_{i}h^{\prime}_{j}$.

Now, we have all the ingredients to present the different definitions of
strategies. First, we start with a class of strategies in which the agents
determine their actions by considering only the current state of the MAS.

######  Definition 4 (Memoryless Strategy)

A _memoryless strategy_ for agent $i\in Ag$ is a function $f_{i}:S\to Act_{i}$
such that for each state $s\in S$, (i) $f_{i}(s)\in d(i,s)$; and (ii)
$s\sim_{i}s^{\prime}$ implies $f_{i}(s)=f_{i}(s^{\prime})$.

By Def. 4, any strategy for agent $i$ must return actions that are enabled for
$i$ (i.e. condition (i)). Additionally, whenever two states are
indistinguishable for $i$, the same action is returned (i.e. condition (ii)).
This latter introduces the concept of _uniformity_ , where an agent can select
a strategy that adheres to its visibility. Notice that, for the case of
perfect information, condition (ii) is satisfied by any function $f_{i}:S\to
Act_{i}$.

The notion of memoryless strategy is considered too weak for an agent. For
this reason, the concept of memoryfull strategy has been introduced.

######  Definition 5 (Memoryfull Strategy)

A _memoryfull strategy_ for agent $i\in Ag$ is a function $f_{i}:S^{+}\to
Act_{i}$ such that for all histories $h,h^{\prime}\in S^{+}$, (i) $f_{i}(h)\in
d(i,last(h))$; and (ii) $h\sim_{i}h^{\prime}$ implies
$f_{i}(h)=f_{i}(h^{\prime})$.

As for the memoryless case, memoryfull strategies must adhere to the protocol
function and indistinguishability relation.

Between these two approaches, i.e. memoryless and memoryfull, several
different classes of bounded strategies have been proposed, including works by
Ågotnes and Walther [2], Brihaye et al. [9], Vester [28], and Belardinelli et
al. [7]. In this work, we focus our attention to natural strategies [19]. The
idea behind natural strategies is to adopt the view of bounded rationality,
and look at “simple” strategies in specification of agents’ abilities. This
notion has been introduced in both ATL and SL in the context of perfect [18]
and imperfect information [6, 20]. Here, we focus on the definition provided
in [20].

A natural strategies is an _ordered list of guarded actions_ , i.e., sequences
of pairs $(\phi_{i},\alpha_{i})$ such that: $\phi_{i}$ is a condition, and
$\alpha_{i}$ is an action. That is, a natural strategy is a rule-based
representation in which the first rule whose condition holds in the current
execution of the MAS is selected, and the corresponding action is executed.

With respect to the nature of the conditions, it is possible to define
different classes of natural strategies. We start by recalling the notion of
_uniform natural memoryless strategy_.

###### Definition 6

In an uniform natural memoryless strategy for any agent $a$, the conditions
are defined over epistemic formulas as follows:

$\psi::=\top\mid K_{a}\varphi\mid\neg\psi\mid\psi\land\psi$

$\varphi::=p\mid\neg\varphi\mid\varphi\land\varphi\mid K_{b}\varphi$

where $p$ is an atomic proposition, $b$ an agent, and $K_{i}$ is the knowledge
operator for any agent $i$. Intuitively, a formula $K_{i}\varphi$ can be
interpreted as _“the agent $i$ knows $\varphi$”_.

So, we have formulas that are prefixed by $K_{a}$ and then possibly combined
by boolean operators. In other words, the formulas are always boolean
conditions on $a$’s knowledge. As discussed in [18], to define _natural
memoryless strategy_ in the perfect information case, we can replace epistemic
formulas with boolean formulas only.

To improve the abilities of the agents, natural strategies have also been
defined with recall. In particular, to evaluate properties over histories
instead of states, a way to define conditions is to use regular expressions
with the standard constructors $\cdot,\cup,*$ representing concatenation,
nondeterministic choice, and finite iteration, respectively. Thus, to define a
_natural strategies with recall_ in the perfect information context, we can
use regular expressions over boolean formulas. Similarly, to define a _uniform
natural strategies with recall_ in the imperfect information context, we can
use regular expressions over epistemic formulas.

In the next section, we will provide the main model checking results for the
above mentioned classes.

##  4 Model Checking Complexities

Here, we discuss the model checking complexities for ATL and SL in terms of
memoryless, memoryfull, and natural strategies in the perfect and imperfect
information context.

First, we can analyze ATL. As you can see in Table 1, in the worst case, that
is imperfect information and perfect recall strategies, the problem becomes
undecidable, while in the perfect information case, the problem is polynomial.
An interesting point of ATL is that memoryless and memoryfull strategies are
equivalent in the perfect information case. This is because ATL is too weak in
expressive power.

ATL | perfect information | imperfect information
---|---|---
memoryless |  $PTIME$-complete [3] |  $\Delta_{2}^{P}$-complete [27]
memoryfull |  $PTIME$-complete [3] | undecidable [13]
Table 1: Model checking complexities for ATL.

To overcome this problem, there is ATL∗. In this logic, strategic and temporal
operators are decoupled to express more complex strategic objectives. As you
can see in Table 2, the model checking complexity becomes solvable in
polynomial space in the memoryless case, double-exponential time in the
memoryfull and perfect information case, and again undecidable in the
memoryfull and imperfect information case. To address the latter problem, some
works have either focused on an approximation to perfect information [4],
developed notions of bounded memory [7], or employed hybrid techniques [15,
16]. Despite its expressiveness, ATL∗ suffers from the strong limitation that
strategies are treated only implicitly in the semantics of strategic
operators. This restriction makes the logic less suited to formalize several
important solution concepts, such as the Nash Equilibrium [23].

ATL∗ | perfect information | imperfect information
---|---|---
memoryless |  $PSPACE$-complete [27] |  $PSPACE$-complete [27]
memoryfull |  $2EXPTIME$-complete [3] | undecidable [13]
Table 2: Model checking complexities for ATL∗.

To gain expressive power, we need to move to Strategy Logic. As shown in Table
3, the model checking problem becomes intractable in the memoryfull case.
Given the relevance of this logic, several fragments have been proposed [22,
5]. Among others, we would like to mention Strategic Logic One Goal that has
the same model checking complexity as ATL∗ but more expressive power, and
Strategic Logic Simple Goal that has the same model checking complexity as ATL
but more expressive power.

SL | perfect information | imperfect information
---|---|---
memoryless | - |  $PSPACE$-complete [21]
memoryfull | non-elementary [22] | undecidable [13]
Table 3: Model checking complexities for SL. NatATL | perfect information | imperfect information
---|---|---
memoryless |  $\Delta_{2}^{P}$-complete [19] |  $\Delta_{2}^{P}$-complete [20]
with recall |  $PSPACE$-complete [19] |  $PSPACE$-complete [20]
Table 4: Model checking complexities for NatATL.

In all the above-mentioned logics, the model checking problem is undecidable
in the worst case. In the last few years, a natural way to represent
strategies has been studied. From the definition of natural strategies, two
variants of ATL and SL have been proposed. In these variants, called NatATL
[19] and NatSL [6], the strategic operators are equipped with graded
modalities that represent the complexity of the natural strategies in
achieving the temporal objectives. As you can see in Tables 4 and 5 the model
checking problem has a complexity less than or equal $PSPACE$.

NatSL | perfect information | imperfect information
---|---|---
memoryless | - |  $PSPACE$-complete [6]
with recall | - |  $PSPACE$-complete [6]
Table 5: Model checking complexities for NatSL.

Can this approach solve all the problems related to model checking for MAS?
Unfortunately (or fortunately for researchers), there are several open
problems related to what we have summarized in this work. We will discuss some
of them in the following section.

##  5 Future Directions

As promised throughout the paper, in this section, we will discuss some
directions for future research. We will summarize these aspects with respect
to the three main features related to the formal verification of multi-agent
systems, namely: strategies, information, and logics.

### About strategies: find the good representation.

As we briefly discussed along the paper, both memoryless and memoryful
strategies are not suitable choices. In fact, memoryless and memoryfull are
too weak and strong, respectively, to describe agents’ abilities. The weakness
of memoryless strategies is a gain in terms of complexity, and the strength of
memoryfull strategies is paid in terms of complexity. In addition, memoryfull
strategies cannot be used to implement a model checker due to their domain
over histories. As we mentioned earlier, there are some bounded versions
between memoryless and memoryfull, but there is a lot of work to do to
standardize the good choice. For instance, in the context of natural
strategies, there are various aspects that require attention, such as defining
the appropriate notion of complexity for these strategies. In the above-
mentioned works, the authors have proposed the total size of the strategy as
complexity, i.e., the overall complexity is the sum of all the symbols
involved in the conditions. Is this the best way to define the complexity of a
strategy? This is an open problem that needs to be investigated.

### About information: perfect and imperfect is not enough.

We believe there is significant work to be done in this area. For instance, it
seems too reductive to consider only white (i.e. perfect information) and
black (i.e. imperfect information) settings. We advocate the need to define a
taxonomy for imperfect information. As discussed earlier in the paper, some
approaches try to make some MAS with imperfect information decidable. However,
the authors in [6, 4, 17] do not give a specific class of MAS with imperfect
information that is decidable. Currently, only the class of hierarchical
information has been proposed [26, 25] and analyzed in SL [8].

### About logics: find the gap between ATL and SL.

The two logics for the strategic reasoning discussed in this work suffer from
two main problems on two different sides. On one hand, ATL has a good model
checking complexity, but it cannot express several solution concepts such as
the Nash Equilibrium. The strong limitation of ATL is that it treats
strategies only implicitly in the semantics of its modalities. So, it is weak
in expressiveness. On the other hand, SL is the more powerful logic for the
strategic reasoning, but its model checking problem is not tractable. So, the
full logic cannot have practical applications. The idea is to define a new
logic for the strategic reasoning that can incorporate the positive features
of ATL in terms of complexity and the good features of SL in terms of
expressiveness. We understand that this is not a simple challenge, and finding
a perfect trade-off between ATL and SL may be difficult. However, we see this
need and want to go all the way on this point.

## References

  * [1]
  * [2] Thomas Ågotnes & Dirk Walther (2009): _A Logic of Strategic Ability Under Bounded Memory_.  J. Log. Lang. Inf. 18(1), pp. 55–77.  Available at https://doi.org/10.1007/s10849-008-9075-4.
  * [3] Rajeev Alur, Thomas A. Henzinger & Orna Kupferman (2002): _Alternating-time temporal logic_.  J. ACM 49(5), pp. 672–713.  Available at https://doi.org/10.1145/585265.585270.
  * [4] Francesco Belardinelli, Angelo Ferrando & Vadim Malvone (2023): _An abstraction-refinement framework for verifying strategic properties in multi-agent systems with imperfect information_.  Artif. Intell. 316, p. 103847.  Available at https://doi.org/10.1016/j.artint.2022.103847.
  * [5] Francesco Belardinelli, Wojciech Jamroga, Damian Kurpiewski, Vadim Malvone & Aniello Murano (2019): _Strategy Logic with Simple Goals: Tractable Reasoning about Strategies_.  In Sarit Kraus, editor: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, ijcai.org, pp. 88–94.  Available at https://doi.org/10.24963/ijcai.2019/13.
  * [6] Francesco Belardinelli, Wojtek Jamroga, Vadim Malvone, Munyque Mittelmann, Aniello Murano & Laurent Perrussel (2022): _Reasoning about Human-Friendly Strategies in Repeated Keyword Auctions_.  In Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud & Matthew E. Taylor, editors: 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 62–71.  Available at https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p62.pdf.
  * [7] Francesco Belardinelli, Alessio Lomuscio, Vadim Malvone & Emily Yu (2022): _Approximating Perfect Recall when Model Checking Strategic Abilities: Theory and Applications_.  J. Artif. Intell. Res. 73, pp. 897–932.  Available at https://doi.org/10.1613/jair.1.12539.
  * [8] Raphaël Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin & Moshe Y. Vardi (2021): _Strategy Logic with Imperfect Information_.  ACM Trans. Comput. Log. 22(1), pp. 5:1–5:51.  Available at https://doi.org/10.1145/3427955.
  * [9] Thomas Brihaye, Arnaud Da Costa Lopes, François Laroussinie & Nicolas Markey (2009): _ATL with Strategy Contexts and Bounded Memory_.  In Sergei N. Artëmov & Anil Nerode, editors: Logical Foundations of Computer Science, International Symposium, LFCS 2009, Deerfield Beach, FL, USA, January 3-6, 2009. Proceedings, Lecture Notes in Computer Science 5407, Springer, pp. 92–106.  Available at https://doi.org/10.1007/978-3-540-92687-0_7.
  * [10] Edmund M. Clarke & E. Allen Emerson (1981): _Design and Synthesis of Synchronization Skeletons Using Branching-Time Temporal Logic_.  In Dexter Kozen, editor: Logics of Programs, Workshop, Yorktown Heights, New York, USA, May 1981, Lecture Notes in Computer Science 131, Springer, pp. 52–71.  Available at https://doi.org/10.1007/BFb0025774.
  * [11] E.M. Clarke, O. Grumberg, D. Kroening, D. Peled & H. Veith (2018): _Model Checking, second edition_.  Cyber Physical Systems Series, MIT Press.  Available at https://books.google.fr/books?id=OJV5DwAAQBAJ.
  * [12] E.M. Clarke, O. Grumberg, D. Peled & D.A. Peled (1999): _Model Checking_.  The Cyber-Physical Systems Series, MIT Press.  Available at https://books.google.fr/books?id=Nmc4wEaLXFEC.
  * [13] Catalin Dima & Ferucio Laurentiu Tiplea (2011): _Model-checking ATL under Imperfect Information and Perfect Recall Semantics is Undecidable_.  CoRR abs/1102.4225.  arXiv:https://arxiv.org/abs/1102.4225.
  * [14] R. Fagin, J.Y. Halpern, Y. Moses & M. Vardi (2004): _Reasoning About Knowledge_.  A Bradford Book, MIT Press.  Available at https://doi.org/10.7551/mitpress/5803.001.0001.
  * [15] Angelo Ferrando & Vadim Malvone (2022): _Towards the Combination of Model Checking and Runtime Verification on Multi-agent Systems_.  In Frank Dignum, Philippe Mathieu, Juan Manuel Corchado & Fernando de la Prieta, editors: Advances in Practical Applications of Agents, Multi-Agent Systems, and Complex Systems Simulation. The PAAMS Collection - 20th International Conference, PAAMS 2022, L’Aquila, Italy, July 13-15, 2022, Proceedings, Lecture Notes in Computer Science 13616, Springer, pp. 140–152.  Available at https://doi.org/10.1007/978-3-031-18192-4_12.
  * [16] Angelo Ferrando & Vadim Malvone (2023): _How to Find Good Coalitions to Achieve Strategic Objectives_.  In Ana Paula Rocha, Luc Steels & H. Jaap van den Herik, editors: Proceedings of the 15th International Conference on Agents and Artificial Intelligence, ICAART 2023, Volume 1, Lisbon, Portugal, February 22-24, 2023, SCITEPRESS, pp. 105–113.  Available at https://doi.org/10.5220/0011778700003393.
  * [17] Angelo Ferrando & Vadim Malvone (2023): _Towards the Verification of Strategic Properties in Multi-Agent Systems with Imperfect Information_.  In Noa Agmon, Bo An, Alessandro Ricci & William Yeoh, editors: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, ACM, pp. 793–801.  Available at https://dl.acm.org/doi/10.5555/3545946.3598713.
  * [18] Wojciech Jamroga, Vadim Malvone & Aniello Murano (2017): _Reasoning about Natural Strategic Ability_.  In Kate Larson, Michael Winikoff, Sanmay Das & Edmund H. Durfee, editors: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, ACM, pp. 714–722.  Available at http://dl.acm.org/citation.cfm?id=3091227.
  * [19] Wojciech Jamroga, Vadim Malvone & Aniello Murano (2019): _Natural strategic ability_.  Artif. Intell. 277\.  Available at https://doi.org/10.1016/j.artint.2019.103170.
  * [20] Wojciech Jamroga, Vadim Malvone & Aniello Murano (2019): _Natural Strategic Ability under Imperfect Information_.  In Edith Elkind, Manuela Veloso, Noa Agmon & Matthew E. Taylor, editors: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, International Foundation for Autonomous Agents and Multiagent Systems, pp. 962–970.  Available at http://dl.acm.org/citation.cfm?id=3331791.
  * [21] Bastien Maubert, Munyque Mittelmann, Aniello Murano & Laurent Perrussel (2021): _Strategic Reasoning in Automated Mechanism Design_.  In Meghyn Bienvenu, Gerhard Lakemeyer & Esra Erdem, editors: Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, November 3-12, 2021, pp. 487–496.  Available at https://doi.org/10.24963/kr.2021/46.
  * [22] Fabio Mogavero, Aniello Murano, Giuseppe Perelli & Moshe Y. Vardi (2014): _Reasoning About Strategies: On the Model-Checking Problem_.  ACM Trans. Comput. Log. 15(4), pp. 34:1–34:47.  Available at https://doi.org/10.1145/2631917.
  * [23] R.B. Myerson (1991): _Game Theory: Analysis of Conflict_.  Harvard University Press.  Available at https://books.google.fr/books?id=E8WQFRCsNr0C.
  * [24] Amir Pnueli (1977): _The Temporal Logic of Programs_.  In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, IEEE Computer Society, pp. 46–57.  Available at https://doi.org/10.1109/SFCS.1977.32.
  * [25] Amir Pnueli & Roni Rosner (1990): _Distributed Reactive Systems Are Hard to Synthesize_.  In: 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, IEEE Computer Society, pp. 746–757.  Available at https://doi.org/10.1109/FSCS.1990.89597.
  * [26] John H. Reif (1984): _The Complexity of Two-Player Games of Incomplete Information_.  J. Comput. Syst. Sci. 29(2), pp. 274–301.  Available at https://doi.org/10.1016/0022-0000(84)90034-5.
  * [27] Pierre-Yves Schobbens (2003): _Alternating-time logic with imperfect recall_.  In Wiebe van der Hoek, Alessio Lomuscio, Erik P. de Vink & Michael J. Wooldridge, editors: 1st International Workshop on Logic and Communication in Multi-Agent Systems, LCMAS 2003, Eindhoven, The Netherlands, June 29, 2003, Electronic Notes in Theoretical Computer Science 85, Elsevier, pp. 82–93.  Available at https://doi.org/10.1016/S1571-0661(05)82604-0.
  * [28] Steen Vester (2013): _Alternating-time temporal logic with finite-memory strategies_.  In Gabriele Puppis & Tiziano Villa, editors: Proceedings Fourth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2013, Borca di Cadore, Dolomites, Italy, 29-31th August 2013, EPTCS 119, pp. 194–207.  Available at https://doi.org/10.4204/EPTCS.119.17.