journal article
Open Access
Apr 11, 2026
Multi-robot navigation in social mini-games: definitions, taxonomy, and algorithms
Abstract
Abstract
The “Last Mile Challenge” has long been considered an important, yet unsolved, challenge for autonomous vehicles, public service robots, and delivery robots. A central issue in this challenge is the ability of robots to navigate constrained and cluttered environments that have high agency (e.g., doorways, hallways, corridor intersections), often while competing for space with other robots and humans. We refer to these environments as “Social Mini-Games” (SMGs). Traditional navigation approaches designed for MRN do not perform well in SMGs, which has led to focused research on dedicated SMG solvers. However, publications on SMG navigation research make different assumptions (on centralized versus decentralized, observability, communication, cooperation, etc.), and have different objective functions (safety versus liveness). These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult to establish appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. Such ad-hoc representation of the field also presents a barrier to new researchers wanting to start research in this area. SMG navigation research requires its own taxonomy, definitions, and evaluation protocols to guide effective research moving forward. This survey is the first to catalog SMG solvers using a well-defined and unified taxonomy and to classify existing methods accordingly. It also discusses the essential properties of SMG solvers, defines what SMGs are and how they appear in practice, outlines how to evaluate SMG solvers, and highlights the differences between SMG solvers and general navigation systems. The survey concludes with an overview of future directions and open challenges in the field. Our project is open-sourced at
https://socialminigames.github.io/
.
The “Last Mile Challenge” has long been considered an important, yet unsolved, challenge for autonomous vehicles, public service robots, and delivery robots. A central issue in this challenge is the ability of robots to navigate constrained and cluttered environments that have high agency (e.g., doorways, hallways, corridor intersections), often while competing for space with other robots and humans. We refer to these environments as “Social Mini-Games” (SMGs). Traditional navigation approaches designed for MRN do not perform well in SMGs, which has led to focused research on dedicated SMG solvers. However, publications on SMG navigation research make different assumptions (on centralized versus decentralized, observability, communication, cooperation, etc.), and have different objective functions (safety versus liveness). These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult to establish appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. Such ad-hoc representation of the field also presents a barrier to new researchers wanting to start research in this area. SMG navigation research requires its own taxonomy, definitions, and evaluation protocols to guide effective research moving forward. This survey is the first to catalog SMG solvers using a well-defined and unified taxonomy and to classify existing methods accordingly. It also discusses the essential properties of SMG solvers, defines what SMGs are and how they appear in practice, outlines how to evaluate SMG solvers, and highlights the differences between SMG solvers and general navigation systems. The survey concludes with an overview of future directions and open challenges in the field. Our project is open-sourced at
https://socialminigames.github.io/
.
Topics
No keywords indexed for this article. Browse by subject →
References
210
[1]
Abdullhak, M.,& Vardy, A. (2021). “Deadlock prediction and recovery for distributed collision avoidance with buffered voronoi cells,” in 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 429–436, IEEE.
10.1109/iros51168.2021.9636609
[2]
Alahi, A., Goel, K., Ramanathan, V., Robicquet, A., Fei-Fei, L.,& Savarese, S. (2016). “Social lstm: Human trajectory prediction in crowded spaces,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 961–971.
10.1109/cvpr.2016.110
[3]
Alonso-Mora, J., Breitenmoser, A., Rufli, M., Beardsley, P.,& Siegwart, R. (2013). “Optimal reciprocal collision avoidance for multiple non-holonomic robots,” in Distributed autonomous robotic systems: The 10th international symposium, pp. 203–216, Springer.
10.1007/978-3-642-32723-0_15
[4]
Alonso-Mora, J., DeCastro, J. A., Raman, V., Rus, D., & Kress-Gazit, H. (2018). Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles. Autonomous Robots, 42, 801–824.
10.1007/s10514-017-9665-6
[5]
Alzetta, F., Giorgini, P., Najjar, A., Schumacher, M. I.,& Calvaresi, D. (2020). “In-time explainability in multi-agent systems: Challenges, opportunities, and roadmap,” in International Workshop on Explainable, Transparent Autonomous Agents and Multi-Agent Systems, pp. 39–53, Springer.
10.1007/978-3-030-51924-7_3
[6]
Amador, S., Okamoto, S.,& Zivan, R. (2014). “Dynamic multi-agent task allocation with spatial and temporal constraints,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 28.
10.1609/aaai.v28i1.8889
[7]
Antonyshyn, L., Silveira, J., Givigi, S., & Marshall, J. (2023). Multiple mobile robot task and motion planning: A survey. ACM Computing Surveys, 55(10), 1–35.
10.1145/3564696
[8]
Arif, M. U. (2022). Robot coalition formation against time-extended multi-robot tasks. International Journal of Intelligent Unmanned Systems, 10(4), 468–481.
10.1108/ijius-12-2020-0070
[9]
Aroor, A., Esptein, S. L.,& Korpan, R. (2017).“Mengeros: A crowd simulation tool for autonomous robot navigation,” in 2017 AAAI Fall Symposium Series.
[10]
Arul, S. H., Park, J. J.,& Manocha, D. (2023). “Ds-mpepc: Safe and deadlock-avoiding robot navigation in cluttered dynamic scenes,” in 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2256–2263, IEEE.
10.1109/iros55552.2023.10341869
[11]
Azarm, K.,& Schmidt, G. (1997). “Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation,” in Proceedings of international conference on robotics and automation, vol. 4, pp. 3526–3533, IEEE.
10.1109/robot.1997.606881
[12]
Barer, M., Sharon, G., Stern, R.,& Felner, A. (2014). “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” in Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS), pp. 19–27.
10.3233/978-1-61499-419-0-961
[13]
Biswas, A., Wang, A., Silvera, G., Steinfeld, A., & Admoni, H. (2022). Socnavbench: A grounded simulation testing framework for evaluating social navigation. ACM Trans. on Human-Robot Interaction (THRI), 11(3), 1–24.
10.1145/3476413
[14]
Cao, Z., Biyik, E., Rosman, G.,& Sadigh, D. (2022). “Leveraging smooth attention prior for multi-agent trajectory prediction,” in 2022 International Conference on Robotics and Automation (ICRA), pp. 10723–10730, IEEE.
10.1109/icra46639.2022.9811718
[15]
Cao, Y., Hu, H.,& Prorok, A. (2021). “Multi-agent communication graph optimization with spatial-temporal constraints,” in 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 9109–9115, IEEE.
[16]
Čáp, M., Gregoire, J.,& Frazzoli, E. (2016). “Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5113–5118, IEEE.
10.1109/iros.2016.7759750
[17]
Cappello, D., Garcin, S., Mao, Z., Sassano, M., Paranjape, A., & Mylvaganam, T. (2020). A hybrid controller for multi-agent collision avoidance via a differential game formulation. IEEE Transactions on Control Systems Technology, 29(4), 1750–1757.
10.1109/tcst.2020.3005602
[18]
Chan, F. K. S., Law, Y. N., Lu, B., Chick, T., Lai, E. S. B.,& Ge, M. (2022). “Multi-agent pathfinding for deadlock avoidance on rotational movements,” in 2022 17th International Conference on Control, Automation, Robotics and Vision (ICARCV), pp. 765–770, IEEE.
10.1109/icarcv57592.2022.10004303
[19]
Chandra, R., Karnan, H., Mehr, N., Stone, P., & Biswas, J. (2024). “Towards imitation learning in real world unstructured social mini-games in pedestrian crowds,” arXiv preprint arXiv:2405.16439.
[20]
Chandra, R., Wang, M., Schwager, M.,& Manocha, D. (2022). “Game-theoretic planning for autonomous driving among risk-aware human drivers,” in 2022 Intl. Conf. on Robotics and Automation (ICRA), pp. 2876–2883, IEEE.
10.1109/icra46639.2022.9811865
[21]
Chandra, R., Zinage, V., Bakolas, E., Stone, P.,& Biswas, J. (2024). “Deadlock-free, safe, and decentralized multi-robot navigation in social mini-games via discrete-time control barrier functions,”.
10.21203/rs.3.rs-3979309/v1
[22]
Chandra, R., Maligi, R., Anantula, A., & Biswas, J. (2023). Socialmapf: Optimal and efficient multi-agent path finding with strategic agents for social navigation. IEEE Robotics and Automation Letters, 8(6), 3214–3221.
10.1109/lra.2023.3265169
[23]
Chandra, R., & Manocha, D. (2022). Gameplan: Game-theoretic multi-agent planning with human drivers at intersections, roundabouts, and merging. IEEE Robotics and Automation Letters, 7(2), 2676–2683.
10.1109/lra.2022.3144516
[24]
Chandra, R., Zinage, V., Bakolas, E., Stone, P., & Biswas, J. (2025). Deadlock-free, safe, and decentralized multi-robot navigation in social mini-games via discrete-time control barrier functions. Autonomous Robots, 49(2), 12.
10.1007/s10514-025-10194-8
[25]
Recent trends in social aware robot navigation: A survey
Konstantinos Charalampous, Ioannis Kostavelis, Antonios Gasteratos
Robotics and Autonomous Systems
2017
10.1016/j.robot.2017.03.002
[26]
Chen, Y. F., Everett, M., Liu, M.,& How, J. P. (2017).“Socially aware motion planning with deep reinforcement learning,” in 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1343–1350, IEEE.
10.1109/iros.2017.8202312
[27]
Chen, Y., Guo, M.,& Li, Z. (2022). “Recursive feasibility and deadlock resolution in mpc-based multi-robot trajectory generation,” arXiv preprint arXiv:2202.06071.
[28]
Chen, Y., Guo, M.,& Li, Z. (2024). “Deadlock resolution and recursive feasibility in mpc-based multi-robot trajectory generation,” IEEE Transactions on Automatic Control.
10.1109/tac.2024.3393126
[29]
Chen, Y. F., Liu, M., Everett, M.,& How, J. P. (2017). “Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning,” in 2017 IEEE Intl. Conf. on robotics and automation (ICRA), pp. 285–292, IEEE.
10.1109/icra.2017.7989037
[30]
Chen, C., Liu, Y., Kreiss, S.,& Alahi, A. (2019). “Crowd-robot interaction: Crowd-aware robot navigation with attention-based deep reinforcement learning,” in 2019 International Conference on Robotics and Automation (ICRA), pp. 6015–6022, IEEE.
10.1109/icra.2019.8794134
[31]
Chen, J., Moarref, S.,& Kress-Gazit, H. (2018). “Verifiable control of robotic swarm from high-level specifications,” in Proceedings of the 17th international conference on autonomous agents and multiagent systems, pp. 568–576.
10.65109/izsr8388
[32]
Chen, J.,& Chandra, R. (2025). “Livepoint: Fully decentralized, safe, deadlock-free multi-robot control in cluttered environments with high-dimensional inputs,” arXiv preprint arXiv:2503.13098.
[33]
Cheng, J., Cheng, H., Meng, M. Q.-H.,& Zhang, H. (2018). “Autonomous navigation by mobile robots in human environments: A survey,” in 2018 IEEE Intl. Conf. on robotics and biomimetics (ROBIO), pp. 1981–1986, IEEE.
10.1109/robio.2018.8665075
[34]
Chen, Y., Rosolia, U., & Ames, A. D. (2021). Decentralized task and path planning for multi-robot systems. IEEE Robotics and Automation Letters, 6(3), 4337–4344.
10.1109/lra.2021.3068103
[35]
Chen, Y., Wang, C., Guo, M., & Li, Z. (2023). Multi-robot trajectory planning with feasibility guarantee and deadlock resolution: An obstacle-dense environment. IEEE Robotics and Automation Letters, 8(4), 2197–2204.
10.1109/lra.2023.3248377
[36]
Chik, S., Yeong, C., Su, E., Lim, T., Subramaniam, Y., & Chin, P. (2016). “A review of social-aware navigation frameworks for service robot in dynamic human environments,’’ Journal of Telecommunication. Electronic and Computer Engineering (JTEC), 8(11), 41–50.
[37]
Choi, J. J., Aloor, J. J., Li, J., Mendoza, M. G., Balakrishnan, H.,& Tomlin, C. J. (2025). “Resolving conflicting constraints in multi-agent reinforcement learning with layered safety,” arXiv preprint arXiv:2505.02293.
10.15607/rss.2025.xxi.094
[38]
Choi, J. J., Lee, D., Sreenath, K., Tomlin, C. J.,& Herbert, S. L. (2021). “Robust control barrier–value functions for safety-critical control,” in 2021 60th IEEE Conference on Decision and Control (CDC), pp. 6814–6821, IEEE.
10.1109/cdc45484.2021.9683085
[39]
Chung, C. H., & Jang, Y. J. (2024). Deadlock prevention and multi agent path finding algorithm considering physical constraint for a massive fleet agv system. Applied Soft Computing, 161, Article 111725.
10.1016/j.asoc.2024.111725
[40]
Cirillo, M., Uras, T.,& Koenig, S. (2014). “A lattice-based approach to multi-robot motion planning for non-holonomic vehicles,” in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 232–239, IEEE.
10.1109/iros.2014.6942566
[41]
Coskun, A., O’Kane, J.,& Valtorta, M. (2021). “Deadlock-free online plan repair in multi-robot coordination with disturbances,” in The International FLAIRS Conference Proceedings, vol. 34.
10.32473/flairs.v34i1.128371
[42]
Cosner, R. K., Rodriguez, I. D. J., Molnar, T. G., Ubellacker, W., Yue, Y., Ames, A. D.,& Bouman, K. L. (2022). “Self-supervised online learning for safety-critical control using stereo vision,” in International Conference on Robotics and Automation (ICRA), pp. 11487–11493.
10.1109/icra46639.2022.9812183
[43]
Das, A., Gervet, T., Romoff, J., Batra, D., Parikh, D., Rabbat, M.,& Pineau, J. (2019). “Tarmac: Targeted multi-agent communication,” in International Conference on Machine Learning (ICML), pp. 1538–1546.
[44]
Das, G., Hanheide, M.,& Zhu, Z. (2023). “Autonomous topological optimisation for multi-robot systems in logistics,”.
[45]
Das, S., Nath, S.,& Saha, I. (2019). “Sparcas: A decentralized, truthful multi-agent collision-free path finding mechanism,” arXiv preprint arXiv:1909.08290.
[46]
Davis, B., Karamouzas, I.,& Guy, S. J. (2019). “Nh-ttc: A gradient-based framework for generalized anticipatory collision avoidance,” arXiv preprint arXiv:1907.05945.
10.15607/rss.2020.xvi.078
[47]
Dawson, C., Lowenkamp, B., Goff, D.,& Fan, C. (2022). “Learning safe, generalizable perception-based hybrid control with certificates,”.
10.1109/lra.2022.3141657
[48]
De Sa, M., Kotaru, P.,& Sreenath, K. (2024). “Point cloud-based control barrier function regression for safe and efficient vision-based control,” in 2024 IEEE International Conference on Robotics and Automation (ICRA), (Yokohama, Japan), pp. 366–372.
10.1109/icra57147.2024.10610647
[49]
DeCastro, J. A., Alonso-Mora, J., Raman, V., Rus, D., & Kress-Gazit, H. (2018). Collision-free reactive mission and motion planning for multi-robot systems. Robotics Research, 1, 459–476.
10.1007/978-3-319-51532-8_28
[50]
Demesure, G., Defoort, M., Bekrar, A., Trentesaux, D., & Djemai, M. (2017). Decentralized motion planning and scheduling of agvs in an fms. IEEE Transactions on Industrial Informatics, 14(4), 1744–1752.
10.1109/tii.2017.2749520
Showing 50 of 210 references
Metrics
0
Citations
210
References
Details
- Published
- Apr 11, 2026
- Vol/Issue
- 50(2)
- License
- View
Authors
Cite This Article
Rohan Chandra, Shubham Singh, Wenhao Luo, et al. (2026). Multi-robot navigation in social mini-games: definitions, taxonomy, and algorithms. Autonomous Robots, 50(2). https://doi.org/10.1007/s10514-026-10251-w
Related
You May Also Like
Globally Consistent Range Scan Alignment for Environment Mapping
F. Lu, E. Milios · 1997
977 citations
Multiagent Systems: A Survey from a Machine Learning Perspective
Peter Stone, Manuela Veloso · 2000
707 citations
Progress and prospects of the human–robot collaboration
Arash Ajoudani, Andrea Maria Zanchettin · 2017
685 citations
Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot
Scott Kuindersma, Robin Deits · 2015
674 citations