Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding
Authors: Liron Cohen, Tansel Uras, T. K. Satish Kumar, Hong Xu, Nora Ayanian, Sven Koenig
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experimental results show that i ECBS(w1) can run faster than ECBS(w1) despite both MAPF solvers having the same suboptimality factor. So far, the highways used with MAPF solvers have been human-generated. We also develop two first approaches for automatically generating experience graphs for a given MAPF instance that can make ECBS(w1)+HWY(w2) and i ECBS(w1) about as fast as human-generated experience graphs in Kiva-like warehousing domains, thus potentially reducing the dependency on human expertise for highway generation. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of i ECBS(w1) within a given runtime limit. |
| Researcher Affiliation | Academia | Liron Cohen, Tansel Uras, T. K. Satish Kumar, Hong Xu, Nora Ayanian, Sven Koenig Department of Computer Science , University of Southern California {lironcoh, turas}@usc.edu tkskwork@gmail.com {hongx, ayanian, skoenig}@usc.edu |
| Pseudocode | Yes | Algorithm 1 shows the HM-based approach, which first converts each undirected edge to two directed edges with HM costs one and then updates the following values for each directed edge hu, vi to update its HM cost: |
| Open Source Code | No | The paper states, "Our implementation of the GM-based approach uses lib DAI [Mooij, 2010]", which refers to a third-party library used, not the authors' own source code. No explicit statement of releasing their code or a link to a repository is provided. |
| Open Datasets | No | The paper uses "randomly generated MAPF instances" and refers to a "Kiva-like warehousing domain" as the setting for these instances. It does not mention the use of a publicly available dataset with specific access information (link, DOI, formal citation). |
| Dataset Splits | No | The paper mentions "10 randomly generated MAPF instances" and running "10 trials" or "50 trials" but does not specify formal training, validation, or test dataset splits in terms of percentages, sample counts, or predefined partition methods for reproducibility. |
| Hardware Specification | Yes | We run all experiments in this paper on a PC with a 3.2GHz Intel Core i7 CPU and a 300-second runtime limit per MAPF instance, unless stated otherwise. |
| Software Dependencies | Yes | Our implementation of the GM-based approach uses lib DAI [Mooij, 2010]. |
| Experiment Setup | Yes | Our implementation uses parameters = 0.5, β = 1.2, γ = 1.3 and Max Iterations = 100,000. It considers the 1/7th of the edges with the lowest HM costs after Max Iterations iterations and then returns 1/5th of these edges randomly. |