Push and Rotate: a Complete Multi-agent Pathfinding Algorithm
Authors: B. de Wilde, A. W. ter Mors, C. Witteveen
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In our experiments we compare our approach with the Push and Swap, MAPP, and Bibox algorithms. The latter algorithm is restricted to a smaller class of instances as it requires biconnected graphs, but can nevertheless be considered state of the art due to its strong performance. Our experiments show that Push and Swap suffers from incompleteness, MAPP is generally not competitive with Push and Rotate, and Bibox is better than Push and Rotate on randomly generated biconnected instances, while Push and Rotate performs better on grids. |
| Researcher Affiliation | Academia | Boris de Wilde EMAIL Adriaan W. ter Mors EMAIL Cees Witteveen EMAIL Faculty of Electrical Engineering, Mathematics, and Computer Science Mekelweg 4, 2628 CD Delft, The Netherlands |
| Pseudocode | Yes | Algorithm 1 find subgraphs(G,m)... Algorithm 2 assign agents to subgraphs(G,A,A,S)... Algorithm 3 subgraph priority(G,S,T , f)... Algorithm 4 push(Π,G,A,r,v,U)... Algorithm 5 swap(Π,G,A,r,s)... Algorithm 6 rotate(Π,G,A,c)... Algorithm 7 Push and Rotate(G,A,A,T )... Algorithm 8 solve(G,A,A,T ,S, f, )... Algorithm 9 smooth(Π)... Algorithm 10 clear vertex(Π,G,A,v,U)... Algorithm 11 multipush(Π,G,A,r ,s ,v)... Algorithm 12 clear(Π,G,A,r ,s ,v)... Algorithm 13 exchange(Π,G,A,r ,s ,v) |
| Open Source Code | No | The paper mentions external code used for instance generation ("Surynek's code17 generates random instances by iteratively adding handles...") and external datasets ("The maps of the original Starcraft have been made available for research at http://movingai.com/benchmarks/"), but does not provide any statement or link for the source code of the Push and Rotate algorithm itself. |
| Open Datasets | Yes | The maps of the original Starcraft have been made available for research at http://movingai.com/benchmarks/. |
| Dataset Splits | No | The paper describes generating different 'instances' for pathfinding problems based on parameters like number of agents, handles, cycle sizes, and grid dimensions. It does not mention traditional training, validation, or test splits with percentages or sample counts, as it deals with problem instances to be solved rather than data to be learned from using supervised learning methodologies. |
| Hardware Specification | No | The paper mentions 'CPU times' when comparing algorithm performance and discusses 'C++ implementation' versus 'Java implementation', but it does not provide any specific details about the hardware (e.g., CPU model, GPU, memory) used for running the experiments. |
| Software Dependencies | No | The paper mentions that the Push and Swap algorithm was implemented in C++ and the Push and Rotate algorithm in Java. However, it does not specify any version numbers for these languages or any specific libraries or other software components used for the experiments. |
| Experiment Setup | Yes | Figure 18 compares Push and Rotate, Push and Swap and Bibox on instances generated according to a single variable x that ranged from 20 to 50, with steps of two, that was used for all three parameters (number of handles, initial cycle size, and maximum handle length), while the number of empty vertices was kept at two. Figure 19 shows experiments on random biconnected instances with 40 handles, initial cycle size 5, maximum handle length 10, and an increasing number of empty vertices, ranging from 2 to 40 (step size 2), and 180 instances per step. |