Multi-Agent Path Finding with Deadlines

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.

Authors

• Hang Ma Simon Fraser University
• Glenn Wagner Carnegie Mellon University
• Ariel Felner Computer and Information Sciences, Ben-Gurion University of the Negev
• Jiaoyang Li Carnegie Mellon University
• T. K. Satish Kumar
• Sven Koenig University of California & Örebro University

Keywords

• Agent-based and Multi-agent Systems: Coordination and Cooperation
• Agent-based and Multi-agent Systems: Multi-agent Planning
• Heuristic Search and Game Playing: Combinatorial Search and Optimisation
• Planning and Scheduling: Planning Algorithms
• Planning and Scheduling: Planning and Scheduling
• Planning and Scheduling: Search in Planning and Scheduling