study-mapfMAPF / Lifelong MAPF / MAPD 教材

EECBSExplicit Estimation CBS

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

online error から残り cost を推定し、CLEANUP・OPEN・FOCAL を使い分ける bounded CBS。

概要

Explicit Estimation CBS（EECBS）は、ECBS の low-level bound を保ちつつ、high level に Explicit Estimation Search（EES）を使います。admissible lower bound だけでなく、残り conflict 数と過去の展開で観測した error から solution cost を推定します[eecbs-aaai-2021, §3.3, p.5]。

まず何がうれしいのか

ECBS は conflict 数が少ない CT node を優先しますが、path cost と conflict 数が逆相関すると同じ枝の周辺を何度も行き来できます。EECBS は「goal に近そう」「推定 solution cost が良さそう」「lower bound を上げるべき」の 3 役を別 list に分け、状況に応じて選びます[eecbs-aaai-2021, §3.1, p.3]。

前提となる知識

対象問題

原論文は vertex / swapping conflict、stay at target、sum of costs の MAPF variant を対象にします[eecbs-aaai-2021, §2.1, p.2]。サイト版もこの rule に合わせ、4 近傍 grid に限定します。

中心となるアイデア

high level は同じ active CT node を 3 通りに見ます。

SELECTNODE はまず FOCAL best の実 cost が w*bestLB 以内ならそれを選び、次に OPEN best を同じ条件で試し、どちらも外なら CLEANUP best を選びます。このため選択 node は常に cost(N)<=w*lb(bestLB) を満たします[eecbs-aaai-2021, §3.3, p.5]。

アルゴリズムの手順

  1. ECBS と同じ bounded low-level focal search で root を作ります。
  2. active CT nodes から CLEANUP best、OPEN best、FOCAL best を求めます。
  3. EES の 3 条件で展開 node を選びます。
  4. conflict が無ければ返します。
  5. standard split と bounded low-level replan で children を作ります。
  6. 推定 fHat が最小の child から one-step distance / cost error を観測し、global average を更新します。
  7. 次の SELECTNODE で新しい推定を使います。

小さな例

CLEANUP best の lb=10、w=1.2 なら実 cost の安全上限は 12 です。FOCAL best の cost=13 は goal に近そうでも選べません。OPEN best が cost=11 ならそれを選べます。両方が 12 を超える場合だけ lb=10 の CLEANUP node を展開し、lower bound の改善を促します。

データ構造

疑似コード

while active CT nodes are not empty:
  bestLB ← minimum lb
  bestFHat ← minimum learned fHat
  bestD ← minimum hc among nodes with fHat ≤ w * bestFHat.fHat

  if bestD.cost ≤ w * bestLB.lb: node ← bestD
  else if bestFHat.cost ≤ w * bestLB.lb: node ← bestFHat
  else: node ← bestLB

  if node is conflict-free: return node.paths
  children ← standardSplitAndBoundedReplan(node)
  update one-step error from estimated-best child
return failure

Algorithm 1 の基礎 high-level search と §3.3 の SELECTNODE を、list 更新の実装詳細を省いて再構成しています[eecbs-aaai-2021, Algorithm 1, p.6][eecbs-aaai-2021, §3.3, p.5]。

実装上の注意

fHat は admissible ではありません。bound の判定には必ず node の実 cost と CLEANUP の admissible lb を使います。online error の平均が不安定でも、CLEANUP を残すことで探索を進められます。

原論文の one-step distance error は hc(bestChild)-(hc(parent)-1)、cost error は child と parent の cost 差です。サイト版は観測済み全展開の global running average を使います[eecbs-aaai-2021, §3.4, p.5]。

よくある誤解

他手法との比較

ECBS は high-level FOCAL を conflict 数だけで選びます。EECBS は learned cost estimate と CLEANUP fallback を追加します。ICBS の bypass / conflict classification は最短 path 用なので、bounded path の EECBS へ入れるには §4 の再定義が必要です。

サイト上の実装との差異

§4 の relaxed bypass、PC、rectangle / corridor / target symmetry reasoning、adaptive WDG は未対応です。公開 eecbs commit 06ec7058... はこれらを含みますが、USC の教育・研究・非営利限定ライセンスなので閲覧だけに留め、コードは転記していません。

実験してみる

verbose trace の CT expand-node で selectedFrom を見てください。focal、open、cleanup が切り替わっても、返却 SOC と metrics.lowerBound の比が指定 w 以下であることを確認できます。

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

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

適用範囲の注意: Explicit Estimation Search を CBS 高レベルへ適用し、非許容推定をオンライン学習で得る。本サイトは §3 の基礎 EECBS を実装し、§4 の BP/PC/symmetry/WDG は未対応。

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

eecbs-aaai-2021 p.5 式 (2) と直後は EECBS が cost(N)≤w*lb(bestlb) を満たす CT node だけを選び、bounded suboptimality を保証すると述べる。EECBS 自身の完全性を明示する記述は確認できないため complete は unknown のままとした。

原論文

確認済みの箇所

公開実装

最終照合日: