# Distributed Multi-agent Interaction Generation
with Imagined Potential Games

Lingfeng Sun1 Pin-Yun Hung1 Changhao Wang1 Masayoshi Tomizuka1 Zhuo Xu2
1Department of Mechanical Engineering, University of California, Berkeley,
Berkeley, CA 94720, USA. {lingfengsun, pinyun_hung, changhaowang,
<EMAIL_ADDRESS>Deepmind, Mountain View, CA 94043, USA.
<EMAIL_ADDRESS>
###### Abstract

Interactive behavior modeling of multiple agents is an essential challenge in
simulation, especially in scenarios when agents need to avoid collisions and
cooperate at the same time. Humans can interact with others without explicit
communication and navigate in scenarios when cooperation is required. In this
work, we aim to model human interactions in this realistic setting, where each
agent acts based on its observation and does not communicate with others. We
propose a framework based on distributed potential games, where each agent
imagines a cooperative game with other agents and solves the game using its
estimation of their behavior. We utilize iLQR to solve the games and closed-
loop simulate the interactions. We demonstrate the benefits of utilizing
distributed imagined games in our framework through various simulation
experiments. We show the high success rate, the increased navigation
efficiency, and the ability to generate rich and realistic interactions with
interpretable parameters. Illustrative examples are available at
https://sites.google.com/berkeley.edu/distributed-interaction.

##  I INTRODUCTION

Modeling the interactive behavior of multiple agents in different scenarios is
an essential task in crowd simulation. One of the main challenges is to model
the interactive behaviors of multiple agents, especially in narrow scenarios
where they have to avoid obstacles at the same time. The agents’ decisions are
interdependent, meaning that each agent’s decision influences and is
influenced by the decision of the other agents. In real life, humans can
cooperate with each other without explicit communication; instead, we make
decisions based on observations. In this work, we aim to analyze and model the
interactions in a distributed game setting without communication.

The problems can be naturally formulated as a multi-agent planning problem
with separate goals and a shared environment. Some previous works have used
centralized [1, 2] algorithms, which solve trajectories of all agents together
to control all robots. However, centralized methods are computationally
expensive and require full information about the environment and other agents.
In contrast, distributed algorithms separately solve the short-horizon
reaction plans [3, 4] or long-horizon trajectory plans [5, 6, 7] for each
robot. Distributed methods are more scalable and robust but suffer from
deadlocks, especially in human-like interaction cases where no communication
is allowed. For instance, as shown in Figure 1, in a narrow-way situation, if
both agents are in the hallway, they have no collision-free navigation plans
to their goals. If agents have no information from the others, they need to
estimate other’s intentions and figure out how to cooperate in the distributed
setting.

Figure 1: A narrow-way problem challenging to solve in the distributed and no-
communication setting. There’s no collision-free for single-agent navigation,
and agents must cooperate (one moving backward to yield the other agent) to
solve the problem. We propose adding imagined cooperation in distributed
planning to simulate cooperative interactions.

We propose to model and solve the interaction problem in a distributed manner
where each agent imagines a cooperation game with others. There are several
works considering game-theoretic frameworks [8, 9, 10, 11] to model
cooperative behaviors. We follow the dynamic game formulation introduced by
[10], where the multi-agent potential game is formulated into an equivalent
single optimal control problem to find cooperative plans for all agents. We
assume an “imagined” game exists in all agents’ distributed planners to
predict others’ behavior and use the iterative LQR (iLQR) to solve optimal
plans. In addition to the basic formulation in [10], we add collision
avoidance to environmental obstacles, observation range, and blind area for
agents in the optimization since they are essential causes of human-like
interactions.

Figure 2: An example interaction generated in T-intersection. From left to
right is the closed-loop trajectory over time. Solid lines are past
trajectories; darker and lighter dotted lines are plans of ego agents and
predictions of other agents (e.g., the light blue line is the predicted green
agent behavior by the blue agent). All green lines are from the green agent’s
planner.

We demonstrate the effectiveness of introducing the “Imagined Potential Game
(IPG)” formulation into the multi-agent planning problem without
communication. The open-loop plans are used to simulate the closed-loop
behaviors using receding horizon control. Agents may have different open-loop
cooperative strategies but can gradually converge to cooperative behaviors in
closed-loop simulation. Experiments on the narrow-way scenario with random
initialization empirically show the improved success rate and navigation
efficiency in simulating cooperative interactions. Furthermore, we show the
framework’s capability to generate diverse and realistic interaction behaviors
by varying parameters, such as safety distance or objective weights. Lastly,
we demonstrate that the IPG-controlled agents can robustly interact with non-
IPG-controller agents. The contribution of this work lies in the following
aspects:

  1. 1.

We propose a multi-agent interaction generation framework using the imagined
potential games under a distributed and no-communication setting to simulate
interactions in dense obstacle scenarios.

  2. 2.

We use simulated experiments to empirically demonstrate the improvement in
success rate and navigation efficiency for simulating complex interactions.

  3. 3.

We demonstrate the algorithm can generate diverse and realistic interactions
using interpretable parameters and interact with heterogeneous agents.

##  II Related Works

###  II-A Multi-robot planning

Multi-robot trajectory planning algorithms can be categorized based on where
the computation is done. Two main strategies to solve the problem are
centralized and distributed. Centralized planning algorithms solve the
trajectories for all the agents in the same problem utilizing the global
information and then send the control commands to the robots. Most previous
works use multi-agent path finding (MAPF) solvers with trajectory optimization
algorithms[1, 12, 2, 13] to find feasible trajectories for all agents. A
series of works [9, 14, 11, 15, 16, 17, 18] models interactions in multi-agent
planning via game theoretic frameworks. [10] utilizes potential games [8] for
multi-agent trajectory planning with symmetric inter-agent costs. Centralized
algorithms can provide theoretical guarantees for planning success and
optimality. However, the centralized setting cannot simulate realistic
interactive behaviors in the distributed setting, where single-agent behaviors
are affected by other agents’ online reactions.

In the distributed setting, each agent runs a separate algorithm to compute
its own trajectory. Depending on whether communication exists between the
agents. Reactive algorithms[3, 19, 20] like Optimal Reciprocal Collision
Avoidance (ORCA) can effectively avoid collisions but fail to avoid deadlocks
in environments with dense obstacles[5]. Learning-based reactive
strategies[21, 22, 23, 24] are computationally more efficient but suffer from
distribution shifts and also experience deadlocks. Another series of works
like dMPC[6] and MADER[25] consider longer horizons and generate sequences
instead of single actions; however, they require communication of plans for
collision avoidance. [26] turns multiple agents into distributed groups and
solves the in-group interactions, but the in-group agents are modeled in the
centralized setting. RLSS[5] uses a fully distributed setting and requires
only the current state sensing of other agents to plan piece-wise Bézier
trajectories to improve deadlock performance. However, these methods don’t
explicitly model the cooperation of agents and, therefore, have trouble
simulating interactions when the initial condition is not feasible for
collision-free planning.

###  II-B Interaction Generation

Simulating the behaviors of actors is an important task with a wide range of
applications in transportation and robotics research since simulators play
essential roles in training and evaluating intelligent agents like indoor
robots and autonomous vehicles. Many autonomous-driving research works focus
on simulating distributed agents’ behaviors in the simulator to generate
realistic interactions and reactive agents[27, 28, 29, 30, 31] or analyzing
and predicting interactive behaviors of heterogeneous agents[32, 33, 34].
Previous works on crowd simulation[35] focus more on the scalability of
simulating agents[36, 37], and grouping in the crowd[38, 39]. In this paper,
we focus on the interactions in scenarios where cooperation is required to
simulate multi-agent behaviors.

##  III Preliminaries

###  III-A Distributed multi-agent planning

Assume we have $N$ agents in the scenario. For each agent $i,1\leq i\leq N$,
let the vector $x_{i}(t)\in\mathbb{R}^{n_{i}}$ denote the state of agent $i$,
let $u_{i}(t)\in\mathbb{R}^{m_{i}}$ denote the control input of agent $i$ at
time $t$. Each agent follows its system dynamics

$x_{i}(k+1)=f_{i}(x_{i}(k),u_{i}(k))$

Unless otherwise specified, throughout this paper, for variable $x$, we use a
subscript $x_{i}$ to denote agent $i$ and a superscript $x^{k}$ or $x(k)$ to
indicate the time horizon $k$. If $i,k$ are not specified, it means $x$ for
all agents or across all time steps. $x_{-i}$ denotes $x$ of all agents
excluding agent $i$.

Obstacles in the scenario are represented by $\\{O_{j}\\}_{j=1}^{M}$. Each
agent has its initial state $x_{i}^{0}$ and a target goal state in the
scenario $g_{i}$. All the agents in the scenario navigate to their target goal
while avoiding collision with the environment and other agents. Interactions
happen when their planned trajectories
$\\{x_{i}(0),x_{i}(1),...,x_{i}(T)\\}_{i=1}^{N}$ have conflicts and need to
interact to reach non-conflict new plans. Control inputs of multiple agents
$U=[u_{1}^{0:T},u_{2}^{0:T},...,u_{N}^{0:T}]$ are the plans of all the agents.
Under the distributed setting with no communication, we assume each agent $i$
is solving an optimal control optimization without knowing others’ plans.

$\displaystyle\min_{u_{i}(0:T),x_{i}(0:T)}$ $\displaystyle
J_{i}(x(0),u_{i},\tilde{u}_{-i})$ (1) s.t. $\displaystyle
x_{i}(k+1)=f_{i}(x_{i}(k),u_{i}(k))$ $\displaystyle
h(x_{i},\tilde{x}_{-i},O)\leq 0$

$J_{i}=S_{i}(x(T),T)+\sum_{k=0}^{T-1}L_{i}(x(k),\tilde{u}_{-i})$ is the cost
function for agent $i$. The stage cost $L_{i}$ can include distance, time, and
energy costs, and the terminal cost $S_{i}$ can include goal conditions. The
collision-free requirements are described using the constraints $h\leq 0$. The
hard constraints in $h$ can be added as weighted cost functions depending on
the solver used. $\tilde{u}_{-i}$ and $\tilde{x}_{-i}$ are the estimation of
other agents’ plans and states to prevent collisions since we assume no
communication between agents. To consider other agents during planning, it
needs to use predictions. In most cases where environmental constraints are
not strict, constant velocity predictions are well enough to provide collision
avoidance planning. However, cooperative predictions are required to generate
feasible interactions in cases like narrow-way interaction in Figure 1.
Therefore, we proposed to use an Imagined Potential Game (IPG) framework to
predict $\tilde{x}_{-i}$ during the planning of agent $i$.

Comparison with the centralized or distributed with sharing setting: In the
centralized setting, $U$ is solved together in a single large problem given
all agents’ initial and goal states simultaneously. The weighted
($\alpha_{i}$) costs of all agents are optimized in one problem.

$\displaystyle\min_{U}$ $\displaystyle\sum_{i=1}^{N}\alpha_{i}J_{i}(x(0),U)$
(2) s.t. $\displaystyle x(k+1)=f(x(k),u(k)),\quad h(x,O)\leq 0$

The distributed setting with sharing is quite similar to the centralized
setting; plans are solved separately but are shared with other agents,
enabling accurate predictions in a distributed setting [6] for cooperation.
Many game-theoretical interaction models operate in a similar setting. The
cost functions of all agents are shared to consider others’ behaviors and find
equilibrium plans for all agents.

###  III-B Differentiable Potential Game

We then introduce the definitions of dynamic games from previous works [10].
We describe a differential game by the compact notation of
$\Gamma_{x_{0}}^{T}=(N,\\{U_{i}\\}_{i=1}^{N},\\{J_{i}\\}_{i=1}^{N},\\{f_{i}\\}_{i=1}^{N})$,
where $x_{0}$ is the initial states of all agents, and each agent seeks to
optimize its cost $J_{i}$ under the dynamic $f_{i}$. The cost function
$J_{i}(x(0),U)=S_{i}(x(T))+\sum_{k=0}^{T-1}L_{i}(x(k),U(k))$ consists of
running cost $L_{i}$ and terminal cost $S_{i}$. We look for Nash equilibrium
solution of the dynamic game defined by:

###### Definition 1

Given a differential game
$\Gamma_{x_{0}}^{T}=(N,\\{U_{i}\\}_{i=1}^{N},\\{J_{i}\\}_{i=1}^{N},\\{f_{i}\\}_{i=1}^{N})$,
a set of control signals $U$ is an open-loop Nash equilibrium if, for every
agent $i\in[N]$:

$J_{i}(x_{0},u^{*})\leq J_{i}(x_{0},u_{i},u_{-i}^{*})$ (3)

At a Nash equilibrium, no agent has the incentive to change its current
control input $u_{i}^{*}$ as such a change would not yield any benefits, given
that all other agents’ controls $u_{-i}^{*}$ remain fixed. While this
equilibrium solution can best represent the cooperative multi-agent behavior
in the interaction, finding the Nash equilibrium solution is challenging since
there are $N$ coupled optimal control problems to solve simultaneously. Recent
progress in solving this problem, especially in robotics applications, find
efficient solutions to the problems under certain conditions. As introduced in
[10], problems in a potential differential game form can be solved by
formulating a single centralized optimal control problem. We summarize the
result in the following theorem.

###### Theorem 1

For a given differential game
$\Gamma_{x_{0}}^{T}=(N,\\{U_{i}\\}_{i=1}^{N},\\{J_{i}\\}_{i=1}^{N},\\{f_{i}\\}_{i=1}^{N})$,
if for each agent $i$, the running cost and terminal cost functions have the
structure of

$L_{i}(x(k),u(k))=p(x(k),u(k))+c_{i}(x_{-i}(k),u_{-i}(k))$ (4)
$S_{i}(x(T)=\bar{s}(x(T))+s_{i}(x_{-i}(T))$ (5)

then the open-loop Nash equilibria can be found by solving the following
optimal control problem

$\displaystyle\min_{U}$
$\displaystyle\sum_{k=1}^{T-1}p(x(k),u(k))+\bar{s}(x(T))$ (6) s.t.
$\displaystyle x_{i}(k+1)=f_{i}(x_{i}(k),u_{i}(k))$

The key takeaway from this theorem is that one can formulate a differentiable
potential game if all the cost function terms can be decomposed into potential
functions ($p(\cdot),\bar{s}(\cdot)$) that depend on the full state and
control vectors of all the agents, and other cost terms
($c_{i}(\cdot),s_{i}(\cdot)$) that have no dependence on the state and control
input of agent $i$. Then the optimal solution for both agents can be solved by
the centralized problem Eq.6 using only $p,\bar{s}$. The following section
will show how this theorem is used for distributed no-communication settings.
For each agent in the interaction, it assumes all agents are in the potential
game, but it doesn’t know the interaction parameters for other agents.
Therefore, each agent will solve a separate Imagined Potential Game (IPG)
using estimated parameters.

###  III-C System Notations and Assumptions

To simplify the problem, we make several assumptions on system dynamics. We
assume that all agents are modeled using the same unicycle dynamic model. The
state vector $x_{i}=[p_{x,i},p_{y,i},\theta_{i},v_{i}]^{T}$, the control
vector $u_{i}=[a_{i},w_{i}]^{T}$. The discrete-time dynamic equations of the
system are:

$\displaystyle p_{x,i}(k+1)$ $\displaystyle=p_{x,i}(k)+T_{s}\ v_{i}(k)\
cos(\theta_{i}(k))$ (7) $\displaystyle p_{y,i}(k+1)$
$\displaystyle=p_{y,i}(k)+T_{s}\ v_{i}(k)\ sin(\theta_{i}(k))$
$\displaystyle\theta_{i}(k+1)$ $\displaystyle=\theta_{i}(k)+T_{s}\ w_{i}(k)$
$\displaystyle v_{i}(k+1)$ $\displaystyle=v_{i}(k)+T_{s}\ a_{i}(k)$

System notations are summarized in Table I.

TABLE I: Notation describing common variable. | Definition |  | Definition (Default value)
---|---|---|---
$p_{x},p_{y}$ | position in 2D | Q | state weight ([0.01, 0.01, 0, 0])
$\theta$ | heading angle | R | input weight ([1, 1])
v | velocity | D | safety weight (40)
a | acceleration | B | back up weight (10)
w | angular velocity | r | safety radius (1.2$\sim$2.0)
$O$ | static obstacles | $T_{s}$ | sampling time (0.1)
|  |  |

##  IV Distributed multi-agent interaction modeling with imagined potential
game

As described in section III-A, for interactions under the distributed setting
with no shared plans, each agent is solving the problem in Eq. 1 but needs to
estimate the future inputs and states of other agents
$(\tilde{x}_{-i},\tilde{u}_{-i})$ to avoid collision. One common assumption in
navigation is the constant velocity prediction, which estimates other agents’
states with the current velocity. However, this doesn’t work for cooperation-
required cases, as shown in Figure 1. The potential game formulation in
section III-B gives optimal actions for cooperative agents but assumes the
cost parameters in $J_{i}$ are pre-known. In this paper, we use this
formulation to make cooperative predictions of other agents with an Imagined
Potential Game (IPG) setting but use estimated parameters of other agents to
solve the game.

Parameters in agent $i$’s cost function are the goal position $g_{i}$ and the
interaction parameters, including safety radius $r_{i}$, and different weights
$Q_{i},R_{i},D_{i},B_{i}$, each will affect the behavior in interaction. In
this project, we assume other agents’ long-term goal positions (intentions)
are already predicted. For interaction parameters, agents will assume other
agents using the same parameters they have, e.g., $\tilde{r}_{j}=r_{i}$ for
all $j\neq i$. This assumption is simple, but in practice, we found it strong
enough to simulate diverse interactions, especially when all participants are
cooperative agents. For cases where inaccurate estimation of others’
parameters causes failure, we can update the estimation online (see section
V-C).

###  IV-A Solving Potential game with estimated parameters

Based on Theorem 1, Nash equilibrium solutions of all agents can be solved by
Eq. 6 if the interaction can be formulated into a potential game. Here, we
show the running cost function $L_{i}(x)$ in the potential game, consisting of
the stage cost term $C_{tr,i}^{0:T-1}(x_{i},u_{i})$, the collision avoidance
term $C_{a,ij}(x_{i},x_{j})$ and the reverse avoidance term $C_{b,i}(x_{i})$.
The stage cost includes the minimum goal distance and input penalty terms:

$\displaystyle
C_{tr,i}^{0:T-1}(x_{i},u_{i})=(x_{i}-g_{i})^{T}Q_{i}(x_{i}-g_{i})+u_{i}^{T}R_{i}u_{i}$
(8)

The collision avoidance term is counted when the distance between two agents
$d_{ij}$ is smaller than the safety distance:

$C_{a,ij}(x_{i},x_{j})=\begin{cases}(d_{ij}-d_{safe})^{2}\cdot D_{i},&\text{if
$d_{ij}<d_{safe}$}\\\ 0,&\text{others}\end{cases}$ (9)

and satisfy the symmetric property
$C_{a,ij}(x_{i},x_{j})=C_{a,ji}(x_{j},x_{i})$ for potential game described in
[10].

The reverse avoidance term discourages the agent for moving backward:

$C_{b,i}(x_{i})=\begin{cases}|v_{i}|\cdot B_{i},&\text{if $v_{i}<0$}\\\
0,&\text{others}\end{cases}$ (10)

To prove this running cost function is a potential game, we can represent the
$p(x,u)$ and $c_{i}(x_{-i},u_{-i})$ in Theorem 1:

$\displaystyle p(x,u)=$
$\displaystyle\sum_{i=1}^{N}C_{tr,i}^{0:T-1}(x_{i},u_{i})$ (11)
$\displaystyle+\sum_{1\leq
i<j}C_{a,ij}(x_{i},x_{j})+\sum_{i=1}^{N}C_{b,i}(x_{i})$ $\displaystyle
c_{i}(x_{-i},u_{-i})=$ $\displaystyle-\sum_{j\neq
i}C_{tr,j}^{0:T-1}(x_{j},u_{j})$ (12)
$\displaystyle-\sum_{\begin{subarray}{c}1\leq j<k\\\ j,k\neq
i\end{subarray}}C_{a,jk}(x_{j},x_{k})-\sum_{j\neq i}C_{b,j}(x_{j})$

With this representation, we show that the running cost
$L_{i}(x_{i},u_{i})=p(x,u)+c_{i}(x_{-i},u_{-i})$ follows the Theorem 1,

Similarly, the terminal cost
$S_{i}(x(T))=C_{tr,i}^{T}(x_{i},u_{i})=\bar{s}(x(T))+s_{i}(x_{-i}(T))$, with
terminal cost term:

$\displaystyle
C_{tr,i}^{T}(x_{i},u_{i})=(x_{i}(T)-g_{i})^{T}Q_{i}(x_{i}(T)-g_{i})$ (13)

Set $\bar{s}(x(T))$ and $s_{i}(x_{-i}(T))$ to be :

$\displaystyle\bar{s}(x^{T})=\sum_{i=1}^{N}C_{tr,i}^{T}(x_{i}),s_{i}(x_{-i}^{T})=-\sum_{j\neq
i}^{N}C_{tr,j}^{T}(x_{j})$ (14)

We have the required terminal cost $S_{i}(x(T))$ in Theorem 1.

To address the problem in scenarios involving obstacles, we introduce some
extra constraints in addition to the existing dynamic constraints, including
the state boundary constraint, input constraint, and obstacle avoidance
constraint. These constraints can be added as weighted costs into $J_{i}$ and
don’t affect the potential game assumptions.

One important difference between centralized planning and the IPG setting is
the safety distance $d_{safe}$. For centralized planning, the maximum safety
distance between them is used $d_{safe}=max(r_{i},r_{j})$, for IPG, each agent
assumes others have the same safety distance, $d_{safe,i}=r_{i}$, unless it
changes its estimation.

The full IPG problem for each agent to solve is:

$\displaystyle\min_{U}$
$\displaystyle\sum_{k=1}^{T-1}p(x(k),u(k))+\bar{s}(x(T))$ (15) $\displaystyle
s.t.$ $\displaystyle x(k+1)=f(x(k),u(k))$ $\displaystyle x(0)=x_{0}$
$\displaystyle x_{L}\leq x(k)\leq x_{U}$ $\displaystyle u_{L}\leq u(k)\leq
u_{U}$ $\displaystyle r_{obs}-dis(x(k),O_{m})\leq 0,m=1...M$ $\displaystyle
r_{i}-dis(x_{i}(k),x_{j}(k))\leq 0,i,j=1...N$

where $x_{U},x_{L},u_{U},u_{L}$ are the state and input boundaries, and
$r_{obs}$ is the radius of the circle obstacle.

Algorithm 1 outlines the process of closed-loop simulation of the interaction:
each agent solves the IPG using iLQR. Following the receding horizon control
manner, only the first step for itself, denoted as $u_{i}^{0}$ is used. All
agents can solve their IPG in parallel; the closed-loop simulating process
continues until all agents are sufficiently close to their target goals. The
stored trajectories $\\{\tau_{i}\\}_{i=0}^{N}$ are the generated interactions.

Algorithm 1 Closed-loop Distributed multi-agent Planning using IPG

Initialize: U = 0, $\\{\tau_{i}\\}_{i=0}^{N}$ = empty

while termination condition not satisfied do

for i in N do in parallel

$\quad U\leftarrow iLQR(x_{0},g,U,O,Q_{i},R_{i},D_{i},B_{i},d_{safe,i})$

$\quad u_{i}^{0}\leftarrow U=[u_{1}^{0:T},u_{2}^{0:T},...,u_{N}^{0:T}]$

$\quad x_{next,i}\leftarrow f(x_{0},u_{i}^{0})$

end for

for i in N do

$\quad x_{0,i}\leftarrow x_{next,i}$

$\quad\tau_{i}\leftarrow[\tau_{i},x_{0,i}]$

end for

$x_{0}\leftarrow x_{0,i=1,...,N}$

end while

##  V Experiments

Figure 3: In the distributed setting, Vanilla agents without IPG are stuck at
a deadlock for a long time and take extremely long time to finish interaction.
IPG agents cooperatively interact with each other.

In this section, we present the simulating results under the distributed
multi-agent interaction setting to address the following key questions of
interest:

  1. 1.

Is the proposed framework able to solve the complex (infeasible) cases in
navigation under the distributed setting? Does it prevent the failures that
result from deadlock and collision?

  2. 2.

Is the proposed framework able to generate rich interactions with various
parameters? Is the behavior realistic and diverse for crowd simulation?

Environment settings: We first quantitatively evaluate and demonstrate the
interaction generation capability in the classic “narrow way” problem, the
most common but challenging indoor navigation scenario where only one agent
can pass at one time. Then, we demonstrate and analyze the interactions with
more agents or in more complex scenarios.

Comparison baselines: We use two baselines to compare the effect of our
proposed framework. 1) Vanilla: This is the vanilla version of distributed
multi-agent planning. Each agent is running a collision avoidance planning
algorithm. The agent will follow the previous plan if the planner cannot
generate a feasible collision-free solution. Note that an open-loop collision
solution might not cause an actual collision in the closed-loop simulation
since distributed agents use wrong predictions during open-loop planning. 2)
Brake: To avoid collision under infeasible solutions, the agent will brake and
stop if the planner solution has collision. This conservative implementation
can avoid collisions in simulation but is more likely to cause deadlocks.

Evaluation metrics: We generate 20 test cases with randomized starting and
goal points. To make sure interactions happen between agents, we enforce
starting and goal points on different sides of the hallway. The safety and
navigation parameters are randomly sampled from a pre-defined range for
different agents. The metrics for evaluating the interaction generation are 1)
Success rate: We test whether the two agents reach the target goals without
collision before the time limit. For failure cases, we separate the failure
caused by collision and failure by deadlocks. 2) Extra interacting time: We
use the total time for agents to finish interaction under a centralized
setting as a baseline to test how much extra time the agents spent in the
distributed setting.

Observation range in distributed setting: In the distributed setting, the ego-
agent will consider other agents’ behaviors unless they are blinded (e.g.,
there are obstacles on the line connecting the two agents) or other agents are
behind the ego-agent and out of a pre-defined sensing range.

###  V-A Interaction in “narrow way” in distributed setting

Both agents aim to reach the target positions sampled on the opposite side
while avoiding collisions with other agents and the walls. The experiment
results are shown in Table II.

[b]  Success Rate Deadlock Collision AET(second) Vanilla 13/20 2/20 5/20
+2.054 Brake 12/20 8/20 0/20 +2.308 IPG(Ours) 20/20 0/20 0/20 +0.395

TABLE II: Evaluation in Narrow-way Scenario

  * •

AET: Average Extra Time compared to Centralized in Success cases

The proposed method generated interactions successfully under all random
settings. The vanilla version has a higher success rate than the the brake
version but caused more collision during closed-loop simulating. For extra
time cost for interaction, we use the closed-loop interaction completion time
for the same setting under the centralized potential game setting as the
baseline and only calculate the average extra time for success cases. All
distributed settings experience increased interaction completion time, but our
IPG setting is the most efficient in solving interaction.

An illustrative comparison of interaction using different distributed
interaction settings is shown in Figure 3 using different stages of
interactions. The vanilla distributed agents stuck at a deadlock for a long
time during interaction. We didn’t show the brake agents since they
experienced deadlock and got stuck from the beginning. Using IPG, with an
imagined game in mind, agents assume the presence of cooperation and predict
others’ cooperation using the estimated parameters. This results in one agent
yielding to the other or assuming the other’s yielding in interaction.

We show how IPG recovers from open-loop deadlocks in Figure 4. In the
distributed setting, we don’t have a guarantee that agents don’t get
contradicting open-loop plans causing deadlocks. At 3.2s for the IPG setting,
the blue agent had wrong predictions on the green agent, causing the deadlock.
However, as the interaction progressed, we observed the predictions converging
to correct ones. If agents are assigned non-identical safety parameters, they
have a low chance of always getting symmetric and contradicting plans.

Figure 4: Vanilla distributed agents can collide during simulation when facing
deadlocks. Agents with IPG also experienced deadlock when the imagined
cooperation didn’t match. However, IPG agents can converge to success plans in
the closed-loop simulation.

###  V-B Realistic and Diverse Behaviors with IPG

Realistic Behavior in a T-intersection case A typical case and extension for
the narrow-way case is the T-intersection case, where the obstacles obscure
the agents until one arrives at the intersection. In centralized planning, the
optimal cooperative strategy is to wait at the starting point and move until
the other agent passes. However, in the distributed setting, the agent cannot
observe the other agent until it enters the intersection. Therefore, as shown
in Figure 2, the agent entered the intersection, realized it had to yield to
the other agent, and then retreated to wait. These realistic and human-like
reactions happen only in distributed settings. Full animations of interactions
and comparisons with baselines for different scenarios can be found on the
website[40]. In general, evaluating realistic behavior in rich interactions is
hard since these interactions only happen with certain initial conditions, and
there’s no quantitative metric for realism. We found adding imagined
cooperation into planning is an effective way to generate realistic behavior,
especially in indoor scenarios, where collision-free trajectories are often
not available for some agents.

Interactions of more than two agents Fig 5. illustrates the distinct behaviors
exhibited by three agents in a centralized and distributed IPG setting. To
demonstrate the different behaviors of agents with different safety radii, we
chose an open area to interact. In the distributed setting, agents lack the
safety distance information of others, and they assume that other agents
possess equal safety distance. Therefore, the agent with a larger safety
distance (green) will react more conservatively.

Figure 5: Three agents interacting with different safety radii.

Effects of different interaction parameters The effect of safety and cost
parameters on agents’ behavior is shown in Figure 6. The state cost weight $Q$
determines the flexibility in planning, and the safety weight $D$ affects its
conservatism in interaction. More examples are shown on the website[40].

Figure 6: Effects of different interaction parameters on behaviors.

###  V-C Interaction between Heterogeneous agents

In the previous two sections, we’ve demonstrated the proposed IPG framework
for simulating interactions under the distributed setting by preventing
collision and deadlocks. An extension of this framework, as mentioned in the
introduction, is to use the proposed framework as evaluation agents to
interact with tested agents. This requires the IPG agent to interact with
different types of agents.

In Figure 7, we demonstrate the cases where an IPG agent is asked to interact
with a vanilla agent using constant velocity prediction, and a ignore agent
ignoring other agents, the IPG agent can react wisely to those non-cooperative
agents. However, IPG agents with aggressive or non-adaptive parameters might
collide or get stuck in interactions. We claim various IPG agents can
represent different human agents in the simulator to test the robustness and
generalizability of social navigation algorithms.

Figure 7: Interactions between of heterogeneous agents.

##  VI Discussion

Conclusion: In this work, we propose an Imagined Potential Game framework
under the distributed without communication setting to model realistic
interactions in complex scenarios. We demonstrate the improvement of IPG
agents in the distributed setting in success rate and navigation efficiency in
simulating interactions and the ability to generate realistic and diverse
interactions in different scenarios.

Limitations and Future works The current framework is analyzed in selected
scenarios where cooperative interaction is required to solve the problem. In
future works, we will adapt the framework for general in-door scenarios where
obstacles have random and non-convex shapes. We also plan to develop a test
benchmark using IPG agents with various interaction parameters to test
different social navigation algorithms.

## References

  * [1] S. Tang and V. Kumar, “Safe and complete trajectory generation for robot teams with higher-order dynamics,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2016, pp. 1894–1901.
  * [2] A. Desai and N. Michael, “Online planning for quadrotor teams in 3-d workspaces via reachability analysis on invariant geometric trees,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 8769–8775.
  * [3] J. van den Berg, S. J. Guy, M. Lin, and D. Manocha, “Reciprocal n-body collision avoidance,” in _Robotics Research_ , C. Pradalier, R. Siegwart, and G. Hirzinger, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 3–19.
  * [4] D. Zhou, Z. Wang, S. Bandyopadhyay, and M. Schwager, “Fast, on-line collision avoidance for dynamic vehicles using buffered voronoi cells,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 2, pp. 1047–1054, 2017.
  * [5] B. Şenbaşlar, W. Hönig, and N. Ayanian, “Rlss: Real-time multi-robot trajectory replanning using linear spatial separations,” 2022.
  * [6] C. E. Luis, M. Vukosavljev, and A. P. Schoellig, “Online trajectory generation with distributed model predictive control for multi-robot motion planning,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 604–611, apr 2020.
  * [7] C. Wang, J. Bingham, and M. Tomizuka, “Trajectory splitting: A distributed formulation for collision avoiding trajectory optimization,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 8113–8120.
  * [8] A. Fonseca-Morales and O. Hernández-Lerma, “Potential Differential Games,” _Dynamic Games and Applications_ , vol. 8, no. 2, pp. 254–279, June 2018\. [Online]. Available: https://ideas.repec.org/a/spr/dyngam/v8y2018i2d10.1007_s13235-017-0218-6.html
  * [9] J. F. Fisac, E. Bronstein, E. Stefansson, D. Sadigh, S. S. Sastry, and A. D. Dragan, “Hierarchical game-theoretic planning for autonomous vehicles,” in _2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 9590–9596.
  * [10] T. Kavuncu, A. Yaraneri, and N. Mehr, “Potential ilqr: A potential-minimizing controller for planning multi-agent interactive trajectories,” 2021.
  * [11] M. Wang, Z. Wang, J. Talbot, J. C. Gerdes, and M. Schwager, “Game-theoretic planning for self-driving cars in multivehicle competitive scenarios,” _IEEE Transactions on Robotics_ , vol. 37, no. 4, pp. 1313–1325, 2021.
  * [12] J. Park, J. Kim, I. Jang, and H. J. Kim, “Efficient multi-agent trajectory planning with feasibility guarantee using relative bernstein polynomial,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 434–440.
  * [13] C. Wang, H.-C. Lin, S. Jin, X. Zhu, L. Sun, and M. Tomizuka, “Bpomp: A bilevel path optimization formulation for motion planning,” in _2022 American Control Conference (ACC)_. IEEE, 2022, pp. 1891–1897.
  * [14] R. Spica, E. Cristofalo, Z. Wang, E. Montijano, and M. Schwager, “A real-time game theoretic planner for autonomous two-player drone racing,” _IEEE Transactions on Robotics_ , vol. 36, no. 5, pp. 1389–1403, 2020.
  * [15] K. Miller and S. Mitra, “Multi-agent motion planning using differential games with lexicographic preferences,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 2022, pp. 5751–5756.
  * [16] S. L. Cleac’h, M. Schwager, and Z. Manchester, “Algames: A fast augmented lagrangian solver for constrained dynamic games,” 2021.
  * [17] F. Laine, D. Fridovich-Keil, C.-Y. Chiu, and C. Tomlin, “The computation of approximate generalized feedback nash equilibria,” 2022.
  * [18] N. Mehr, M. Wang, M. Bhatt, and M. Schwager, “Maximum-entropy multi-agent dynamic games: Forward and inverse solutions,” _IEEE Transactions on Robotics_ , vol. 39, no. 3, pp. 1801–1815, 2023.
  * [19] L. Wang, A. D. Ames, and M. Egerstedt, “Safety barrier certificates for collisions-free multirobot systems,” _IEEE Transactions on Robotics_ , vol. 33, no. 3, pp. 661–674, 2017.
  * [20] Z. Jian, S. Zhang, L. Sun, W. Zhan, N. Zheng, and M. Tomizuka, “Long-term dynamic window approach for kinodynamic local planning in static and crowd environments,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 6, pp. 3294–3301, 2023.
  * [21] G. Sartoretti, J. Kerr, Y. Shi, G. Wagner, T. K. S. Kumar, S. Koenig, and H. Choset, “Primal: Pathfinding via reinforcement and imitation multi-agent learning,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 3, pp. 2378–2385, 2019.
  * [22] B. Rivière, W. Hönig, Y. Yue, and S.-J. Chung, “Glas: Global-to-local safe autonomy synthesis for multi-robot motion planning with end-to-end learning,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 3, pp. 4249–4256, 2020.
  * [23] Q. Li, F. Gama, A. Ribeiro, and A. Prorok, “Graph neural networks for decentralized multi-robot path planning,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020, pp. 11 785–11 792.
  * [24] S. Batra, Z. Huang, A. Petrenko, T. Kumar, A. Molchanov, and G. S. Sukhatme, “Decentralized control of quadrotor swarms with end-to-end deep reinforcement learning,” 2021.
  * [25] J. Tordesillas and J. P. How, “Mader: Trajectory planner in multiagent and dynamic environments,” _IEEE Transactions on Robotics_ , vol. 38, no. 1, pp. 463–476, 2022.
  * [26] Z. Williams, J. Chen, and N. Mehr, “Distributed potential ilqr: Scalable game-theoretic trajectory planning for multi-agent interactions,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , 2023, pp. 01–07.
  * [27] R. A. Yeh, A. G. Schwing, J. Huang, and K. Murphy, “Diverse generation for multi-agent sports games,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * [28] S. Suo, S. Regalado, S. Casas, and R. Urtasun, “Trafficsim: Learning to simulate realistic multi-agent behaviors,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2021, pp. 10 400–10 409.
  * [29] Z.-H. Yin, L. Sun, L. Sun, M. Tomizuka, and W. Zhan, “Diverse critical interaction generation for planning and planner evaluation,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 7036–7043.
  * [30] W.-J. Chang, C. Tang, C. Li, Y. Hu, M. Tomizuka, and W. Zhan, “Editing driver character: Socially-controllable behavior generation for interactive traffic simulation,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 9, pp. 5432–5439, 2023.
  * [31] Q. Zhang, Y. Gao, Y. Zhang, Y. Guo, D. Ding, Y. Wang, P. Sun, and D. Zhao, “Trajgen: Generating realistic and diverse trajectories with reactive and feasible agent behaviors for autonomous driving,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 12, pp. 24 474–24 487, 2022\.
  * [32] Z. Zhou, J. Wang, Y.-H. Li, and Y.-K. Huang, “Query-centric trajectory prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * [33] L. Sun, C. Tang, Y. Niu, E. Sachdeva, C. Choi, T. Misu, M. Tomizuka, and W. Zhan, “Domain knowledge driven pseudo labels for interpretable goal-conditioned interactive trajectory prediction,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 13 034–13 041.
  * [34] L. Sun, W. Zhan, D. Wang, and M. Tomizuka, “Interactive prediction for multiple, heterogeneous traffic participants with multi-agent hybrid dynamic bayesian network,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_ , 2019, pp. 1025–1031.
  * [35] B. Piccoli and A. Tosin, “Pedestrian flows in bounded domains with obstacles,” _Continuum Mechanics and Thermodynamics_ , vol. 21, no. 2, pp. 85–107, apr 2009. [Online]. Available: https://doi.org/10.1007%2Fs00161-009-0100-x
  * [36] W. van Toll, N. Jaklin, and R. Geraerts, “Towards believable crowds : A generic multi-level framework for agent navigation,” 2015. [Online]. Available: https://api.semanticscholar.org/CorpusID:14620077
  * [37] W. G. van Toll, A. F. Cook IV, and R. Geraerts, “Real-time density-based crowd simulation,” _Computer Animation and Virtual Worlds_ , vol. 23, no. 1, pp. 59–69, 2012. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/cav.1424
  * [38] S. Sarmady, F. Haron, and A. Z. H. Talib, “Modeling groups of pedestrians in least effort crowd movements using cellular automata,” in _2009 Third Asia International Conference on Modelling and Simulation_ , 2009, pp. 520–525.
  * [39] N. K. Mahato, A. Klar, and S. Tiwari, “Particle methods for multi-group pedestrian flow,” 2017.
  * [40] [Online]. Available: https://sites.google.com/berkeley.edu/distributed-interaction/