Open AccessSolving Multi-agent Path Finding on Strongly Biconnected Digraphs
Author(s) -
Adi Botea,
Davide Bonusi,
Pavel Surynek
Publication year - 2018
Publication title -
journal of artificial intelligence research/the journal of artificial intelligence research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.79
H-Index - 123
eISSN - 1943-5037
pISSN - 1076-9757
DOI - 10.1613/jair.1.11212
Subject(s) - path (computing) , computer science , directed graph , combinatorics , longest path problem , scalability , block graph , undirected graph , graph , mathematics , theoretical computer science , shortest path problem , pathwidth , algorithm , line graph , database , programming language
Much of the literature on suboptimal, polynomial-time algorithms for multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, traveling on directed graphs is relevant in navigation domains, such as path finding 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 have a solution, except for a particular, degenerate subclass where the graph has a cyclic shape. We present diBOX, an algorithm for multi-agent path finding on strongly biconnected directed graphs. diBOX runs in polynomial time, computes suboptimal solutions and is complete for instances on strongly biconnected digraphs with at least two unoccupied positions. We theoretically analyze properties of the algorithm and properties of strongly biconnected directed graphs that are relevant to our approach. We perform a detailed empirical analysis of diBOX, showing a good scalability. To our knowledge, our work is the first study of multi-agent path finding focused on directed graphs.