# SOCIALMAPF: Optimal and Efficient Multi-Agent Path Finding with Strategic Agents for Social Navigation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 54 references that are in the map.
- First posted on arXiv 15 Oct 2022.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Socially Aware Motion Planning with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.08862/) (2017)
- [Core Challenges of Social Robot Navigation: A Survey](https://mlsanity.com/paper/2103.05668/) (2021)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [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)
- [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)
- [B-GAP: Behavior-Rich Simulation and Navigation for Autonomous Driving](https://mlsanity.com/paper/2011.03748/) (2020)
- [Conflict Avoidance in Social Navigation -- a Survey](https://mlsanity.com/paper/2106.12113/) (2021)
- [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)
- [Newton's Method and Differential Dynamic Programming for Unconstrained Nonlinear Dynamic Games](https://mlsanity.com/paper/1906.09097/) (2019)
- [X*: Anytime Multi-Agent Path Finding for Sparse Domains using Window-Based Iterative Repairs](https://mlsanity.com/paper/1811.12598/) (2018)
- [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, 6 of 6)

- [Principles and Guidelines for Evaluating Social Robot Navigation Algorithms](https://mlsanity.com/paper/2306.16740/) (2023)
- [Multi-Agent Inverse Reinforcement Learning in Real World Unstructured Pedestrian Crowds](https://mlsanity.com/paper/2405.16439/) (2024)
- [SOCIALGYM 2.0: Simulator for Multi-Agent Social Robot Navigation in Shared Human Spaces](https://mlsanity.com/paper/2303.05584/) (2023)
- [iPLAN: Intent-Aware Planning in Heterogeneous Traffic via Distributed Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.06236/) (2023)
- [Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization](https://mlsanity.com/paper/2306.08815/) (2023)
- [Scalable Mechanism Design for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.17044/) (2024)

## Abstract (arXiv)

We propose an extension to the MAPF formulation, called SocialMAPF, to account for private incentives of agents in constrained environments such as doorways, narrow hallways, and corridor intersections. SocialMAPF is able to, for instance, accurately reason about the urgent incentive of an agent rushing to the hospital over another agent's less urgent incentive of going to a grocery store; MAPF ignores such agent-specific incentives. Our proposed formulation addresses the open problem of optimal and efficient path planning for agents with private incentives. To solve SocialMAPF, we propose a new class of algorithms that use mechanism design during conflict resolution to simultaneously optimize agents' private local utilities and the global system objective. We perform an extensive array of experiments that show that optimal search-based MAPF techniques lead to collisions and increased time-to-goal in SocialMAPF compared to our proposed method using mechanism design. Furthermore, we empirically demonstrate that mechanism design results in models that maximizes agent utility and minimizes the overall time-to-goal of the entire system. We further showcase the capabilities of mechanism design-based planning by successfully deploying it in environments with static obstacles. To conclude, we briefly list several research directions using the SocialMAPF formulation, such as exploring motion planning in the continuous domain for agents with private incentives.