study-mapfMAPF / Lifelong MAPF / MAPD 教材

ICBSImproved CBS

一部のみ実装解説: 原論文と照合済み

cardinal conflict を優先し、同 cost の helpful bypass で CT 分岐を減らす CBS 改良。

概要

Improved CBS（ICBS）は、CBS の意味を変えずに CT を小さくする改善群です。原論文は meta-agent、Bypassing Conflicts（BP）、Prioritizing Conflicts（PC）、Merge and Restart（MR）を統合した ICBS を示します[icbs-ijcai-2015, p.1]。サイト版はこのうち PC と BP を実行できます。

まず何がうれしいのか

CBS はどの conflict を先に split するかで CT サイズが大きく変わります。解 cost を必ず上げる cardinal conflict を先に処理すれば lower bound を早く上げられます。また、同じ cost の別 path へ差し替えるだけで conflict が減るなら、2 child を OPEN へ積む必要がありません。

前提となる知識

対象問題

one-shot MAPF の SOC 最適化です。PC と BP は low level が最短 path を返すことを前提にします。

中心となるアイデア

conflict から 2 child を作ったとき、両 child の cost が親より増えるなら cardinal、片方だけ増えるなら semi-cardinal、どちらも増えないなら non-cardinal です。論文は individual agent では path cost 固定の MDD の幅を使って分類し、meta-agent では child cost を直接調べます[icbs-ijcai-2015, p.5]。

BP は cardinal 以外の conflict で child を試し、同 cost で選択 conflict を避け、かつ node 全体の conflict 数を減らす path を helpful bypass として親へ採用します[icbs-ijcai-2015, p.4]。

アルゴリズムの手順

  1. CT node の全 conflict を調べます。
  2. cardinal があれば即座に選びます。無ければ最初の semi-cardinal、最後に non-cardinal を選びます。
  3. cardinal 以外では 2 child の path を調べ、helpful bypass があれば constraint を保存せず親の path だけ差し替えます。
  4. bypass できなければ CBS と同じ 2 child を OPEN へ入れます。
  5. conflict-free node まで繰り返します。

小さな例

親 cost が 8 で 2 個の conflict を持つとします。ある split child が cost 8 のまま conflict を 1 個へ減らすなら、その path は helpful bypass です。親は constraint を追加せず path を採用し、もう片方の child も OPEN へ追加しません。cost 8 の探索層を保ったまま CT node 数を減らせます。

データ構造

疑似コード

while OPEN is not empty:
  node ← minimum CBS key
  if node has no conflicts: return node.paths

  for conflict in node.conflicts:
    children ← probe both standard-split branches
    class ← compare child costs with node.cost
    remember first cardinal, else first semi, else first non

  chosen ← highest-priority remembered conflict
  if chosen is not cardinal:
    if a same-cost child reduces conflictCount:
      node.paths ← child.paths
      continue with node
  insert both feasible children into OPEN

原論文 Algorithm 1 の PC（lines 9–10）と BP（lines 11–12）をサイト共通モデルへ再構成しています[icbs-ijcai-2015, Algorithm 1, p.2]。

実装上の注意

helpful bypass は「選んだ conflict が消えた」だけでは足りません。同 cost、親 constraints と整合、node 全体の conflict 数減少が必要です。cardinal conflict には同 cost bypass が存在しないため、論文どおり BP を試しません[icbs-ijcai-2015, p.5]。

サイト版は MDD を構築せず、定義と等価な「両 constraint を加えて最短 cost が増えるか」を直接 probe します。この probe の low-level 展開も metrics と上限に含めます。

よくある誤解

他手法との比較

CBS は最初の conflict をそのまま選びます。ICBS の PC+BP は最適 cost を保ったまま conflict 選択と path tie を改善します。EECBS §4 は bounded path に合わせて classification と bypass 条件を再定義するため、ICBS の条件をそのまま流用できません。

サイト上の実装との差異

MA-CBS と MR、MDD cache、meta-agent MDD は未対応です。mapf-icbs はライセンスファイルが無いため閲覧のみにし、cbsh2-rtc は USC 独自ライセンスのためコードを取り込んでいません。公開コードは一切転記していません。

実験してみる

detailed trace で classify-conflict と bypass を選んでください。cardinal では child cost が上がり、helpful bypass では SOC を保ったまま conflict 数だけが減ります。

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

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

適用範囲の注意: 論文の完全版 ICBS(25) は MA-CBS(25)+BP+PC+MR。本サイトは PC と helpful BP を実装し、MDD と等価な child-cost 判定を使う。MA-CBS merge / MR は未対応のため partial。

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

icbs-ijcai-2015 p.1 は optimal MAPF を対象とし、ICBS を最適 CBS 系の MA-CBS・同 cost の BP・PC・MR を統合したものとして定義する。p.4 の valid bypass は同 cost を条件とする。ICBS 固有の完全性定理は無く、CBS と complete/optimal な coupled low level に依存するため complete は conditional とした。

原論文

確認済みの箇所

公開実装

最終照合日: