{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T18:26:09Z","timestamp":1778178369216,"version":"3.51.4"},"reference-count":85,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T00:00:00Z","timestamp":1732924800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/100019201","name":"Honda Research Institute, USA","doi-asserted-by":"publisher","award":["HRI-001479"],"award-info":[{"award-number":["HRI-001479"]}],"id":[{"id":"10.13039\/100019201","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>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\u2019 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.<\/jats:p>","DOI":"10.1177\/02783649241302342","type":"journal-article","created":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T03:11:53Z","timestamp":1732936313000},"page":"1156-1185","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":7,"title":["Mixed strategy Nash equilibrium for crowd navigation"],"prefix":"10.1177","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3704-6315","authenticated-orcid":false,"given":"Max","family":"Muchen Sun","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering, Northwestern University, Evanston, IL 60208, USA"}]},{"given":"Francesca","family":"Baldini","sequence":"additional","affiliation":[{"name":"Honda Research Institute, San Jose, CA, USA"}]},{"given":"Katie","family":"Hughes","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, Northwestern University, Evanston, IL 60208, USA"}]},{"given":"Peter","family":"Trautman","sequence":"additional","affiliation":[{"name":"Honda Research Institute, San Jose, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2262-8176","authenticated-orcid":false,"given":"Todd","family":"Murphey","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, Northwestern University, Evanston, IL 60208, USA"}]}],"member":"179","published-online":{"date-parts":[[2024,11,30]]},"reference":[{"key":"e_1_3_5_2_1","doi-asserted-by":"publisher","unstructured":"Alahi A Goel K Ramanathan V et al. (2016) Social LSTM: human trajectory prediction in crowded spaces. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Las Vegas NV USA June 27-30 2016 961\u2013971. DOI: 10.1109\/CVPR.2016.110. https:\/\/ieeexplore.ieee.org\/document\/7780479.ISSN:1063-6919.","DOI":"10.1109\/CVPR.2016.110"},{"key":"e_1_3_5_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.add8091"},{"key":"e_1_3_5_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139219"},{"key":"e_1_3_5_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-021-10023-8"},{"key":"e_1_3_5_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3476413"},{"key":"e_1_3_5_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2022.3159527"},{"key":"e_1_3_5_8_1","first-page":"11","volume-title":"Proceedings of the Fifteenth National\/tenth Conference on Artificial intelligence\/Innovative Applications of Artificial Intelligence, AAAI \u201998\/IAAI \u201998","author":"Burgard W","year":"1998","unstructured":"Burgard W, Cremers AB, Fox D, et al. (1998) The interactive museum tour-guide robot. In: Proceedings of the Fifteenth National\/tenth Conference on Artificial intelligence\/Innovative Applications of Artificial Intelligence, AAAI \u201998\/IAAI \u201998. Washington, DC, USA: American Association for Artificial Intelligence, 11\u201318."},{"key":"e_1_3_5_9_1","doi-asserted-by":"publisher","unstructured":"Cao C Trautman P Iba S (2019) Dynamic Channel: a planning framework for crowd navigation. In: 2019 International Conference on Robotics and Automation (ICRA) Montr\u00e9al QC 20-24 May 2019 5551\u20135557. DOI: 10.1109\/ICRA.2019.8794192.","DOI":"10.1109\/ICRA.2019.8794192"},{"key":"e_1_3_5_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/lnms\/1196285403"},{"key":"e_1_3_5_11_1","doi-asserted-by":"publisher","unstructured":"Cathcart C Santos M Park S et al. (2023) Proactive opinion-driven robot navigation around human movers. In: 2023 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Detroit Michigan October 1 \u2013 5 2023. pp. 4052\u20134058. DOI:10.1109\/IROS55552.2023.10341745. https:\/\/ieeexplore.ieee.org\/document\/10341745.ISSN:2153-0866.","DOI":"10.1109\/IROS55552.2023.10341745"},{"key":"e_1_3_5_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2008.07.011"},{"key":"e_1_3_5_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8202312"},{"key":"e_1_3_5_14_1","doi-asserted-by":"publisher","unstructured":"Chen C Liu Y Kreiss S et al. (2019) Crowd-robot interaction: crowd-aware robot navigation with attention-based deep reinforcement learning. In: 2019 International Conference on Robotics and Automation (ICRA) Montreal Canada 20 \u2013 24 2019 6015\u20136022. DOI: 10.1109\/ICRA.2019.8794134.","DOI":"10.1109\/ICRA.2019.8794134"},{"key":"e_1_3_5_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROMAN.2006.314378"},{"key":"e_1_3_5_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1461928.1461951"},{"key":"e_1_3_5_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2166435"},{"key":"e_1_3_5_18_1","volume-title":"Simulating the Collision Avoidance Behavior of Pedestrians. Master\u2019s Thesis","author":"Feurtey F","year":"2000","unstructured":"Feurtey F (2000) Simulating the Collision Avoidance Behavior of Pedestrians. Master\u2019s Thesis. Bunky\u014d, Japan: University of Tokyo. https:\/\/svn.sable.mcgill.ca\/sable\/courses\/COMP763\/oldpapers\/collision-00-feurtey.pdf."},{"key":"e_1_3_5_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/100.580977"},{"key":"e_1_3_5_20_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919859436"},{"key":"e_1_3_5_21_1","doi-asserted-by":"publisher","unstructured":"Fridovich-Keil D Ratner E Peters L et al. (2020b) Efficient iterative linear-quadratic approximations for nonlinear multi-player general-sum differential games. In: 2020 IEEE International Conference on Robotics and Automation (ICRA) Paris France 31 May 2020 \u2013 31 Aug 2020 1475\u20131481. DOI: 10.1109\/ICRA40945.2020.9197129. https:\/\/ieeexplore.ieee.org\/abstract\/document\/9197129.ISSN:2577-087X.","DOI":"10.1109\/ICRA40945.2020.9197129"},{"key":"e_1_3_5_22_1","volume-title":"Calculus of variations","author":"Gelfand IM","year":"2000","unstructured":"Gelfand IM, Fomin SV, Silverman RA (2000) Calculus of variations. North Chelmsford, MA: Courier Corporation."},{"key":"e_1_3_5_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00240"},{"key":"e_1_3_5_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.51.4282"},{"key":"e_1_3_5_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509772"},{"key":"e_1_3_5_26_1","first-page":"2067","volume-title":"Proceedings of the 31st Conference on Learning Theory","author":"Hoeven D","year":"2018","unstructured":"Hoeven D, Erven T, Kot\u0142owski W (2018) The many faces of exponential weights in online learning. In: Proceedings of the 31st Conference on Learning Theory. New York, NY, USA: PMLR, 2067\u20132092. https:\/\/proceedings.mlr.press\/v75\/hoeven18a.html.ISSN:2640-3498."},{"key":"e_1_3_5_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3164789"},{"key":"e_1_3_5_28_1","doi-asserted-by":"publisher","unstructured":"Kim B Pineau J (2013) Maximum mean discrepancy imitation learning. In: Robotics: Science and Systems IX. Robotics: Science and Systems Foundation Los Angeles California June 21 \u2013 June 25 2025. DOI: 10.15607\/RSS.2013.IX.038. https:\/\/www.roboticsproceedings.org\/rss09\/p38.pdf.","DOI":"10.15607\/RSS.2013.IX.038"},{"key":"e_1_3_5_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12369-015-0310-2"},{"key":"e_1_3_5_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2021.3069362"},{"key":"e_1_3_5_31_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915619772"},{"key":"e_1_3_5_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3074880"},{"key":"e_1_3_5_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-021-10024-7"},{"key":"e_1_3_5_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01089.x"},{"key":"e_1_3_5_35_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/583"},{"key":"e_1_3_5_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV48922.2021.01484"},{"key":"e_1_3_5_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6385716"},{"key":"e_1_3_5_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341207"},{"key":"e_1_3_5_39_1","doi-asserted-by":"publisher","DOI":"10.1126\/scirobotics.abm6074"},{"key":"e_1_3_5_40_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918781016"},{"key":"e_1_3_5_41_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649211037731"},{"key":"e_1_3_5_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8206601"},{"key":"e_1_3_5_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3171221.3171255"},{"key":"e_1_3_5_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3223024"},{"key":"e_1_3_5_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583741"},{"key":"e_1_3_5_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3232300"},{"key":"e_1_3_5_47_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918790369"},{"key":"e_1_3_5_48_1","doi-asserted-by":"publisher","DOI":"10.1126\/sciadv.abe7758"},{"key":"e_1_3_5_49_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_3_5_50_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_5_51_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649211037697"},{"key":"e_1_3_5_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341469"},{"key":"e_1_3_5_53_1","first-page":"381","volume-title":"Proceedings of the 6th Conference on Robot Learning","author":"Nishimura H","year":"2023","unstructured":"Nishimura H, Mercat J, Wulfe B, et al. (2023) RAP: risk-aware prediction for robust planning. In: Proceedings of the 6th Conference on Robot Learning. New York, NY, USA: PMLR, 381\u2013392. https:\/\/proceedings.mlr.press\/v205\/nishimura23a.html.ISSN:2640-3498."},{"key":"e_1_3_5_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1249720"},{"key":"e_1_3_5_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2009.5459260"},{"key":"e_1_3_5_56_1","unstructured":"Peters L Fridovich-Keil D Tomlin CJ et al. (2020) Inference-based strategy alignment for general-sum differential games. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems AAMAS \u201920. Richland SC: International Foundation for Autonomous Agents and Multiagent Systems Auckland New Zealand May 9-13 2020 1037\u20131045."},{"key":"e_1_3_5_57_1","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2022.XVIII.051"},{"key":"e_1_3_5_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2024.3354548"},{"key":"e_1_3_5_59_1","volume-title":"Adaptive Computation and Machine Learning","author":"Rasmussen CE","year":"2006","unstructured":"Rasmussen CE, Williams CKI (2006) Gaussian processes for machine learning. In: Adaptive Computation and Machine Learning. Cambridge, Mass: MIT Press."},{"key":"e_1_3_5_60_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920917446"},{"key":"e_1_3_5_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-018-9746-1"},{"key":"e_1_3_5_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58523-5_40"},{"key":"e_1_3_5_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2996593"},{"key":"e_1_3_5_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3135560"},{"key":"e_1_3_5_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2969925"},{"key":"e_1_3_5_66_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1820676116"},{"key":"e_1_3_5_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0921-8890(02)00376-7"},{"key":"e_1_3_5_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jhtm.2021.10.014"},{"key":"e_1_3_5_69_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2201.12925"},{"key":"e_1_3_5_70_1","doi-asserted-by":"publisher","unstructured":"So O Drews P Balch T et al. (2023) MPOGames: efficient multimodal partially observable dynamic games. In: 2023 IEEE International Conference on Robotics and Automation (ICRA) London England 29 May 2023 \u2013 2 Jun 2023 3189\u20133196. DOI: 10.1109\/ICRA48891.2023.10160342. https:\/\/ieeexplore.ieee.org\/document\/10160342.","DOI":"10.1109\/ICRA48891.2023.10160342"},{"key":"e_1_3_5_71_1","doi-asserted-by":"publisher","unstructured":"Sun M Baldini F Trautman P et al. (2021) Move beyond trajectories: distribution space coupling for crowd navigation. In: Robotics: Science and Systems XVII. Robotics: Science and Systems Foundation Los Angeles California USA June 21 \u2013 June 25 2025. DOI: 10.15607\/RSS.2021.XVII.053. https:\/\/www.roboticsproceedings.org\/rss17\/p053.pdf.","DOI":"10.15607\/RSS.2021.XVII.053"},{"key":"e_1_3_5_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2012.6426381"},{"issue":"104","key":"e_1_3_5_73_1","first-page":"3137","article-title":"A generalized path integral control approach to reinforcement learning","volume":"11","author":"Theodorou E","year":"2010","unstructured":"Theodorou E, Buchli J, Schaal S (2010) A generalized path integral control approach to reinforcement learning. Journal of Machine Learning Research 11(104): 3137\u20133181. https:\/\/jmlr.org\/papers\/v11\/theodorou10a.html.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_5_74_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783640022067922"},{"key":"e_1_3_5_75_1","volume-title":"Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)","author":"Thrun S","year":"2005","unstructured":"Thrun S, Burgard W, Fox D (2005) Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). Cambridge: The MIT Press."},{"key":"e_1_3_5_76_1","doi-asserted-by":"publisher","unstructured":"Trautman P (2017) Sparse interacting Gaussian processes: efficiency and optimality theorems of autonomous crowd navigation. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC) Melbourne Victoria December 12-15 2017 327\u2013334. DOI: 10.1109\/CDC.2017.8263686.","DOI":"10.1109\/CDC.2017.8263686"},{"key":"e_1_3_5_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2010.5654369"},{"key":"e_1_3_5_78_1","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v30i1.6741"},{"key":"e_1_3_5_79_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914557874"},{"key":"e_1_3_5_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19457-3_1"},{"key":"e_1_3_5_81_1","first-page":"641","volume-title":"Theory of Games and Economic Behavior","author":"Von Neumann J","year":"1947","unstructured":"Von Neumann J, Morgenstern O (1947) Theory of games and economic behavior. In: Theory of Games and Economic Behavior. 2nd rev. Princeton, NJ, US: Princeton University Press, 641.","edition":"2"},{"key":"e_1_3_5_82_1","doi-asserted-by":"publisher","unstructured":"Von Stackelberg H (2011) Market structure and equilibrium. Berlin Heidelberg: Springer. DOI: 10.1007\/978-3-642-12586-7.","DOI":"10.1007\/978-3-642-12586-7"},{"key":"e_1_3_5_83_1","first-page":"871","volume-title":"Proceedings of the 5th Conference on Robot Learning","author":"Wang A","year":"2022","unstructured":"Wang A, Mavrogiannis C, Steinfeld A (2022) Group-based motion prediction for navigation in crowded environments. In: Proceedings of the 5th Conference on Robot Learning. New York, NY, USA: PMLR, 871\u2013882. https:\/\/proceedings.mlr.press\/v164\/wang22e.html.ISSN:2640-3498."},{"key":"e_1_3_5_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487277"},{"key":"e_1_3_5_85_1","doi-asserted-by":"publisher","unstructured":"Williams G Goldfain B Drews P et al. (2018) Best response model predictive control for agile interactions between autonomous ground vehicles. In: 2018 IEEE International Conference on Robotics and Automation (ICRA) Brisbane Australia 21 May 2018-26 May 2018 2403\u20132410. DOI: 10.1109\/ICRA.2018.8462831. https:\/\/ieeexplore.ieee.org\/document\/8462831.ISSN:2577-087X.","DOI":"10.1109\/ICRA.2018.8462831"},{"key":"e_1_3_5_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2009.5354147"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241302342","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649241302342","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241302342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:38Z","timestamp":1777457858000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649241302342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,30]]},"references-count":85,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.1177\/02783649241302342"],"URL":"https:\/\/doi.org\/10.1177\/02783649241302342","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,30]]}}}