# Mixed Strategy Nash Equilibrium for Crowd Navigation

arXiv: https://arxiv.org/abs/2403.01537 · HTML: https://mlsanity.com/paper/2403.01537/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 99 references that are in the map.
- First posted on arXiv 3 Mar 2024.

## Builds on (most cited first, 30 of 37)

- [Social GAN: Socially Acceptable Trajectories with Generative Adversarial Networks](https://mlsanity.com/paper/1803.10892/) (2018)
- [Human Motion Trajectory Prediction: A Survey](https://mlsanity.com/paper/1905.06113/) (2019)
- [Robot Operating System 2: Design, Architecture, and Uses In The Wild](https://mlsanity.com/paper/2211.07752/) (2022)
- [Crowd-Robot Interaction: Crowd-aware Robot Navigation with Attention-based Deep Reinforcement Learning](https://mlsanity.com/paper/1809.08835/) (2018)
- [Socially Aware Motion Planning with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.08862/) (2017)
- [Human Trajectory Forecasting in Crowds: A Deep Learning Perspective](https://mlsanity.com/paper/2007.03639/) (2020)
- [Core Challenges of Social Robot Navigation: A Survey](https://mlsanity.com/paper/2103.05668/) (2021)
- [What the Constant Velocity Model Can Teach Us About Pedestrian Motion Prediction](https://mlsanity.com/paper/1903.07933/) (2019)
- [The Marathon 2: A Navigation System](https://mlsanity.com/paper/2003.00368/) (2020)
- [Social NCE: Contrastive Learning of Socially-aware Motion Representations](https://mlsanity.com/paper/2012.11717/) (2020)
- [Continuous-Time Gaussian Process Motion Planning via Probabilistic Inference](https://mlsanity.com/paper/1707.07383/) (2017)
- [Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games](https://mlsanity.com/paper/1909.04694/) (2019)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [The Multi-Agent Behavior Dataset: Mouse Dyadic Social Interactions](https://mlsanity.com/paper/2104.02710/) (2021)
- [SocNavBench: A Grounded Simulation Testing Framework for Evaluating Social Navigation](https://mlsanity.com/paper/2103.00047/) (2021)
- [Maximum-Entropy Multi-Agent Dynamic Games: Forward and Inverse Solutions](https://mlsanity.com/paper/2110.01027/) (2021)
- [DualSMC: Tunneling Differentiable Filtering and Planning under Continuous POMDPs](https://mlsanity.com/paper/1909.13003/) (2019)
- [Risk-Sensitive Sequential Action Control with Multi-Modal Human Trajectory Forecasting for Safe Crowd-Robot Interaction](https://mlsanity.com/paper/2009.05702/) (2020)
- [LUCIDGames: Online Unscented Inverse Dynamic Games for Adaptive Trajectory Prediction and Planning](https://mlsanity.com/paper/2011.08152/) (2020)
- [ALGAMES: A Fast Augmented Lagrangian Solver for Constrained Dynamic Games](https://mlsanity.com/paper/2104.08452/) (2021)
- [Frozone: Freezing-Free, Pedestrian-Friendly Navigation in Human Crowds](https://mlsanity.com/paper/2003.05395/) (2020)
- [Group-based Motion Prediction for Navigation in Crowded Environments](https://mlsanity.com/paper/2107.11637/) (2021)
- [RAP: Risk-Aware Prediction for Robust Planning](https://mlsanity.com/paper/2210.01368/) (2022)
- [Contingency Games for Multi-Agent Interaction](https://mlsanity.com/paper/2304.05483/) (2023)
- [Winding Through: Crowd Navigation via Topological Invariance](https://mlsanity.com/paper/2109.05084/) (2021)
- [Dynamic Channel: A Planning Framework for Crowd Navigation](https://mlsanity.com/paper/1903.00143/) (2019)
- [Inference-Based Strategy Alignment for General-Sum Differential Games](https://mlsanity.com/paper/2002.04354/) (2020)
- [Move Beyond Trajectories: Distribution Space Coupling for Crowd Navigation](https://mlsanity.com/paper/2106.13667/) (2021)
- [Avoiding Dense and Dynamic Obstacles in Enclosed Spaces: Application to Moving in Crowds](https://mlsanity.com/paper/2105.11743/) (2021)
- [Nonlinear Opinion Dynamics with Tunable Sensitivity](https://mlsanity.com/paper/2009.04332/) (2020)

## Built on by (most cited first, 3 of 3)

- [From Obstacles to Etiquette: Robot Social Navigation with VLM-Informed Path Selection](https://mlsanity.com/paper/2602.09002/) (2026)
- [Recent Advances in Multi-Agent Human Trajectory Prediction: A Comprehensive Review](https://mlsanity.com/paper/2506.14831/) (2025)
- [Structured Imitation Learning of Interactive Policies through Inverse Games](https://mlsanity.com/paper/2511.12848/) (2025)

## Abstract (arXiv)

Robots navigating in crowded areas should negotiate free space with humans rather than fully controlling collision avoidance, as this can lead to freezing behavior. Game theory provides a framework for the robot to reason about potential cooperation from humans for collision avoidance during path planning. In particular, the mixed strategy Nash equilibrium captures the negotiation behavior under uncertainty, making it well suited for crowd navigation. However, computing the mixed strategy Nash equilibrium is often prohibitively expensive for real-time decision-making. In this paper, we propose an iterative Bayesian update scheme over probability distributions of trajectories. The algorithm simultaneously generates a stochastic plan for the robot and probabilistic predictions of other pedestrians' paths. We prove that the proposed algorithm is equivalent to solving a mixed strategy game for crowd navigation, and the algorithm guarantees the recovery of the global Nash equilibrium of the game. We name our algorithm Bayesian Recursive Nash Equilibrium (BRNE) and develop a real-time model prediction crowd navigation framework. Since BRNE is not solving a general-purpose mixed strategy Nash equilibrium but a tailored formula specifically for crowd navigation, it can compute the solution in real-time on a low-power embedded computer. We evaluate BRNE in both simulated environments and real-world pedestrian datasets. BRNE consistently outperforms non-learning and learning-based methods regarding safety and navigation efficiency. It also reaches human-level crowd navigation performance in the pedestrian dataset benchmark. Lastly, we demonstrate the practicality of our algorithm with real humans on an untethered quadruped robot with fully onboard perception and computation.