Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions
Authors: Shuai Zhou, Shizhe Zhao, Zhongqiang Ren
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We analyze the properties of our method and test it against several baselines with up to 1000 agents in various maps. Given a runtime limit, our method can handle an order of magnitude more agents than the baselines with about 25% longer makespan. For the experiments, we compare LSRP against several baselines including CCBS (Andreychuk et al. 2022) and prioritized planning in various maps from a MAPF benchmark (Stern et al. 2019), and the results show that LSRP can solve up to an order of magnitude more agents than existing methods with low runtime, despite about 25% longer makespan. |
| Researcher Affiliation | Academia | 1UM-SJTU Joint Institute, Shanghai Jiao Tong University, China 2SHIEN-MING WU School of Intelligent Engineering, South China University of Technology, China 3Department of Automation, Shanghai Jiao Tong University, China EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: LSRP, LSRP-SWAP Input: graph G, starts {v1 s, . . . , vn s }, goals {v1 g, . . . , vn g } Output: paths {π1, . . . , πn} 1: T {0}; ST {s0}; Φ {} 2: ϵ0 INITPRIORITY() 3: ϵ ϵ0 4: while T = do 5: sprev ST .back() 6: if i I, si prev.v = vi g then 7: return POSTPROCESS(ST ) 8: for i I do 9: if si prev.v = vi g then ϵi ϵi 0 10: else ϵi ϵi + 1 11: tmin T.pop() 12: Icurr EXTRACTAGENTS(I, tmin, sprev) 13: if T = then 14: tnext T.top() 15: else 16: tnext tmin + mini I,e E D(i, e) 17: snext GET SNEXT(Φ, Icurr, sprev) 18: for i Icurr in descending order of ϵi do 19: if si next = then 20: ASY-PUSH(i, {}, tmin, tnext, False) 21: (or ASY-PUSH-SWAP(i, {}, tmin, tnext, False)) 22: ST .append(snext) 23: Add si prev.tv for i I to T 24: return failure |
| Open Source Code | Yes | Code https://github.com/rap-lab-org/public LSRP Extended version https://arxiv.org/abs/2412.11678 |
| Open Datasets | Yes | Our experiments use three maps and the corresponding instances (starts and goals) from a MAPF benchmark (Stern et al. 2019). |
| Dataset Splits | No | The paper mentions running |
| Hardware Specification | Yes | All tests use Intel i5 CPU with 16GB RAM. |
| Software Dependencies | No | The paper states: "We implement our LSRP and LSRP-SWAP in C++", but does not specify any version numbers for C++ or any libraries used. |
| Experiment Setup | Yes | For each map, we run 25 instances with varying number of agents N, and we set a 30-seconds runtime limit for each instance. We make the grid maps four-connected, and each agent has a constant duration when going through any edge in the grid. This duration constant of agents vary from 1.0 to 5.0. We implement our LSRP and LSRP-SWAP in C++, and compare against two baselines. The first baseline is a modified CCBS (Andreychuk et al. 2022). The original CCBS implementation considers the shape of the agents and does not allow different agents to have different durations when going through the same edge. We modified this public implementation by using the duration conflict and allow different agents to have different duration. Note that the constraints remain sound (Andreychuk et al. 2022), and the solution obtained is optimal to MAPF-AA. The second baseline SIPP (see Sec. 3.3) adopts prioritized planning using SIPP (Phillips and Likhachev 2011) as the single-agent planner. It uses the same initial priority as LSRP and LSRP-SWAP. |