{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T00:28:01Z","timestamp":1768004881396,"version":"3.49.0"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"12","license":[{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper proposes a novel two-layer framework based on conflict-based search and regional divisions to improve the efficiency of multi-robot path planning. The high-level layer targets the reduction of conflicts and deadlocks, while the low-level layer is responsible for actual path planning. Distinct from previous dual-level search frameworks, the novelties of this work are (1) subdivision of planning regions for each robot to decrease the number of conflicts encountered during planning; (2) consideration of the number of robots in the region during planning in the node expansion stage of A*, and (3) formal proof demonstrating the nonzero probability of the proposed method in obtaining a solution, along with providing the upper bound of the solution in a special case. Experimental comparisons with Enhanced Conflict-Based Search demonstrate that the proposed method not only reduces the number of conflicts but also achieves a computation time reduction of over 30%.<\/jats:p>","DOI":"10.1017\/s0263574724000894","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T04:31:00Z","timestamp":1724733060000},"page":"4150-4160","source":"Crossref","is-referenced-by-count":4,"title":["RH-ECBS: enhanced conflict-based search for MRPP with region heuristics"],"prefix":"10.1017","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3552-5862","authenticated-orcid":false,"given":"Zhangchao","family":"Pan","sequence":"first","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Runhua","family":"Wang","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingchen","family":"Bi","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuebo","family":"Zhang","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4112-2250","authenticated-orcid":false,"given":"Jingjin","family":"Yu","sequence":"additional","affiliation":[{"name":"Rutgers University New Brunswick"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,8,27]]},"reference":[{"key":"S0263574724000894_ref15","first-page":"12353","article-title":"EECBS: A bounded-suboptimal search for multi-agent path finding","volume":"35","author":"Li","year":"2021","journal-title":"Proceed AAAI Conf Artif Intell"},{"key":"S0263574724000894_ref12","article-title":"Icbs: The improved conflict-based search algorithm for multi-agent pathfinding","volume":"6","author":"Boyarski","year":"2015","journal-title":"Proceed Int Symp Combin Sear"},{"key":"S0263574724000894_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32723-0_15"},{"key":"S0263574724000894_ref23","doi-asserted-by":"publisher","DOI":"10.1049\/trit.2020.0024"},{"key":"S0263574724000894_ref27","first-page":"159","article-title":"ECBS with flex distribution for bounded-suboptimal multi-agent path finding","volume":"12","author":"Chan","year":"2021","journal-title":"Proceed Int Symp Combin Sear"},{"key":"S0263574724000894_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341668"},{"key":"S0263574724000894_ref18","doi-asserted-by":"publisher","DOI":"10.1177\/027836499801700706"},{"key":"S0263574724000894_ref4","first-page":"9368","article-title":"Anytime multi-agent path finding via machine learning-guided large neighborhood search","volume":"36","author":"Huang","year":"2022","journal-title":"Proceed AAAI Conf Artif Intell"},{"key":"S0263574724000894_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8461113"},{"key":"S0263574724000894_ref7","unstructured":"[7] Standley, T. and Korf, R. , \u201cComplete Algorithms for Cooperative Pathfinding Problems,\u201d In: IJCAI, (2011)."},{"key":"S0263574724000894_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.3044834"},{"key":"S0263574724000894_ref17","doi-asserted-by":"crossref","unstructured":"[17] Guo, T. and Yu, J. , \u201cSub-1.5 time-optimal multi-robot path planning on grids in polynomial time, \u201c(2022) arXiv preprint arXiv: 2201.08976.","DOI":"10.15607\/RSS.2022.XVIII.057"},{"key":"S0263574724000894_ref14","article-title":"Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem","volume":"5","author":"Barer","year":"2014","journal-title":"Proceed Int Symp Combin Sear"},{"key":"S0263574724000894_ref2","first-page":"1","article-title":"CURE: A hierarchical framework for multi-robot autonomous exploration inspired by centroids of unknown regions","volume":"99","author":"Bi","year":"2023","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"S0263574724000894_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.11.006"},{"key":"S0263574724000894_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3161699"},{"key":"S0263574724000894_ref1","first-page":"10256","article-title":"MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search","volume":"36","author":"Li","year":"2022","journal-title":"Proceed AAAI Conf Artif Intell"},{"key":"S0263574724000894_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.006"},{"key":"S0263574724000894_ref3","first-page":"1443","article-title":"Structure and intractability of optimal multi-robot path planning on graphs","volume":"27","author":"Yu","year":"2013","journal-title":"Proceed AAAI Conf Artif Intell"},{"key":"S0263574724000894_ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2120810"},{"key":"S0263574724000894_ref16","doi-asserted-by":"publisher","DOI":"10.1177\/02783649211059844"},{"key":"S0263574724000894_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631119"},{"key":"S0263574724000894_ref13","article-title":"Adding heuristics to conflict-based search for multi-agent path finding","volume":"28","author":"Felner","year":"2018","journal-title":"Proceed Int Conf Autom Plan Sched"},{"key":"S0263574724000894_ref6","first-page":"173","article-title":"Finding optimal solutions to cooperative pathfinding problems","volume":"24","author":"Standley","year":"2010","journal-title":"Proceed AAAI Conf Artif Intell"},{"key":"S0263574724000894_ref8","doi-asserted-by":"crossref","unstructured":"[8] Wagner, G. and Choset, H. , \u201cM*: A Complete Multirobot Path Planning Algorithm with Performance Bounds,\u201d In: 2011 IEEE\/RSJ international conference on intelligent robots and systems. IEEE, (2011).","DOI":"10.1109\/IROS.2011.6095022"},{"key":"S0263574724000894_ref5","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2408"},{"key":"S0263574724000894_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2008.4543489"},{"key":"S0263574724000894_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19457-3_1"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574724000894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T07:52:07Z","timestamp":1755589927000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574724000894\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,27]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["S0263574724000894"],"URL":"https:\/\/doi.org\/10.1017\/s0263574724000894","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"value":"0263-5747","type":"print"},{"value":"1469-8668","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,27]]}}}