Disjoint SplittingDisjoint Splitting for CBS

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

同じ agent の正制約と負制約で、重なりのない 2 つの CT branch を作る CBS の分割法。

概要

Disjoint Splitting（DS）は CBS の high level を作り直す手法ではなく、1 回の conflict を 2 child へ分ける規則を置き換えます。standard splitting が conflict の 2 agent へ別々の負制約を与えるのに対し、DS は選んだ同じ agent へ「通る」という正制約と「通らない」という負制約を与えます[disjoint-splitting-icaps-2019, §4, p.3]。

まず何がうれしいのか

standard split の 2 child には、両方の禁止を満たす plan が重複して入ります。DS の 2 child はある条件 P とその否定 ¬P なので重なりません。重複探索を減らしつつ、CBS の CT と low level をそのまま再利用できます。

中心となるアイデア

vertex conflict C=(ai,aj,v,t) から ai を選んだとします。

positive child: ai は時刻 t に v へ必ず居る
negative child: ai は時刻 t に v へ居てはならない

任意の candidate plan は ai@v@t を満たすか満たさないかのちょうど一方です。そのため 2 branch は排他的で、親 node が含む conflict-free solution を場合分けし尽くします。原論文も、このどちらか一方を任意の candidate conflict-free plan が満たすことから completeness を説明しています[disjoint-splitting-icaps-2019, §4, p.3]。より一般には、互いに素な constraint set での分割が CBS の完全性・最適性を保つことが Theorem 2 で示されています[cbsh2-rtc-aij-2021, Theorem 2, p.6]。

正制約が他 agent に及ぼす意味

ai に ai@v@t を必須としたら、他 agent は同じ v,t を使えません。正制約は対象 agent の必須条件であると同時に、他 agent への暗黙の禁止です。原論文は positive child で正制約に違反する agent を再計画する処理を説明しています[disjoint-splitting-icaps-2019, §4.1, p.3]。

サイト版はこの意味を vertex と有向 edge の両方へ適用します。edge の正制約なら、対象 agent は指定時刻に指定方向へ通り、他 agent は両 endpoint の同時占有と逆向き edge swap を避けます。

アルゴリズムの手順

CBS と同じ CT node を SOC 順に取り出します。
earliest conflict を 1 個選びます。
conflict の 2 agent から split agent を seeded random で 1 体選びます。
同じ時空間 predicate の positive / negative child を作ります。
negative child は対象 agent、positive child は制約へ違反する全 agent を再計画します。
feasible child を CBS の OPEN へ戻します。

疑似コード

conflict ← earliestConflict(node.paths)
x ← seededRandomChoice(conflict.agentA, conflict.agentB)
P ← positiveConstraint(x, conflict)

for constraint in [not P, P]:
  child.constraints ← node.constraints + constraint
  affected ← every path violating constraint or its implication
  replan affected agents
  if feasible: OPEN.push(child)

split agent の Random 方策は原論文 §4.2 にある選択肢です[disjoint-splitting-icaps-2019, §4.2, p.3]。サイト版は conflict 自体の選択を既存 CBS の earliest 規則に残した実装上の選択であり、論文の主張ではありません。

理論保証と実装上限

マニフェストでは完全性を conditional、最適性を true としています。これは DS が CBS の保証を保存するという意味であり、CBS が持たない無条件の no-solution 有限判定まで主張するものではありません。

サイト上の実装との差異

原論文 §4.1 の positive landmark 間だけを再探索する最適化、MDD Singletons / Width を使う agent 選択、Disjoint3 は未実装です。公開実装のコードは参照・転記していません。ブラウザ安全上限、有限 maxHorizon、timeout、AbortSignal による打切りは保証対象外です。

実験してみる

detailed trace で add-constraint を見ると、同じ conflict から positive: true と負制約の両方が作られます。low-level-replan が正制約の対象以外にも出る場合は、暗黙の禁止に違反した path を再計画しています。

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

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

適用範囲の注意: 同じ agent の negative / positive constraint で排他的に分岐する。本サイトは正制約を対象 agent の必須条件、他 agent の暗黙の禁止として vertex / edge / following へ強制し、違反 path を持つ全 agent を再計画する。split agent は seeded Random。landmark 区間再探索と MDD 選択方策は未実装。

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

disjoint-splitting-icaps-2019 p.3「Clearly, disjoint splitting is complete since one of the two constraints must hold for any candidate conflict-free plan in the parent CT node」/ cbsh2-rtc-aij-2021 p.6 Theorem 2「Using two sets of mutually disjunctive constraints to split a CT node preserves the completeness and optimality of CBS.」。complete は CBS と同じく conditional。

原論文

Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search
Jiaoyang Li, Daniel Harabor, Peter J. Stuckey ほか (2019) Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search. ICAPS 2019, pp. 279-283
DOI外部リンクのみPDF 非同梱
Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
Jiaoyang Li, Daniel Harabor, Peter J. Stuckey ほか (2021) Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search. Artificial Intelligence, vol. 301, art. 103574
DOI外部リンクのみPDF 非同梱

確認済みの箇所

disjoint-splitting-icaps-2019 — §3, §4, §4.1, §4.2 — p.2, p.3
cbsh2-rtc-aij-2021 — p.6

公開実装

Jiaoyang-Li/CBSH2-RTC著者が管理
ライセンス: NOASSERTIONコード転記不可。挙動確認のみに使う
参照コミット: a834df1e16c1

最終照合日: 2026-08-31