{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T15:49:22Z","timestamp":1776440962903,"version":"3.51.2"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T00:00:00Z","timestamp":1753401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T00:00:00Z","timestamp":1753401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach. Intell. Res."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Embodied intelligence applications, such as autonomous robotics and smart transportation systems, require efficient coordination of multiple agents in dynamic environments. A critical challenge in this domain is the multi-agent pathfinding (MAPF) problem, which ensures that agents can navigate conflict-free while optimizing their paths. Conflict-based search (CBS) is a well-established two-level solver for the MAPF problem. However, as the scale of the problem expands, the computation time becomes a significant challenge for the implementation of CBS. Previous optimizations have mainly focused on reducing the number of nodes explored by the high-level or low-level solver. This paper takes a different perspective by proposing a parallel version of CBS, namely GPU-accelerated conflict-based search (GACBS), which significantly exploits the parallel computing capabilities of GPU. GACBS employs a task coordination framework to enable collaboration between the high-level and low-level solvers with lightweight synchronous operations. Moreover, GACBS leverages a parallel low-level solver, called GATSA, to efficiently find the shortest path for a single agent under constraints. Experimental results show that the proposed GACBS significantly outperforms CPU-based CBS, with the maximum speedup ratio reaching over 46.<\/jats:p>","DOI":"10.1007\/s11633-025-1568-y","type":"journal-article","created":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T06:32:46Z","timestamp":1753425166000},"page":"641-654","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["GPU-accelerated Conflict-based Search for Multi-agent Embodied Intelligence"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5914-4178","authenticated-orcid":false,"given":"Mingkai","family":"Tang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9548-5076","authenticated-orcid":false,"given":"Ren","family":"Xin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3430-1189","authenticated-orcid":false,"given":"Chao","family":"Fang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4222-9060","authenticated-orcid":false,"given":"Yuanhang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0272-3045","authenticated-orcid":false,"given":"Hongji","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5930-4170","authenticated-orcid":false,"given":"Jin","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,25]]},"reference":[{"issue":"2","key":"1568_CR1","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1109\/TETCI.2022.3141105","volume":"6","author":"J Duan","year":"2022","unstructured":"J. Duan, S. Yu, H. L. Tan, H. Zhu, C. Tan. A survey of embodied AI: From simulators to research tasks. IEEE Transactions on Emerging Topics in Computational Intelligence, vol. 6, no. 2, pp. 230\u2013244, 2022. DOI: https:\/\/doi.org\/10.1109\/TETCI.2022.3141105.","journal-title":"IEEE Transactions on Emerging Topics in Computational Intelligence"},{"key":"1568_CR2","volume-title":"Aligning cyber space with physical world: A comprehensive survey on embodied AI","author":"Y Liu","year":"2024","unstructured":"Y. Liu, W. Chen, Y. Bai, X. Liang, G. Li, W. Gao, L. Lin. Aligning cyber space with physical world: A comprehensive survey on embodied AI, [Online], Available: https:\/\/arxiv.org\/abs\/2407.06886, 2024."},{"key":"1568_CR3","volume-title":"From machine learning to robotics: Challenges and opportunities for embodied intelligence","author":"N Roy","year":"2021","unstructured":"N. Roy, I. Posner, T. Barfoot, P. Beaudoin, Y. Bengio, J. Bohg, O. Brock, I. Depatie, D. Fox, D. Koditschek, T. Lozano-Perez, V. Mansinghka, C. Pal, B. Richards, D. Sadigh, S. Schaal, G. Sukhatme, D. Therien, M. Toussaint, M. Van de Panne. From machine learning to robotics: Challenges and opportunities for embodied intelligence, [Online], Available: https:\/\/arxiv.org\/abs\/2110.15245, 2021."},{"key":"1568_CR4","series-title":"Ph. D. dissertation","volume-title":"Advancing the Cognitive Abilities of Embodied Agents: Large-scale Simulations and Multi-agent Collaborations","author":"R Gong","year":"2024","unstructured":"R. Gong. Advancing the Cognitive Abilities of Embodied Agents: Large-scale Simulations and Multi-agent Collaborations, Ph. D. dissertation, University of California, USA, 2024."},{"key":"1568_CR5","doi-asserted-by":"publisher","first-page":"16135","DOI":"10.1609\/aaai.v37i13.26928","volume-title":"Proceedings of the 37th AAAI Conference on Artificial Intelligence","author":"E Seraj","year":"2023","unstructured":"E. Seraj. Embodied, intelligent communication for multi-agent cooperation. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington DC, USA, pp. 16135\u201316136, 2023. DOI: https:\/\/doi.org\/10.1609\/aaai.v37i13.26928."},{"key":"1568_CR6","volume-title":"COMBO: Compositional world models for embodied multi-agent cooperation","author":"H Zhang","year":"2024","unstructured":"H. Zhang, Z. Wang, Q. Lyu, Z. Zhang, S. Chen, T. Shu, B. Dariush, K. Lee, Y. Du, C. Gan. COMBO: Compositional world models for embodied multi-agent cooperation, [Online], Available: https:\/\/arxiv.org\/abs\/2404.10775, 2024."},{"key":"1568_CR7","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence","author":"R Morris","year":"2016","unstructured":"R. Morris, C. S. Pasareanu, K. S. Luckow, W. Malik, H. Ma, T. K. S. Kumar, S. Koenig. Planning, scheduling and monitoring for airport surface operations. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, USA, 2016."},{"key":"1568_CR8","first-page":"272","volume-title":"Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems","author":"S Choudhury","year":"2022","unstructured":"S. Choudhury, K. Solovey, M. Kochenderfer, M. Pavone. Coordinated multi-agent pathfinding for drones and trucks over road networks. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 272\u2013280, 2022."},{"key":"1568_CR9","doi-asserted-by":"publisher","first-page":"9925","DOI":"10.1609\/aaai.v34i06.6547","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence","author":"N M Kou","year":"2020","unstructured":"N. M. Kou, C. Peng, H. Ma, T. K. S. Kumar, S. Koenig. Idle time optimization for target assignment and path finding in sortation centers. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, New York, USA, pp. 9925\u20139932, 2020. DOI: https:\/\/doi.org\/10.1609\/aaai.v34i06.6547."},{"key":"1568_CR10","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1609\/aiide.v13i1.12919","volume-title":"Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment","author":"H Ma","year":"2017","unstructured":"H. Ma, J. Yang, L. Cohen, T. K. Kumar, S. Koenig. Feasibility study: Moving non-homogeneous teams in congested video game environments. In Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Snowbird, USA, pp. 270\u2013272, 2017. DOI: https:\/\/doi.org\/10.1609\/aiide.v13i1.12919."},{"key":"1568_CR11","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1609\/aaai.v27i1.8541","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence","author":"J Yu","year":"2013","unstructured":"J. Yu, S. LaValle. Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, USA, pp. 1443\u20131449, 2013. DOI: https:\/\/doi.org\/10.1609\/aaai.v27i1.8541."},{"key":"1568_CR12","doi-asserted-by":"publisher","first-page":"3166","DOI":"10.1609\/aaai.v30i1.10409","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence","author":"H Ma","year":"2016","unstructured":"H. Ma, C. Tovey, G. Sharon, T. K. S. Kumar, S. Koenig. Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, USA, pp. 3166\u20133173, 2016. DOI: https:\/\/doi.org\/10.1609\/aaai.v30i1.10409."},{"issue":"1","key":"1568_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1109\/LRA.2015.2503143","volume":"1","author":"J Yu","year":"2016","unstructured":"J. Yu. Intractability of optimal multirobot path planning on planar graphs. IEEE Robotics and Automation Letters, vol. 1, no. 1, pp. 33\u201340, 2016. DOI: https:\/\/doi.org\/10.1109\/LRA.2015.2503143.","journal-title":"IEEE Robotics and Automation Letters"},{"issue":"4","key":"1568_CR14","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1109\/LRA.2017.2715406","volume":"2","author":"J Banff","year":"2017","unstructured":"J. Banff, N. Basilico, F. Amigoni. Intractability of time-optimal multirobot path planning on 2D grid graphs with holes. IEEE Robotics and Automation Letters, vol. 2, no. 4, pp. 1941\u20131947, 2017. DOI: https:\/\/doi.org\/10.1109\/LRA.2017.2715406.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"1568_CR15","doi-asserted-by":"publisher","unstructured":"J. Li, D. Harabor, P. J. Stuckey, H. Ma, G. Gange, S. Koenig. Pairwise symmetry reasoning for multi-agent path finding search. Artificial Intelligence, vol. 301, Article number 103574, 2021. DOI: https:\/\/doi.org\/10.1016\/j.artint.2021.103574.","DOI":"10.1016\/j.artint.2021.103574"},{"key":"1568_CR16","doi-asserted-by":"publisher","unstructured":"H. Zhang, J. Li, P. Surynek, T. K. S. Kumar, S. Koenig. Multi-agent path finding with mutex propagation. Artificial Intelligence, vol. 311, Article number 103766, 2022. DOI: https:\/\/doi.org\/10.1016\/j.artint.2022.103766.","DOI":"10.1016\/j.artint.2022.103766"},{"key":"1568_CR17","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1609\/icaps.v32i1.19798","volume-title":"Proceedings of the 32nd International Conference on Automated Planning and Scheduling","author":"S Hu","year":"2022","unstructured":"S. Hu, D. D. Harabor, G. Gange, P. J. Stuckey, N. R. Sturtevant. Multi-agent path finding with temporal jump point search. In Proceedings of the 32nd International Conference on Automated Planning and Scheduling, Singapore, pp. 169\u2013173, 2022. DOI: https:\/\/doi.org\/10.1609\/icaps.v32i1.19798."},{"key":"1568_CR18","doi-asserted-by":"publisher","first-page":"95099","DOI":"10.1109\/ACCESS.2020.2995392","volume":"8","author":"Z Yang","year":"2020","unstructured":"Z. Yang, M. Tang, Z. Li, Z. Ren, Q. Zhang. GPU accelerated polar harmonic transforms for feature extraction in ITS applications. IEEE Access, vol. 8, pp. 95099\u201395108, 2020. DOI: https:\/\/doi.org\/10.1109\/ACCESS.2020.2995392.","journal-title":"IEEE Access"},{"key":"1568_CR19","doi-asserted-by":"publisher","first-page":"1406","DOI":"10.1109\/ICIP40778.2020.9191179","volume-title":"Proceedings of IEEE International Conference on Image Processing","author":"M Tang","year":"2020","unstructured":"M. Tang, Z. Li, Z. Yang, Y. Zhan, J. Su, W. Yu. Gpu accelerated polar Fourier analysis for feature extraction. In Proceedings of IEEE International Conference on Image Processing, IEEE, Abu Dhabi, UAE, pp. 1406\u20131410, 2020. DOI: https:\/\/doi.org\/10.1109\/ICIP40778.2020.9191179."},{"issue":"5","key":"1568_CR20","doi-asserted-by":"publisher","first-page":"2502","DOI":"10.1287\/ijoc.2022.1193","volume":"34","author":"J Gmys","year":"2022","unstructured":"J. Gmys. Exactly solving hard permutation flowshop scheduling problems on Peta-scale GPU-accelerated supercomputers. INFORMS Journal on Computing, vol. 34, no. 5, pp. 2502\u20132522, 2022. DOI: https:\/\/doi.org\/10.1287\/ijoc.2022.1193.","journal-title":"INFORMS Journal on Computing"},{"key":"1568_CR21","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","volume":"219","author":"G Sharon","year":"2015","unstructured":"G. Sharon, R. Stern, A. Felner, N. R. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, vol. 219, pp. 40\u201366, 2015. DOI: https:\/\/doi.org\/10.1016\/j.artint.2014.11.006.","journal-title":"Artificial Intelligence"},{"key":"1568_CR22","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/1837274.1837289","volume-title":"Proceedings of the 47th Design Automation Conference","author":"L Luo","year":"2010","unstructured":"L. Luo, M. Wong, W. M. Hwu. An effective GPU implementation of breadth-first search. In Proceedings of the 47th Design Automation Conference, IEEE, Anaheim, USA, pp. 52\u201355, 2010."},{"key":"1568_CR23","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1609\/aaai.v29i1.9367","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence","author":"Y Zhou","year":"2015","unstructured":"Y. Zhou, J. Zeng. Massively parallel A* search on a GPU. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, USA, pp. 1248\u20131254, 2015. DOI: https:\/\/doi.org\/10.1609\/aaai.v29i1.9367."},{"key":"1568_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cag.2019.10.006","volume":"86","author":"V Rahmani","year":"2020","unstructured":"V. Rahmani, N. Pelecha Multi-agent parallel hierarchical path finding in navigation meshes (MA-HNA*). Computers & Graphics, vol. 86, pp. 1\u201314, 2020. DOI: https:\/\/doi.org\/10.1016\/j.cag.2019.10.006.","journal-title":"Computers & Graphics"},{"key":"1568_CR25","first-page":"65","volume-title":"Proceedings of the 23rd ACM SIGGRAPH\/EUROGRAPHICS Symposium on Graphics Hardware","author":"A Bleiweiss","year":"2008","unstructured":"A. Bleiweiss. GPU accelerated pathfinding. In Proceedings of the 23rd ACM SIGGRAPH\/EUROGRAPHICS Symposium on Graphics Hardware, Sarajevo, Bosnia and Herzegovina, pp. 65\u201374, 2008."},{"issue":"2","key":"1568_CR26","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P E Hart","year":"1968","unstructured":"P. E. Hart, N. J. Nilsson, B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100\u2013107, 1968. DOI: https:\/\/doi.org\/10.1109\/TSSC.1968.300136.","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"1568_CR27","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1609\/aaai.v24i1.7564","volume-title":"Proceedings of the 24th AAAI Conference on Artificial Intelligence","author":"T Standley","year":"2010","unstructured":"T. Standley. Finding optimal solutions to cooperative pathfinding problems. In Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, USA, pp. 173\u2013178, 2010. DOI: https:\/\/doi.org\/10.1609\/aaai.v24i1.7564."},{"key":"1568_CR28","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1109\/ICTAI59109.2023.00055","volume-title":"Proceedings of the 35th International Conference on Tools with Artificial Intelligence","author":"P Surynek","year":"2023","unstructured":"P. Surynek. Non-refined abstractions in counterexample guided abstraction refinement for multi-agent path finding. In Proceedings of the 35th International Conference on Tools with Artificial Intelligence, IEEE, Atlanta, USA, pp. 333\u2013340, 2023. DOI: https:\/\/doi.org\/10.1109\/ICTAI59109.2023.00055."}],"container-title":["Machine Intelligence Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11633-025-1568-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11633-025-1568-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11633-025-1568-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T22:51:18Z","timestamp":1757285478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11633-025-1568-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,25]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["1568"],"URL":"https:\/\/doi.org\/10.1007\/s11633-025-1568-y","relation":{},"ISSN":["2731-538X","2731-5398"],"issn-type":[{"value":"2731-538X","type":"print"},{"value":"2731-5398","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,25]]},"assertion":[{"value":"31 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declared that they have no conflicts of interest to this work.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations of conflict of interest"}}]}}