{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T06:41:44Z","timestamp":1769755304540,"version":"3.49.0"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SOCS"],"abstract":"<jats:p>Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-Based Planning (LSRP) is proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSPR* and test it against several baselines with up to 1000 agents in various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.<\/jats:p>","DOI":"10.1609\/socs.v18i1.36016","type":"journal-article","created":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T06:06:55Z","timestamp":1753078015000},"page":"275-276","source":"Crossref","is-referenced-by-count":1,"title":["LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions (Extended Abstract)"],"prefix":"10.1609","volume":"18","author":[{"given":"Shuai","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shizhe","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongqiang","family":"Ren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9382","published-online":{"date-parts":[[2025,7,20]]},"container-title":["Proceedings of the International Symposium on Combinatorial Search"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/36016\/38171","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/download\/36016\/38171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T07:01:07Z","timestamp":1753081267000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/SOCS\/article\/view\/36016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,20]]},"references-count":0,"URL":"https:\/\/doi.org\/10.1609\/socs.v18i1.36016","relation":{},"ISSN":["2832-9163","2832-9171"],"issn-type":[{"value":"2832-9163","type":"electronic"},{"value":"2832-9171","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7,20]]}}}