Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization

論文概要：Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization

1. 問題定義と背景

**多エージェント経路探索（MAPF）**は、倉庫や物流システムにおいて、複数のエージェントが衝突を避けながらスタート地点からゴール地点へ移動する問題を指します。

• 既存の課題:
  • 最適性とスケーラビリティのトレードオフ: 完全な最適解を保証する手法（CBS など）は計算量が膨大になり、大規模なエージェント数には適用困難です。一方、スケーラブルなヒューリスティック手法は、最適性や完全性の保証が得られないことが多いです。
  • クローズドループ（閉ループ）計画の限界: 全体経路を一度に計画するのではなく、次の移動のみを計画してオンラインで再計画する「クローズドループ MAPF」はスケーラビリティに優れますが、有限の計画視野（Finite-Horizon）に依存するため、先を見通すことが難しく、高密度な環境では解の品質が低下したり、不安定になったりする問題があります。
  • ACCBS の限界: 著者らが以前提案した「Anytime Closed-Loop Conflict-Based Search (ACCBS)」は、有限視野内で CBS を適用して視野を拡張する手法ですが、計算時間制限により視野が短く終了してしまうと、短期的な判断（近視眼的）になり、大規模・高密度なインスタンスで解の品質が劣化します。また、エージェント間の構造的な独立性（因数分解）を時間を超えて利用することが困難でした。

2. 提案手法：CDCBS と証明（Certificate）フレームワーク

本論文では、上記の問題を解決するために、**証明駆動型衝突ベース探索（Certificate-Driven Conflict-Based Search: CDCBS）**を提案します。この手法の核心は、「証明（Certificate）」と「継承可能な因数分解（Inheritable Factorization）」の導入にあります。

A. 証明経路（Certificate Trajectories）と艦隊予算（Fleet Budget）

• 証明経路: 各タイムステップにおいて、現在の状態からゴールまでの「衝突のない完全な経路セット」を保持します。これは、計画が失敗した場合のフォールバックプランとして機能します。
• 艦隊予算（Fleet Budget）: 証明経路の総コスト（Sum of Costs, SOC）を「艦隊予算」として定義します。
• 更新ルール: 新しいクローズドループの更新（次の移動）は、それが現在の証明経路のコストを厳密に減少させる場合のみ受け入れられます。
  • これにより、有限視野の計画であっても、全体として「コストの単調減少」が保証され、完全性（すべてのエージェントがゴールに到達すること）が回復します。
  • 計算リソースが不足して視野が短くても、常に有効なフォールバックプランが存在するため、システムは不安定になりません。

B. 予算制限到達可能領域と継承可能な因数分解

• スラック（Slackness）: 艦隊予算から、各エージェントの最短経路コストの合計を引いた値（余裕分）を定義します。
• 予算制限到達可能領域: このスラックに基づき、各エージェントが将来到達しうる領域（Budget-Limited Reachable Region）を定義します。エージェントがその領域外に出ると、艦隊予算を超えてしまうため、証明を更新できません。
• 因数分解（Factorization）: 異なるエージェント群の「到達可能領域」が重ならない場合、それらの群は互いに独立して計画できます。
• 継承性（Inheritability）: 重要な理論的発見として、時間が経過するにつれてスラックが減少し、到達可能領域が縮小するため、一度確立された「独立した群」は、将来のタイムステップでも独立し続けることが証明されました。これにより、一度計算された因数分解構造を再利用でき、並列計算の効率を大幅に向上させます。

3. アルゴリズムの流れ（CDCBS）

1. 初期化と継承: 前ステップの証明経路と艦隊予算、および因数分解結果（エージェントのグループ分け）を継承します。
2. 証明更新: 現在の状態から、バックアップコントローラー（例：LaCAM）を用いて衝突のない経路を生成し、証明候補を作成します。
3. 制約木探索（ACCBS 拡張）: 有限視野の CBS を実行し、衝突のないアクティブプレフィックス（現在の移動までの経路）を見つけます。
4. 証明の改善: 見つかったプレフィックスにバックアップ経路を連結し、候補証明を作成します。もしそのコストが現在の艦隊予算より小さければ、証明と予算を更新します。
5. 因数分解の再計算: スラックが一定閾値以上減少した場合、到達可能領域を再計算し、より細かくエージェントをグループ化（因数分解）します。これにより、グループごとに並列計画が可能になります。
6. 実行: 現在の証明経路の最初のステップを実行し、次のタイムステップへ進みます。

4. 実験結果

ベンチマークマップ（Empty Map, Random Map）を用いた実験で、ACCBS や LaCAM と比較評価を行いました。

• 解の品質と安定性:
  • 高密度な環境（エージェントの占有率が高い場合）において、CDCBS は ACCBS よりも**一貫して優れた解の品質（低い SOC 増加分）**を示しました。
  • ACCBS は計算時間制限により視野が短くなると解の品質が急激に劣化しますが、CDCBS は証明メカニズムにより、追加の計算時間を投入するほど安定して性能が向上する（単調改善）傾向が見られました。
• 因数分解の効果:
  • 提案された因数分解により、大規模なエージェント群が小さな独立したサブグループに分割されました（例：200 エージェントが 24 グループなどに分割）。
  • これにより、グループごとの並列計画が可能となり、実質的な計算負荷の削減が期待されます。
• バックアップコントローラーの影響:
  • より高精度なバックアップコントローラー（Engineered LaCAM）を使用すると証明の質（艦隊予算の tightness）は向上しますが、必ずしも最終的なソルブ性能が比例して向上するわけではありません。証明の生成コストと品質のバランスが重要であることが示されました。

5. 意義と貢献

本論文の主な貢献は以下の 3 点です。

1. 証明駆動型フィルタリングの導入: 有限視野のクローズドループ計画に「証明経路」と「艦隊予算」を導入し、更新をフィルタリングすることで、完全性を回復させつつ、フォールバックプランを常に保持できるようにしました。
2. 予算制限因数分解と継承性: 艦隊予算に基づいて到達可能領域を定義し、それが時間を超えて縮小・維持される性質を利用することで、グローバルかつ継承可能な因数分解を実現しました。これにより、クローズドループ計画において構造的な独立性を効果的に活用できるようになりました。
3. CDCBS アルゴリズムの実装と評価: 既存の ACCBS にこのフレームワークを適用した CDCBS を提案し、高密度環境でのロバスト性と解の安定性を実証しました。

総括:
この研究は、クローズドループ MAPF が抱える「近視眼的な計画」と「構造的な複雑さ」という 2 つの課題に対し、証明（Certificate）という概念を通じて解決策を提示しました。特に、計算リソースが限られる環境でも、グローバルな保証（完全性）と並列計算の恩恵（因数分解）を両立させた点は、大規模な物流システムやロボット群制御の実用化において非常に重要です。