Robust Multi-Agent Path Finding and Executing
Authors: Dor Atzmon, Roni Stern, Ariel Felner, Glenn Wagner, Roman Barták, Neng-Fa Zhou
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different robust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy. |
| Researcher Affiliation | Academia | Dor Atzmon EMAIL Roni Stern EMAIL Ariel Felner EMAIL Dept. of Software & Information Systems Engineering Ben-Gurion University of the Negev P.O.B. 653 Beer-Sheva 8410501, Israel Glenn Wagner EMAIL Carnegie Mellon University 5000 Forbes Ave, Pittsburgh, PA 15213, United States Roman Bart ak EMAIL Dept. of Theoretical Computer Science & Mathematical Logic Charles University, Faculty of Mathematics and Physics Malostransk e n am. 25, 118 00 Prague, Czech Republic Neng-Fa Zhou EMAIL Dept. of Computer & Information Science CUNY Brooklyn College 2900 Bedford Ave, Brooklyn, NY 11210, United States |
| Pseudocode | No | No explicit pseudocode or algorithm blocks are provided. The paper describes algorithms like k-robust CBS and its improved version, and discusses their adaptations from existing MAPF solvers, but does not present them in structured pseudocode format. |
| Open Source Code | Yes | Our implementation of k R-CBS is available at https://git.hub.com/doratzmon/k_robust. |
| Open Datasets | Yes | We also performed a similar experiment on a significantly larger map from the Dragon Age Origins (DAO) video game. Specifically, we chose the brc202d map, which has 43,151 vertices. This map is publicly available in the movingai repository (Sturtevant, 2012). We also experimented on the warehouse domain described by Ma et al. (2017) |
| Dataset Splits | No | The paper mentions creating random k-robust MAPF instances by randomly choosing start and goal vertices, and randomly allocating obstacles. However, it does not provide specific dataset splits like training/validation/test percentages or counts. |
| Hardware Specification | Yes | All experiments throughout this paper were executed on an Intel R Xeon E5-2660 v4 @ 2.00GHz processor with 16 GB of RAM. |
| Software Dependencies | No | The paper mentions using "CBS with the bypass enhancement of ICBS" and implementing a solver using "Picat (Zhou et al., 2015)". However, it does not specify concrete version numbers for these or any other software components used in the experiments. |
| Experiment Setup | Yes | We experimented with k=0, 1, and 2, and with 4, 6 8, and 10 agents. We also performed a similar experiment on open 32x32 and 64x64 4-neighborhood grids. We created 50 random problems on a 16x16 open 4-neighborhood grid with 5, 10, and 15 agents, and solved each problem with Ik R-CBS with the symmetric constraints. Delays occurred with probability p per each move of each agent, where p is a parameter. We experimented with p = 0.1, 0.01, and 0.001. In this set of experiments the communication frequency was T = 0, 2, 4, and 6, and the original plans were built to match this frequency and thus were optimal and T-robust for T = 0, 2, 4, and 6, respectively. |