Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem
Authors: Hang Ma, Craig Tovey, Guni Sharon, T. K. Kumar, Sven Koenig
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances. Experiments We now report our experimental results for makespan minimization. We implemented a flow-based PERR solver based on a software package provided by the authors of (Yu and La Valle 2013a). |
| Researcher Affiliation | Academia | Hang Ma Department of Computer Science University of Southern California hangma@usc.edu Craig Tovey School of Industrial and Systems Engineering Georgia Institute of Technology ctovey@isye.gatech.edu Guni Sharon Department of Information Systems Engineering Ben-Gurion University of the Negev gunisharon@gmail.com T. K. Satish Kumar and Sven Koenig Department of Computer Science University of Southern California tkskwork@gmail.com and skoenig@usc.edu |
| Pseudocode | No | The paper contains mathematical formulations and descriptions of algorithms but does not include structured pseudocode or an algorithm block explicitly labeled as such. |
| Open Source Code | No | The paper states: "We thank Jingjin Yu for making the code of their flow-based MAPF solver and Nathan Sturtevant for making game maps available to us." This refers to third-party code used by the authors, not their own source code for the methodology described in the paper. No explicit statement or link for the authors' code release is provided. |
| Open Datasets | Yes | small benchmark maps with three to sixteen robots each (Sajid, Luna, and Bekris 2012) and benchmark map brc202d from the video game Dragon Age: Origins (Sturtevant 2012) |
| Dataset Splits | No | The paper describes instance generation (e.g., "thirty instances with randomly blocked cells and random source and destination vertices") but does not specify train/validation/test dataset splits with percentages, counts, or references to predefined splits. |
| Hardware Specification | Yes | We ran all solvers on a 2.50GHz Intel Core i5-2450M computer with 6GB RAM, a 1.5GB JVM and a single thread. |
| Software Dependencies | Yes | each of which is formulated as an ILP and given to the ILP solver Gurobi 6.0. Both flow-based solvers are written in Java. It is written in C#. |
| Experiment Setup | Yes | Our flow-based solver casts a PERR instance as a series of integer multi-commodity networkflow problems as described in Section Network Flow and PERR , each of which is formulated as an ILP and given to the ILP solver Gurobi 6.0. We also use a version of this flow-based solver that determines a solution only on the subgraph given by the set of shortest individual paths of all packages from their source vertices to their destination vertices. This version sacrifices optimality for reducing the size of the graph to be searched. Both flow-based solvers are written in Java. Additionally, we adapted the Conflict-Based Search (CBS) algorithm (Sharon et al. 2015) from MAPF to PERR, which requires only the addition of exchange operations. The adapted CBS solver is correct, complete and optimal, as can be shown with arguments similar to those in (Sharon et al. 2015) using the upper bound from Equation 1. It is written in C#. We ran all solvers on a 2.50GHz Intel Core i5-2450M computer with 6GB RAM, a 1.5GB JVM and a single thread. We generated thirty instances with randomly blocked cells and random source and destination vertices each for different numbers of robots (varied from 10 to 50 in increments of 10) and obstacle densities (varied from 0% to 30% in increments of 5%). |