Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees

Luna, Ryan; Bekris, Kostas E.

doi:10.5591/978-1-57735-516-8/IJCAI11-059

Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees

Ryan Luna, Kostas E. Bekris

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 294-299.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-059

Abstract

Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This paper proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graph's topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a push operation where agents move towards their goals up to the point that no progress can be made, and a swap operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents.

Ryan Luna, and Kostas E. Bekris. 2011. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 294–299. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-059

@inproceedings{ijcai2011p59,
  title     = {Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees},
  author    = {Luna, Ryan and Bekris, Kostas E.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {294--299},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-059},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-059},
}

TY  - CPAPER
TI  - Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees
AU  - Luna, Ryan
AU  - Bekris, Kostas E.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 294
EP  - 299
DO  - 10.5591/978-1-57735-516-8/IJCAI11-059
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-059
ER  -