Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding
Authors: Shao-Hung Chan, Jiaoyang Li, Graeme Gange, Daniel Harabor, Peter J. Stuckey, Sven Koenig9313-9322
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.Empirical Evaluation We evaluate the algorithms on eight 4-neighbor maps from the MAPF benchmark suite (Stern et al. 2019). We use 4 large maps, namely a 256 256 grid map (Berlin 1 256, denoted as city ), a 256 257 grid map and a 530 481 grid map from the video game Dragon Age: Origin (DAO) (den520d and brc202d), and a 321 123 warehouse grid map (warehouse-20-40-10-2-1, denoted as warehouse ). The number of agents ranges from 200 to 800 in increments of 200. We also use 4 small maps of size 32 32, namely grid map maze-32-32-2 (denoted as maze ), with the number of agents ranging from 10 to 50 in increments of 10, grid map room-32-32-4 (denoted as room ), with the number of agents ranging from 10 to 50 in increments of 10, grid map random-32-32-20 (denoted as random ), with the number of agents ranging from 20 to 100 in increments of 20, and grid map empty-32-32 (denoted as empty ), with the number of agents ranging from 100 to 500 in increments of 100. We use the even and the random scenarios, which each yields 25 MAPF instances for each map and number of agents. We use 4 suboptimality factors w, namely 1.01, 1.02, 1.05, and 1.10. The algorithms are implemented in C++, and the experiments are conducted with Cent OS Linux on an AMD EPYC 7302 16-Core Processor with a memory limit of 16 GB. Our comparison metrics are the success rate, which is the percentage of MAPF instances solved within the runtime limit of 60 seconds per MAPF instance, and the runtime. |
| Researcher Affiliation | Academia | Shao-Hung Chan,1 Jiaoyang Li,1 Graeme Gange,2 Daniel Harabor,2 Peter J. Stuckey,2 Sven Koenig1 1 University of Southern California 2 Monash University, Australia |
| Pseudocode | Yes | Algorithm 1 shows the pseudo-code of the low-level focal-A* search with flex distribution and flex restrictions. |
| Open Source Code | No | The paper does not contain any explicit statement about providing open-source code for the described methodology, nor does it include a link to a code repository. |
| Open Datasets | Yes | We evaluate the algorithms on eight 4-neighbor maps from the MAPF benchmark suite (Stern et al. 2019). |
| Dataset Splits | No | The paper evaluates algorithms on pre-defined MAPF instances and scenarios. It does not describe traditional training, validation, or test dataset splits in the context of machine learning model training, as it focuses on search algorithms for pathfinding. |
| Hardware Specification | Yes | The algorithms are implemented in C++, and the experiments are conducted with Cent OS Linux on an AMD EPYC 7302 16-Core Processor with a memory limit of 16 GB. |
| Software Dependencies | No | The paper only states that 'The algorithms are implemented in C++', but does not provide specific version numbers for any ancillary software libraries, solvers, or frameworks. |
| Experiment Setup | Yes | We use 4 suboptimality factors w, namely 1.01, 1.02, 1.05, and 1.10. We evaluate EECBS+ (EECBS with all speed-up techniques), FEECBS+ (FEECBS with all speed-up techniques), FEECBS+ (FR:50) (FEECBS with all speed-up techniques, flex restrictions, and restart with EECBS with TN = 50, which results in the lowest average runtime over all MAPF instances among TN = {10, 50, 100}), EECBS+ (FA*:20) (EECBS with all speed-up techniques and low-level focal A* search with κ = 20, which results in the lowest average runtime over all MAPF instances among κ = {10, 20, 30, 40}), and FEECBS+ (FR:50,FA*:30) (FEECBS with all speed-up techniques, flex restrictions, restart with EECBS with TN = 50, and low-level focal-A* search with κ = 30, which results in the lowest average runtime over all MAPF instances among κ = {10, 20, 30, 40} with TN = 50). |