TY - JOUR AU - Botea, Adi AU - Surynek, Pavel PY - 2015/02/18 Y2 - 2024/03/28 TI - Multi-Agent Path Finding on Strongly Biconnected Digraphs JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - AAAI Technical Track: Multiagent Systems DO - 10.1609/aaai.v29i1.9430 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9430 SP - AB - <p> 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. </p> ER -