Multi-Agent Path Finding on Strongly Biconnected Digraphs
Abstract
Much of the literature on multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, travelling on directed graphs is relevant in navigation domains, such as pathfinding in games, and asymmetric communication networks. We consider multi-agent path finding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions can be solved or proven unsolvable. We present a polynomial-time algorithm for this class of problems, and analyze its complexity. Our work may be the first formal study of multi-agent path finding on directed graphs.
Cite
Text
Botea and Surynek. "Multi-Agent Path Finding on Strongly Biconnected Digraphs." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9430Markdown
[Botea and Surynek. "Multi-Agent Path Finding on Strongly Biconnected Digraphs." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/botea2015aaai-multi/) doi:10.1609/AAAI.V29I1.9430BibTeX
@inproceedings{botea2015aaai-multi,
title = {{Multi-Agent Path Finding on Strongly Biconnected Digraphs}},
author = {Botea, Adi and Surynek, Pavel},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {2024-2030},
doi = {10.1609/AAAI.V29I1.9430},
url = {https://mlanthology.org/aaai/2015/botea2015aaai-multi/}
}