期限付きマルチエージェント経路計画
Multi-Agent Path Finding with Deadlines
各エージェントが期限内にゴールへ到達できる数を最大化するMAPF-DL問題を定式化し、NP困難性を示した上で、フロー問題と整数線形計画に基づく手法と組合せ探索に基づく手法の2種類の最適アルゴリズムを提案した。
著者: Hang Ma, Glenn Wagner, Ariel Felner, Jiaoyang Li, T. K. Satish Kumar, Sven Koenig
分類: cs.AI, cs.MA, cs.RO
原文アブストラクト
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.
