{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T06:11:10Z","timestamp":1778652670760,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018699","name":"HORIZON EUROPE Digital, Industry and Space","doi-asserted-by":"publisher","award":["101138451"],"award-info":[{"award-number":["101138451"]}],"id":[{"id":"10.13039\/100018699","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Intell Robot Syst"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This article introduces a novel Multi-agent path planning scheme based on Conflict Based Search (CBS) for heterogeneous holonomic and non-holonomic agents, designated as Heterogeneous CBS (HCBS). The proposed methodology employs a hybrid <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$A^*$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>\u2217<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> algorithm for non-holonomic car-like robots and a conventional <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$A^*$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>\u2217<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> algorithm for holonomic robots. Following this, a body conflict detection strategy is utilized to construct the conflict tree, bridging the initial path planning with the resolution of conflicts among agents. Moreover, we present two variants of HCBS: the Enhanced Conflict-Based Search (EHCBS) and the Depth-First Conflict-Based Search (DFHCBS). We evaluate the efficacy of our proposed algorithms\u2014HCBS, EHCBS, and DFHCBS\u2014against a standard prioritized planning algorithm, focusing on success rates and computational efficiency in environments with varying numbers of agents and obstacles. The empirical results demonstrate that EHCBS exhibits superior computational efficiency in small, dense environments, while DFHCBS performs well in larger-scale environments. This highlights the adaptability of our proposed approaches in various settings, proving the computational advantage of EHCBS and DFHCBS over traditional methods.<\/jats:p>","DOI":"10.1007\/s10846-025-02229-0","type":"journal-article","created":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T06:32:38Z","timestamp":1739428358000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Multi-agent Path Planning Based on Conflict-Based Search (CBS) Variations for Heterogeneous Robots"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6762-7172","authenticated-orcid":false,"given":"Yifan","family":"Bai","sequence":"first","affiliation":[]},{"given":"Shruti","family":"Kotpalliwar","sequence":"additional","affiliation":[]},{"given":"Christoforos","family":"Kanellakis","sequence":"additional","affiliation":[]},{"given":"George","family":"Nikolakopoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,13]]},"reference":[{"key":"2229_CR1","doi-asserted-by":"publisher","unstructured":"Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D., Shimony, E.: Icbs: The improved conflict-based search algorithm for multi-agent pathfinding. In: Proceedings of the International Symposium on Combinatorial Search, vol. 6, pp. 223\u2013225 (2015). https:\/\/doi.org\/10.1609\/socs.v6i1.18343","DOI":"10.1609\/socs.v6i1.18343"},{"key":"2229_CR2","doi-asserted-by":"publisher","unstructured":"Barer, M., Sharon, G., Stern, R., Felner, A.: Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In: Proceedings of the International Symposium on Combinatorial Search, vol. 5, pp. 19\u201327 (2014). https:\/\/doi.org\/10.1609\/socs.v5i1.18315","DOI":"10.1609\/socs.v5i1.18315"},{"issue":"3","key":"2229_CR3","doi-asserted-by":"publisher","first-page":"5816","DOI":"10.1109\/LRA.2021.3074883","volume":"6","author":"Z Chen","year":"2021","unstructured":"Chen, Z., Alonso-Mora, J., Bai, X., Harabor, D.D., Stuckey, P.J.: Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics and Automation Letters 6(3), 5816\u20135823 (2021). https:\/\/doi.org\/10.1109\/LRA.2021.3074883","journal-title":"IEEE Robotics and Automation Letters"},{"key":"2229_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2021.103871","volume":"146","author":"A Contini","year":"2021","unstructured":"Contini, A., Farinelli, A.: Coordination approaches for multi-item pickup and delivery in logistic scenarios. Robot. Auton. Syst. 146, 103871 (2021). https:\/\/doi.org\/10.1016\/j.robot.2021.103871","journal-title":"Robot. Auton. Syst."},{"issue":"2","key":"2229_CR5","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1109\/TRO.2022.3216801","volume":"39","author":"A Camisa","year":"2022","unstructured":"Camisa, A., Testa, A., Notarstefano, G.: Multi-robot pickup and delivery via distributed resource allocation. IEEE Trans. Rob. 39(2), 1106\u20131118 (2022). https:\/\/doi.org\/10.1109\/TRO.2022.3216801","journal-title":"IEEE Trans. Rob."},{"key":"2229_CR6","unstructured":"Dolgov, D., Thrun, S., Montemerlo, M., Diebel, J.: Practical search techniques in path planning for autonomous driving. Ann Arbor 1001(48105), 18\u201380 (2008)"},{"key":"2229_CR7","doi-asserted-by":"publisher","unstructured":"Felner, A., Li, J., Boyarski, E., Ma, H., Cohen, L., Kumar, T.S., Koenig, S.: Adding heuristics to conflict-based search for multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 28, pp. 83\u201387 (2018). https:\/\/doi.org\/10.1609\/icaps.v28i1.13883","DOI":"10.1609\/icaps.v28i1.13883"},{"key":"2229_CR8","doi-asserted-by":"publisher","unstructured":"Gange, G., Harabor, D., Stuckey, P.J.: Lazy cbs: implicit conflict-based search using lazy clause generation. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 29, pp. 155\u2013162 (2019). https:\/\/doi.org\/10.1609\/icaps.v29i1.3471","DOI":"10.1609\/icaps.v29i1.3471"},{"key":"2229_CR9","doi-asserted-by":"publisher","unstructured":"H\u00f6nig, W., Kumar, T., Cohen, L., Ma, H., Xu, H., Ayanian, N., Koenig, S.: Multi-agent path finding with kinematic constraints. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 26, pp. 477\u2013485 (2016). https:\/\/doi.org\/10.1609\/icaps.v26i1.13796","DOI":"10.1609\/icaps.v26i1.13796"},{"key":"2229_CR10","doi-asserted-by":"publisher","unstructured":"Kottinger, J., Almagor, S., Lahijanian, M.: Conflict-based search for multi-robot motion planning with kinodynamic constraints. In: 2022 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 13494\u201313499 (2022). https:\/\/doi.org\/10.1109\/IROS47612.2022.9982018 . IEEE","DOI":"10.1109\/IROS47612.2022.9982018"},{"key":"2229_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103574","volume":"301","author":"J Li","year":"2021","unstructured":"Li, J., Harabor, D., Stuckey, P.J., Ma, H., Gange, G., Koenig, S.: Pairwise symmetry reasoning for multi-agent path finding search. Artif. Intell. 301, 103574 (2021). https:\/\/doi.org\/10.1016\/j.artint.2021.103574","journal-title":"Artif. Intell."},{"key":"2229_CR12","doi-asserted-by":"publisher","unstructured":"Li, J., Ruml, W., Koenig, S.: Eecbs: A bounded-suboptimal search for multi-agent path finding. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 12353\u201312362 (2021). https:\/\/doi.org\/10.48550\/arXiv.2010.01367","DOI":"10.48550\/arXiv.2010.01367"},{"issue":"2","key":"2229_CR13","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1109\/LRA.2020.3044834","volume":"6","author":"J Li","year":"2021","unstructured":"Li, J., Ran, M., Xie, L.: Efficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization. IEEE Robotics and Automation Letters 6(2), 405\u2013412 (2021). https:\/\/doi.org\/10.1109\/LRA.2020.3044834","journal-title":"IEEE Robotics and Automation Letters"},{"key":"2229_CR14","doi-asserted-by":"publisher","unstructured":"Li, J., Surynek, P., Felner, A., Ma, H., Kumar, T.S., Koenig, S.: Multi-agent path finding for large agents. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 7627\u20137634 (2019). https:\/\/doi.org\/10.1609\/aaai.v33i01.33017627","DOI":"10.1609\/aaai.v33i01.33017627"},{"key":"2229_CR15","doi-asserted-by":"publisher","unstructured":"Ma, H., H\u00f6nig, W., Kumar, T.S., Ayanian, N., Koenig, S.: Lifelong path planning with kinematic constraints for multi-agent pickup and delivery. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 7651\u20137658 (2019). https:\/\/doi.org\/10.48550\/arXiv.1812.06355","DOI":"10.48550\/arXiv.1812.06355"},{"key":"2229_CR16","doi-asserted-by":"publisher","unstructured":"Ma, H., Harabor, D., Stuckey, P.J., Li, J., Koenig, S.: Searching with consistent prioritization for multi-agent path finding. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 7643\u20137650 (2019). https:\/\/doi.org\/10.48550\/arXiv.1812.06356","DOI":"10.48550\/arXiv.1812.06356"},{"key":"2229_CR17","doi-asserted-by":"publisher","first-page":"191617","DOI":"10.1109\/ACCESS.2020.3030190","volume":"8","author":"JP Queralta","year":"2020","unstructured":"Queralta, J.P., Taipalmaa, J., Pullinen, B.C., Sarker, V.K., Gia, T.N., Tenhunen, H., Gabbouj, M., Raitoharju, J., Westerlund, T.: Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision. Ieee Access 8, 191617\u2013191643 (2020). https:\/\/doi.org\/10.1109\/ACCESS.2020.3030190","journal-title":"Ieee Access"},{"issue":"2","key":"2229_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.2140\/pjm.1990.145.367","volume":"145","author":"J Reeds","year":"1990","unstructured":"Reeds, J., Shepp, L.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145(2), 367\u2013393 (1990)","journal-title":"Pac. J. Math."},{"key":"2229_CR19","doi-asserted-by":"publisher","unstructured":"Silver, D.: Cooperative pathfinding. In: Proceedings of the Aaai Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 1, pp. 117\u2013122 (2005). https:\/\/doi.org\/10.1609\/aiide.v1i1.18726","DOI":"10.1609\/aiide.v1i1.18726"},{"key":"2229_CR20","doi-asserted-by":"publisher","unstructured":"Scherer, J., Rinner, B.: Multi-robot persistent surveillance with connectivity constraints. IEEE Access 8, 15093\u201315109 (2020). https:\/\/doi.org\/10.1109\/ACCESS.2020.2967650","DOI":"10.1109\/ACCESS.2020.2967650"},{"key":"2229_CR21","doi-asserted-by":"publisher","unstructured":"Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T., et al: Multi-agent pathfinding: Definitions, variants, and benchmarks. In: Proceedings of the International Symposium on Combinatorial Search, vol. 10, pp. 151\u2013158 (2019). https:\/\/doi.org\/10.48550\/arXiv.1906.08291","DOI":"10.48550\/arXiv.1906.08291"},{"key":"2229_CR22","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","volume":"219","author":"G Sharon","year":"2015","unstructured":"Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40\u201366 (2015). https:\/\/doi.org\/10.1016\/j.artint.2014.11.006","journal-title":"Artif. Intell."},{"key":"2229_CR23","doi-asserted-by":"publisher","unstructured":"Standley, T.: Finding optimal solutions to cooperative pathfinding problems. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 24, pp. 173\u2013178 (2010). https:\/\/doi.org\/10.1609\/aaai.v24i1.7564","DOI":"10.1609\/aaai.v24i1.7564"},{"key":"2229_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2014.11.001","volume":"219","author":"G Wagner","year":"2015","unstructured":"Wagner, G., Choset, H.: Subdimensional expansion for multirobot path planning. Artif. Intell. 219, 1\u201324 (2015). https:\/\/doi.org\/10.1016\/j.artint.2014.11.001","journal-title":"Artif. Intell."},{"key":"2229_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2021.103997","volume":"150","author":"L Wen","year":"2022","unstructured":"Wen, L., Liu, Y., Li, H.: Cl-mapf: Multi-agent path finding for car-like robots with kinematic and spatiotemporal constraints. Robot. Auton. Syst. 150, 103997 (2022). https:\/\/doi.org\/10.1016\/j.robot.2021.103997","journal-title":"Robot. Auton. Syst."},{"key":"2229_CR26","doi-asserted-by":"publisher","unstructured":"Yu, J., LaValle, S.: Structure and intractability of optimal multi-robot path planning on graphs. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 27, pp. 1443\u20131449 (2013). https:\/\/doi.org\/10.1609\/aaai.v27i1.8541","DOI":"10.1609\/aaai.v27i1.8541"}],"container-title":["Journal of Intelligent &amp; Robotic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-025-02229-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10846-025-02229-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-025-02229-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T22:02:14Z","timestamp":1743890534000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10846-025-02229-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["2229"],"URL":"https:\/\/doi.org\/10.1007\/s10846-025-02229-0","relation":{},"ISSN":["1573-0409"],"issn-type":[{"value":"1573-0409","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,13]]},"assertion":[{"value":"11 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or nonfinancial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest\/Competing interests"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"26"}}