SF2A 2021

# Nonlinear simulations of tides in the convective envelopes
of low-mass stars and giant gaseous planets

A. Astoul  Department of Applied Mathematics, School of Mathematics,
University of Leeds, Leeds, LS2 9JT, UK  A. J. Barker1

###### Abstract

In close two-body astrophysical systems, such as binary stars or Hot Jupiter
systems, tidal interactions often drive dynamical evolution on secular
timescales. Many host stars and presumably giant gaseous planets feature a
convective envelope. Tidal flows generated therein by the tidal potential of
the companion can be dissipated through viscous friction, leading to the
redistribution and exchange of angular momentum within the convective shell
and with the companion, respectively. In the tightest systems, nonlinear
effects are likely to have a significant impact on the tidal dissipation and
trigger differential rotation in the form of zonal flows, as has been shown in
previous studies. In this context, we investigate how the addition of
nonlinearities affect the tidal flow properties, and energy and angular
momentum balances, using 3D nonlinear simulations of an adiabatic and
incompressible convective shell. In our study, we have chosen a body forcing
where the equilibrium tide (the quasi-hydrostatic tidal flow component) acts
via an effective forcing to excite tidal inertial waves in a spherical shell.
Within this set-up, we show new results for the amplitude of the energy stored
in zonal flows, angular momentum evolution, and its consequences on tidal
dissipation in the envelopes of low-mass stars and giant gaseous planets.

###### keywords:

star-planet interactions – tides – hydrodynamics – inertial waves – nonlinear
simulations

##  1 Introduction

In tight stellar and exoplanetary systems, tidal interactions are a key
process to understand orbital migration and circularisation, spin
synchronisation, and possibly the low obliquities of the closest bodies (e.g.
Mathis 2019; Ogilvie 2014). For low-mass stars and Hot Jupiter planets which
feature a convective envelope, the dissipation of inertial waves restored by
the Coriolis acceleration significantly contributes to the tidal dissipation.
This is particularly true in the early stages of the life of rapidly rotating
low-mass stars, as shown for example in Mathis (2015), Bolmont & Mathis
(2016), and Barker (2020), and possibly may explain the rapid orbital
expansion measured for Titan through resonant-locking of inertial modes in
Jupiter (Lainey et al. 2020). Furthermore, for the most compact two-body
systems, internal nonlinear fluid effects can become important (Barker et al.
2016), especially when considering the small-scales of inertial waves in
spherical shells (Rieutord et al. 2001). This typically happens when the tidal
amplitude parameter***It is a measure of the ratio of the tidal gravity to the
self-gravity at the surface of the perturbed body (e.g. Barker et al. 2016).
$\epsilon$ is large, as for the ultra short-period Hot Jupiter WASP-19 b
($\epsilon\sim 0.05$, e.g. Ogilvie 2014). In Favier et al. (2014, denoted
Paper I in the following), the authors performed a nonlinear numerical study
of tidally-forced inertial waves in spherical shells. They found that the
amplitude of the tidal dissipation could greatly differ from linear tidal
response predictions (e.g. as in Ogilvie 2009) due to the inhomogeneous
deposition of angular momentum which generates strong azimuthal zonal flows
(see also Astoul et al. 2021). They also observed for some forcing frequencies
unexpected evolution of the angular momentum, pushing the body away from
synchronisation. Building upon their initial study, we have performed
nonlinear hydrodynamical simulations of tidal waves in an adiabatic and
incompressible convective envelope, but with different boundary conditions and
tidal forcing. While they imposed a radial velocity through the outer boundary
to force the tidal flow, we use an effective body force which accounts for the
residual action of the large-scale non-wavelike tidal flow in exciting
inertial waves (Ogilvie 2013), with stress-free impenetrable boundary
conditions at the inner and outer boundaries. Within this more realistic set-
up, we are able to separate wavelike and non-wavelike contributions in the
nonlinear terms to elucidate the unphysical behaviour obtained for certain
frequencies in Paper I. By removing the relevant nonlinearities that produce
this unphysical behaviour (which should be less important than the ones we
retain in reality), we present new results regarding the amplitude and spatial
structure of kinetic energy, tidal dissipation, and azimuthal component of the
velocity of inertial waves propagating in an adiabatic and incompressible
convective shell.

Figure 1: Left: Terms in the energy balance (Eq. (3)) over time. Middle:
Kinetic energy over time with or without the various nonlinear terms (nl).
Right: Dissipation spectrum $D_{\nu}$ of wavelike-wavelike nonlinear
simulations as a function of tidal forcing frequency in the fluid frame
$\omega/\Omega^{*}$, where $\Omega^{*}$ is the modified spin rate due to the
creation of zonal flows (see Paper 1 for a definition), also showing the
energy in the differential rotation $\mathrm{E_{dr}}$. In the three panels,
$C\approx 0.009$.

##  2 Governing equations and energy balance for nonlinear tidal inertial
waves

We model the outer convective envelope of our low-mass star or giant gaseous
planet as an incompressible and adiabatic spherical shell as a first approach
to treat the nonlinear hydrodynamic tidal response. The action of turbulent
convection on tides is considered through a viscous term $\nu\Delta\bm{u}$
(e.g. Duguid et al. 2020, and references therein), where $\nu$ is the
(constant) effective/turbulent viscosity and $\bm{u}$ is the total tidal flow.
The flow $\bm{u}$ is decomposed into a large-scale non-wavelike component
$\bm{u}_{\mathrm{nw}}$ (the equilibrium tide in this model) and a wave-like
component $\bm{u}_{\mathrm{w}}$ (the dynamical tide, consisting of inertial
waves) such that $\bm{u}=\bm{u}_{\mathrm{nw}}+\bm{u}_{\mathrm{w}}$ as in
Ogilvie (2013, building upon earlier ideas reviewed in e.g. ). The equations
of motion and continuity for tidally-forced inertial waves in the fluid frame
are then:

$\displaystyle\partial_{t}\bm{u}_{\mathrm{w}}+(\bm{u}\cdot\bm{\nabla})\bm{u}+2\bm{\Omega}\wedge\bm{u}_{\mathrm{w}}$
$\displaystyle=-\frac{\bm{\nabla}p_{\mathrm{w}}}{\rho}+\bm{f}_{\mathrm{t}}+\nu\Delta\bm{u},$
(1) $\displaystyle\bm{\nabla}\cdot\bm{u}_{\mathrm{w}}$ $\displaystyle=0,$ (2)

which are solved together with stress-free and impenetrable boundary
conditions on the inner and outer boundaries at radii $r=\alpha R$ and $r=R$,
respectively, with $\alpha$ the radial aspect ratio and $R$ the radius of the
body. We have introduced $\bm{\Omega}$, the initial uniform rotation rate
along the vertical axis, $p_{\mathrm{w}}$, the reduced wavelike pressure, and
$\rho$, the (uniform) mean fluid density. The effective tidal forcing is
$\bm{f}_{\mathrm{t}}=-2\bm{\Omega}\wedge\bm{u}_{\mathrm{nw}}$, which takes
into account the remaining action of non-inertial terms (here only the
Coriolis acceleration) on the non-wavelike flow, since the equilibrium tide
satisfies a quasi-hydrostatic equation of motion. The non-wavelike flow can be
written
$\bm{u}_{\mathrm{nw}}=\mathrm{Re}[C~{}i\omega\bm{\nabla}\left[f(r)Y^{2}_{2}(\theta,\varphi)\right]\mathrm{e}^{-i\omega
t}]$, where $C$ is proportional to the tidal amplitude parameter $\epsilon$
(with a factor depending on the internal structure), $\omega$ is the tidal
forcing frequency, $f(r)$ is a dimensionless radial function required for the
scalar potential to satisfy Laplace’s equation, and
$Y^{2}_{2}(\theta,\varphi)$ is the dominant quadrupolar spherical harmonic
function for colatitude $\theta$ and azimuth $\varphi$ (Ogilvie 2013). Our
approach considers the non-wavelike flow to be an imposed “background flow” to
study the instantaneous tidal response (relative to tidal evolutionary
timescales), as described in Barker & Astoul (2021). We use units of length
and time equal to $R$ and $\Omega^{-1}$, respectively.

Taking the scalar product of Eq. (1) with $\rho\bm{u}_{\mathrm{w}}$ and
integrating spatially, we obtain the energy balance for tidal inertial waves:

$\partial_{t}{\langle
K_{\mathrm{w}}\rangle_{V}}=\mathcal{I}_{\mathrm{nw-w}}+\mathcal{I}_{\mathrm{w-nw}}-D_{\nu}+P_{\mathrm{t}},$
(3)

where $\langle
K_{\mathrm{w}}\rangle_{V}=\langle\rho|{\bm{u}_{\mathrm{w}}}|^{2}/2\rangle_{V}$
is the wavelike kinetic energy integrated over the volume $V$,
$\mathcal{I}_{\mathrm{i-j}}=-\langle\rho\bm{u}_{\mathrm{w}}\cdot(\bm{u}_{i}\cdot\bm{\nabla})\bm{u}_{j}\rangle_{V}$,
with $i,j\in\\{\mathrm{w,nw}\\}$, are the terms coming from the mixed (w-nw
and nw-w) nonlinearities which transfer energy between the non-wavelike and
wavelike flows, $D_{\nu}$ is the viscous dissipation of wavelike flows†††The
dissipation of the non-wavelike flow has been found to be negligible in our
simulations since $\nu$ is small, as is also typically expected in reality.
and the energy injected into tidal waves by the forcing is
$P_{\mathrm{t}}=\langle\bm{u}_{\mathrm{w}}\cdot\bm{f}_{\mathrm{t}}\rangle_{V}$.
Note that $\mathcal{I}_{\mathrm{i-i}}=-\oint_{\partial
V}K_{\mathrm{i}}\,\bm{u}_{\mathrm{w}}\cdot{\bm{n}}\mathrm{d}S=0$ with $\bm{n}$
the unit normal vector to the bounding surface $\partial V$, using the
divergence theorem along with the incompressible and impenetrable assumptions
(which can also be applied to demonstrate that
$\langle\bm{u}_{\mathrm{w}}\cdot\nabla p_{w}\rangle_{V}=0$). One can also
demonstrate that $\mathcal{I}_{\mathrm{nw-w}}=-\oint_{\partial
V}K_{\mathrm{w}}~{}\bm{u}_{\mathrm{nw}}\cdot\bm{n}\mathrm{d}S$, which does not
necessarily vanish in our idealised spherical model. However, in a more
realistic ellipsoidal model, the streamlines of the non-wavelike tidal flow in
the bulge frame are expected to be tangential to the boundary so that
$\bm{u}_{\mathrm{nw}}\cdot\bm{n}=0$, cancelling $\mathcal{I}_{\mathrm{nw-w}}$
in that frame (see also Barker & Astoul 2021). The only physical nonlinear
term expected to contribute to the energy exchange between inertial waves and
the non-wavelike tidal flow is
$\mathcal{I}_{\mathrm{w-nw}}=-\langle\rho\bm{u}_{\mathrm{w}}\cdot(\bm{u}_{\mathrm{w}}\cdot\bm{\nabla})\bm{u}_{\mathrm{nw}}\rangle_{V}$,
namely Reynolds stresses involving correlations between wavelike flow
components.

##  3 Analysis of nonlinear simulations

To solve Eqs. (1) and (2), we use the pseudo-spectral code
MagIC‡‡‡https://magic-sph.github.io/ (e.g. Christensen et al. 2001) using
Chebyshev polynomials in the radial direction and a spherical harmonic
decomposition in the azimuthal and latitudinal directions, utilising the SHTns
library for fast spherical harmonic transforms (Schaeffer 2013). In these
initial simulations, the Ekman number is set to $\mathrm{Ek}=\nu/(\Omega
R^{2})=10^{-5}$, the aspect ratio is $\alpha=0.5$, and we vary the tidal
forcing frequency $\omega$ and the tidal amplitude $C$. Our typical spatial
resolution is $N_{r}=97$ Chebyshev points in radius and spherical harmonics up
to degree $l_{\mathrm{max}}=85$. Further details about the simulations will be
presented elsewhere.

In the left panel of Fig. 1, we display each term in the energy balance (Eq.
(3)) for $C\approx 0.009$ and $\omega=1.1$. The term
$\mathcal{I}_{\mathrm{nw-w}}$ represents an unrealistic flux through the
boundary which is not negligible compared to the tidal dissipation and tidal
power $P_{\mathrm{t}}$, unlike the “physical” transfer term
$\mathcal{I}_{\mathrm{w-nw}}$, which is very small here. This is especially
true for low to moderate tidal amplitudes satisfying $C\lesssim 0.05$, but not
for higher tidal amplitude (e.g. $C\sim 0.1$) where
$\mathcal{I}_{\mathrm{w-nw}}$ can contribute more significantly. As a result,
we have chosen to switch off nonlinear terms involving non-wavelike tides in
the momentum equation, which is justified except for the highest tidal
amplitudes considered ($C\lesssim 0.05$). Our choice is also motivated by the
fact that the total angular momentum
$\bm{L}=\langle\rho\bm{r}\wedge\bm{u}\rangle_{V}$ can be shown to evolve as:

$\partial_{t}\bm{L}=-\oint_{\partial
V}\rho(\bm{r}\wedge\bm{u})\bm{u}_{\mathrm{nw}}\cdot\bm{n}~{}\mathrm{d}S.$ (4)

Thus, $\bm{L}$ is not conserved in this model (as $\bm{u}_{\mathrm{nw}}$ is
perfectly maintained) only because of the unphysical non-wavelike flux through
the spherical boundaries, which drives the unexpected evolution of the total
angular momentum as in Fig. 17 of Paper I.

We find that when all nonlinearities are included, the kinetic energy and
tidal dissipation in our simulations are almost identical to those obtained in
Paper I (after appropriate rescaling). In the middle panel of Fig. 1, we show
that the kinetic energy including all nonlinearities highly departs from the
linear prediction for $\omega=1.05$ and $1.1$, with the departure being
somewhat less pronounced when considering only the wavelike-wavelike
nonlinearity. In both cases this departure from linear predictions may
strongly depend on whether wave attractors are produced (i.e. wave focusing
along limit cycles) or to the presence of hidden large-scale flows (see
Ogilvie 2009; Lin & Ogilvie 2021). When one or both of these features are
present the linear dissipation is enhanced, as we can see in the right panel
of Fig. 1. At the beginning of these simulations, kinetic energy and
dissipation converge towards their linear values, and then evolve away for
$\omega=1.05$ and $1.1$ due to the establishment of strong zonal flows
indicated by the energy in the differential rotation (colorbar, see Paper 1
and Tilgner 2007, for a definition). Since the total angular momentum is
conserved here (as $\bm{u}_{\mathrm{nw}}$ is perfectly maintained), a steady
state is reached at the end of the simulation ($\max(\Omega t)=5000$). The
inhomogeneous deposition of kinetic energy (and angular momentum) near the
rotation axis triggers cylindrical differential rotation from the pole to the
equator as shown in Fig. 2 for the case with $\omega=1.1$. The final
dissipation of wavelike-wavelike nonlinear simulations can be neatly recovered
by running new linear simulations with a background cylindrical differential
rotation, using the zonal flows extracted from the associated nonlinear
simulation (right panel of Fig. 1 using the flow shown in e.g. Fig. 2). We
have therefore demonstrated that the effects of zonal flows on tidal waves
explains the departure of tidal dissipation rates in these simulations from
linear theoretical predictions assuming uniform rotation.

Figure 2: Azimuthal average of the kinetic energy $u^{2}$ and azimuthal
velocity $v_{\varphi}$ at times $\Omega t=245$ and $\Omega t=995$ in one
quarter of the meridional plane (due to equatorial and axial symmetry) for
$\omega=1.1$ and $C=0.009$.

##  4 Conclusions

We have performed new nonlinear hydrodynamical simulations of tidally-forced
inertial waves in an incompressible and adiabatic convective shell. Our
approach is different from that in Paper 1 by the use of (a more realistic)
effective tidal body force to excite inertial waves, along with stress-free
and impenetrable boundary conditions. Within this framework, we analysed in
detail the energy transfer terms between wavelike and non-wavelike tidal
flows, and demonstrated that an “unphysical” energy flux through the spherical
boundaries was responsible for the unrealistic angular momentum evolution
obtained in certain cases in Paper 1. We have removed the mixed wavelike-non-
wavelike nonlinearities responsible, which can be further justified by scaling
arguments (since wave-wave nonlinearities are predicted to dominate for short
wavelength inertial waves). Differential rotation in the form of zonal flows
is triggered inside the shell due to wavelike-wavelike nonlinearities and
there are important departures from linear predictions as observed in Paper 1,
though the differences here are less pronounced in the cases we have
presented. Finally, we have also demonstrated that the departure of the
nonlinear tidal dissipation from the linear prediction is explained by the
zonal flows that are generated.

###### Acknowledgements.

This research has been supported by STFC grants ST/R00059X/1 and ST/S000275/1.
Simulations were undertaken using the MagIC software on ARC4 and DiRAC, part
of the High Performance Computing facilities at the University of Leeds and
Leicester.

## References

  * Astoul et al. (2021) Astoul, A., Park, J., Mathis, S., Baruteau, C., & Gallet, F. 2021, A&A, 647, A144
  * Barker (2020) Barker, A. J. 2020, MNRAS, 498, 2270
  * Barker & Astoul (2021) Barker, A. J. & Astoul, A. A. V. 2021, MNRAS, 506, L69
  * Barker et al. (2016) Barker, A. J., Braviner, H. J., & Ogilvie, G. I. 2016, MNRAS, 459, 924
  * Bolmont & Mathis (2016) Bolmont, E. & Mathis, S. 2016, Celestial Mechanics and Dynamical Astronomy, 126, 275
  * Christensen et al. (2001) Christensen, U. R., Aubert, J., Cardin, P., et al. 2001, Physics of the Earth and Planetary Interiors, 128, 25
  * Duguid et al. (2020) Duguid, C. D., Barker, A. J., & Jones, C. A. 2020, MNRAS, 497, 3400
  * Favier et al. (2014) Favier, B., Barker, A. J., Baruteau, C., & Ogilvie, G. I. 2014, MNRAS, 439, 845
  * Lainey et al. (2020) Lainey, V., Casajus, L. G., Fuller, J., et al. 2020, Nature Astronomy, 4, 1053
  * Lin & Ogilvie (2021) Lin, Y. & Ogilvie, G. I. 2021, arXiv e-prints, arXiv:2108.08515
  * Mathis (2015) Mathis, S. 2015, A&A, 580, L3
  * Mathis (2019) Mathis, S. 2019, in EAS Publications Series, Vol. 82, EAS Publications Series, 5–33
  * Ogilvie (2009) Ogilvie, G. I. 2009, MNRAS, 396, 794
  * Ogilvie (2013) Ogilvie, G. I. 2013, MNRAS, 429, 613
  * Ogilvie (2014) Ogilvie, G. I. 2014, ARA&A, 52, 171
  * Rieutord et al. (2001) Rieutord, M., Georgeot, B., & Valdettaro, L. 2001, Journal of Fluid Mechanics, 435, 103
  * Schaeffer (2013) Schaeffer, N. 2013, Geochemistry, Geophysics, Geosystems, 14, 751
  * Tilgner (2007) Tilgner, A. 2007, Phys. Rev. Lett., 99, 194501
  * Zahn (2008) Zahn, J. P. 2008, in EAS Publications Series, Vol. 29, EAS Publications Series, ed. M. J. Goupil & J. P. Zahn, 67–90


# Intention Communication and Hypothesis Likelihood
in Game-Theoretic Motion Planning

Makram Chahine1, Roya Firoozi2, Wei Xiao1, Mac Schwager2 and Daniela Rus1 1
Computer Science and Artificial Intelligence Lab, Massachusetts Institute of
Technology {chahine, weixy<EMAIL_ADDRESS>Department of Aeronautics &
Astronautics, Stanford University {rfiroozi<EMAIL_ADDRESS>
###### Abstract

Game-theoretic motion planners are a potent solution for controlling systems
of multiple highly interactive robots. Most existing game-theoretic planners
unrealistically assume a priori objective function knowledge is available to
all agents. To address this, we propose a fault-tolerant receding horizon
game-theoretic motion planner that leverages inter-agent communication with
intention hypothesis likelihood. Specifically, robots communicate their
objective function incorporating their intentions. A discrete Bayesian filter
is designed to infer the objectives in real-time based on the discrepancy
between observed trajectories and the ones from communicated intentions. In
simulation, we consider three safety-critical autonomous driving scenarios of
overtaking, lane-merging and intersection crossing, to demonstrate our
planner’s ability to capitalize on alternative intention hypotheses to
generate safe trajectories in the presence of faulty transmissions in the
communication network.

##  I Introduction

Robot control in interactive environments is very challenging due to the
complexity of evaluating the impact of an agent’s actions on the behaviour of
others. Predict-then-plan strategies have substantially been addressed in the
literature; trajectories of other agents are predicted first, then used as
constraints in a single-agent planning scheme. However this decoupling ignores
the inherently interactive nature of the problem. Indeed, in order to capture
the reactive nature of agents in a scene, a robot must be able to
simultaneously predict the trajectories of other agents while planning its own
trajectory. Differential game theory provides a suitable framework for
expressing these types of multi-agent planning problems without requiring a
priori predictive assumptions. Solvers exist to find Nash equilibrium
trajectories for such problems in real-time, and although they provide open-
loop solutions to the motion planning problem over the time horizon
considered, repeatedly resolving the game as new information is processed
generates a policy that is closed-loop in the model-predictive control (MPC)
sense.

The main challenge of decentralized implementation of game-theoretic motion
planners is that common knowledge of the dynamics, constraints and objective
functions of all partaking players is required. One can argue that dynamics
and constraints could be assumed or inferred in structured environments e.g.
in driving scenarios. However, for a player to assign an objective function to
each of the other agents, they must have a representation of their intentions.
We propose to use vehicle-to-vehicle (V2V) communication for vehicles to share
their intentions with one another.

Robotics settings can hugely benefit from communication technologies. In the
current robotics settings, i.e. autonomous driving, each agent acts as an
isolated agent, choosing its own control decisions solely based on its own on-
board sensing information.

Figure 1: Overtaking on a highway. As the red car signals to the right, the
green car anticipates it making way and accelerates. If the red car’s
signalling is reliable and it does move over, the green car would have
capitalized on this communicated intention to reach its objective faster (left
scenario). On the other hand, if the red car does not switch lanes, the green
car runs the risk of collision if it is unable to react in time (right
scenario).

However, the collaborative communication of agents’ intentions over a V2V
network can significantly improve the quality of planned trajectories, as
vehicles can reason about the actions that others might take to reach their
objective. A simple and very frequent real-life example is that of overtaking,
where knowledge of the other vehicle’s intention allows for a more efficient
maneuver as shown in Fig. 1. In the game-theoretic framework, the
communication of intention is best formalized as the sharing of one’s cost
function, which directly intervenes in computing the Nash equilibrium
trajectory solution. In cooperative settings, we could thus design
collaborative planning solutions requiring agents to communicate their cost
functions at regular intervals. In turn, this raises questions about the
security and robustness of the communication protocol to breaches and faults
in safety-critical applications. In the example shown above in Fig. 1, we
present a case where faulty communication could lead to a collision.

In this paper, we investigate the use of V2V communication as a solution to
the safety shortcomings arising from cost function mismatch in MPC
implementations of game-theoretic motion planners. We specify the requirements
such a solution would need to satisfy, namely robustness to communication
faults and adaptability throughout the unfolding of an evolving multi-agent
scene. The following assumptions are made in our proposed framework:

  1. 1.

A cooperative setting is assumed in which vehicles are connected using a V2V
communication network.

  2. 2.

A set of possible intentions (hypotheses) for each vehicle is available to be
used in real time.

Our proposed planner updates hypothesis likelihoods, allowing an agent to
reassess the reliability of communicated intentions coming from each player in
the scene. With a hypothesis likelihood assigned to each of the other players
intentions, the agent adapts its version of a dynamic game at each replanning
interval. Our main contributions are,

  1. 1.

An online Bayesian inference approach to estimate the relative likelihoods of
available hypotheses based on past observations in the context of dynamic
games with communicated cost functions,

  2. 2.

A communication-based game-theoretic receding horizon motion planner is
designed to be resilient to faulty transmissions and safer than naive MPC
implementations of dynamic game motion planners,

  3. 3.

Simulations on three autonomous driving scenarios: overtaking, lane-merging
and intersection crossing, empirically showcasing the superiority of our
approach in planning safe trajectories and avoiding crashes.

##  II Related Work

Dynamic Games. Differential game theory provides a framework to model multi-
agent interactions without requiring a priori assumption about predicting
other agents’ behaviors [1]. Differential games are characterized by solving
Hamilton-Jacobi equations in which all agent’s Hamiltonians are coupled with
one another. However, most of these methods do not admit analytical solutions,
suffer from the curse of dimensionality and cannot be solved efficiently using
numerical techniques. To make the problem tractable, iterative linear-
quadratic (iLQ) games are proposed in [2],[3]. In the iLQ games at each
iteration, the problem is solved locally by successive approximation using
linear dynamics and quadratic cost. The iterative linear quadratic game can be
solved as a coupled Riccati differential equation and provides feedback
strategies which form a feedback Nash equilibrium of the game [4], [5]. These
approximation techniques are computationally efficient and suitable for real-
time applications, but since the feedback policies are fixed, these approaches
cannot adapt to any change in the behavior of the other agents. In other
words, the game structure is assumed to remain fixed. In contrast, our
proposed approach allows adaptability to any change in the game structure and
provides open-loop Nash equilibrium, instead.

Game-theoretic planning A game-theoretic setting allows to model both
adversarial and cooperative agents. In fact, scenarios such as autonomous
driving, where robots need to interact with other intelligent agents, are
fundamentally game-theoretic [6, 7], [8]. Formalizing such interactions as a
game, robots can weigh the impact of their decisions on the actions of other
agents [9], even in competitive settings such as drone or car racing [10, 11].
Most game-theoretic works do not assume availability of a communication
network among the agents and model the interactions as a game formulation. In
[12, 13, 14] data-driven methods are presented to infer objective functions of
other agents online in game theoretic planning without communication. On the
other hand distributed optimization approaches assume the existence of a
communication network and solve the optimization based on the received
communicated predictions [15], [16]. They devise a communication and planning
protocol in which all the agents share their predicted planned trajectories.
One drawback of the former approach is that in an uncertain and dynamic
environment such as autonomous driving setting, solving a game with a fixed
structure may not be robust with respect to adversarial agents’ behavior.
Also, distributed optimization approaches that completely rely on the
communicated trajectories and make use of predictions in the planning are
susceptible to adversarial cyber-attacks. In contrast, our proposed approach
considers a combination of the two, in which we consider solving a game while
a communication network is assumed among the agents and they make use of
communicated information to update their reliability towards other agents.
Within the receding-horizon game-theoretic framework the agents update the
game cost function according to the communicated information about other
agents’ intentions. Incorporating reliability into the game formulation leads
to quick adaptation and promotes resilience against failures.

Communication-based planning and control. Based on vehicle-to-infrastructure
(V2I) communication, the emergence of connected and automated vehicles [17],
[18], [19] has the potential to drastically improve the performance of
vehicles in traffic bottlenecks (such as merging, intersection, etc.),
ultimately saving energy, and avoiding congestion and accidents. Optimal
control problem are used in some of these approaches [20], while Model
Predictive Control (MPC) techniques are employed as an alternative [21],
mainly to take additional constraints and disturbances into account [22]. All
the above mentioned works assume that information shared through V2I is trust-
worthy. While in this work, we consider communication-based control in the
presence of faulty transmissions on the communication network.

##  III Problem Statement

We consider a sequence of Generalized Nash Equilibrium Problems (GNEPs)
involving $N$ players $i\in\\{1,\dots,N\\}$ over a horizon of $H$ time steps.
An agent $i$’s state at time step index $t$ is denoted
$\mathbf{x}_{t}^{i}\in\mathbb{R}^{n^{i}}$ and control input
$\mathbf{u}_{t}^{i}\in\mathbb{R}^{m^{i}}$, with dimensions of agent $i$’s
state and control $n^{i}$ and $m^{i}$. Let
$\mathbf{x}_{t}=[\mathbf{x}_{t}^{1,\top},\dots,\mathbf{x}_{t}^{N,\top}]^{\top}\in\mathbb{R}^{n}$
denote the joint state and
$\mathbf{u}_{t}=[\mathbf{u}_{t}^{1,\top},\dots,\mathbf{u}_{t}^{N,\top}]^{\top}\in\mathbb{R}^{m}$
denote the joint control of all agents at time $t$, with joint dimensions
$n=\sum_{i}n^{i}$ and $m=\sum_{i}m^{i}$. We define player $i$’s policy as
$\pi^{i}=[\mathbf{u}_{1}^{i,\top},\dots,\mathbf{u}_{H-1}^{i,\top}]^{\top}\in\mathbb{R}^{\tilde{m}^{i}}$
where $\tilde{m}^{i}=m^{i}(H-1)$ denotes the dimension of the entire
trajectory of agent $i$’s control inputs. The notation $\neg i$ indicates all
agents except $i$, for instance $\pi^{\neg i}$ represents the vector of the
agents’ policies except that of $i$. Also, let
$X=[\mathbf{x}_{1}^{\top},\dots,\mathbf{x}_{H-1}^{\top}]^{\top}\in\mathbb{R}^{\tilde{n}}$,
with $\tilde{n}=n(H-1)$, denote the trajectory of joint state variables
resulting from the application of the joint control inputs to the dynamical
system defined by
$f:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ such that,

$\displaystyle\mathbf{x}_{t+1}=f(\mathbf{x}_{t},\mathbf{u}_{t})$ (1)

Over the whole trajectory we can express the above kinodynamic constraints
with $\tilde{n}$ equality constraints,

$\displaystyle D(X,\pi^{1},\dots,\pi^{N})=D(X,\pi)=0\in\mathbb{R}^{\tilde{n}}$
(2)

The cost function of each player $i$ depends on its policy $\pi^{i}$ as well
as on the joint state trajectory $X$, which is common to all players, such
that $\forall i\in\\{1,\dots,N\\}$,

$\displaystyle
J^{i}(X,\pi^{i})=c_{H}^{i}(\mathbf{x}_{H})+\sum_{t=1}^{H-1}c_{t}^{i}(\mathbf{x}_{t},\mathbf{u}_{t}^{i})$
(3)

Notice that as player $i$ minimizes $J^{i}$ with respect to $X$ and $\pi^{i}$,
the selection of $X$ is constrained by the other players’ strategies
$\pi^{\neg i}$ and the dynamics of the joint system via (2). In addition, the
strategy $\pi^{i}$ could be required to satisfy (safety) constraints that
depend on the joint state trajectory $X$ as well as on the other players
strategies $\pi^{\neg i}$ . This can be expressed with a set of $g$ inequality
constraints,

$\displaystyle C(X,\pi)\leq 0\in\mathbb{R}^{g}$ (4)

where
$C:\mathbb{R}^{\tilde{n}}\times\mathbb{R}^{\tilde{m}}\rightarrow\mathbb{R}^{g}$.
The GNEP we form is the problem of minimizing (3) for all players
$i\in\\{1,\dots,N\\}$ with respect to (2) and (4). More specifically,

$\displaystyle\underset{X,\pi^{i}}{\min}\ $ $\displaystyle
J^{i}(X,\pi^{i})\qquad\forall i\in\\{1,\dots,N\\}$ subject to $\displaystyle
D(X,\pi)=0$ (5) $\displaystyle C(X,\pi)\leq 0$

The solution to such a dynamic game is a generalized Nash equilibrium, i.e. a
policy $\pi$ such that, $\forall i\in\\{1,\dots,N\\}$, $\pi^{i}$ is a solution
to (5) with the other players’ policies given by $\pi^{\neg i}$ that is also
solved by (5) for all $\neg i$. As a consequence, at a Nash equilibrium point
solution, no player can improve their strategy by unilaterally modifying their
policy.

### MPC implementation with cost updates

Cost structures are fixed during the resolution of a dynamic game, which can
lead to dangerous trajectories when costs used differ from the true
expressions. Solutions with state feedback such as iLQG, or MPC
implementations of open-loop solvers have been shown to mitigate this issue.
However, these solutions do not tackle the root of the problem which is the
assumed versus true cost mismatch. Furthermore, in real-life scenarios, a
robot’s representation of its environment evolves through sensor measurement
and inter-agent communication. Hence, intelligent agents should be able to
update their interpretation of others’ intentions. In our game-theoretic
framework, this is equivalent to enabling objective function estimate updates
at relevant frequencies. Proposed methods to achieve this include inverse
optimal control algorithms and Inverse Reinforcement Learning (IRL).

To the best of our knowledge, this problem has not yet been tackled for
intention-communicating agents with possible transmission faults corrupting
the communication channel. We design a communication-based game-theoretic
receding horizon motion planner to update the cost representations agents have
of others by capitalizing on truthful communication and absorbing misleading
transmissions to avoid dangerous trajectories.

##  IV Hypothesis Adaptive Motion Planner

Our solution relies on updating the perceived costs by comparing executed
trajectories to those obtained by solving the set of games corresponding to
various intention hypotheses. This approach is based upon the observation that
the set of broadly defined possible intentions in many multi-robot motion
planning is small, and that solutions that are close most likely arise from
cost formulations that are also close. The latter assumption might not hold
for arbitrary systems with complex nonlinear dynamics, however is sound for
agents only interacting via collision constraints. The non-uniqueness of Nash
equilibria also means that even with correct costs, potentially large
trajectory deviations can arise. However, Peters et al. [23] show that it is
possible to ensure agents agree on a Nash equilibrium.

We denote agent $i$’s true cost function as $c_{v}^{i}$. Agent $i$ broadcasts
a communicated cost denoted $c_{c}^{i}$ to all other agents in its vicinity.
(In the most general setting, an agent could communicate different cost
functions to different agents in the scene, and could modify the communicated
cost at each MPC iteration). We also have access in a database to a set of
$\xi$ possible hypotheses for other agents intentions, notably for agent $i$,
cost functions $c_{h,I}^{i}$ for $I\in\\{1,2,\dots,\xi\\}$. We denote
$c^{i}_{h}$ the vector of hypothetical cost functions agent $i$ has about the
scene such that $c^{i}_{h}=[c_{h,1}^{i},\dots,c_{h,\xi}^{i}]$. Agent $i$
solves a recursive game and must estimate $\xi+1$ probability parameters
representing the relative likelihood of each of the hypotheses, $\lambda_{I}$
with $I\in\\{0,\dots,\xi\\}$ and such that $\sum_{I=0}^{\xi}\lambda_{I}=1$ and
$\lambda_{I}\geq 0$, then uses the estimated likelihoods to assign a cost for
agent $j$ denoted $c_{j}^{i}$. Omitting the $i$, the ego vehicle solves a non-
cooperative game with its own cost $c_{v}$ and the assigned cost function
$c_{j}$ for the ado agent $j$ according to,

$\displaystyle
k_{\textrm{max}}=\mathrm{argmax}([\lambda_{0},\dots,\lambda_{\xi}])$ (6)
$\displaystyle c_{j}=\begin{cases}\mbox{$c_{c}^{j}$\quad,}&\mbox{if
}k_{\textrm{max}}=0\\\
\mbox{$c_{h,k_{\textrm{max}}}$\quad,}&\mbox{otherwise}\end{cases}$ (7)

The design choice of planning with the highest likely hypothesis is motivated
by the discrete nature of possible cost functions in most driving scenarios
(switching lanes, turning left or right etc.). In games with continuous cost
structure (desired speed, aggressiveness, comfort metrics), we propose using
the weighted sum of the intention hypotheses to determine the cost assigned to
agent $j$,

$\displaystyle c_{j}=\lambda_{0}c_{c}^{j}+\sum_{I=1}^{\xi}\lambda_{I}c_{h,I}$
(8)

###  IV-A Online Bayesian inference for hypothesis estimation

We use online discrete Bayesian filtering to update the distribution weights.
The belief vector $\bm{\Lambda}$ is defined as
$\bm{\Lambda}=[\lambda_{0},\lambda_{1},...\lambda_{\xi}]^{T}$. The transition
matrix is defined as $\mathbf{T}=[T{{}_{kl}}]_{k,l=0}^{\xi}$, where each entry
of the matrix is $T{{}_{kl}}=p(I_{t+1}=k|I_{t}=l)$. The filter predict step
is,

$\displaystyle\bm{\Lambda}_{t+1|t}=\mathbf{T}\bm{\Lambda}_{t|t}$ (9)

where the subscript $t|t^{\prime}$ denotes the estimate of $\bm{\Lambda}$ at
time $t$ given the observations up to and including time $t^{\prime}$. To make
minimal assumption on how the intention dynamics evolve, we take $\mathbf{T}$
to be the identity matrix. The measurement matrix $\mathbf{M}$ is defined as,

$\displaystyle\mathbf{M}=\textrm{diag}[p(\mathbf{y}_{t-s:t}|I_{t}=0),...,p(\mathbf{y}_{t-s:t}|I_{t}=\xi)]$
(10)

where the measurement likelihood for diagonal elements of the matrix
$\mathbf{M}$ are computed based on the steps outlined in Algorithm 1. The
filtering equations are formulated over $s$ state measurements and the filter
update step is,

$\displaystyle\bm{\Lambda}_{t+1|t+1}=\frac{\mathbf{M}\bm{\Lambda}_{t+1|t}}{1^{T}\mathbf{M}\bm{\Lambda}_{t+1|t}}$
(11)

In Algorithm 1, the inputs are measurements $\mathbf{y}_{t-s:t}$ and belief
vector $\bm{\Lambda}_{t-s}$ over the past $s$ time steps. The output is the
measurement likelihood
$p(\hat{\mathbf{x}}_{t-s:t}=\mathbf{y}_{t-s:t}|\bm{\Lambda}_{t-s})$, where
$\hat{\mathbf{x}}$ denotes the open-loop Nash solution of the dynamic game
(5). The game is solved over $H$ horizon from $\mathbf{y}_{t-s}$ with
$\bm{\Lambda}_{t-s}$ and the control sequence $\mathbf{u}_{t-s:t+H}$ is
computed. Then the dynamics is propagated forward up to time t and the state
trajectory $\hat{\mathbf{x}}_{t-s:t}$ is computed. Finally the measurement
likelihood $p(\hat{\mathbf{x}}_{t-s:t}=\mathbf{y}_{t-s:t}|\bm{\Lambda}_{t-s})$
is computed.

Algorithm 1 Measurement likelihood for discrete Bayesian filter

1:Input: $\mathbf{y}_{t-s:t},\bm{\Lambda}_{t-s}$

2:Output: $p(\hat{\mathbf{x}}_{t-s:t}=\mathbf{y}_{t-s:t}|\bm{\Lambda}_{t-s})$

3:Steps: $\mathbf{u}_{t-s:t+H}\leftarrow$ solve game (5) from
$\mathbf{y}_{t-s}$ with $\bm{\Lambda}_{t-s}$ over $H$ horizon

4:$\hat{\mathbf{x}}_{t-s:t}\leftarrow$ forward propagate (1) up to time $t$

5:$p(\hat{\mathbf{x}}_{t-s:t}=\mathbf{y}_{t-s:t}|\bm{\Lambda}_{t-s})\leftarrow$
likelihood with $p(\mathbf{x}_{t-s:t}|\bm{\Lambda}_{t-s})\propto
p(\mathbf{x}_{t-s:t}|\hat{\mathbf{x}}_{t-s:t}(\mathbf{u}_{t-s:t}(\bm{\Lambda}_{t-s})))$

In our setup, at time step $t-s$ agent $i$ solves his current perceived game
determined by $\bm{\Lambda}_{t}$ according to (6)-(7) with horizon $H$ and
executes the trajectory obtained for $s<H$ time steps. At step $t$, agent $i$
observes the executed joint state trajectories of all agents between $t-s$ and
$t$ which we denote
$\hat{X}_{t-s:t}=[\mathbf{\hat{x}}_{t-s}^{\top},\dots,\mathbf{\hat{x}}_{t}^{\top}]^{\top}$.
Similarly, for $I\in\\{0,1,\dots,\xi\\}$ agent $i$ can obtain hypothetical
trajectories
$X^{I}_{t-s:t}=[\mathbf{x}_{t-s}^{I,\top},\dots,\mathbf{x}_{t}^{I,\top}]^{\top}$
by solving each of the available versions of the game, with the convention
that $I=0$ represents the communicated game. We can thus compute, for
hypotheses $I\in\\{0,1,\dots,\xi\\}$, a disparity score with the observed
executed joint trajectory $d^{I}$, which we take to be the sum along all
points of the trajectory if the $l1$-norm of the element-wise relative state
error, such that,

$\displaystyle
d^{I}=\sum_{k=t-s}^{t}\left\lVert(\mathbf{x}_{k}^{I}-\mathbf{\hat{x}}_{k})\oslash\mathbf{\hat{x}}_{k}\right\rVert_{1}$
(12)

where the $\oslash$ symbol represents the Hadamard element-wise division. The
choice of this formulations allows for all elements of the observed state
(positions, translation velocities, angular rates. etc.) to have the same
weight in the norm computation. We shed light on the necessity of taking
numerical precautions to avoid divisions by zero in (12). We also ensure all
computed error scores are in practice strictly positive by adding a small
offset to (12). The hypothesis relative likelihoods $\lambda_{I}$ for
$I\in\\{0,1,\dots,\xi\\}$ presented in Section IV-A must rank in the inverse
order of that of the disparity scores as closer trajectories are assumed to
arise from games with more accurate cost function representations. We obtain
our current estimate of the relative likelihoods denoted
$\tilde{\bm{\Lambda}}_{t}=[\tilde{\lambda}_{0},\dots,\tilde{\lambda}_{\xi}]$
by requiring likelihoods to be inversely proportional to disparity scores and
thus to satisfy the following conditions,

$\displaystyle\tilde{\lambda}_{I}$
$\displaystyle=\frac{d^{J}}{d^{I}}\tilde{\lambda}_{J},\quad\forall
I,J\in\\{0,1,\dots,\xi\\},\ I\neq J$ (13)
$\displaystyle\sum_{I=0}^{\xi}\tilde{\lambda}_{I}$ $\displaystyle=1$ (14)
$\displaystyle\tilde{\lambda}_{I}$ $\displaystyle\geq 0,\quad\forall
I\in\\{0,1,\dots,\xi\\}$ (15)

Note that the $\xi+1\choose 2$ conditions ($\xi+1$ choose $2$) in (13) are
highly redundant and can be replaced by $\xi$ conditions:

$\displaystyle\tilde{\lambda}_{I}$
$\displaystyle=\frac{d^{0}}{d^{I}}\tilde{\lambda}_{0},\quad\forall
I\in\\{1,\dots,\xi\\}$ (16)

Also the strict positivity of $d^{I}$ for $I\in\\{0,1,\dots,\xi\\}$ combined
with condition (14) ensures that any solution to (16) and (14) necessarily
satisfies (15). Thus, computing the current estimate of the relative
likelihoods comes down to solving the simple linear system

$\displaystyle\mathbf{A}_{t}\tilde{\bm{\Lambda}}_{t}^{\top}=\mathbf{B}$ (17)

with $\mathbf{A}_{t}\in\mathbb{R}^{(\xi+1)\times(\xi+1)}$ and
$\mathbf{B}\in\mathbb{R}^{\xi+1}$ such that,

$\displaystyle\mathbf{A}_{t}=\begin{bmatrix}1&1&1&\cdots&1\\\
1&-\frac{d^{1}}{d^{0}}&0&\cdots&0\\\ 1&0&\ddots&&\vdots\\\
\vdots&\vdots&&\ddots&0\\\ 1&0&\cdots&0&-\frac{d^{\xi}}{d^{0}}\end{bmatrix},\
\mathbf{B}=\begin{bmatrix}1\\\ 0\\\ \vdots\\\ \vdots\\\ 0.\end{bmatrix}$ (18)

The likelihood estimation scheme is based on the online filtering approach
presented in section IV-A. For the filter predict step (9), the transition
probability matrix is assumed as identity matrix
$\mathbf{T}=\mathbf{I}_{\xi+1}$ to make minimal assumption on the transition
dynamics between different hypothesis. Therefore
$\bm{\Lambda}_{t+1|t}=\bm{\Lambda}_{t|t}$. Equation (17) is equivalent to the
filter update step (11). While the measurement likelihood
$p(\hat{\mathbf{x}}_{t-s:t}=\mathbf{y}_{t-s:t}|\bm{\Lambda}_{t-s})$ discussed
in algorithm 1 is computed using equation (12). We finally obtain the new
value of $\bm{\Lambda}_{t}$ used to define the next perceived game to solve
via the fusion of the previous value $\bm{\Lambda}_{t-s}$ with the new
estimate $\tilde{\bm{\Lambda}}_{t}$ according to a fixed update rate $\gamma$,
such that,

$\displaystyle\bm{\Lambda}_{t}=(1-\gamma)\bm{\Lambda}_{t-s}+\gamma\tilde{\bm{\Lambda}}_{t}$
(19)

The update rate $\gamma$ is the filter’s only hyperparameter. It determines
how fast we update our likelihood vector according to previous estimates.
Smaller $\gamma$ values (slower) can be useful in scenarios with high
replanning frequencies, where shorter observed trajectories contain less
useful signal, and a gradual convergence of $\bm{\Lambda}$ over a larger
sample is desired. Larger $\gamma$ values favor quick adaptation to new
observations contradicting the current active hypothesis.

###  IV-B Proposed Motion Planner

Our solution consists of an MPC implementation of the open-loop dynamic game
solver over a time horizon $H$, with the Nash equilibrium policy subsequently
executed for $H_{N}$ time steps before updating the perceived game costs and
repeating. Agent $i$, with cost function $c^{i}$, initial joint state of the
scene $\mathbf{x}_{0}$, initial hypothesis likelihood vector
$\bm{\Lambda}_{0}$, and hypothesis cost models for other agents $c_{h}^{i}$,
thus computes its motion according to our decentralized on-board planner
outlined in Algorithm 2.

Algorithm 2 Planner for robot $i$

1:procedure
$\textsc{Planner}(\mathbf{x}_{0},\bm{\Lambda}_{0},c^{i},c_{h}^{i},H,H_{N},\gamma)$

2: $\mathbf{x}\leftarrow\mathbf{x}_{0}$,
$\bm{\Lambda}\leftarrow\bm{\Lambda}_{0}$

3: while $interacting$ do

4: $\textsc{Communicate}(c^{i})$

5: $c_{c}^{\neg i}\leftarrow\textsc{ReceiveCommunicatedCosts}$

6: $c\leftarrow\textsc{FormPerceivedGame}(\bm{\Lambda},c_{c}^{\neg
i},c_{h}^{i})$ (6)-(7)

7: $\pi\leftarrow\textsc{SolveDynamicGame}(\mathbf{x},c,H)$ (5)

8: $\mathbf{x}^{i}\leftarrow\textsc{Execute}(\mathbf{x}^{i},\pi^{i},H_{N})$

9: $\mathbf{x}^{\neg i}\leftarrow\textsc{ObserveState}(H_{N})$

10: $\bm{\Lambda}\leftarrow\textsc{UpdateLikelihood}(\pi,\mathbf{x},\gamma)$
(17)-(19)

11: end while

12: end procedure

The hypothesis likelihood update compute time is largely negligible relative
to the dynamic game solver. Hence, the planning time scales linearly with the
number of hypotheses as compared to using ALGAMES to plan a single version of
the dynamic game. Indeed, for a single version of a 3 agent game, a 20 step
look-ahead and a 5 step executed trajectory, the compute costs required for
solving the game and updating the hypotheses likelihood vector are shown in
Table I.

TABLE I: Orders of magnitude of the run time, number of allocations and disk space required to solve the dynamic game and to update the hypothesis likelihood vector. Task | Run time (s) | # alloc. | Space (MB)
---|---|---|---
SolveDynamicGame | $10^{-1}$ | $10^{5}$ | 100
UpdateLikelihood | $10^{-4}$ | $10^{3}$ | 0.1

##  V Simulations

We test our proposed solution on three autonomous driving scenarios inspired
by real-life confusion cases with increasing complexity. We look at a two
vehicle overtaking maneuver, a three vehicle lane merging scenario and a four
vehicle intersection negotiation. In all the simulations, all agents plan
their trajectories using our proposed planner.

###  V-A Simulations setup

The dynamic games solver we use is ALGAMES [24], which handles trajectory
optimization problems with multiple actors and general nonlinear state and
input constraints. The vehicles obey nonlinear unicycle dynamics. The state of
a vehicle $\mathbf{x}^{i}_{t}$ comprises of its 2D position, its heading angle
and scalar velocity. The control input $\mathbf{u}^{i}_{t}$ comprises of the
angular velocity and scalar acceleration.

####  V-A1 Constraints

The dynamics constraints at time $t$ consist in following the system dynamics
given by (1), with $f$ being unicycle dynamics in all our driving simulations.
We also enforce collision-avoidance constraints on the trajectories, by
modelling collision zones of the vehicles by circles or radius $r$, such that,
at any time step $t$,

$\displaystyle\left\lVert\mathbf{p}^{i}_{t}-\mathbf{p}^{j}_{t}\right\rVert_{2}^{2}\geq
r^{2},\quad\forall i,j\in\\{1,\dots,N\\}$ (20)

In addition, we require the vehicles to remain on the road, by constraining
the distance between each vehicle and the closest point $\mathbf{q}$ on each
boundary $b$ to remain larger than the collision radius $r$,

$\displaystyle\left\lVert\mathbf{p}^{i}_{t}-\mathbf{q}_{b}\right\rVert_{2}^{2}\geq
r^{2},\quad\forall b,\forall i\in\\{1,\dots,N\\}$ (21)

where $\mathbf{p}^{i}_{t}=[px_{t}^{i},py_{t}^{i}]$ contains the plane
coordinates of the agent $i$ at time $t$ extracted from the complete state
vector $\mathbf{x}^{i}_{t}$. Thus, the autonomous driving problem is
formalized via non-convex and non-linear coupled constraints.

####  V-A2 Cost function

The cost structure considered is quadratic, penalizing the distance to the
desired final state $\mathbf{x}_{f}$ and the use of controls,

$\displaystyle J^{i}(X,\pi^{i})$
$\displaystyle=\sum_{t-1}^{H-1}\frac{1}{2}(\mathbf{x}_{t}-\mathbf{x}_{f})^{\top}\mathbf{Q}(\mathbf{x}_{t}-\mathbf{x}_{f})+\frac{1}{2}\mathbf{u}_{t}^{i,\top}\mathbf{R}\mathbf{u}_{t}^{i}$
$\displaystyle\hskip
10.00002pt+\frac{1}{2}(\mathbf{x}_{H}-\mathbf{x}_{f})^{\top}\mathbf{Q}_{f}(\mathbf{x}_{H}-\mathbf{x}_{f})$
(22)

where $\mathbf{Q}$, $\mathbf{R}$ and $\mathbf{Q}_{f}$ represent state, input
and final state penalization weight matrices, respectively. This cost function
depends only on the decision variables of vehicle $i$, as players’ behaviors
are only coupled through collision constraints. Thus, although knowledge of
other agents’ intentions does not intervene in the individual cost agent $i$
is optimizing for, it does however determine the trajectories of others, and
subsequently the collision constraints agent $i$ has to satisfy.

###  V-B Advantage of V2V communication

We show through a simple takeover maneuver experiment that intention sharing
between agents can improve the quality of the planned solutions. Vehicle
$v_{1}$ wishes to maintain high velocity on the left lane along a two-lane
highway. Vehicle $v_{2}$ is in front of it initially and is driving at a
slower speed. $v_{2}$ wishes to move to the right lane. We consider two
scenarios: first with $v_{1}$ agnostic to $v_{2}$’s intention, and second with
the $v_{2}$’s true cost function available to $v_{1}$. In the first case,
since no information is available to $v_{1}$, we let $v_{1}$ suppose that
$v_{2}$ intends to continue driving on the left lane at the same speed. The
trajectories in both cases are presented in Fig. 2.

Figure 2: No communication (top) and true cost communication (bottom). $v_{1}$
and $v_{2}$ executed trajectories in green and red respectively. Marker size
increases with respect to time.

We clearly notice that access to $v_{2}$’s intentions allows $v_{1}$ to
satisfy its objective of maintaining high speed on the left. On the other
hand, the absence of such information and of the ability to update the cost
based on observations deteriorates the reward collected as $v_{1}$ gets stuck
behind $v_{2}$, expecting the latter to drift back to the left lane.

###  V-C Unique true alternative

We first validate the soundness of our approach by considering cases with one
agent sending faulty communication. The other agents use our planner with one
alternative hypothesis, which we here assume to be the true cost function of
the faulty agent. Furthermore, we assume that all players initially trust each
other (at $t=0$ we initialise $\lambda_{0}=1,\lambda_{1}=0$). We simulate
three real-life driving situations: a takeover maneuver, a lane merging, and
an intersection negotiation.

####  V-C1 Takeover

Vehicle $v_{1}$ wishes to maintain high velocity on the left lane along a two-
lane highway. In front of it on the same lane is a slower vehicle, $v_{2}$,
which misleadingly expresses its intention to make way (e.g. by signalling to
the right), when its true intention is to stay on the left lane.

The obtained trajectories with and without the use of our planner are
presented in Fig. 3.

Figure 3: Communication only planner solution (top) and adaptive hypothesis
likelihood planner with $\gamma=0.6$ solution (bottom). $v_{1}$ and $v_{2}$
executed trajectories in green and red respectively. Marker size increases
with respect to time.

Relying on communicated cost functions only, the overtaking vehicle $v_{1}$
persists in attempting to pass by $v_{2}$ from the left as at each episode the
Nash equilibrium with the fixed communicated cost from $v_{2}$ would yield an
optimal policy in which $v_{2}$ moves out of $v_{1}$’s way. This leads to an
aggressive maneuver where $v_{1}$ repeatedly bumps $v_{2}$ pushing it to the
right lane for $v_{1}$ to squeeze through. Using our planner, $v_{1}$ observes
$v_{2}$’s reluctance to make way over the first few iterations, and quickly
assigns the alternative cost function to $v_{2}$, leading to a smooth overtake
from the right.

####  V-C2 Lane-merging

Next we consider a lane-merging maneuver involving three vehicles on a two-
lane highway. Let $v_{1}$ be the source of the fault, communicating its
willingness to make way to the merging vehicle $v_{2}$, when in truth it
wishes to maintain driving along the right lane without reducing its speed.
Driving along the left lane, $v_{3}$’s objective is to maintain high velocity.

Fig. 4 shows the trajectory obtained using communicated intentions only, and
that with $v_{2}$ and $v_{3}$ using our planner.

Figure 4: Communication only planner solution (top) and adaptive hypothesis
likelihood planner with $\gamma=0.6$ (bottom) cases : $v_{1}$, $v_{2}$ and
$v_{3}$ executed trajectories in green, red, and blue respectively. Marker
size increases with respect to time.

The first trajectory depicts an aggressive and unsafe merging scenario.
Indeed, at each planning step, $v_{2}$ persists in assuming $v_{1}$ will
either slow down or switch to the left lane in order to accommodate it. Hence,
$v_{2}$ continues to execute the merge in front of $v_{1}$, passing
dangerously close to both $v_{1}$ and the road boundary. Using our adaptive
planner, $v_{2}$, notices $v_{1}$’s reluctance to make way over a couple of
planning episodes, assigns larger likelihood to the alternative scenario and
subsequently plans to allow $v_{1}$ to pass first before merging. In this
case, $v_{2}$ avoids finding itself in the hazardous situation of being
tailgated by $v_{1}$.

####  V-C3 4-way intersection

The last example we consider involves four vehicles negotiating an
intersection crossing. Three vehicles, $v_{1}$, $v_{2}$ and $v_{3}$ intend to
drive straight across (west to east, east to west and north to south
respectively). Vehicle $v_{4}$ wants to execute a left turn (south to west).
We assume $v_{4}$ misleads the other agents about its aggressiveness.
Trajectories planned with the faulty intention as well as those obtained with
agents $v_{1}$, $v_{2}$ and $v_{3}$ using our adaptive planner are presented
in Fig. 5.

Figure 5: Communication only planner solution (left) and adaptive hypothesis
likelihood planner with $\gamma=0.4$ (right) cases : $v_{1}$, $v_{2}$, $v_{3}$
and $v_{4}$ executed trajectories in green, red, blue and yellow respectively.
Marker size increases with respect to time.

Without adapting the cost functions, $v_{2}$ does not hasten its passage as
$v_{4}$ comes increasing close to it, as communication from $v_{4}$ suggest it
is willing to slow down to let $v_{2}$ through. Thus $v_{2}$ drives right in
front of $v_{4}$ as it executes its turn, leading to a collision. In the
adaptive case, $v_{2}$, noticing $v_{4}$’s absence of braking, accelerates as
it enters the intersection and avoids getting crashed into.

####  V-C4 Update rate dependency

We study the effect of the update rate $\gamma$ on evolution of the perceived
game determined by $\bm{\Lambda}$ and present quantitative analysis of the
minimum distance between each pair of vehicles with respect to this filter
parameter. Closed-loop simulations of our proposed planner for all three
scenarios are presented in Fig. 6.

Figure 6: Left: Evolution of the hypotheses relative likelihoods
$\bm{\Lambda}$ throughout the simulation as a function of the filter update
rate $\gamma$. The communicated cost’s likelihood is depicted in blue, and the
alternative hypothesis in red, the largest bar determining which version of
the game is used for planning during the current episode. Right: Normalized
distances between each pair of vehicles $d(v_{i},v_{j})/d_{min}$ (logarithmic
scale) as a function of $\gamma$. The dashed line depicts the collision
threshold $d_{min}$.

The main observation is that it is desirable for the hypothesis likelihood
filter to converge before the start of the inter-vehicle interactions. Indeed,
this not only allows agents to enjoy additional lead time to adapt their
maneuvers to avoid collisions, but also to avoid interactions corrupting the
intention signal used to update the filter. Overall, we notice that for large
enough update rates, our planner allows agents to identify the correct
intention of the faulty agent and use this information to replan safe
trajectories.

###  V-D Multiple inexact alternatives

We next test and validate our planner in the more complex, realistic setting
of multiple hypotheses about other agents’ intentions, which have no reason to
necessarily include the exact true cost functions. We show that when the
hypothesis set contains a cost function that is close enough to the true one,
safer planning is achieved using our approach. Indeed, we revisit the takeover
example presented earlier, but now consider three alternative hypotheses to
the communicated intention of $v_{2}$. The first is to maintain the left lane
with a penalty on deviation from the lane center a quarter as small as the
true one, the second is to maintain the left lane with a penalty 20 times
smaller than the true value, and the third is to change lanes at a third of
the initial speed. We show the evolution of $\bm{\Lambda}$ and of the minimum
inter-vehicle distance as a function of $\gamma$ in Fig. 7.

Figure 7: Evolution of the hypotheses relative likelihoods $\bm{\Lambda}$
throughout the simulation as a function of the filter update rate $\gamma$.
The communicated cost’s likelihood is depicted in blue, and alternatives in
red, yellow and purple. For $\gamma\geq 0.8$, collision is avoided.

According to the simulation results, our planner achieves collision-free
trajectories in complex environments with broad and imprecise assumptions
about other agents’ costs utilizing the proposed online Bayesian filtering
scheme which allows fast adaptation for the planner. The simulation results
confirm that our solution can be used to ensure safety and improve performance
in various driving scenarios.

###  V-E Performance and robustness

We test the robustness of our approach to intention communication reliability,
initial state conditions and process noise on the lane-merging scenario,
comparing it to two planning baselines. We consider two available intention
hypotheses for $v_{1}$ ($I_{1}$: $v_{1}$ wishes to stay on the right lane
maintaining same speed, and $I_{2}$: $v_{1}$ wishes to accelerate with less
emphasis on lane keeping), in addition to the communicated intention ($I_{c}$:
$v_{1}$ is willing to yield the lane to the merging $v_{2}$). We assume all
agents have access to the correct cost functions for $v_{2}$ and $v_{3}$. Our
planner has access to all three hypotheses for planning. The first baseline is
a communication-only planner using only $I_{c}$. The second uses our planner
in a no-communication scheme, i.e. with only $I_{1}$ and $I_{2}$ as possible
options. We uniformly randomize the initial positions of all three agents and
introduce $20\%$ uniform process noise on the executed control commands. We
run 100 merging simulations with faulty communication ($v_{1}$’s cost function
is represented by $I_{1}$ and not $I_{c}$) and 100 runs with correct
communication ($v_{1}$’s cost is $I_{c}$ as communicated). The results are
presented in Table II.

| Hyp. | $\bm{d}$ | Risky | Crash | $\bm{J}$ | $\bm{acc}_{max}$
---|---|---|---|---|---|---
Faulty | $\\{I_{c}\\}$ | $1.40\pm 0.09$ | 16% | 0% | 11.46 | 10.92
$\\{I_{1},I_{2}\\}$ | $1.56\pm 0.04$ | 2% | 0% | 11.21 | 10.80
$\\{I_{c},I_{1},I_{2}\\}$ | $1.55\pm 0.06$ | 1% | 0% | 11.07 | 10.74
Correct | $\\{I_{c}\\}$ | $1.57\pm 0.01$ | 0% | 0% | 11.09 | 10.66
$\\{I_{1},I_{2}\\}$ | $1.54\pm 0.12$ | 4% | 2% | 11.19 | 10.76
$\\{I_{c},I_{1},I_{2}\\}$ | $1.57\pm 0.01$ | 0% | 0% | 11.07 | 10.66
Total | $\\{I_{c}\\}$ | $1.48\pm 0.10$ | 8% | 0% | 11.28 | 10.79
$\\{I_{1},I_{2}\\}$ | $1.56\pm 0.09$ | 3% | 1% | 11.20 | 10.78
$\\{I_{c},I_{1},I_{2}\\}$ | $1.55\pm 0.05$ | 0.5% | 0% | 11.07 | 10.70
TABLE II: Statistical performance of our planner versus communication and
agnostic baselines ($n=100$ manuevres for each of Faulty/Correct communication
scenarios). $d$ (mean $\pm$ std) represents the minimum normalized distance
between each pair of vehicles, such that $d=\min\\{d(v_{i},v_{j})/d_{min}\ |\
i,j\in\\{1,2,3\\},\ i\neq j\\}$, with $d_{min}$ denoting the collision
threshold. Risky maneuvres are accounted for when $d$ is within $30\%$ of
$d_{min}$, and crashes when $d\leq d_{min}$. The LQR cost of the maneuvre for
the merging agent, denoted $J$, is computed according to equation (22). The
maximum acceleration of the merging vehicle $acc_{max}$ is used as a comfort
score.

As intended, our proposed planner generates safe trajectories whether the
communicated intention is correct or not. Indeed, over the 200 simulations
with our adaptive planner, only one trajectory is considered risky and no
crashes are recorded. Also as expected, our planner matches the perfect
information game in terms of performance when communication is correct. We
also notice the importance correct communication can have in insuring safety,
as not having access to a close enough intention in the set of hypotheses can
lead to dangerous trajectories and crashes. Indeed, when $v_{1}$ correctly
communicates its intention $I_{c}$ the adaptive planner using only
$\\{I_{1},I_{2}\\}$ exhibits a large variance in trajectories leading to a
$2\%$ crash rate. Our planner is capable of both absorbing situations with
faulty intention communication, and leveraging correct information for Nash
optimal trajectory planning, without compromising on performance and comfort.

##  VI Conclusion

We have introduced a new receding horizon game-theoretic motion planner
designed to operate in real-time in the framework of intention sharing multi-
robot systems with potential communication faults. We demonstrate the
robustness of our solution to such perturbations on complex autonomous driving
scenarios, showcasing its ability to plan safe trajectories in situations from
which naive implementations fail to recover. Future directions include
integrating online intention identification into our framework in addition to
incorporating state uncertainty.

## References

  * [1] A. W. Starr and Y. C. Ho, “Nonzero-sum differential games,” _J. Optim. Theory Appl._ , vol. 3, no. 3, p. 184–206, mar 1969. [Online]. Available: https://doi.org/10.1007/BF00929443
  * [2] D. Fridovich-Keil, E. Ratner, L. Peters, A. D. Dragan, and C. J. Tomlin, “Efficient iterative linear-quadratic approximations for nonlinear multi-player general-sum differential games,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 1475–1481.
  * [3] W. Schwarting, A. Pierson, S. Karaman, and D. Rus, “Stochastic dynamic games in belief space,” _IEEE Transactions on Robotics_ , vol. 37, no. 6, pp. 2157–2172, 2021.
  * [4] T.-Y. Li and Z. Gajic, “Lyapunov iterations for solving coupled algebraic riccati equations of nash differential games and algebraic riccati equations of zero-sum games,” in _New Trends in Dynamic Games and Applications_ , G. J. Olsder, Ed. Boston, MA: Birkhäuser Boston, 1995, pp. 333–351.
  * [5] H. Mukai, A. Tanikawa, P. Rinaldi, and S. Louis, “Sequential quadratic methods for differential games,” in _Proceedings of the 2001 American Control Conference._ , vol. 1, 2001, pp. 182–189 vol.1.
  * [6] J. F. Fisac, E. Bronstein, E. Stefansson, D. Sadigh, S. S. Sastry, and A. D. Dragan, “Hierarchical game-theoretic planning for autonomous vehicles,” 2018\.
  * [7] P. Trautman and A. Krause, “Unfreezing the robot: Navigation in dense, interacting crowds,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2010, pp. 797–803.
  * [8] A. Dreves and M. Gerdts, “A generalized nash equilibrium approach for optimal control problems of autonomous cars,” _Optimal Control Applications & Methods_, vol. 39, pp. 326–342, 2018.
  * [9] D. Sadigh, S. S. Sastry, S. A. Seshia, and A. D. Dragan, “Planning for autonomous cars that leverage effects on human actions,” in _Robotics: Science and Systems_ , 2016.
  * [10] R. Spica, D. Falanga, E. Cristofalo, E. Montijano, D. Scaramuzza, and M. Schwager, “A real-time game theoretic planner for autonomous two-player drone racing,” 2018.
  * [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] L. Peters, D. Fridovich-Keil, V. Rubies-Royo, C. J. Tomlin, and C. Stachniss, “Inferring objectives in continuous dynamic games from noise-corrupted partial state observations,” _arXiv preprint arXiv:2106.03611_ , 2021.
  * [13] F. Laine, D. Fridovich-Keil, C.-Y. Chiu, and C. Tomlin, “Multi-hypothesis interactions in game-theoretic motion planning,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 8016–8023.
  * [14] S. Le Cleac’h, M. Schwager, and Z. Manchester, “Lucidgames: Online unscented inverse dynamic games for adaptive trajectory prediction and planning,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 5485–5492, 2021\.
  * [15] F. Rey, Z. Pan, A. Hauswirth, and J. Lygeros, “Fully decentralized admm for coordination and collision avoidance,” in _2018 European Control Conference (ECC)_ , 2018, pp. 825–830.
  * [16] L. Ferranti, R. R. Negenborn, T. Keviczky, and J. Alonso-Mora, “Coordination of multiple vessels via distributed nonlinear model predictive control,” in _2018 European Control Conference (ECC)_ , 2018, pp. 2523–2528.
  * [17] B. Schrank, B. Eisele, T. Lomax, and J. Bak. (2015) The 2015 urban mobility scorecard. Texas A&M Transportation Institute. [Online]. Available: http://mobility.tamu.edu
  * [18] V. Milanes, J. Godoy, J. Villagra, and J. Perez, “Automated on-ramp merging system for congested traffic situations,” _IEEE Trans. on Intelligent Transportation Systems_ , vol. 12, no. 2, pp. 500–508, 2012.
  * [19] Y. Bichiou and H. A. Rakha, “Developing an optimal intersection control system for automated connected vehicles,” _IEEE Trans. on Intelligent Transportation Systems_ , vol. 20, no. 5, pp. 1908–1916, 2019.
  * [20] W. Xiao and C. G. Cassandras, “Decentralized optimal merging control for connected and automated vehicles with safety constraint guarantees,” _Automatica_ , vol. 123.109333, 2021.
  * [21] I. A. Ntousakis, I. K. Nikolos, and M. Papageorgiou, “Optimal vehicle trajectory planning in the context of cooperative merging on highways,” _Trans. Resear. part C_ , vol. 71, pp. 464–488, 2016.
  * [22] M. H. B. M. Nor and T. Namerikawa, “Merging of connected and automated vehicles at roundabout using model predictive control,” in _Annual Conference of the Society of Instrument and Control Engineers of Japan_ , pp. 272–277, 2018.
  * [23] L. Peters, D. Fridovich-Keil, C. J. Tomlin, and Z. N. Sunberg, “Inference-based strategy alignment for general-sum differential games,” in _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS ’20. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2020, p. 1037–1045.
  * [24] S. L. Cleac’h, M. Schwager, and Z. Manchester, “ALGAMES: A fast solver for constrained dynamic games,” _CoRR_ , vol. abs/1910.09713, 2019. [Online]. Available: http://arxiv.org/abs/1910.09713