アルゴリズム一覧
全 41 手法。うち 34 手法が シミュレータで実際に動きます。残りは解説と出典のみ、または準備中です。
バッジの意味
- 実行可 シミュレータで動かせます
- 一部実装 動きますが原論文の全機能ではありません
- 解説のみ / 準備中 実装はありません
実行可否は、宣言ではなく実際に登録されている実装から判定しています。
基礎探索Basic search
時間拡張探索Space-time search
優先順位付き計画Prioritized planning
優先順位付き計画Prioritized Planning実行可固定した優先順位に従い、先行経路を避けてエージェントを 1 体ずつ計画する。Cooperative A*Cooperative A* (CA*)実行可Space-Time A* と予約表で、エージェントを固定順に協調させる基本手法。HCA*Hierarchical Cooperative A*実行可CA* の heuristic を、RRA* で必要時に求める静的な真の距離へ強化する。WHCA*Windowed Hierarchical Cooperative A*実行可HCA* の協調探索を有限 window に切り、経路を実行しながら繰り返し再計画する。PBSPriority-Based Search実行可衝突する 2 体の相対 priority を分岐し、半順序を depth-first に組み立てる優先順位付き MAPF 解法。
CBS系Conflict-Based Search family
CBSConflict-Based Search実行可衝突を制約へ変換し、制約木と単一エージェント探索を組み合わせる SOC 最適解法。BCBSBounded CBS実行可CBS の高・低レベルを focal search にし、係数の積で SOC を保証する手法。ECBSEnhanced CBS実行可low-level の fMin を CT 下界へ持ち上げ、1 個の w で二層を柔軟に探索する手法。ICBSImproved CBS一部実装cardinal conflict を優先し、同 cost の helpful bypass で CT 分岐を減らす CBS 改良。EECBSExplicit Estimation CBS実行可online error から残り cost を推定し、CLEANUP・OPEN・FOCAL を使い分ける bounded CBS。
ICTS・結合状態・M*系ICTS / joint-state / M*
PIBT・LaCAM系PIBT / LaCAM family
PIBTPriority Inheritance with Backtracking実行可動的 priority を占有 agent へ継承し、1 step の衝突なし configuration を再帰的に組み立てる高速手法。winPIBTwindowed PIBT実行可PIBT の 1-step priority inheritance を有限 window と provisional path へ拡張する先読み手法。LaCAMLazy Constraints Addition search for MAPF実行可全 agent の次位置を一度に列挙せず、部分制約を BFS で 1 個ずつ足しながら configuration を遅延生成する完全探索。LaCAM*LaCAM star実行可LaCAM の遅延探索を続行し、発見済み configuration graph の parent と cost を張り替えて sum-of-loss optimum へ収束する anytime 手法。
Push系Push-based rule algorithms
LNS系Large Neighborhood Search
MAPF-LNSAnytime Multi-Agent Path Finding via Large Neighborhood Search実行可実行可能解の一部を壊して再計画し、時間とともに改善する anytime LNS。MAPF-LNS2MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search実行可衝突を含む暫定 path を出発点に、collision pair を減らす LNS。Regret 挿入法Regret insertion内部実装あり（単体では実行不可）RMCA の task sequence を作る内部割当ヒューリスティクス。
Lifelong MAPFLifelong MAPF
MAPDMulti-Agent Pickup and Delivery
TPToken Passing実行可全 agent の path と task 集合を token で共有する decoupled MAPD 手法。TPTSToken Passing with Task Swaps実行可TP の token と Path1 / Path2 を保ったまま、未 pickup task の再割当を試す拡張。CENTRALCENTRAL実行可agent assignment と path planning を中央でまとめて行う MAPD の比較用 strawman。MLA*Multi-Label A*内部実装あり（単体では実行不可）pickup と delivery のような ordered goals を一つの A* 探索で扱う低レベル探索。HBHHungarian-Based / h-value-Based Heuristic内部実装あり（単体では実行不可）MLA* の候補を agent–task の h 値で順序付ける中央 assignment heuristic。RMCARMCA実行可容量制約を持つ agent の task assignment と path planning を同時に扱う MAPD 手法。LNS-PBSLNS-PBS実行可LNS で task sequence を組み替え、PBS で multi-goal path を計画する MAPD 手法。LNS-wPBSLNS-wPBS実行可LNS-PBS の windowed 版。効率を重視するが完全性保証はない。
TAPF・タスク割当TAPF / task assignment
CBMConflict-Based Min-Cost-Flow実行可チーム内の匿名経路を最小費用流、チーム間の衝突を CBS で解消する TAPF Solver。CBS-TACBS with Task Assignment実行可割当行列と CBS を組み合わせ、sum of costs を最小化する TAPF Solver。ハンガリアン法Hungarian Method内部実装あり（単体では実行不可）線形割当問題を多項式時間で解く、CBS-TA の割当部品。Gale-ShapleyGale-Shapley / Deferred Acceptance内部実装あり（単体では実行不可）blocking pair のない安定マッチングを作る deferred acceptance。最小費用最大流Min-Cost Max-Flow実行可時空間ネットワークへ匿名エージェントを流し、到達時刻と移動距離を最適化する。