# Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 55 references that are in the map.
- First posted on arXiv 15 Jun 2023.

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

- [Socially Aware Motion Planning with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.08862/) (2017)
- [Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning](https://mlsanity.com/paper/1609.07845/) (2016)
- [Motion Planning Among Dynamic, Decision-Making Agents with Deep Reinforcement Learning](https://mlsanity.com/paper/1805.01956/) (2018)
- [Core Challenges of Social Robot Navigation: A Survey](https://mlsanity.com/paper/2103.05668/) (2021)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning](https://mlsanity.com/paper/1709.10082/) (2017)
- [TraPHic: Trajectory Prediction in Dense and Heterogeneous Traffic Using Weighted Interactions](https://mlsanity.com/paper/1812.04767/) (2018)
- [Motion Planning and Control for Mobile Robot Navigation Using Machine Learning: a Survey](https://mlsanity.com/paper/2011.13112/) (2020)
- [Collision Avoidance in Pedestrian-Rich Environments with Deep Reinforcement Learning](https://mlsanity.com/paper/1910.11689/) (2019)
- [Hierarchical Game-Theoretic Planning for Autonomous Vehicles](https://mlsanity.com/paper/1810.05766/) (2018)
- [Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games](https://mlsanity.com/paper/1909.04694/) (2019)
- [Forecasting Trajectory and Behavior of Road-Agents Using Spectral Clustering in Graph-LSTMs](https://mlsanity.com/paper/1912.01118/) (2019)
- [SocNavBench: A Grounded Simulation Testing Framework for Evaluating Social Navigation](https://mlsanity.com/paper/2103.00047/) (2021)
- [Stochastic Dynamic Games in Belief Space](https://mlsanity.com/paper/1909.06963/) (2019)
- [CMetric: A Driving Behavior Measure Using Centrality Functions](https://mlsanity.com/paper/2003.04424/) (2020)
- [ALGAMES: A Fast Augmented Lagrangian Solver for Constrained Dynamic Games](https://mlsanity.com/paper/2104.08452/) (2021)
- [GamePlan: Game-Theoretic Multi-Agent Planning with Human Drivers at Intersections, Roundabouts, and Merging](https://mlsanity.com/paper/2109.01896/) (2021)
- [METEOR:A Dense, Heterogeneous, and Unstructured Traffic Dataset With Rare Behaviors](https://mlsanity.com/paper/2109.07648/) (2021)
- [Using Graph-Theoretic Machine Learning to Predict Human Driver Behavior](https://mlsanity.com/paper/2111.02964/) (2021)
- [SOCIALGYM: A Framework for Benchmarking Social Robot Navigation](https://mlsanity.com/paper/2109.11011/) (2021)
- [GraphRQI: Classifying Driver Behaviors Using Graph Spectrums](https://mlsanity.com/paper/1910.00049/) (2019)
- [GAMEOPT: Optimal Real-time Multi-Agent Planning and Control for Dynamic Intersections](https://mlsanity.com/paper/2202.11572/) (2022)
- [Autonomous and Semi-Autonomous Intersection Management: A Survey](https://mlsanity.com/paper/2006.13133/) (2020)
- [Game-Theoretic Planning for Autonomous Driving among Risk-Aware Human Drivers](https://mlsanity.com/paper/2205.00562/) (2022)
- [SOCIALMAPF: Optimal and Efficient Multi-Agent Path Finding with Strategic Agents for Social Navigation](https://mlsanity.com/paper/2210.08390/) (2022)
- [Newton's Method and Differential Dynamic Programming for Unconstrained Nonlinear Dynamic Games](https://mlsanity.com/paper/1906.09097/) (2019)
- [iPLAN: Intent-Aware Planning in Heterogeneous Traffic via Distributed Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.06236/) (2023)
- [First-Order Algorithms for Constrained Nonlinear Dynamic Games](https://mlsanity.com/paper/2001.01826/) (2020)
- [Differential Dynamic Programming for Nonlinear Dynamic Games](https://mlsanity.com/paper/1809.08302/) (2018)
- [Incorporating Gaze into Social Navigation](https://mlsanity.com/paper/2107.04001/) (2021)

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

- [Multi-Agent Inverse Reinforcement Learning in Real World Unstructured Pedestrian Crowds](https://mlsanity.com/paper/2405.16439/) (2024)
- [Learning Implicit Social Navigation Behavior using Deep Inverse Reinforcement Learning](https://mlsanity.com/paper/2501.06946/) (2025)

## Abstract (arXiv)

This paper presents a fully decentralized approach for realtime non-cooperative multi-robot navigation in social mini-games, such as navigating through a narrow doorway or negotiating right of way at a corridor intersection. Our contribution is a new realtime bi-level optimization algorithm, in which the top-level optimization consists of computing a fair and collision-free ordering followed by the bottom-level optimization which plans optimal trajectories conditioned on the ordering. We show that, given such a priority order, we can impose simple kinodynamic constraints on each robot that are sufficient for it to plan collision-free trajectories with minimal deviation from their preferred velocities, similar to how humans navigate in these scenarios. We successfully deploy the proposed algorithm in the real world using F1/10 robots, a Clearpath Jackal, and a Boston Dynamics Spot as well as in simulation using the SocialGym 2.0 multi-agent social navigation simulator, in the doorway and corridor intersection scenarios. We compare with state-of-the-art social navigation methods using multi-agent reinforcement learning, collision avoidance algorithms, and crowd simulation models. We show that (i) classical navigation performs 44% better than the state-of-the-art learning-based social navigation algorithms, (ii) without a scheduling protocol, our approach results in collisions in social mini-games (iii) our approach yields 2× and 5× fewer velocity changes than CADRL in doorways and intersections, and finally (iv) bi-level navigation in doorways at a flow rate of 2.8 - 3.3 (ms)-1 is comparable to flow rate in human navigation at a flow rate of 4 (ms)-1.