本研究は、単一エージェントのタスク実行を前提とした従来のMAPFやTAPFを拡張し、タスクごとに必要なエージェント数が異なるチーム編成、タスク割り当て、および衝突回避経路計画を統合したCT-TAPF問題を扱う。CT-TAPFは、タスクの選択、チーム形成、および複数エージェントによる協調移動を同時に解決する必要があり、TAPFの一般化としてNP-hardな問題となる。既存のCBS-TAなどの手法は、1対1の割り当てを前提としており、本研究が扱うような「能動的な協調」を伴うチーム形成における組合せ爆発に対応できていない。本論文では、この複雑な問題に対し、最適性とスケーラビリティの両面からアプローチしている。
第一に、チーム形成における組合せ爆発を抑制するため、タスクをスロットごとに段階的に割り当てる「Incremental Expansion」戦略を備えた最適ソルバーCT-TCBSを提案した。第二に、大規模問題に対応するため、タスクの困難度に基づきBest Task (BT) または Worst Task (WT) を選択する、グローバルな視点を持つ複数の劣最適解ソルバーを開発した。第三に、高度な衝突解決手法がCT-TAPF設定下では逆に探索効率を低下させる「task-conflict expansion dilemma」の存在を理論的・実験的に明らかにした。最後に、提案するWTソルバーが、既存のエージェント中心的な手法と比較して、解の質と実行時間のトレードオフにおいて新たな効率的フロンティアを確立することを示した。
最適解を得るためのCT-TCBSは、2レベルの階層的探索アルゴリズムである。上位レベルでは、制約木に対して$f(n) = g(n) + h(n)$を用いるA*探索を行い、タスク割り当ての組合せを探索する。ここで$g(n)$は割り当て済みタスクの最適コスト、$h(n)$は未割り当てタスクの完了に必要な最小追加コストの許容的な推定値である。下位レベルでは、Unified A*を用いて、個々のエージェントおよびコンボイ（Convoy）の時空間制約を満たす経路を計算する。コンボイは基準位置 $p$ と相対座標の集合 $\mathcal{R}$ により、時刻 $t$ における占有頂点集合 $F(p, \mathcal{R}) = \{p + r \mid r \in \mathcal{R}\}$ として定義される。衝突回避にはMC-CBSフレームワークを採用し、$\text{ASYM}$、$\text{SYM}$、$\text{MAX-}d$ の戦略を用いる。また、Incremental Expansionにより、タスクをスロットごとに展開することで分岐係数を削減している。
グリッドマップ上の3つのシナリオ（Random, Spatially-biased, Collision-rich）を用いた実験により、提案手法を評価した。Incremental戦略は、Incremental-LRやCombinatorial手法よりも高い成功率を示し、タスク展開ノードと衝突展開ノードの比率の中央値は $10.0$ (IQR $4.0$) であった。衝突解決器の比較では、$\text{MAX-}d$ 変種が他の手法より多くのノードを展開する「Task-Conflict Dilemma」が確認された。劣最適解ソルバーの評価では、Worst-Task (WT) セレクタがBest-Task (BT) セレクタよりも最適解との乖離（Optimality gap）が有意に小さく、ランダム配置で高い成功率を示した。372の共通インスタンスを用いたトレードオフ分析の結果、WTソルバーは既存のエージェント中心型手法（$-nn1, -nn2$）より高速であり、Greedy-PPより高品質な解を提供することが示された。
本研究は、CT-TAPFにおけるタスク割り当てと経路計画の密な結合が、探索空間の爆発と衝突解決の複雑さを同時に引き起こすことを示した。特に、経路計画における高度な衝突解決アルゴリズムが、タスク割り当ての探索プロセスにおいて逆効果となる「task-conflict expansion dilemma」の発見は、統合的なマルチエージェント計画における重要な知見である。また、タスク中心のグローバルな視点（WTセレクタ）が、エージェント中心的な局所的視点よりも効率的な探索を実現できることが示された。今後の課題として、現実的な倉庫環境への適用に向けた連続的な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 設定下では逆効果となる「task-conflict expansion dilemma」が存在することが明らかになった。さらに、提案する劣最適解ソルバーは、既存のエージェント中心的なベースラインと比較して、解の質と実行時間のトレードオフにおいて新たな効率的フロンティアを確立している。
本研究では、複数のエージェントが協力して大型または不規則な形状の物品を運搬する、Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) 問題を新たに定式化している。従来のMAPFやTAPFは単一エージェントによるタスク実行を前提としていたが、CT-TAPFはタスクごとに必要なエージェント数が異なるチーム編成を必要とし、TAPFの一般化として NP-hard な問題となる。提案手法として、最適解を導出する Cooperative Task Conflict-Based Search (CT-TCBS) と、スケーラビリティを確保するために設計された複数の劣最適（suboptimal）なバリアントを導入している。実験では、計算資源の制約下における成功率、タスク割り当てと衝突回避の探索空間のトレードオフ、および解の品質と実行時間のバランスについて包括的な評価を行っている。
本セクションでは、マルチエージェント経路探索（MAPF）から、タスク割り当てと経路探索を統合したTAPF、さらには協調的な輸送を扱うCT-TAPFへと至る研究の系譜が整理されている。MAPFはNP困難な問題であり、最適解を求める手法として$A^*$ベースの結合探索やConflict-Based Search (CBS) などの階層的探索が提案されている一方、大規模問題に対してはPPやLNSといった劣最適解を求めるスケーラブルなアルゴリズムが用いられる。TAPFは、タスク割り当てと経路計画の密な結合が課題であり、CBSを拡張したCBS-TAやTCBSが既存手法として挙げられるが、これらは負の干渉を避ける「調整」に留まり、複数のエージェントが単一の大きな物体を運ぶような「能動的な協調」をモデル化できていない。協調型MAPF（Co-MAPF）や、エージェントが複数の頂点を占有するLarge Agents MAPF (LA-MAPF) などの先行研究はあるものの、それらは協調動作を瞬間的なイベントとして簡略化しすぎており、個別のタスクと複数エージェントによるタスクが混在する現実的なシナリオを扱えていない。本研究が提案するCT-TAPFは、タスク選択、チーム形成、および協調移動を統合した問題であり、既存のCBS-TAのような1対1の割り当てを前提とする手法では、チーム形成に伴う組合せ爆発により計算が困難となる。これに対し、著者らはTCBSの枠組みを基に、チーム形成を段階的に管理する増分的な展開戦略を用いた最適ソルバーCT-TCBSを提案している。
本研究では、無向グラフ $G = (V, E)$ 上におけるマルチエージェントのタスク割り当ておよび経路計画問題を定義している。エージェント集合 $\mathcal{A}$ とタスク集合 $\mathcal{T}$ が存在し、各タスク $t \in \mathcal{T}$ は開始構成 $S_t$ と目標構成 $G_t$（共に $V$ の連結部分グラフ）で定義され、エージェントは各タスクの各スロットに割り当てられる。タスク実行は、エージェントが各スロットへ移動する「集合フェーズ（assembly phase）」と、エージェントが一体の「コンボイ（Convoy）」として振る舞う「隊列フェーズ（convoy phase）」の2段階で構成され、コンボイは基準位置 $p$ と相対座標の集合 $\mathcal{R}$ によって、時刻 $t$ における占有頂点集合 $F(p, \mathcal{R}) = \{p + r \mid r \in \mathcal{R}\}$ として定義される。最適解は、全エージェントの総運用時間である $SoC$ を最小化することであり、経路 $P_i = (v_{i,0}, v_{i,1}, \dots, v_{i,T_i})$ は隣接頂点への移動または待機を許容する。衝突回避条件として、2つのエンティティ $a, b$ のフットプリントが重なる $F_a(t) \cap F_b(t) \neq \emptyset$ となる「一般化された頂点衝突」を禁止しており、これは基準位置が異なっていてもフットプリントが重なれば衝突とみなす幾何学的な定義となっている。
CT-TCBSは、協調輸送タスク割り当ておよび経路計画（CT-TAPF）問題を解くための、最適かつ2レベルの探索アルゴリズムである。上位レベルでは、制約木に対するA*探索を行い、タスク割り当ての組合せ空間を探索する。各ノードの評価には $f(n) = g(n) + h(n)$ を用い、$g(n)$ は割り当て済みタスクの最適コスト、$h(n)$ は未割り当てタスクの完了に必要な最小追加コストの許容的な推定値である。下位レベルでは、Unified A*を用いて、個々のエージェントおよび複数エージェントによるコンボイ（Convoy）の時空間制約を満たす最適経路を計算する。衝突解決においては、MC-CBSフレームワークを採用しており、$\text{ASYM}$、$\text{SYM}$、および$\text{MAX-}d$ の3つの戦略を用いて、コンボイ間の衝突を効率的に解消する。タスク割り当ての爆発的な分岐を防ぐため、本手法は「Incremental Expansion」を導入しており、タスクを一度に割り当てるのではなく、スロットごとに段階的に割り当てることで分岐係数を大幅に削減している。この際、未完了のタスクについては、エージェントが割り当てスロットに到達するまでのコストのみを $g(n)$ に算入する。
本実験では、グリッドマップ上で生成された3つのシナリオ（Random, Spatially-biased, Collision-rich）を用い、提案手法であるCT-TAPF（Cooperative Transportation Task Allocation and Path Finding）アルゴリズムの性能を評価している。最適解を求める展開戦略の比較では、Incremental戦略がIncremental-LRやCombinatorialよりも高い成功率を示し、これはタスク割り当てに伴う探索空間の枝刈りが効率的であるためである（タスク展開ノードと衝突展開ノードの比率の中央値は $10.0$、IQRは $4.0$）。衝突解決器（Conflict Resolver）の比較では、MAX-d変種が他の手法よりも多くのノードを展開する「Task-Conflict Dilemma」が確認された。また、非最適解を求めるタスク選択器の比較では、Worst-Task (WT) セレクタがBest-Task (BT) セレクタよりも最適解との乖離（Optimality gap）が有意に小さく、特にランダムな配置において高い成功率を示すことが明らかになった。最終的なトレードオフ分析（372の共通インスタンスを使用）により、提案するWTソルバーは、既存のエージェント中心型手法（$-nn1, -nn2$）よりも高速であり、かつGreedy-PPよりも高品質な解を提供することで、実行時間と解の品質の新たな効率的フロンティアを形成していることが示された。
本論文では、新たに定式化されたCooperative Transportation Task Allocation and Path Finding (CT-TAPF) 問題に対し、理論的な最適性を保証するソルバーである CT-TCBS を提案した。実験を通じて、インクリメンタルな拡張戦略が性能向上に不可欠であること、および高度な経路探索解決策が統合的な設定下では逆に性能を低下させる「タスク競合拡張のジレンマ (task-conflict expansion dilemma)」が存在することを明らかにした。また、最適解の計算コストを抑制するため、タスク中心のグローバルな視点を持つサブオプティマルなソルバー群 (CT-TCBS-BT/WT) を開発し、解の質と実行時間のトレードオフにおいて新たな効率的フロンティアを確立した。今後の展望として、現実的な倉庫環境における連続的な MAPD への拡張、ソーシャルオークションや交渉を用いた分散制御の探索、および特殊な能力を持つ異種エージェントの導入によるシステム柔軟性と探索効率の向上が挙げられている。