Symmetry Breaking for k-Robust Multi-Agent Path Finding
Authors: Zhe Chen, Daniel D. Harabor, Jiaoyang Li, Peter J. Stuckey12267-12274
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results show very large gains in success rate for k-CBS; not only on classic MAPF benchmarks but also in two application specific domains: in warehouse logistics, where k-robust plans are desirable and in railway scheduling where k-robust plans are mandatory. and Experiments The implementation is based on CBS with rectangle, corridor and target reasoning of Li et al. (2020) and support for k-robust planning is added on top of it. It is programmed in C++ and experiments were performed on a server with AMD Opteron 63xx class CPU and 32 GB RAM. |
| Researcher Affiliation | Academia | Zhe Chen,1 Daniel Harabor,1 Jiaoyang Li,2 Peter J. Stuckey1 1Monash University, Australia 2University of Southern California, USA |
| Pseudocode | No | The paper describes algorithms and methods but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide an explicit statement or link for the open-sourcing of their code for the described methodology. |
| Open Datasets | Yes | We use 25 even scenarios from movingai.com to evaluate our algorithms., We use a 31 79 Warehouse map (Li et al. 2020) with randomly generated problems to evaluate the performance of robots in warehouse system., The Flatland challenge is a railway scheduling challenge 1 provides a simplified railway simulator using a directed grid map, where trains cannot move backwards. Railway systems have headway control, one train cannot start to enter a railway block if another train currently occupies the block. Hence the railway domain requires k = 1 robust plans. Our experiments use flatland-rl v2.0.0 to generate experiment problems. Note, no target conflicts can occur in the Flatland challenge scenarios since trains disappear when reaching their destination. We have two settings for evaluation: (1) a 100 100 fixed dense map contains fixed 140 start and goal locations, and each pair of start and goal are connected by 5 railways; and (2) a 100 100 incremental sparse map has one start and goal location per agent, and each pair of start and goal are only connected by 1 railway. The experiment on railway maps, Figure 5f shows that KCBSH and K-CBSH-RM performs substantially better than KCBS. k-robust corridor reasoning helps further improve performance on sparse maps. and 1Swiss Federal Railways, 2019, Flatland Challenge. https://www.aicrowd.com/challenges/flatland-challenge |
| Dataset Splits | No | For each map, we keep increasing the number of agents, and for each number of agent we solve 25 different instances. |
| Hardware Specification | Yes | experiments were performed on a server with AMD Opteron 63xx class CPU and 32 GB RAM. |
| Software Dependencies | Yes | It is programmed in C++ and experiments were performed on a server with AMD Opteron 63xx class CPU and 32 GB RAM. and Our experiments use flatland-rl v2.0.0 to generate experiment problems. |
| Experiment Setup | No | The time limit is set to 90s for each instance. |