Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities
Authors: Yue Zhang, Zhe Chen, Daniel Harabor, Pierre Le Bodic, Peter J. Stuckey
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We instantiate our framework with different execution and replanning strategies, and experimentally evaluate them. Overall, we find that this framework can substantially improve the throughput by up to a factor 3 for lifelong MAPF, compared to approaches that handle delays with simple execution policies. |
| Researcher Affiliation | Academia | Monash University, Australia EMAIL |
| Pseudocode | Yes | Algorithm 1: PIE-D Framework Require: G, A ; k, Commit Window, P, Planner; E, Executor; D, Dummy Simulation 1: π P.Initial Planning(A) 2: while not interrupted do 3: states E.Get Current States() 4: πk, A.starts, A.goals D.Simulate(π, states) 5: π π \ πk 6: In parallel do: 7: E.execute(πk, k)) 8: π P.Plan( G, A , π) |
| Open Source Code | Yes | 2Code and benchmark instances are available at https://github.com/Yue Zhang-studyuse/LMAPF-delay |
| Open Datasets | Yes | We run experiments on four maps from different domains using grid-based Multi-Agent Path Finding (MAPF) benchmarks sourced from (Sturtevant 2012). ... Code and benchmark instances are available at https://github.com/Yue Zhang-studyuse/LMAPF-delay |
| Dataset Splits | No | For each map, we generate instances for different number of agents from 100 to 500 with increments of 100 for Random, 200 to 1400 with increments of 200 for Warehouse and Game, and 1000 to 5000 with increments of 1000 for City. The start and goal locations are randomly positioned. |
| Hardware Specification | Yes | The experiments are conducted on a cloud instance with 32GB RAM, 16 AMD EPYC-Rome CPUs. |
| Software Dependencies | No | We implement our framework in C++2 on top of PIE (Zhang et al. 2024). |
| Experiment Setup | Yes | We set l [1, 10] for all the experiments. ... For each timestep, we sample for each agent with a given delay probability p (p 0) to be delayed... We set commit length k = 3 ... we vary the commit length: either short commit (k = 3) or long commit (k = 10). ... For each instance, we run LMAPF evaluations for each algorithm once for 600 timesteps of LMAPF simulation. ... Replanning fails if it exceeds the 3s runtime timelimit. |