HCAHierarchical Cooperative A

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

CA* の heuristic を、RRA* で必要時に求める静的な真の距離へ強化する。

概要

Hierarchical Cooperative A*（HCA*）は、CA* の探索手順を保ったまま heuristic を強くした手法です。時間軸と reservation table を無視した静的 2D map を抽象空間とし、そこにおけるゴールまでの最短距離を協調探索の heuristic にします[cooperative-pathfinding-2005, p.2]。

まず何がうれしいのか

Manhattan distance は壁を無視するため、迷路ではゴールへ近そうで実は遠いセルを多く展開します。静的な真の距離（true distance）は壁を考慮しながら他 agent だけを無視するため、許容性を保ったまま協調探索をより正確に導きます。

前提となる知識

CA* と reservation table
abstraction による admissible heuristic
A* で状態を展開した時点の最短距離

対象問題

対象モデルと固定 priority order は CA* と同じです。違うのは個別 Space-Time A* が使う heuristic だけです。したがって HCA* も one-shot MAPF 全体を共同探索しません。

中心となるアイデア

各 agent ごとに Reverse Resumable A*（RRA*）を 1 個持ちます。RRA* はゴールから開始位置の方向へ逆向きに探索します。協調探索がセル N の抽象距離を要求したとき、N が Closed に無ければ、N を展開するまで RRA* を再開します。その後は確定した g(N) を何度でも再利用できます[cooperative-pathfinding-2005, Algorithm 1, p.3]。

アルゴリズムの手順

agent のゴールを根とする RRA* の OPEN / Closed を初期化します。
CA* と同じ固定順で Space-Time A* を始めます。
状態 (cell,time) の h が必要なら、RRA* を cell まで再開します。
得た静的距離を h にして予約を避ける経路を探索します。
経路を予約し、次の agent へ進みます。

小さな例

ゴールが壁のすぐ向こうにあると、Manhattan distance は 1 でも、実際には壁を回って 9 歩かかることがあります。RRA* は一度その回り道を展開すると距離 9 を返します。同じ周辺セルの距離要求では、その OPEN / Closed を再利用できます。

データ構造

協調層: (cell,time) の OPEN、best-g、reservation table
抽象層: agent ごとの RRA* OPEN / Closed、静的距離 g
RRA* の origin: agent の元の start、探索開始点: goal

疑似コード

function abstractDistance(cell):
  if cell is in RRA.closed:
    return RRA.g[cell]
  while RRA.open is not empty:
    current ← pop minimum f from RRA.open
    move current to RRA.closed
    if current.cell = cell:
      return current.g
    relax reverse neighbors of current
  return infinity

for agent in input order:
  path ← SpaceTimeAStar(agent, reservations, h=abstractDistance)
  reserve path or fail for this ordering

前半は Silver の Algorithm 1[cooperative-pathfinding-2005, Algorithm 1, p.3]をサイトの grid 記法へ短く再構成しています。OPEN 更新の細部と successor reversal の行は実装説明へ移しました。

実装上の注意

論文は前向き探索と逆向き探索で同値分岐の向きを合わせる successor reversal を説明します[cooperative-pathfinding-2005, p.3]。サイト版は grid 上で決定的な f、g、y、x 順を使いますが、任意 graph で論文と同じ path tie を再現するとは主張しません。

RRA* と協調探索は 1 個の global expansion budget を共有します。expand-node の state.phase が abstract-rra なら抽象探索、cooperative なら時空間探索です。

よくある誤解

hierarchical は空間の多段階縮約を必ず意味しません。本論文の HCA* は時間と他 agent を落とす 1 個の domain abstraction です。
heuristic が強くなっても、固定順で経路を確定する不完全性は消えません。
RRA* は全セル距離を最初に前計算するのではなく、要求に応じて再開します。

他手法との比較

CA*: Manhattan heuristic。構造が単純ですが、壁の多い map では弱い見積もりです。
HCA*: on-demand RRA* distance。完全経路を固定順に計画します。
WHCA*: 同じ RRA* を使いながら、協調部分を window に限定して再計画します。

サイト上の実装との差異

公開 pibt2 の HCA は、長い静的距離を持つ agent を先にする優先規則と start / goal を考慮した tie-break を採用しています。本サイトは論文の CA* → HCA* の差を heuristic に限定して示すため、入力順を保ちます。pibt2 はサブモジュール未取得のため実行比較できず、コードも転記していません。

論文で明示されない edge-swap / following、有限 horizon、ブラウザ上限を追加しています。RRA* の厳密な successor reversal は、上述の決定的 grid tie-break へ置き換えています。

実験してみる

壁の多い map で CA* と HCA* の expandedNodes を比べてください。経路 cost が同じでも、abstract-rra の前処理と cooperative search の展開配分が変わります。

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

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

適用範囲の注意: CA* に、他エージェントを無視した抽象距離（true distance heuristic）を導入した版。MAPF 全体の最適性は原論文で定理として確認できないため unknown。

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

cooperative-pathfinding-2005 PDF p.2 は decoupled greedy approach の不完全例を示し、同 p.3 は HCA* を CA* の heuristic だけを RRA* の抽象距離へ置き換えた方式と定義するため、その順序依存は残る。

原論文

Cooperative Pathfinding
David Silver (2005) Cooperative Pathfinding. AIIDE 2005
DOI外部リンクのみPDF 非同梱

確認済みの箇所

cooperative-pathfinding-2005 — p.2, p.3

公開実装

Kei18/pibt2公式実装
ライセンス: MITコード転記可（著作権表示の保持が必要）
参照コミット: faab5b916649

最終照合日: 2026-07-27