Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

技術的概要：マルチエージェント協調輸送：最適かつ効率的なタスク割り当てと経路探索

問題定義：CT-TAPF
本論文は、既存のマルチエージェント経路探索（MAPF）およびタスク割り当てと経路探索（TAPF）の枠組みにおける重要な欠陥、すなわち、単一の大型物体を移動させるために複数のエージェントが協調する必要がある輸送タスクを処理できないという欠陥に対処する。著者らは、協調輸送タスク割り当てと経路探索（CT-TAPF）問題を形式化した。この設定では、$n$ 個のエージェントの集合が $m$ 個の協調タスクの集合に割り当てられる。各タスク $\tau_i$ は特定のチームサイズ $k_i$ を要求し、以下の 2 つのフェーズを含む：

1. アセンブリーフェーズ：エージェントは独立して移動し、チームを形成するための指定された「スロット」（開始構成頂点）に到達する。
2. コンボイフェーズ：割り当てられたすべてのエージェントが到着し、同期すると、それらは単一の剛体（「コンボイ」）としてゴール構成へ移動する。

この問題は NP 困難であり、TAPF を一般化する。有効な解は、衝突のない経路を確保しつつ、コストの総和（SoC）を最小化しなければならない。重要なのは、本論文が、参照位置が異なっていてもエージェントやコンボイの足跡が重なる場合に衝突が発生するという幾何学的な衝突定義を導入している点である。

手法
著者らは、CT-TAPF を解決するための 2 段階の探索アーキテクチャを提案し、最適ソルバーと非最適バリエーションのファミリーの両方を導入する。

1. 最適ソルバー：CT-TCBS
   **協調輸送タスク衝突ベース探索（CT-TCBS）**は、衝突ベース探索（CBS）フレームワークに基づく 2 段階アルゴリズムである：

   • 高レベル探索：制約木上で A* 探索を実行する。各ノードは、タスク割り当てと時空間制約によって定義された部分解を表す。アルゴリズムは、新しいタスクを割り当てる前に経路の衝突を解決することを優先する。
   • 低レベルプランナー：統一 A* を使用して、個々のエージェントおよびマルチエージェント・コンボイの最適経路を計算する。これは、アセンブリースロットに到着するエージェントの同期を処理し、コンボイの共同移動を計画する。
   • 増分的展開戦略：核心的な貢献は、「組合展開」（一度にすべての可能なチームの順列を生成する）を増分的展開に置き換えることである。チーム全体を即座に割り当てるのではなく、エージェントをタスクスロットへ 1 人ずつ割り当てる。これにより、中間的な、部分的に割り当てられたノードが生成され、分岐係数が劇的に減少し、チーム形成に内在する組合爆発が管理される。
   • ヒューリスティック関数：ヒューリスティック $H$ は、2 つの許容可能な成分の和である：$H_1$（部分的に割り当てられたエージェントのコミットされた輸送コスト）と $H_2$（未割り当てスロットの推定割り当てコスト）。著者らは、その許容可能な下限を計算することが計算的に困難（一般化割り当て問題に相当する）であるため、同期待ち時間成分（$H_3$）を明示的に除外している。

2. 非最適ソルバー：タスク中心セレクター
   スケーラビリティに対処するため、著者らはグローバルでタスク中心の視点を取り入れた非最適バリエーションを開発する。エージェント中心の「ニアレスト・ネイバー」アプローチ（非効率的なチーム形成を招く可能性がある）とは異なり、これらのソルバーは、グローバルな難易度指標に基づいて次に割り当てるタスクを選択する：

   • ベストタスク（BT）：推定完了コストが最も低いタスクを選択する（貪欲アプローチ）。
   • ワーストタスク（WT）：推定完了コストが最も高いタスクを選択する（フェイルファストアプローチ）。これは、デッドロックを回避するために複雑なチームを早期に形成することを目指す。
     これらのソルバーは、エージェントの可用性と移動時間に基づいてタスクの難易度を推定するために、ハンガリー法を使用する。

主要な発見と結果
密度やタスク分布が異なるグリッドマップ上での包括的な実証評価を通じて、本論文は 3 つの主要な発見を報告する：

1. 増分的展開の優位性：増分的展開戦略は、単純な組合アプローチを大幅に凌駕する。統計分析により、タスク割り当ての組合的負担が経路探索の衝突よりも支配的な計算ボトルネックであることが確認された。タスク割り当ての探索空間を剪定することにより、増分的戦略ははるかに高い成功率を達成する。
2. タスク - 衝突展開のジレンマ：本論文は、洗練された衝突解決戦略（特に大規模エージェント MAPF に効果的な MAX-d）が、統合された CT-TAPF 設定ではパフォーマンスが低下するという反直感的な現象を特定している。著者らはこれを「タスク - 衝突ジレンマ」に起因すると帰属している。MAX-d の戦略は、衝突木を剪定するためにノードコストを増加させるが、これが高レベル探索にタスク割り当ての分岐を早期に探索させ、結果として探索空間が拡大し、時間制限内での成功率が低下する。
3. 新たな効率性のフロンティア：提案された非最適ソルバー（特にワーストタスクバリエーション）は、解の質と実行時間の間の新たなトレードオフフロンティアを確立する。最適 CT-TCBS は最良の解を提供するが、計算コストが高い。非最適ソルバーは、エージェント中心のベースライン（-nn1/-nn2 など）よりも高品質な解をより迅速に見つけることで凌駕し、単純な貪欲ヒューリスティックよりも堅牢である。具体的には、WT セレクターは、エージェントが散らばるのを防ぐために複雑なチームの形成を早期に優先するため、BT よりも一般的に最適解に近い解を生み出す。

意義と主張
本論文は、新しいクラスの協調マルチエージェント問題のための基礎的な枠組みを提供すると主張する。その意義は以下の点にある：

• CT-TAPF の形式化：個別的なタスク実行を超えて、持続的で物理的に結合された協調行動をモデル化する。
• アルゴリズム的革新：標準的な TAPF ソルバーが効率的に処理できないチーム形成に特有の組合爆発を管理するための増分的展開戦略の導入。
• 実用的スケーラビリティ：最適から非最適までのアルゴリズムのスイートを提供し、実務者が、大型または不規則な貨物を含む現実世界の物流シナリオにおける、解の最適性と計算の実現可能性の間のトレードオフを navigat することを可能にする。

著者らは、現在の枠組みは離散的であるが、将来の研究はこれらの概念を連続領域および異種エージェントに拡張するだろうと結論付けているが、現在の貢献は協調輸送に必要な理論的およびアルゴリズム的基盤を確立している。