手法比較

docs/sources/algorithms.yaml から生成しています。同じ情報を複数箇所へ手書きしていないので、マニフェストを直せばここも変わります。

「不明」は「保証が無い」ではありません。原論文の該当箇所をまだ確認できていない、という意味です。確認できたものだけを「あり」「なし」と書いています。

「最適」と「条件付き（eventually optimal など）」は別物です。各手法のページで根拠を確認してください。

絞り込み分類シミュレータ対応のみ

手法	対象問題	完全性	最適性	準最適保証	一括/オンライン	分類	実装状態	シミュレータ
幅優先探索BFS	単一エージェント	不明	不明	なし	一括	基礎探索	実行可	対応
AA	単一エージェント	不明	不明	なし	一括	基礎探索	実行可	対応
時空間 ASpace-Time A	one-shot MAPF	不明	不明	なし	一括	時間拡張探索	実行可	対応
SIPPSafe Interval Path Planning	単一エージェント / one-shot MAPF / 連続時間 MAPF	あり	最適	なし	一括	時間拡張探索	実行可	対応
優先順位付き計画Prioritized Planning	one-shot MAPF	なし	なし	なし	一括	優先順位付き計画	実行可	対応
Cooperative ACooperative A (CA*)	one-shot MAPF	なし	不明	なし	一括	優先順位付き計画	実行可	対応
HCAHierarchical Cooperative A	one-shot MAPF	なし	不明	なし	一括	優先順位付き計画	実行可	対応
WHCAWindowed Hierarchical Cooperative A	one-shot MAPF / lifelong MAPF	不明	不明	なし	オンライン	優先順位付き計画	実行可	対応
CBSConflict-Based Search	one-shot MAPF	条件付き	最適	なし	一括	CBS系	実行可	対応
BCBSBounded CBS	one-shot MAPF	あり	なし	あり	一括	CBS系	実行可	対応
ECBSEnhanced CBS	one-shot MAPF	あり	なし	あり	一括	CBS系	実行可	対応
ICBSImproved CBS	one-shot MAPF	条件付き	最適	なし	一括	CBS系	一部実装	対応
EECBSExplicit Estimation CBS	one-shot MAPF	不明	なし	あり	一括	CBS系	実行可	対応
PBSPriority-Based Search	one-shot MAPF	不明	なし	なし	一括	優先順位付き計画	実行可	対応
ICTSIncreasing Cost Tree Search	one-shot MAPF	不明	最適	なし	一括	ICTS・結合状態・M*系	実行可	対応
MSubdimensional Expansion / M	one-shot MAPF	あり	最適	なし	一括	ICTS・結合状態・M*系	実行可	対応
PIBTPriority Inheritance with Backtracking	one-shot MAPF / lifelong MAPF	条件付き	なし	なし	オンライン	PIBT・LaCAM系	実行可	対応
winPIBTwindowed PIBT	one-shot MAPF / lifelong MAPF	条件付き	不明	なし	オンライン	PIBT・LaCAM系	実行可	対応
LaCAMLazy Constraints Addition search for MAPF	one-shot MAPF	あり	なし	なし	一括	PIBT・LaCAM系	実行可	対応
LaCAM*LaCAM star	one-shot MAPF	あり	条件付き	なし	一括	PIBT・LaCAM系	実行可	対応
Push and SwapPush and Swap	one-shot MAPF	なし	なし	なし	一括	Push系	実行可	対応
Push and RotatePush and Rotate	one-shot MAPF	条件付き	なし	なし	一括	Push系	実行可	対応
MAPF-LNSAnytime Multi-Agent Path Finding via Large Neighborhood Search	one-shot MAPF	不明	なし	なし	一括	LNS系	実行可	対応
MAPF-LNS2MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search	one-shot MAPF	なし	なし	なし	一括	LNS系	実行可	対応
RHCRRolling-Horizon Collision Resolution	lifelong MAPF	なし	なし	不明	オンライン	Lifelong MAPF	実行可	対応
TPToken Passing	MAPD	条件付き	不明	なし	オンライン	MAPD	実行可	対応
TPTSToken Passing with Task Swaps	MAPD	条件付き	不明	なし	オンライン	MAPD	実行可	対応
CENTRALCENTRAL	MAPD	なし	なし	なし	オンライン	MAPD	実行可	対応
MLAMulti-Label A	MAPD	不明	不明	なし	オンライン	MAPD	内部実装あり（単体では実行不可）	—
HBHHungarian-Based / h-value-Based Heuristic	MAPD	不明	不明	なし	オンライン	MAPD	内部実装あり（単体では実行不可）	—
RMCARMCA	MAPD	不明	不明	なし	オンライン	MAPD	実行可	対応
Regret 挿入法Regret insertion	MAPD	不明	不明	不明	オンライン	LNS系	内部実装あり（単体では実行不可）	—
LNS-PBSLNS-PBS	MAPD	条件付き	不明	なし	オンライン	MAPD	実行可	対応
LNS-wPBSLNS-wPBS	MAPD	なし	不明	なし	オンライン	MAPD	実行可	対応
CBMConflict-Based Min-Cost-Flow	TAPF	あり	最適	なし	一括	TAPF・タスク割当	実行可	対応
CBS-TACBS with Task Assignment	TAPF	あり	最適	なし	一括	TAPF・タスク割当	実行可	対応
ハンガリアン法Hungarian Method	割当	あり	最適	なし	一括	TAPF・タスク割当	内部実装あり（単体では実行不可）	—
Gale-ShapleyGale-Shapley / Deferred Acceptance	割当	あり	条件付き	なし	一括	TAPF・タスク割当	内部実装あり（単体では実行不可）	—
最小費用最大流Min-Cost Max-Flow	フロー / TAPF	条件付き	条件付き	なし	一括	TAPF・タスク割当	実行可	対応
PRIMALPRIMAL	one-shot MAPF	不明	不明	なし	一括	学習ベース	解説のみ	—
PRIMAL2PRIMAL2	lifelong MAPF	不明	不明	なし	オンライン	学習ベース	解説のみ	—

「低レベル探索」「主な目的関数」の列は、原論文での確認が済んだ手法が増えた段階で追加します。現時点で埋めると推測になるため、列ごと出していません。