[2N4-OS-17a] OS-17 (1)

[2N4-OS-17a-02] A New Formulation and Solution for Multi-Agent Path Finding with Deadlines

〇Takuho Harada¹, Katsutoshi Hirayama¹, Tenda Okimoto¹, Taro Kokushi² (1. Graduate School of Maritime Sciences, Kobe University, 2. Faculty of Maritime Sciences, Kobe University)

Keywords:Multi-Agent Path Finding

Multi-Agent Path Finding (MAPF) is the problem of finding the optimal paths for multiple agents to move from their initial positions to their goal positions without colliding with each other. Recently, a novel formulation called MAPF-DL has been proposed whose goal is to maximize the number of agents that can reach the goal positions within a prespecified common deadline. However, in this formulation, there is an unrealistic assumption about the handling of unreachable agents. In this study, we propose a new formulation that corrects this point, and show the initial results on the performance of the off-the-shelf 0-1 integer programming solver and the Lagrangian decomposition method.