{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:18:55Z","timestamp":1759331935555,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T00:00:00Z","timestamp":1685491200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T00:00:00Z","timestamp":1685491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11972314"],"award-info":[{"award-number":["11972314"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many existing multi-agent path finding (MAPF) solvers focus on completeness, speed, or optimization. However, completeness and rapidity are usually in conflict with each other, which makes these algorithms far from satisfactory in practical applications. Motivated by this realistic requirement, we propose an efficient decoupling method to accelerate the solution of large MAPF problems. First, we define the concept of \u2018non-essential vertex\u2019-vertices which are not needed to solve a MAPF problem, and a scheme to identify them. Then, a decoupling scheme based on \u2018non-essential vertex\u2019 is proposed, which will assign higher priorities to agents whose goal positions are non-essential vertices and lower priorities to agents whose start positions are non-essential vertices. That is, invoking our decoupling algorithm can decouple any given MAPF problem into three subproblems while maintaining the completeness of the solution. All three sub-MAPF problems can be solved sequentially by a complete solver (e.g., CBS or EECBS, etc.), and two of them can also be solved by a prioritized planning algorithm. We have conducted several experiments in different workspaces, and the statistical results show that the proposed decoupling method significantly improves the speed and success rate of existing MAPF solvers with almost no degradation in solution quality when solving problems with high agent density. In addition, the solving efficiency can be further improved if the prioritized planning algorithm is invoked to solve the first and third sub-MAPF problems.<\/jats:p>","DOI":"10.1007\/s40747-023-01088-2","type":"journal-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T04:16:44Z","timestamp":1685506604000},"page":"6767-6780","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A decoupling method for solving the multi-agent path finding problem"],"prefix":"10.1007","volume":"9","author":[{"given":"Bin","family":"Liao","sequence":"first","affiliation":[]},{"given":"Shenrui","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Yi","family":"Hua","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4404-5820","authenticated-orcid":false,"given":"Fangyi","family":"Wan","sequence":"additional","affiliation":[]},{"given":"Xinlin","family":"Qing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,31]]},"reference":[{"key":"1088_CR1","doi-asserted-by":"crossref","unstructured":"Tr\u00fcg S, Hoffmann J, Nebel B (2004) Applying automatic planning techniques to airport ground-traffic control-a feasibility study","DOI":"10.1007\/978-3-540-30221-6_15"},{"issue":"1","key":"1088_CR2","first-page":"9","volume":"29","author":"PR Wurman","year":"2008","unstructured":"Wurman PR, D\u2019Andrea R, Mountz M (2008) Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Mag 29(1):9","journal-title":"AI Mag"},{"issue":"2\u20133","key":"1088_CR3","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0921-8890(02)00256-7","volume":"41","author":"M Bennewitz","year":"2002","unstructured":"Bennewitz M, Burgard W, Thrun S (2002) Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots. Robot Auton Syst 41(2\u20133):89\u201399","journal-title":"Robot Auton Syst"},{"key":"1088_CR4","unstructured":"Stern R, Sturtevant NR, Felner A, Koenig S, Ma H, Walker TT, Li J, Atzmon D, Cohen L, Kumar TS et al (2019) Multi-agent pathfinding: definitions, variants, and benchmarks. In: Twelfth annual symposium on combinatorial search"},{"issue":"2","key":"1088_CR5","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100\u2013107","journal-title":"IEEE Trans Syst Sci Cybern"},{"key":"1088_CR6","unstructured":"\u010c\u00e1p M, Nov\u00e1k P, Vok\u0159\u00ednek J, P\u011bchou\u010dek M (2013) Multi-agent rrt*: Sampling-based cooperative pathfinding. arXiv:1302.2828"},{"key":"1088_CR7","doi-asserted-by":"publisher","first-page":"168743","DOI":"10.1109\/ACCESS.2020.3023200","volume":"8","author":"J Jiang","year":"2020","unstructured":"Jiang J, Wu K (2020) Cooperative pathfinding based on memory-efficient multi-agent rrt. IEEE Access 8:168743\u2013168750","journal-title":"IEEE Access"},{"issue":"2","key":"1088_CR8","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1109\/LRA.2020.2967326","volume":"5","author":"SD Han","year":"2020","unstructured":"Han SD, Yu J (2020) Ddm: fast near-optimal multi-robot path planning using diversified-path and optimal sub-problem solution database heuristics. IEEE Robot Autom Lett 5(2):1350\u20131357","journal-title":"IEEE Robot Autom Lett"},{"key":"1088_CR9","doi-asserted-by":"crossref","unstructured":"Kornhauser DM, Miller G, Spirakis P (1984) Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, Master\u2019s thesis, M.I. T., Dept. of Electrical Engineering and Computer Science","DOI":"10.1109\/SFCS.1984.715921"},{"key":"1088_CR10","unstructured":"Luna RJ, Bekris KE (2011) Push and swap: fast cooperative path-finding with completeness guarantees. In: Twenty-second international joint conference on artificial intelligence"},{"key":"1088_CR11","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1613\/jair.4447","volume":"51","author":"B De Wilde","year":"2014","unstructured":"De Wilde B, Ter Mors AW, Witteveen C (2014) Push and rotate: a complete multi-agent pathfinding algorithm. J Artif Intell Res 51:443\u2013492","journal-title":"J Artif Intell Res"},{"key":"1088_CR12","doi-asserted-by":"crossref","unstructured":"Wagner G, Choset H (2011) M*: a complete multirobot path planning algorithm with performance bounds. In: IEEE\/RSJ international conference on intelligent robots and systems, pp 3260\u20133267. IEEE","DOI":"10.1109\/IROS.2011.6095022"},{"key":"1088_CR13","doi-asserted-by":"crossref","unstructured":"Ren Z, Rathinam S, Choset H (2021) Ms*: a new exact algorithm for multi-agent simultaneous multi-goal sequencing and path finding. In: 2021 IEEE international conference on robotics and automation (ICRA), pp 11560\u201311565. IEEE","DOI":"10.1109\/ICRA48506.2021.9561779"},{"key":"1088_CR14","doi-asserted-by":"crossref","unstructured":"Standley T (2010) Finding optimal solutions to cooperative pathfinding problems. In: Proceedings of the AAAI conference on artificial intelligence, vol\u00a024","DOI":"10.1609\/aaai.v24i1.7564"},{"key":"1088_CR15","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.artint.2012.11.006","volume":"195","author":"G Sharon","year":"2013","unstructured":"Sharon G, Stern R, Goldenberg M, Felner A (2013) The increasing cost tree search for optimal multi-agent pathfinding. Artif Intell 195:470\u2013495","journal-title":"Artif Intell"},{"key":"1088_CR16","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 NR (2015) Conflict-based search for optimal multi-agent pathfinding. Artif Intell 219:40\u201366","journal-title":"Artif Intell"},{"key":"1088_CR17","unstructured":"Boyarski E, Felner A, Stern R, Sharon G, Tolpin D, Betzalel O, Shimony E (2015) Icbs: improved conflict-based search algorithm for multi-agent pathfinding. In: Twenty-fourth international joint conference on artificial intelligence"},{"key":"1088_CR18","doi-asserted-by":"crossref","unstructured":"Li J, Ruml W, Koenig S (2021) Eecbs: a bounded-suboptimal search for multi-agent path finding. In: Proceedings of the AAAI conference on artificial intelligence (AAAI), pp 12353\u201312362","DOI":"10.1609\/aaai.v35i14.17466"},{"key":"1088_CR19","doi-asserted-by":"crossref","unstructured":"Boyarski E, Felner A, Harabor D, Stuckey PJ, Cohen L, Li J, Koenig S (2020) Iterative-deepening conflict-based search. In: IJCAI, pp 4084\u20134090","DOI":"10.24963\/ijcai.2020\/565"},{"key":"1088_CR20","unstructured":"Cohen L (2020) Efficient bounded-suboptimal multi-agent path finding and motion planning via improvements to focal search, Ph.D. thesis, University of Southern California"},{"issue":"1","key":"1088_CR21","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF01840371","volume":"2","author":"M Erdmann","year":"1987","unstructured":"Erdmann M, Lozano-Perez T (1987) On multiple moving objects. Algorithmica 2(1):477\u2013521","journal-title":"Algorithmica"},{"issue":"3","key":"1088_CR22","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/TASE.2015.2445780","volume":"12","author":"M \u010c\u00e1p","year":"2015","unstructured":"\u010c\u00e1p M, Nov\u00e1k P, Kleiner A, Seleck\u1ef3 M (2015) Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Trans Autom Sci Eng 12(3):835\u2013849","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"1088_CR23","doi-asserted-by":"crossref","unstructured":"\u010c\u00e1p M, Vok\u0159\u00ednek J, Kleiner A (2015) Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures. In: Twenty-fifth international conference on automated planning and scheduling","DOI":"10.1609\/icaps.v25i1.13696"},{"key":"1088_CR24","doi-asserted-by":"crossref","unstructured":"Dewangan RK, Shukla A, Godfrey WW (2017) Survey on prioritized multi robot path planning. In: IEEE international conference on smart technologies and management for computing, communication, controls, energy and materials (ICSTM), pp 423\u2013428. IEEE","DOI":"10.1109\/ICSTM.2017.8089197"},{"key":"1088_CR25","unstructured":"Bennewitz M, Burgard W (2001) Finding solvable priority schemes for decoupled path planning techniques for teams of mobile robots. In: Proc. of the international symposium on intelligent robotic systems (SIRS), Citeseer"},{"key":"1088_CR26","doi-asserted-by":"crossref","unstructured":"Amir O, Sharon G, Stern R (2015) Multi-agent pathfinding as a combinatorial auction. In: Twenty-ninth AAAI conference on artificial intelligence","DOI":"10.1609\/aaai.v29i1.9427"},{"key":"1088_CR27","doi-asserted-by":"crossref","unstructured":"Morag J, Stern R, Felner A, Atzmon D, Boyarski E (2021) Optimality in online multi-agent path finding","DOI":"10.1609\/socs.v12i1.18592"},{"issue":"2\u20133","key":"1088_CR28","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0921-8890(02)00256-7","volume":"41","author":"M Bennewitz","year":"2002","unstructured":"Bennewitz M, Burgard W, Thrun S (2002) Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots. Robot Auton Syst 41(2\u20133):89\u201399","journal-title":"Robot Auton Syst"},{"key":"1088_CR29","unstructured":"Andreychuk A, Yakovlev K (2018) Two techniques that enhance the performance of multi-robot prioritized path planning. arXiv:1805.01270"},{"key":"1088_CR30","doi-asserted-by":"crossref","unstructured":"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\u00a04, pp 3526\u20133533. IEEE","DOI":"10.1109\/ROBOT.1997.606881"},{"key":"1088_CR31","doi-asserted-by":"crossref","unstructured":"Ma H, Harabor D, Stuckey PJ, Li J, Koenig S (2019) Searching with consistent prioritization for multi-agent path finding. In: Proceedings of the AAAI conference on artificial intelligence, vol\u00a033, pp 7643\u20137650","DOI":"10.1609\/aaai.v33i01.33017643"},{"key":"1088_CR32","doi-asserted-by":"crossref","unstructured":"Wu W, Bhattacharya S, Prorok A (2020) Multi-robot path deconfliction through prioritization by path prospects. In: 2020 IEEE international conference on robotics and automation (ICRA), pp 9809\u20139815. IEEE","DOI":"10.1109\/ICRA40945.2020.9196813"},{"key":"1088_CR33","doi-asserted-by":"crossref","unstructured":"Van Den\u00a0Berg JP, Overmars MH (2005) Prioritized motion planning for multiple robots. In: 2005 IEEE\/RSJ international conference on intelligent robots and systems, pp 430\u2013435. IEEE","DOI":"10.1109\/IROS.2005.1545306"},{"key":"1088_CR34","doi-asserted-by":"crossref","unstructured":"Velagapudi P, Sycara K, Scerri P (2010) Decentralized prioritized planning in large multirobot teams. In: 2010 IEEE\/RSJ international conference on intelligent robots and systems, pp 4603\u20134609. IEEE","DOI":"10.1109\/IROS.2010.5649438"},{"key":"1088_CR35","doi-asserted-by":"crossref","unstructured":"van Den\u00a0Berg J, Snoeyink J, Lin MC, Manocha D (2009) Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: Robotics: science and systems, vol\u00a02, pp 2\u20133","DOI":"10.15607\/RSS.2009.V.018"},{"issue":"2","key":"1088_CR36","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1109\/LRA.2020.2967317","volume":"5","author":"H Wang","year":"2020","unstructured":"Wang H, Rubenstein M (2020) Walk, stop, count, and swap: decentralized multi-agent path finding with theoretical guarantees. IEEE Robot Autom Lett 5(2):1119\u20131126","journal-title":"IEEE Robot Autom Lett"},{"key":"1088_CR37","doi-asserted-by":"crossref","unstructured":"Li J, Chen Z, Zheng Y, Chan S-H, Harabor D, Stuckey PJ, Ma H, Koenig S (2021) Scalable rail planning and replanning: winning the 2020 flatland challenge. In: Proceedings of the international conference on automated planning and scheduling, vol 31, pp 477\u2013485","DOI":"10.1609\/icaps.v31i1.15994"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-023-01088-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-023-01088-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-023-01088-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T14:26:43Z","timestamp":1729520803000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-023-01088-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,31]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1088"],"URL":"https:\/\/doi.org\/10.1007\/s40747-023-01088-2","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"type":"print","value":"2199-4536"},{"type":"electronic","value":"2198-6053"}],"subject":[],"published":{"date-parts":[[2023,5,31]]},"assertion":[{"value":"3 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2023","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 non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable. Our manuscript does not report the results of studies involving humans or animals.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Informed consent was obtained from all individual participants included in the study.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}}]}}