MAPFとは
Multi-Agent Path Finding（MAPF）は、グラフ上に置かれた複数のエージェントに対して、互いに衝突しない経路を全員分まとめて決める問題です。 各エージェントには開始頂点と目標頂点が 1 つずつ与えられます。
本サイトでは、用語と衝突の分類を[mapf-benchmarks-2019] の定義に統一しています。 論文によって前提が違うため、比較するときは必ずどの定義かを確認してください。
なぜ 1 体ずつ解いてはいけないのか
各エージェントに個別に最短経路を引くのは簡単です。しかしそれらを同時に走らせると、 狭い通路や交差点でぶつかります。シミュレータで「A*（各エージェント独立）」を選ぶと、 衝突が実際に残ることを確認できます。
基本モデル
本サイトのシミュレータと解説は、次のモデルを既定にしています。
- グラフは 4 近傍グリッド（上下左右）。斜め移動なし
- 時間は離散。1 タイムステップで隣接頂点へ 1 歩動く（move）か、その場に留まる（wait）
- 全エージェントが同時に動く
衝突の種類
目的関数
| 名前 | 定義 | 直感 |
|---|---|---|
| sum of costs | 各エージェントが目標へ到達した時刻の総和 | 全体の労力。1 体が大回りしても総和が小さければ良しとする |
| makespan | 全エージェントが完了する時刻（最大値） | 最後の 1 体が着くまでの時間。一番遅い人に合わせる |
どちらを最小化するかで最適解は変わります。「この手法は最適」と書かれていても、どの目的関数に対して最適なのかを必ず確認してください。
計算量について
MAPF を最適に解くことは計算量的に難しい問題として知られています。 このため、最適解法・有界準最適解法・保証なしの高速解法が並行して研究されています。 具体的な硬さの主張と証明の出典は、各手法のページで確認できた範囲だけを記載します。
次に読むもの
このページは原論文の定義に基づいて書いていますが、節番号・ページ番号までの照合は未了です。 確認が済み次第、[paper-id, §x, p.y] 形式の出典を本文へ付けます。