{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T14:20:34Z","timestamp":1779373234170,"version":"3.53.1"},"reference-count":21,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:00:00Z","timestamp":1746057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems"],"abstract":"<jats:p>Lifelong multi-agent pathfinding has two interrelated aspects: one is to find conflict-free paths for the agents, and the other is to resolve the conflicts among the agents in the best possible way. We focus on the first aspect by investigating three hierarchical pathfinding approaches, while we apply the same conflict resolution method. We formally present the three pathfinding options: map reduction using fixed waypoints, map reduction using dynamic waypoints, and the classic grid region-based approach. We point out the problem of emerging conflicts in lifelong multi-agent pathfinding with turns. We describe how we evaluate the proposed solutions to example scenarios from the League of Robot Runners competition, and we formulate the goals of the empirical analysis. Based on the experimental results, we point out the need to find the sweet spot between response time and throughput.<\/jats:p>","DOI":"10.3390\/systems13050331","type":"journal-article","created":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T09:16:12Z","timestamp":1746090972000},"page":"331","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Empirical Analysis of Hierarchical Pathfinding in Lifelong Multi-Agent Pathfinding with Turns"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8088-4528","authenticated-orcid":false,"given":"L\u00e1szl\u00f3 Z.","family":"Varga","sequence":"first","affiliation":[{"name":"Faculty of Informatics, ELTE E\u00f6tv\u00f6s Lor\u00e1nd University, P\u00e1zm\u00e1ny P\u00e9ter S\u00e9t\u00e1ny 1\/C, H-1117 Budapest, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,5,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/3137574.3137579","article-title":"AI buzzwords explained: Multi-agent path finding (MAPF)","volume":"3","author":"Ma","year":"2017","journal-title":"AI Matters"},{"key":"ref_2","first-page":"1261","article-title":"An Optimization Variant of Multi-Robot Path Planning Is Intractable","volume":"24","author":"Surynek","year":"2010","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_3","first-page":"29","article-title":"Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges","volume":"8","author":"Felner","year":"2017","journal-title":"Proc. Int. Symp. Comb. Search"},{"key":"ref_4","first-page":"9","article-title":"Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses","volume":"29","author":"Wurman","year":"2008","journal-title":"AI Mag."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Jakab, O., and Varga, L.Z. (2024). Options to Speed-Up Search in Lifelong Multi-Agent Pathfinding. Advances in Practical Applications of Agents, Multi-Agent Systems, and Digital Twins: The PAAMS Collection, Springer Nature.","DOI":"10.1007\/978-3-031-70415-4_11"},{"key":"ref_6","first-page":"1","article-title":"Near Optimal Hierarchical Path-Finding","volume":"1","author":"Botea","year":"2004","journal-title":"J. Game Dev."},{"key":"ref_7","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":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_8","first-page":"117","article-title":"Cooperative Pathfinding","volume":"1","author":"Silver","year":"2005","journal-title":"Proc. AAAI Conf. Artif. Intell. Interact. Digit. Entertain."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Phillips, M., and Likhachev, M. (2011, January 9\u201313). SIPP: Safe interval path planning for dynamic environments. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China.","DOI":"10.1109\/ICRA.2011.5980306"},{"key":"ref_10","first-page":"76","article-title":"A Comparison of High-Level Approaches for Speeding Up Pathfinding","volume":"6","author":"Sturtevant","year":"2010","journal-title":"Proc. AAAI Conf. Artif. Intell. Interact. Digit. Entertain."},{"key":"ref_11","first-page":"209","article-title":"A Hierarchical Approach to Multi-Agent Path Finding","volume":"12","author":"Zhang","year":"2021","journal-title":"Proc. Int. Symp. Comb. Search"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cag.2019.10.006","article-title":"Multi-agent parallel hierarchical path finding in navigation meshes (MA-HNA*)","volume":"86","author":"Rahmani","year":"2020","journal-title":"Comput. Graph."},{"key":"ref_13","first-page":"309","article-title":"Hierarchical Control Framework for Path Planning of Mobile Robots in Dynamic Environments Through Global Guidance and Reinforcement Learning","volume":"12","author":"Zhao","year":"2024","journal-title":"IEEE Internet Things J."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","article-title":"Conflict-based search for optimal multi-agent pathfinding","volume":"219","author":"Sharon","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_15","first-page":"19","article-title":"Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem","volume":"5","author":"Barer","year":"2014","journal-title":"Proc. Int. Symp. Comb. Search"},{"key":"ref_16","first-page":"7643","article-title":"Searching with Consistent Prioritization for Multi-Agent Path Finding","volume":"33","author":"Ma","year":"2019","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_17","first-page":"11272","article-title":"Lifelong Multi-Agent Path Finding in Large-Scale Warehouses","volume":"35","author":"Li","year":"2021","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Li, J., Chen, Z., Harabor, D., Stuckey, P.J., and Koenig, S. (2021, January 19\u201327). Anytime Multi-Agent Path Finding via Large Neighborhood Search. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, IJCAI-2021, Virtual.","DOI":"10.24963\/ijcai.2021\/568"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"103752","DOI":"10.1016\/j.artint.2022.103752","article-title":"Priority inheritance with backtracking for iterative multi-agent path finding","volume":"310","author":"Okumura","year":"2022","journal-title":"Artif. Intell."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1109\/TITS.2015.2506900","article-title":"Intention-Aware Routing of Electric Vehicles","volume":"17","author":"Stein","year":"2016","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_21","first-page":"221","article-title":"On Intention-Propagation-Based Prediction in Autonomously Self-adapting Navigation","volume":"16","author":"Varga","year":"2015","journal-title":"Scalable Comput. Pract. Exp."}],"container-title":["Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-8954\/13\/5\/331\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:25:41Z","timestamp":1760030741000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-8954\/13\/5\/331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,1]]},"references-count":21,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2025,5]]}},"alternative-id":["systems13050331"],"URL":"https:\/\/doi.org\/10.3390\/systems13050331","relation":{},"ISSN":["2079-8954"],"issn-type":[{"value":"2079-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,1]]}}}