シミュレータ
グリッドを編集し、実装済みのアルゴリズムを実行できます。計算はすべてブラウザ内で行い、 サーバへは何も送信しません。探索は Web Worker で動くため、実行中も画面操作ができます。
シミュレーションモデル
このシミュレータが採用しているルールです。論文ごとに前提が違うため、明示しておきます。
| グラフ | 4 近傍グリッド（上下左右）。斜め移動なし |
|---|---|
| 時間 | 離散時間。1 ステップで move（隣接セルへ 1 歩）または wait |
| vertex conflict | 同時刻に 2 体が同じセルを占有すること。禁止 |
| edge-swap conflict | 隣接する 2 体が同一ステップで位置を入れ替えること。既定で禁止 |
| goal 到達後 | 既定は stay（そこに留まり、他エージェントを妨げる）。disappear も選択可 |
| 目的関数 | sum of costs と makespan の両方を表示 |
| MAPD の指標 | service time / throughput / 未処理タスク数（対応 Solver 実装後に有効化） |
ルールを変えた場合はシナリオ JSON の rules に保存されます。 暗黙に変更されることはありません。
実装済みの手法
シミュレータで選べるのは、実際に実装がある手法だけです。 現在 36 種類です。
| 手法 | 原語 | 状態 | 注意 |
|---|---|---|---|
| 幅優先探索（各エージェント独立） | BFS | 実行可 | 各エージェントを独立に計画する。他エージェントとの衝突は解消しない。MAPF の解ではなく、基礎探索の挙動と、衝突が必ず起きることを示すための実装。 |
| A*（各エージェント独立） | A* | 実行可 | 各エージェントを独立に計画する。他エージェントとの衝突は解消しない。MAPF の解ではなく、基礎探索の挙動と、衝突が必ず起きることを示すための実装。 |
| 時空間 A* | Space-Time A* | 実行可 | 原論文どおり (cell,time) を探索する低レベル Solver。CA* と混同しないよう単一エージェントのシナリオだけを受理する。edge-swap / following はサイト共通ルールへの拡張。 |
| SIPP | Safe Interval Path Planning | 実行可 | SIPP の状態 (cell,safe interval) と最早到着時刻を原論文どおり実装。MAPF で実行するため、Solver wrapper は入力順の prioritized planning として各 agent を SIPP で計画する。 |
| 優先順位付き計画（固定順） | Prioritized Planning | 実行可 | 既定は scenario.agents の固定順。extra.priorityOrder で全順序を明示できる。優先順位や同コスト経路によっては、解が存在しても失敗する。PBS のような順序探索は行わない。 |
| Cooperative A* | Cooperative A* (CA*) | 実行可 | Silver (2005) の基本形どおり、入力順に Space-Time A* を実行し、Manhattan heuristic と疎な reservation table を使う。edge-swap / following はサイト規則への拡張。 |
| HCA* | Hierarchical Cooperative A* | 実行可 | CA* の Manhattan heuristic を、Silver (2005) Algorithm 1 の on-demand Reverse Resumable A* による抽象距離へ置き換える。入力順は固定で、公開 pibt2 の distance-first priority は採用しない。 |
| WHCA* | Windowed Hierarchical Cooperative A* | 実行可 | Silver (2005) の window terminal edge、RRA* 再利用、midpoint 再計画、動的 priority を実装。ブラウザ版は同期 window と単純 rotation を使い、サイト既定の stay-at-goal を守るため goal 到達後は離れない。 |
| CBS | Conflict-Based Search | 実行可 | AIJ 2015 Algorithm 2 の CBS 部分を再現。SOC/conflict 数/FIFO の CT tie-break と CAT low-level tie-break を実装する。有限 maxHorizon と安全上限で打ち切られた実行は理論保証の対象外。 |
| BCBS | Bounded CBS | 実行可 | 高・低レベル focal search の係数積 wH*wL を保証値とする。既定は suboptimalityFactor を sqrt(w) ずつ配分し、extra.highLevelWeight / lowLevelWeight で両方を明示できる。 |
| ECBS | Enhanced CBS | 実行可 | low-level FOCAL が返す fMin の和を CT lower bound とし、cost<=w*LB の high-level FOCAL を conflict 数で選ぶ。既定 w=1.5。 |
| ICBS (PC+BP) | Improved Conflict-Based Search | 一部実装 | cardinal/semi/non-cardinal prioritization と helpful bypass を実装。分類は MDD と等価な child-cost 判定を使う。論文の完全版 ICBS(25) に含まれる MA-CBS merge / merge-and-restart は未実装。 |
| EECBS | Explicit Estimation CBS | 実行可 | AAAI 2021 §3 の基礎 EECBS: CLEANUP/OPEN/FOCAL の EES 選択、online one-step error、bounded low level を実装。§4 の relaxed bypass、PC、symmetry reasoning、WDG は未実装。既定 w=1.5。 |
| PBS（優先度ベース探索） | Priority-Based Search | 実行可 | Algorithm 2 の priority-tree DFS、partial-order UpdatePlan、2 段 CAT tie-break を独立実装。finite maxHorizon と row-major 最終 tie-break はブラウザ用の明示的な打切り・決定性規則。 |
| PIBT（優先度継承＋バックトラック） | Priority Inheritance with Backtracking | 実行可 | AIJ 2022 Algorithm 1 の 1-step priority inheritance / backtracking と §4.4.1 の one-shot termination を実装。iterative goal 更新と PIBT+ は未対応。 |
| winPIBT（窓付き PIBT） | windowed PIBT | 実行可 | winPIBT Algorithms 1–2 の centralized provisional paths、disentangled 制約、retroactive priority inheritance を実装。fixed common window と one-shot goal のみで、iterative task allocation は未対応。 |
| ICTS（Increasing Cost Tree Search） | Increasing Cost Tree Search | 実行可 | IJCAI 2011 Algorithm 1 の ICT breadth-first search、exact-cost MDD、k-agent MDD search と optional pairwise pruning を実装。Independence Detection と AIJ 拡張版固有の改良は未対応。 |
| M*（Subdimensional Expansion） | M* | 実行可 | AIJ 2015 Algorithms 1–2 の basic M*、limited neighbors、collision set と backpropagation set を実装。edge collision は site の transition 上で直接検出。recursive / operator-decomposition / inflated M* は未対応。 |
| Push and Swap | Push and Swap | 実行可 | IJCAI 2011 Algorithms 1–3 の push / multipush / exchange / reverse と、後続一次資料の corrected 4-stage clear を独立実装。後続論文が示した反例のため、失敗は一般の解なし証明として扱わない。solution smoothing は未対応。 |
| Push and Rotate | Push and Rotate | 実行可 | AAMAS 2013 Algorithms 1–4 と著者 thesis Algorithms 4.1.1–4.2.11 を基に、biconnected subproblem merge、agent assignment、priority propagation、plan / push / swap / rotate / resolve、4-stage clear を独立実装。4 近傍 unit-cost grid に限定し、solution smoothing と一般 graph import は含まない。 |
| LaCAM（遅延制約追加探索） | Lazy Constraints Addition search for MAPF | 実行可 | AAAI 2023 Algorithm 1 の configuration DFS、constraint-tree BFS、lazy successor generation を独立実装。generator は同論文 §3.3 の PIBT 型 1-step assignment。既知 node 再挿入などの engineering は LaCAM* と区別するため含めない。 |
| LaCAM*（最終的最適探索） | LaCAM star | 実行可 | IJCAI 2023 Algorithm 3 の goal 保持、既知 configuration への有向辺追加、Dijkstra rewiring、admissible f 枝刈りを独立実装。最適性は OPEN 完了時の sum-of-loss に対する eventual guarantee であり、有限 cutoff 時やサイト表示 SOC に対する保証ではない。PIBT swap と random restart は未対応。 |
| MAPF-LNS | Anytime MAPF via Large Neighborhood Search | 実行可 | IJCAI 2021 §4–5 の initial solution → destroy → repair → accept-if-better 骨格と agent/map/random neighborhood を実装。EECBS、SIPP、論文の全 ALNS 細部は既存の deterministic Space-Time A* に簡略化している。 |
| MAPF-LNS2 | MAPF-LNS2 | 実行可 | AAAI 2022 §3–5 の衝突を含む初期 plan、collision-pair / failure / random neighborhood、CP 非増加修復を実装。SIPPS の完全な soft-interval dominance は既存 Space-Time A* と明示的 soft 評価へ簡略化している。 |
| RHCR | Rolling-Horizon Collision Resolution | 実行可 | AAAI 2021 §4 の w-step planning / h-step execution を教材用に実装。one-shot の固定 goal も一要素の queue として実行できる。warehouse 固有 task assigner、Multi-Label A*、Poisson arrivals、windowed ECBS/PBS/CBS の全変種は未対応。 |
| 全探索割当 + CBS | Exhaustive target assignment + CBS | 実行可 | チーム内の割当（順列）を全通り試し、それぞれ CBS で解いて makespan 最小を選ぶ。cbm-tapf-aamas-2016 p.2 が「scalability に難がある」と名指しした素朴な方法そのもので、CBM / CBS-TA の比較対象と最適性の検証用に置いている。組合せ数が上限を超える入力は受け付けない。 |
| CBM | Conflict-Based Min-Cost-Flow | 実行可 | チームごとの匿名経路を時空間 min-cost max-flow で求め、チーム間の衝突を CBS 型に分岐して解消します。目的関数は makespan です。 |
| CBS-TA | Conflict-Based Search with Target Assignment | 実行可 | 割当行列の候補を Hungarian 法で優先付けし、各候補を CBS で評価する教材実装です。論文の遅延 K-best search forest を、ブラウザ向けに決定的な候補列挙へ置き換えています。 |
| 最小費用最大流 | Min-Cost Max-Flow | 実行可 | 1 チーム TAPF（匿名 MAPF）を時空間ネットワークの最小費用最大流で解きます。複数チームの衝突解消は CBM が担当します。 |
| 貪欲割当（MAPD ベースライン） | Greedy MAPD baseline | 実行可 | 論文手法ではないサイト独自のベースライン。手の空いたエージェントに最も近い未割当タスクを渡し、予約表を見ながら時空間 A* で pickup → delivery を計画する。TP の endpoint 規律（同 p.3-4 の Path2 / Property 2）が無いため、手が空いたエージェントがその場に居座って後続を塞ぐことがある。pickup 経由も 2 回の探索に分けており、MLA* のように 1 本では解かない。理論保証は無い。 |
| TP (Token Passing) | Token Passing | 実行可 | 明示的 token、Path1 / Path2、well-formed の endpoint 規律を実装します。低レベルは MLA* に置き換えた TP+MLA* の教育用実装です。 |
| TPTS (Token Passing with Task Swaps) | Token Passing with Task Swaps | 実行可 | TP の token / Path1 / Path2 を共有します。未 pickup の task なら前 timestep の carrying 中でも、pickup までの決定的な距離が短い agent が assign で奪えます。loop が swap-task を出し、old owner は同じ step に再計画します。 |
| CENTRAL | CENTRAL | 実行可 | Hungarian による中央割当と MLA* の token 計画を組み合わせた strawman です。論文の二段 CBS はブラウザ版では未実装で、解決性・最適性を保証しません。 |
| LNS-PBS | Large Neighborhood Search with Priority-Based Search | 実行可 | MG-MAPD の task sequence と multi-goal を扱う決定的な教育実装。LNS の全 anytime 近傍と dummy-path による完全性証明の実装ではなく、順序付き時空間 A* で PBS の役割を可視化します。 |
| LNS-wPBS | Windowed Priority-Based Search with LNS | 実行可 | LNS-PBS の task sequence planner に wPBS の rolling window を接続した教育実装。extra.windowSize（既定 w=10）ごとに再計画し、衝突解消範囲を窓内へ限定するため、論文どおり完全性を保証しません。 |
| RMCA | Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery | 実行可 | capacity つき task sequence を regret insertion で作り、実際の path cost を順序付き planner に反映する教育実装。論文の priority heap 全体と優先順位付き探索の完全性は簡略化しています。objective は service time ではなく TTD です。 |
高度な手法（CBS、PIBT、LaCAM、LNS など）はまだ実装されていません。アルゴリズム一覧では、 実装済みか解説のみかをバッジで区別しています。