Multi-Agent Path Finding with Deadlines: Preliminary Results

We formalize the problem of 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 a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.

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

No keywords are indexed for this paper.