CENTRALCENTRAL

シミュレータで実行可解説: 原論文と照合済み

agent assignment と path planning を中央でまとめて行う MAPD の比較用 strawman。

概要

CENTRAL は TP / TPTS と比較する中央集権の strawman です。free agent へ task endpoint または parking endpoint を割り当て、全 agent の path を再計画します[mapd-tp-tpts-central-2017, §5, p.5]。

まず何がうれしいのか

全 agent の情報を一度に使えるため、局所的な token 順に縛られません。論文の実験では service time が最も小さい側に出ます。

前提となる知識

MAPD、Hungarian assignment、MAPF の衝突回避、service time / makespan が前提です。

対象問題

online MAPD。サイトでは runMapdLoop の一 step ごとに free agent と open task を見て中央 assignment を計算します。

中心となるアイデア

task の pickup を free agent へ割り当て、残りを non-task endpoint へ退避させます。サイト版は既存 Hungarian と MLA* を組み合わせます。

アルゴリズムの手順

free agent と open task を集める。
agent–pickup の距離行列を作り Hungarian で候補を選ぶ。
MLA* で token に衝突しない path を計画する。
task を割り当てられない agent は parking endpoint へ移す。
全 agent を一 step 進める。

小さな例

二体の free agent と一つの task なら、pickup に近い agent を task に、もう一体を non-task endpoint に割り当てます。endpoint は task delivery を塞がない候補から選びます。

データ構造

Hungarian の cost matrix、明示的 token、MLA* の label state を使います。CENTRAL の論文版は二段の CBS path planning ですが、サイト版はブラウザ向けに逐次 token planning へ簡略化しています。

疑似コード

while tasks remain:
  free ← available agents
  X ← feasible pickup endpoints plus non-task parking endpoints
  assignment ← Hungarian(cost(agent, endpoint))
  for each assigned agent:
    token[agent] ← MLA*(current, ordered goals, token)
  move one step

原論文の Agent Assignment / Path Planning の構造を短く再構成しています[mapd-tp-tpts-central-2017, §5, p.5]。

実装上の注意

よくある誤解

CENTRAL は最適 MAPD solver ではありません。
Hungarian が割当を最適化しても、経路と将来 task の全体最適性は得られません。
well-formed でも CENTRAL の解決性は保証されません。

他手法との比較

TP は token を agent が順番に更新し、TPTS は未 pickup task を交換します。CENTRAL は計算量を使って全体を見ますが、理論保証を要求していない比較対象です[mapd-tp-tpts-central-2017, §7, p.8]。

サイト上の実装との差異

サイト版は Hungarian + MLA* の教育用実装で、論文の二段 CBS、無制限の中央探索、warehouse 実験スケールは扱いません。fidelity も educational です。

実験してみる

完全性・最適性などの保証

理論保証。**原論文で確認できた記述だけ**を載せています。「不明」は「保証が無い」ではなく「原論文で未確認」の意味です。
完全性	なし
最適性	なし
対象	MAPD

適用範囲の注意: 割当と経路計画を集中的に解く比較用 strawman。論文 p.5 §5 が well-formed instance すら全て解くことを要求しないと明記する。実験で service time が小さい傾向でも保証を意味しない。サイト版は Hungarian + MLA* の教育用簡略実装。

保証の根拠（原論文の記述）

mapd-tp-tpts-central-2017 PDF p.5 §5「do not require that it is optimally effective or even solves all well-formed MAPD instances.」CENTRAL は解決性・最適性を保証しない。

原論文

Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
Hang Ma, Jiaoyang Li, T. K. Satish Kumar ほか (2017) Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks. AAMAS 2017, pp. 837-845
DOI外部リンクのみPDF 非同梱

公開実装

対応する公開実装は、まだマニフェストへ登録されていません。

最終照合日: 2026-08-02