Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs (Extended Abstract)

Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs (Extended Abstract)

Adi Botea, Davide Bonusi, Pavel Surynek

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Journal track. Pages 5563-5567. https://doi.org/10.24963/ijcai.2018/785

We present and evaluate 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. A detailed empirical analysis shows a good scalability for diBOX.
Keywords:
Planning and Scheduling: Robot Planning
Robotics: Motion and Path Planning
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Theoretical Foundations of Planning