Multi-Agent Path Finding with Deadlines
Conference Paper, Proceedings of 27th International Joint Conference on Artificial Intelligence (IJCAI '18), pp. 417 - 423, July, 2018
Abstract
We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without colliding with each other. We first show that MAPF-DL is NP-hard to solve optimally. We then present two classes of optimal algorithms, one based on a reduction of MAPF-DL to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network and the other one based on novel combinatorial search algorithms. Our empirical results demonstrate that these MAPF-DL solvers scale well and each one dominates the other ones in different scenarios.
BibTeX
@conference{Ma-2018-131437,author = {Hang Ma and Glenn Wagner and Ariel Felner and Jiaoyang Li and T. K. Satish Kumar and Sven Koenig},
title = {Multi-Agent Path Finding with Deadlines},
booktitle = {Proceedings of 27th International Joint Conference on Artificial Intelligence (IJCAI '18)},
year = {2018},
month = {July},
pages = {417 - 423},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.