Multi-Agent Path Finding on Biconnected Directed Graphs

Abstract

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.

Keywords

• multi-agent path finding
• directed graphs