Safe Multi-Agent Pathfinding with Time Uncertainty
Authors: Tomer Shahar, Shashank Shekhar, Dor Atzmon, Abdallah Saffidine, Brendan Juba, Roni Stern
JAIR 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. ... Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost. |
| Researcher Affiliation | Collaboration | Tomer Shahar EMAIL Shashank Shekhar EMAIL Dor Atzmon EMAIL Ben-Gurion University of the Negev, Israel Abdallah Saffidine EMAIL The University of New South Wales, Sydney, Australia Brendan Juba EMAIL Washington University in St. Louis, USA Roni Stern Ben-Gurion University of the Negev, Israel EMAIL Palo Alto Research Center, USA EMAIL |
| Pseudocode | Yes | Algorithm 1 lists the pseudo code for CBSTU, focusing on the high-level search. ... Algorithm 1: The CBSTU Algorithm. Input: A MAPF-TU instance with k agents; An optimization criteria, f Output: A set of collision-free single-agent plans 1 root.constraints = 2 root.solution individual single-agent plans returned by low-level() approach 3 root.cost SOC(root.solution) 4 Add root to OPEN 5 while OPEN not empty do 6 N the best node from OPEN // based on some objective function 7 Validate single-agent plans in N until the first conflict occurs 8 if no conflict found then 9 return N.solution 10 conflict Find Conflict(N.solution) 11 for agent ai belongs to the conflict do 12 Ni Create a new CT node 13 if vertex-conflict(conflict) then 14 Ni.constraints N.constraints (ai, v, t) 16 Ni.constraints N.constraints (ai, e, t) 17 Ni.solution N.solution 18 Update Ni.solution with a single-agent plan returned by low-level(Ni) for ai 19 Ni.cost = SOC(Ni.solution) 20 Add node Ni to OPEN 21 return No solution found |
| Open Source Code | Yes | Nevertheless, the source code for running all our experiments is publicly available at https://github.com/Tomer-Shahar/Conformant-CBS. |
| Open Datasets | Yes | DAO. A grid from the ost003d map of the game Dragon Age Origins (DAO), made publicly available by Sturtevant (Sturtevant, 2012). |
| Dataset Splits | No | For each configuration of grid type, U, and number of agents, we created 50 experiments. These 50 experiments differ in the start and goal locations of the agents, which were randomly selected. |
| Hardware Specification | No | No specific hardware details (like GPU/CPU models or memory) are provided in the paper. The paper only describes the grids used for experiments. |
| Software Dependencies | No | The existing MAPF code frameworks that we explored were not easily adaptable to the MAPF-TU setting. So, we implemented all algorithms from scratch, including the two CBS enhancements mentioned in Section 5.3. |
| Experiment Setup | Yes | To define w (e) and w+(e) for every edge e we introduce a parameter U called the uncertainty rate. For a given value of U, we set w (e) to be a value chosen uniformly at random from the range [1, U + 1], and set w+(e) to be a value chosen uniformly at random from the range [w (e), U + 1]. ... For each configuration of grid type, U, and number of agents, we created 50 experiments. ... We set a timeout of five minutes for each solving each MAPF-TU instance. ... Unless stated otherwise, the objective function we optimized for was SOCpes. |