従来のマルチエージェント経路計画やタスク割り当ての研究は、単一のエージェントで完遂可能なタスクを主に対象としており、複数のエージェントがチームを組んで不規則な形状の物品を運搬するシナリオへの対応が不十分であった。本研究では、エージェントが特定の構成で物体に結合し、同期して移動する協調的な輸送タスクの割り当てと、衝突のない経路計画を統合したCT-TAPF問題を対象とする。この問題は、タスク選択、チーム形成、および協調移動を同時に扱う必要があり、NP困難な問題として定義される。
既存のタスク割り当てと経路計画の統合手法は、負の干渉を避ける調整には長けているが、複数のエージェントが能動的に協力して一つのタスクを遂行するモデル化ができていない。本研究は、チーム形成のプロセスを段階的に管理するIncremental Expansion戦略を導入することで、従来の組合せ論的な手法における探索空間の爆発を抑制する新規性を有する。また、タスクの困難度に基づくグローバルな指標を用いた劣最適解ソルバーを開発し、解の品質と実行時間のトレードオフにおける新たな効率的な領域を確立した。
提案するCT-TCBSは、2レベルの探索構造を持つ。上位レベルでは、制約木に対してA*探索を行い、割り当て済みタスクのコスト $g(n)$ と未割り当てタスクの推定コスト $h(n)$ を用いた $f(n) = g(n) + h(n)$ に基づいてタスク割り当ての組合せを探索する。この際、一度に全チームを割り当てるのではなく、タスクのスロットを一つずつ埋めていくIncremental Expansionを用いる。下位レベルでは、Unified A*を用いてエージェントおよびコンボイの経路を計算する。衝突解決にはMC-CBSフレームワークを採用し、非対称な制約追加を行うASYM、幾何学的な重なりを利用するSYM、およびコスト増加を最大化するMAX-dの3つの戦略を用いてコンボイ間の衝突を解消する。
グリッドマップ上のRandom、Spatially-biased、Collision-richの3種類のシナリオを用いて評価を行った。最適解探索において、Incremental戦略はCombinatorial手法よりも高い成功率を示し、探索空間を大幅に削減できることが確認された。劣最適解手法の比較では、タスクの困難度に基づくWorst-Task (WT) セレクタが、Best-Task (BT) セレクタよりも最適解との乖離が小さく、優れた解の質を実現した。また、WTセレクタは既存のエージェント中心型手法である $\text{A*-nn1}$ や $\text{A*-nn2}$ よりも高速であり、Greedy-PPよりも高品質な解を提供することが示された。
高度な衝突解決手法であるMAX-dは、衝突解決ツリーを枝刈りするために $g$-valueを増加させる性質があるが、これが上位レベルのA*探索においてタスク割り当てのコストを不当に高く見積もらせてしまう「タスク衝突拡張のジレンマ」が存在する。今後の課題として、現実的な倉庫環境における連続的なMulti-Agent Pickup and Delivery (MAPD) への拡張、ソーシャルオークションや交渉を用いた分散制御、および異種エージェントの導入によるシステムの柔軟性と探索効率の向上が挙げられる。
本論文では、複数のエージェントが協力して大きな物体を運搬する際に必要となる、チーム形成、タスク割り当て、および衝突回避経路計画を統合したCooperative Transportation Task Allocation and Path Finding (CT-TAPF) 問題を定式化している。最適解を求める手法として、チーム形成における組合せ爆発を抑制するために、探索空間を効果的に枝刈りするIncremental Expansion戦略を備えたCooperative Transportation Task Conflict-Based Search (CT-TCBS) を提案している。また、計算コストを抑えるための劣最適解ソルバーとして、タスクの困難度に基づくグローバルな指標を用いて次に割り当てるタスクを選択する、Best TaskまたはWorst Taskアプローチを用いた一連の手法を開発している。実験の結果、提案したIncremental Expansion戦略は、単純な組合せ論的手法と比較してタスク割り当ての探索空間を大幅に削減できることが示された。さらに、大規模なエージェント数に対する経路計画では有効な高度な衝突解決手法が、CT-TAPFのような統合的な設定では逆に性能を低下させるという「タスク衝突拡張のジレンマ」を特定している。最終的に、提案された劣最適ソルバーは、エージェント中心の既存手法と比較して、解の品質と実行時間のトレードオフにおいてより効率的なフロンティアを確立している。
従来のマルチエージェント経路計画（MAPF）やタスク割り当てと経路計画の統合（TAPF）は、主に単一のエージェントで実行可能なタスクを対象としており、複数のエージェントが協力して大型または不規則な形状の物品を運搬するシナリオへの対応が不十分である。本研究では、エージェントがチームを形成して協力的な輸送タスクを遂行し、衝突のない経路で目的地へ運ぶ「Cooperative Transportation Task Allocation and Path Finding (CT-TAPF)」問題を定式化する。このCT-TAPF問題はTAPFの一般化であり、NP困難な問題として定義される。本論文では、この問題に対する最適解を得るためのソルバーとしてCooperative Task Conflict-Based Search (CT-TCBS) を提案し、さらにスケーラビリティを確保するために、計算効率と解の品質のトレードオフを考慮した複数の劣最適解（suboptimal）バリアントを開発している。実験では、計算制約下における最適解の成功率、タスク割り当てと衝突解決の探索空間のトレードオフ、および最適手法と劣最適手法間における解の品質と実行時間のバランスについて包括的な評価を行っている。
本セクションでは、エージェント間の衝突回避を目的とするMulti-Agent Path Finding (MAPF) と、タスク割り当てを統合したTask Assignment and Path Finding (TAPF) の関連研究が整理されている。MAPFはNP困難な問題であり、コストの総和（Sum of Costs）やメイクスパンの最小化を目的とし、Conflict-Based Search (CBS) を基盤とした最適解法や、大規模問題向けのLNSなどの劣最適解法が存在する。TAPFは、タスク割り当てと経路計画の密な結合が課題であり、CBSを拡張したCBS-TAやTCBSなどの手法が提案されているが、これらは主に負の干渉を避けるための調整に留まり、複数のエージェントが協調して一つのタスクを遂行する能動的な協力関係をモデル化できていない。既存の協力型モデルであるCo-MAPFやPackage-Exchange Robot-Routing (PERR) は、協力行動を瞬間的なイベントや抽象的な依存関係として簡略化しており、持続的かつ物理的に結合した協調動作を扱うには不十分である。本研究が扱うCooperative Transportation Task Assignment and Path Finding (CT-TAPF) は、タスク選択、チーム形成、および協調移動を統合した問題であり、単一のエージェントをタスクに割り当てる従来のTAPF手法では、チーム形成に伴う組合せ爆発により対応できない。これに対し、本論文ではTCBSの枠組みを拡張し、チーム形成を段階的に管理する増分的な展開戦略を用いた最適解法であるCT-TCBSを提案している。
本研究では、無向グラフ $G = (V, E)$ 上で、エージェント集合 $\mathcal{A}$ がタスク集合 $\mathcal{T}$ を完遂するための、タスクスロット割り当てと衝突のない経路計画を目的とする問題を定義している。各タスク $t \in \mathcal{T}$ は開始構成 $S_t$ と目標構成 $G_t$ という、連結な部分グラフを形成する頂点の集合によって定義され、エージェントは各タスクの特定の頂点（スロット）に割り当てられる。タスクの実行は、エージェントが各スロットへ個別に移動するアセンブリフェーズと、全エージェントが同期した後に一つの「コンボイ（Convoy）」として剛体状に移動するコンボイフェーズの2段階で構成される。コンボイは、基準位置 $p$ と相対座標のオフセット集合 $\mathcal{R}$ によって定義され、時刻 $t$ における占有頂点集合は $F(p, \mathcal{R}) = \{p + r \mid r \in \mathcal{R}\}$ と表される。解の最適性は、全エージェントの総運用時間である $\text{SoC}$ の最小化によって評価される。衝突回避の条件として、時刻 $t$ における2つのエンティティの占有頂点集合の積集合が空であること、すなわち $F_1(t) \cap F_2(t) = \emptyset$ という幾何学的な頂点衝突の回避が課される。
CT-TCBSは、協調輸送タスク割り当ておよび経路計画（CT-TAPF）問題を解くための、最適かつ2レベル構造の探索アルゴリズムである。上位レベルでは、制約木に対するA*探索を行い、タスク割り当ての組合せ空間を探索する。各ノードの評価には、割り当て済みタスクの真の最適コストを表す $g(n)$ と、未割り当てタスクの完了に必要な最小追加コストの許容的推定値である $h(n)$ を用いた $f(n) = g(n) + h(n)$ が使用される。下位レベルでは、個々のエージェントおよび複数エージェントによるコンボイ（Convoy）の経路を、時空間制約を考慮したUnified A*を用いて計算する。衝突解決においては、MC-CBSフレームワークを採用しており、非対称な制約追加を行うASYM、幾何学的な重なりを利用するSYM、およびコスト増加を最大化するMAX-dの3つの戦略を用いて、コンボイ間の衝突を効率的に解消する。タスク割り当ての爆発的な分岐を防ぐため、一度に全チームを割り当てるCombinatorial Expansionではなく、タスクの空きスロットを一つずつ埋めていくIncremental Expansionを提案しており、これにより探索の分岐数を大幅に抑制している。
本実験では、グリッドマップ上で生成されたCT-TAPFインスタンスを用い、提案手法の有効性を検証している。シナリオは、エージェントとタスクを均一に配置するRandom、中央通路に混雑を誘発するSpatially-biased、および軌道の交差を意図的に作り出すCollision-richの3種類で構成される。最適解を求める手法の比較では、Incremental戦略がIncremental-LRやCombinatorialよりも高い成功率を示し、これはタスク割り当てに伴う探索空間の枝刈りが効率的であるためである。また、衝突解決器の比較において、MAX-d変種は、衝突解決ツリーを枝刈りするために $g$-valueを増加させる戦略が、高レベルのA*探索においてタスク割り当てのコストを不当に高く見せてしまう「Task-Conflict Dilemma」により、ノード展開数が大幅に増加する傾向がある。非最適解手法の評価では、多人数タスクを優先するWorst-Task (WT) セレクタが、Best-Task (BT) セレクタよりも最適解との乖離（optimality gap）が有意に小さく、優れた解の質を実現している。最終的な実行時間と解の質のトレードオフ分析では、提案するWTセレクタが、既存のエージェント中心型手法（$\text{A*-nn1, A*-nn2}$）よりも高速でありながら、ヒューリスティックなGreedy-PPよりも高品質な解を提供することを確認しており、実行時間と解の質のバランスにおいて新たな効率的な領域を確立している。
本論文では、新たに定式化されたCooperative Transportation Task Allocation and Path Finding (CT-TAPF) 問題に対し、最適性が証明されたソルバーであるCT-TCBSを提案している。研究を通じて、逐次的な探索範囲の拡張戦略が性能向上に不可欠であることを示し、高度な経路計画解決手法が統合的な設定においては逆に性能を低下させる「タスク競合拡張のジレンマ」を特定した。最適解の計算コストを抑制するため、タスク中心のグローバルな視点を持つ非最適ソルバーのファミリーであるCT-TCBS-BTおよびCT-TCBS-WTを開発しており、実験ではこれらが解の品質と実行時間のトレードオフにおいて、より効率的なフロンティアを確立することを実証した。今後の展望として、現実的な倉庫環境における連続的なMulti-Agent Pickup and Delivery (MAPD) への拡張や、ソーシャルオークションや交渉を用いた分散制御、さらには特殊な能力を持つ異種エージェントの導入によるシステムの柔軟性と探索効率の向上を目指している。