本研究は、複数のロボットが各タスクの開始地点から目標地点へ運搬を行う、容量制限付きマルチエージェント・ピックアップ＆デリバリー（Capacitated MAPD）問題を対象としている。従来のMAPD手法は、TAとMAPFを逐次的に解くことが多く、TAの段階で実際の経路コストではなく下限推定値を用いるため、最終的な経路コストが予測を大幅に上回る課題があった。本研究では、タスク割り当てと衝突回避経路計画を統合的に扱うことで、この乖離を解決することを目指している。具体的には、全タスクの輸送における総移動遅延（TTD）の最小化を目的関数として定義している。
本研究の主な貢献は、タスク割り当ての評価に優先度付き計画に基づく実際の配送コストを利用する、TAとMAPFの統合アプローチを提案したことである。具体的には、限界コスト割り当てヒューリスティック（MCA）および、相対的後悔（relative regret）に基づくRegret-based MCA（RMCA(r)）を導入した。さらに、Large Neighbourhood Search（LNS）の概念を用いたAnytime Improvement Strategyを導入し、制限時間内で解を継続的に改善できる仕組みを構築した。実験により、提案手法が既存の最良の準最適手法であるTPTSと比較して、効率的かつタイムリーな解を提供し、TTDおよびmakespanの両面で大幅な改善を示すことを証明した。
提案手法は、タスク割り当てを巡回セールスマン問題（TSP）として定式化し、経路計画にはConflict Based Search (CBS) や Space-Time A* を用いる。目的関数は、全タスクの輸送遅延の総和 $f = \sum_{i \in P} (a(g_i) - (r_i + t(s_i, g_i)))$ の最小化である。タスク割り当てアルゴリズムとして、現在の経路 $o_k$ に対しタスク $i$ を $q_1$ 番目と $q_2$ 番目の位置に挿入した際の増分コスト $t((o_k \oplus q_1 s_i) \oplus q_2 g_i) - t(o_k)$ を最小化するMCAを提案している。RMCAでは、最良のロボットと二番目に良いロボットの増分コストの比（相対的後悔）に基づきタスクを選択する。また、LNSに基づく改善戦略として、「Destroy random」「Destroy worst」「Destroy multiple」の3つの破壊戦略を用いて割り当て済みのタスクを再割り当てする。
$21 \times 35$ の倉庫マップを用いた数値シミュレーションにより、提案手法の有効性を検証している。One-shot実験では、容量 $Cap=1$ ではデカップル手法が優れるものの、$Cap=3$ 以上では相対的後悔に基づくRMCA(r)が最も優れた性能を示すことを確認した。Lifelong設定の実験では、$\text{RMCA}(r)$ は $\text{TPTS}$ を大幅に上回り、$\text{CENTRAL}$ と同等の $\text{makespan}$ を維持しつつ、より短いステップあたりの実行時間（$\text{T/TS}$）を実現した。統計的有意性の検証として、正規化された $\text{TTD}$ および $\text{makespan}$ に対して $t$-test を実施し、有意水準 $0.1$ で $\text{RMCA}(r)$ が $\text{CENTRAL}$ および $\text{TPTS}$ に対して有意な改善を示すことを確認した。
提案手法は、実際の衝突回避コストを利用することで、容量制限がある環境下でのタスク割り当ての精度を大幅に向上させた。特に、絶対的後悔に基づくRMCA(a)は、タスク割り当ての偏りにより走行遅延が大きく変動するため、相対的後悔を用いるRMCA(r)の方が頑健であることが示された。また、LNSを用いたAnytime改善戦略において、特に「destroy\_worst」戦略が「destroy\_multiple」よりも優れた性能を示すことが明らかになった。今後の展望として、エージェントのルートをさらに洗練させ、経路計画におけるアルゴリズムの完全性（completeness）を向上させるために、この anytime improvement 戦略を拡張することが挙げられている。
本研究は、複数のロボットが各タスクの開始地点から目標地点へ運搬を行う、容量制限付きマルチエージェント・ピックアップ＆デリバリー（Capacitated MAPD）問題を対象としている。従来のMAPD手法は、タスク割り当て（TA）と経路計画（MAPF）を逐次的に解くことが多く、TAの段階で実際の経路コストではなく下限推定値を用いるため、最終的な経路コストが予測を大幅に上回る課題があった。これに対し、提案手法はTAとMAPFを結合して解くアプローチであり、割り当てコストの評価に優先度付き計画（Prioritised Planning）を用いた実際の配送コストを利用する。具体的には、限界コスト割り当てヒューリスティック（marginal-cost assignment heuristic）と、Large Neighbourhood Search（LNS）に基づくメタヒューリスティックな改善戦略を導入している。数値シミュレーションの結果、提案手法は既存の最良の準最適手法であるTPTSと比較して、効率的かつタイムリーな解を提供し、大幅な改善を示すことが確認された。また、各エージェントが一度に複数のタスクを運搬できる容量制限付きの拡張モデルについても検討されている。
本研究では、容量制限のあるマルチエージェント・ピックアップ＆デリバリー（MAPD）問題において、タスク割り当て（TA）と衝突回避経路計画（MAPF）を統合的に扱う。提案手法のTA-Hybridは、まずタスク割り当てを巡回セールスマン問題（TSP）として定式化して既存のソルバーで解き、次いでConflict Based Search (CBS) に基づくアルゴリズムを用いて衝突のない経路を計画する。関連研究として、CBSを拡張して割り当て探索木を探索する最適解法CBS-TAが挙げられるが、スケーラビリティに課題がある。本論文の定式化では、経路計画を $\sigma_{ijk} \in \{0, 1\}$（ロボット $k$ が地点 $i$ から $j$ へ移動するか）、タスク割り当てを $\mu_{ik} \in \{0, 1\}$（ロボット $k$ がタスク $i$ を担当するか）として定義し、ロボットが地点 $j$ でタスクのピックアップまたはドロップオフを行う時刻を $a(j)$ と用いて、全タスクの輸送における総移動遅延（TTD）の最小化を目的とする。また、実行時の遅延や運動学的制約への対応についても言及されており、提案手法は $k$-robust な計画生成や事後処理によるスケジュール調整とも互換性を持つ。
本セクションでは、容量制限のあるマルチエージェント・ピックアップ＆デリバリー（CAPACITATED MAPD）問題を、タスク割り当てと経路計画を同時に行う最適化問題として定式化している。目的関数は、全タスクの輸送遅延の総和（TTD）を最小化することであり、式は $f = \sum_{i \in P} (a(g_i) - (r_i + t(s_i, g_i)))$ と定義される。制約条件として、各ロボット $k \in \mathcal{R}$ の積載量は容量 $C$ を超えないこと（$\sum_{i \in P} \sigma_{ijk} \cdot (a(i) + t(i, j)) \leq a(j)$ などの関連制約を含む）、各タスクは必ず1台のロボットによって輸送されること、およびロボット間の衝突回避（同一時刻に同一頂点に存在しない、または逆方向の同一エッジを通過しない）が課される。提案手法である Algorithm 1 は、未割り当てタスク集合 $P_u$ が空になるまで、潜在的な割り当てを保持するヒープ $H$ から最適なタスク・ロボットのペア $p_{aik}$ を選択し、割り当て集合 $A$ を更新しながら、Space-Time A* を用いて経路を再計算する。Algorithm 2 は、新しい割り当てによって生じる衝突を回避するため、ヒープ内の他の潜在的な割り当ての経路を更新するプロセスを記述している。
本セクションでは、容量制限のあるマルチエージェント・ピックアップ＆デリバリー（MAPD）問題に対し、タスク割り当てと経路計画を統合した手法が提案されている。タスク割り当てアルゴリズムであるMarginal-cost Based Task Selection (MCA) は、現在の割り当て $a_k$ に対し、タスク $i$ をロボット $k$ の経路 $o_k$ の $q_1$ 番目と $q_2$ 番目の位置に挿入した際の増分コスト $t((o_k \oplus q_1 s_i) \oplus q_2 g_i) - t(o_k)$ を最小化する $(k^*, i^*, q^*_1, q^*_2)$ を選択する。さらに、Regret-based MCA (RMCA) では、最良のロボットと二番目に良いロボットの増分コストの比（相対的後悔）または差（絶対的後悔）に基づき、タスクを選択する。また、Large Neighbourhood Search (LNS) の概念を用いたAnytime Improvement Strategyが導入されており、割り当て済みのタスクを「Destroy random」「Destroy worst」「Destroy multiple」の3つの戦略で一度削除し、RMCAを用いて再割り当てすることで、制限時間内で解の改善を試みる。実験では、$21 \times 35$ の倉庫マップを用い、静的障害物、通路、タスクの起点・終点、ロボットの初期位置が設定された環境で評価が行われている。
本セクションでは、容量制限付きマルチエージェント・ピックアップ＆デリバリー（CMAPD）問題に対し、タスク割り当てと経路計画を統合した手法の有効性を検証するOne-shot実験の結果が示されている。実験では、タスク割り当て後に経路計画を行うデカップル手法（MCA-pbs, RMCA(r)-pbs）と、両者を統合した手法（MCA, RMCA(r)）を比較しており、相対的TTD（実TTDから衝突を無視した場合のRMCA(r)のTTDを引いた値）を評価指標としている。結果として、容量 $Cap=1$ ではデカップル手法が優れるが、$Cap=3$ 以上ではエージェント数が増加するにつれて、相対的後悔（relative regret）に基づくRMCA(r)が最も優れた性能を示すことが確認された。一方で、絶対的後悔に基づくRMCA(a)は、タスク割り当ての偏りにより走行遅延が大きく変動するため、性能が著しく低下する。計算時間に関しては、デカップル手法が高速であるものの、提案する統合手法も他のアルゴリズムと比較して競争力のある実行時間を維持している。また、RMCA(r)に対し、3種類の破壊戦略（DR, DW, DM）を用いたAnytime改善手法を適用する実験も行われている。
Lifelong設定における実験では、提案手法である$\text{RMCA}(r)$を既存手法の$\text{CENTRAL}$および$\text{TPTS}$と比較し、タスクが継続的に到着する環境での性能を評価している。実験結果として、$\text{RMCA}(r)$は$\text{TTD}$（Total Travel Delay）を最適化しつつ、$\text{makespan}$においても$\text{CENTRAL}$に近い優れた値を示し、$\text{TPTS}$を大幅に上回る性能を確認した。また、$\text{RMCA}(r)$は$\text{CENTRAL}$よりもステップあたりの実行時間（$\text{T/TS}$）が短く、リアルタイム運用に適していることが示された。統計的有意性の検証として、正規化された$\text{TTD}$を $\text{TTD} \cdot N_a / (N_t \cdot f)$、正規化された$\text{makespan}$を $(makespan \cdot N_a \cdot f) / N_t$ と定義し、有意水準 $0.1$ で$t$-testを行った結果、$\text{RMCA}(r)$は$\text{CENTRAL}$および$\text{TPTS}$に対して正規化$\text{TTD}$および正規化$\text{makespan}$の両方で有意な改善を示した。さらに、破壊戦略の比較実験（25インスタンス、各500タスク）では、$\text{destroy\_random}$、$\text{destroy\_worst}$、$\text{destroy\_multiple}$の3手法が$\text{RMCA}(r)$の解質を向上させ、特に$\text{destroy\_worst}$が$\text{destroy\_multiple}$よりも優れた性能を示すことが明らかになった。
本研究で提案された MCA および RMCA は、各ロボットが複数の荷物を同時に運搬可能な容量制限付きマルチエージェント・ピックアップ＆デリバリー問題において、タスク割り当てと経路計画を同時に実行する。この手法は、マルチタスク・マルチロボット割り当てプロセスを導くために、実際の衝突回避コスト（real collision-free costs）を利用することで実現されている。また、新たに導入された anytime improvement 戦略によって、解の質が大幅に向上することが確認された。今後の展望として、エージェントのルートを洗練させ、経路計画におけるアルゴリズムの完全性（completeness）を向上させるために、この anytime improvement 戦略を拡張することが挙げられている。