study-mapfMAPF / Lifelong MAPF / MAPD 教材

学習ロードマップ

MAPF は手法の数が多いですが、互いに依存関係があります。 いきなり新しい手法から読むより、この順に辿るほうが速く理解できます。

各項目のバッジは実装状態です。「準備中」の解説はまだ骨格だけですが、 原論文へのリンクは載せています。

第 1 段階 — 単一エージェントの探索

MAPF のほぼ全ての手法が、内部で単一エージェントの経路探索を呼びます。ここが分かっていないと先へ進めません。

第 1・2・3 段階の一部はシミュレータで動かせます。 読む前に触ると理解が早いです。

第 2 段階 — 時間を状態に入れる

他のエージェントが動いている以上、「いつ、どこに居るか」を状態にしないと衝突を避けられません。「待つ」という選択肢が生まれるのがここです。

第 3 段階 — 最初の多エージェント手法

1 体ずつ順に計画し、既に決まった経路を障害物として扱う方法。速い代わりに、順序次第で失敗します。「速いが完全ではない」という感覚をここで掴みます。

第 4 段階 — CBS

衝突を「制約」に変えて二層で探索する枠組み。最適解を返します。以降の多くの手法が CBS の改良なので、ここが山場です。

第 5 段階 — 別系統の考え方

CBS 以外の攻め方を知ると、設計の選択肢が広がります。全体を一度に解かず、1 ステップずつ決める発想もあります。

第 6 段階 — 大規模・実運用

実際の倉庫規模になると、最適解を待てません。実行可能解を作ってから改善する、タスクの割当も同時に考える、といった話になります。

この先

TAPF（チームへの目標割当）、学習ベース（PRIMAL 系）、コンパイル系（SAT / SMT / ILP）は、 上の 6 段階を終えてからで十分です。アルゴリズム一覧から辿れます。