HBHHungarian-Based / h-value-Based Heuristic

内部実装あり（単体では実行不可）解説: 原論文と照合済み

MLA* の候補を agent–task の h 値で順序付ける中央 assignment heuristic。

概要

HBH は MLA* と組み合わせて使う task assignment heuristic です。論文本文の名称は h-value-based heuristic で、Algorithm 2 は agent–task pair を h 値の昇順に試します[mla-star-icaps-2019, Algorithm 2, p.3]。

まず何がうれしいのか

近い pickup を先に試し、MLA* が実行可能な pair だけを採用します。中央で複数 agent をまとめて考えるため、単純な token 順より良い候補順を作れます。

前提となる知識

Hungarian method、MLA*、MAPD の free agent / open task が前提です。

対象問題

MAPD の assignment 部分。HBH 自身は path を返す Solver ではなく、MLA* と組み合わせる MapdStrategy の部品です。

中心となるアイデア

agent–task の h 値行列を作り、サイト版では Batch 7 の Hungarian 実装で deterministic な候補を作ります。各候補の path は MLA* で検証します。

アルゴリズムの手順

available agent と open task を集める。
pickup までの距離を cost にする。
Hungarian で候補を順序付ける。
MLA* が成功した候補を token に書き込む。

小さな例

二体の agent と二つの task の距離行列が [[2,8],[4,3]] なら、近い pair を優先し、実際に衝突しない MLA* path が得られる割当を採用します。

データ構造

rectangular cost matrix、Hungarian の assignment、token の future path を使います。

疑似コード

pairs ← all (agent, task) with h(agent, pickup(task))
sort / assign pairs by h-value
for (agent, task) in pairs:
  if both are still free and MLA*(agent, task, token) succeeds:
    assign and update token

論文 Algorithm 2 の pair scan を短く再構成し、サイト版では Hungarian を補助部品として使います[mla-star-icaps-2019, Algorithm 2, p.3]。

実装上の注意

よくある誤解

HBH は Hungarian だけで MAPD を解く手法ではありません。
h 値順の良さは理論保証ではありません。
MLA* の低レベルと HBH の割当順は別の役割です。

他手法との比較

TP は分散的な token 順、CENTRAL は中央の比較用 strawman、HBH はその assignment 部分を改善する heuristic です。論文は TP+MLA* と HBH+MLA* を実験比較しています[mla-star-icaps-2019, §Computational Experiments, p.3]。

サイト上の実装との差異

サイト版は既存 Hungarian を呼び、MLA* と共通 token strategy を使います。HBH 単独の Simulator 選択肢は用意せず、CENTRAL などの内部 strategy から使える部品として表示します。

実験してみる

HBH は内部ライブラリです。Simulator では CENTRAL の assignment と MLA* の trace を通じて動作を確認できます。

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

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

適用範囲の注意: 論文本文の名称は h-value-based heuristic で、Algorithm 2 は h-value の昇順 pair scan。サイトの manifest 名 Hungarian-Based は互換名として残し、Batch 7 の Hungarian を assignment 候補の部品として呼ぶ。保証を確認できないため guarantees は unknown。MLA* と組み合わせる内部 strategy で、単独 MAPD Solver ではない。

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

mla-star-icaps-2019 PDF p.2–3 Algorithm 2 と p.4 の実験説明を確認したが、HBH の完全性・最適性・準最適性を主張する定理は確認できなかった。

原論文

A Multi-Label A* Algorithm for Multi-Agent Pathfinding
Florian Grenouilleau, Willem-Jan van Hoeve, John N. Hooker (2019) A Multi-Label A* Algorithm for Multi-Agent Pathfinding. ICAPS 2019, pp. 181-185
DOI外部リンクのみPDF 非同梱

公開実装

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

最終照合日: 2026-08-02