EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
Authors: Jiaoyang Li, Wheeler Ruml, Sven Koenig12353-12362
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically evaluate how each improvement affects performance, finding that their combination is best. EECBS with the improvements runs significantly faster than ECBS and BCP-7 (Lam and Le Bodic 2020) and e MDD-SAT (Surynek et al. 2018), two other state-of-the-art bounded-suboptimal MAPF algorithms. We evaluate the algorithms on 6 maps of different sizes and structures from the MAPF benchmark suite (Stern et al. 2019) with 8 different numbers of agents per map. We use the random scenarios, yielding 25 instances for each map and number of agents. We evaluate 10 different values of w for each setting, and the values of w decrease as the map size increases. |
| Researcher Affiliation | Academia | Jiaoyang Li,1 Wheeler Ruml,2 Sven Koenig1 1University of Southern California, Los Angeles, California, USA 2University of New Hampshire, Durham, New Hampshire, USA |
| Pseudocode | Yes | Algorithm 1: High-level search of EECBS. |
| Open Source Code | Yes | The code is available at https://github.com/Jiaoyang-Li/EECBS. |
| Open Datasets | Yes | We test it on 200 standard MAPF benchmarks (Stern et al. 2019) and We evaluate the algorithms on 6 maps of different sizes and structures from the MAPF benchmark suite (Stern et al. 2019). |
| Dataset Splits | No | The paper mentions using "200 standard MAPF benchmarks (Stern et al. 2019)" and "6 maps of different sizes and structures from the MAPF benchmark suite (Stern et al. 2019)". It describes using "25 instances for each number of agents" or "25 instances for each map and number of agents" for evaluation. However, it does not specify explicit training/validation/test splits of a dataset, as is common in machine learning. These are search problems, and the instances are directly used for performance testing. |
| Hardware Specification | Yes | The algorithms are implemented in C++, and the experiments are conducted on Ubuntu 20.04 LTS on an Intel Xeon 8260 CPU with a memory limit of 16 GB and a time limit of 1 minute. |
| Software Dependencies | No | The algorithms are implemented in C++. No specific software libraries, frameworks, or solvers with version numbers are mentioned. |
| Experiment Setup | Yes | In particular, we use map random-32-32-20, a 32 32 4-neighbor grid with 20% randomly blocked cells, shown in Figure 2, with the number of agents varying from 45 to 150 in increments of 15. and We vary the suboptimality factor from 1.02 to 1.20 in increments of 0.02. and The algorithms are implemented in C++, and the experiments are conducted on Ubuntu 20.04 LTS on an Intel Xeon 8260 CPU with a memory limit of 16 GB and a time limit of 1 minute. |