技術的概要：スケーラブルなマルチエージェント協調のための交互ターゲット・パス計画

問題定義

本論文は、**同時ターゲット割り当てと経路探索（TAPF）問題を取り扱います。各エージェントに固定されたターゲットが割り当てられる標準的なマルチエージェント経路探索（MAPF）とは異なり、TAPF では、各エージェントが持つ可能なターゲットの集合から、エージェントに固有のターゲット位置を同時に割り当て、かつ衝突のない経路を生成する計画立案が必要です。目的は、すべてのエージェントが割り当てられたターゲットに到達するまでの総移動時間として定義されるフロータイム（コストの和）**を最小化することです。

TAPF はエージェントとターゲットの組み合わせが柔軟である現実世界の物流を反映していますが、既存の解決策は**コンフリクトベース探索（CBS）**とその変種（例：CBM、CBS-TA、ITA-CBS）に大きく依存しています。これらの手法は、最適性または有界な準最適性を保証するために、ターゲット割り当てと経路探索を密に結合させています。しかし、この結合により計算複雑性が高まり、実用的な時間枠内で 250 未満のエージェントを持つインスタンスへのスケーラビリティが制限されています。

手法

著者らは、ターゲット割り当てを経路探索から分離する反復改善フレームワークを提案します。結合された問題を同時に解くのではなく、このフレームワークはそれらを交互のサブ問題として扱い、現代的で高速な準最適 MAPF ソルバー（具体的にはLaCAM）をサブルーチンとして活用します。

このフレームワークは、与えられた時間制約内で以下のサイクルを通じて動作します：

1. 初期割り当て: 最短経路距離に基づく貪欲戦略（ペアワイズ交換で改善されたもの）を用いて、初期ターゲット割り当てを生成します。
2. 経路探索: 高速な MAPF ソルバーが、現在の割り当てに対して衝突のない経路を計算します。
3. フィードバックとボトルネックの特定: 生成された経路を分析し、遅延や衝突を引き起こす「ボトルネック」エージェントを特定します。
4. ターゲット再割り当て: フィードバックに基づいて、一部のエージェントのターゲットを再配分します。
5. 反復: これまでの最良の解を追跡しながら、このプロセスを繰り返します。

主要コンポーネント

このフレームワークは、ループの各段階に対して 2 つの特定のメカニズムを導入します：

1. フィードバックメカニズム（ボトルネックの特定）:

• 遅延ベース選択（DBS）: エージェントを個別の遅延（$d_i = \text{実際の経路コスト} - \text{理想的な最短経路コスト}$）でランク付けします。遅延が最も大きい上位$m$個のエージェントをボトルネックとして選択します。
• スペクトルボトルネックサンプリング（SBS）: 重み付き性能乖離行列に対してスペクトル分解を用います。この行列は、空間的相関（エージェントの理想的な経路間の潜在的な衝突）と性能劣化（遅延）を組み合わせます。第一固有ベクトルは、混雑した領域で相関した遅延を経験するエージェントのグループを特定します。

2. 再割り当て戦略（割り当ての改善）:

• PIBT（バックトラッキングを伴う優先権継承）: 経路探索からの PIBT メカニズムをターゲット再割り当てに適応させます。ボトルネックエージェントが他者に保持されているターゲットを必要とする場合、実行可能な割り当てが見つかるか、またはプロセスがバックトラックするまで、一連の移動を再帰的にトリガーします。
• ローカルハンガリアン法: フィードバックメカニズムによって特定された小さなエージェント subgroup に対してハンガリアン法を適用します。候補ターゲットのプール（現在のターゲット＋未割り当てターゲット）への最短経路距離を用いてコスト行列を構築し、割り当て段階中のエージェント間衝突を無視して局所最適の再割り当てを求めます。

3. 複数ボトルネック評価:
探索の停滞を回避するため、フレームワークは各反復で複数の候補再割り当てを評価し（アルゴリズム 2）、単一の最良候補を決定論的に選択するのではなく、確率的に 1 つを選択して継続します。

4. 最終経路最適化:
改善ループが終了した後、見つけた最良の割り当てに対して、計算負荷の高いソルバー（LaCAM3）をオプションで適用し、最終経路を最適化して解の品質を向上させます。

主要な貢献

1. 分離されたフレームワーク: ターゲット割り当てを経路探索から分離する新規の反復アプローチにより、非常にスケーラブルな準最適 MAPF ソルバーの使用を可能にします。
2. フィードバック駆動型再割り当て: 経路探索のフィードバックに基づいて、割り当てのボトルネックを体系的に特定し対処するための DBS と SBS の提案。
3. スケーラブルな再割り当てアルゴリズム: 効率的なターゲット再配分のための PIBT の適応とローカルハンガリアン法の適用。
4. 実証的検証: 本フレームワークが数千のエージェントにスケーラブルでありながら、競争力のある解の品質を維持することを示す広範な評価。

実験結果

このフレームワークは、2 つのシナリオ（RANDOM（疎なターゲット）とHOTSPOT（密で重複するターゲット））における標準的な MAPF ベンチマーク（グリッドマップ）で評価されました。

• コンポーネントの性能: DBS とローカルハンガリアン法の組み合わせが、特に困難な HOTSPOT シナリオで最良の結果をもたらしました。200 エージェントのインスタンスにおいて、初期解に対して 10〜25% の改善を達成しました。
• 最先端技術との比較: 最先端の CBS ベース TAPF ソルバーであるITA-ECBSと比較して、提案されたフレームワーク（DBS-Hungarian）は、テストされたすべてのインスタンスで100% の成功率を達成しました。一方、ITA-ECBS は、HOTSPOT シナリオでは 20 超のエージェント、RANDOM シナリオでは約 100 エージェントを持つインスタンスの大部分を解くことに失敗しました。
• スケーラビリティ: このフレームワークは最大10,000 エージェントのインスタンスを正常に処理し、20 秒未満で初期解を見つけ、その後改善を続けました。
• 解の品質: 小規模で解けるインスタンスにおいて、CBS ベースの手法と比較すると提案手法はわずかに高いコスト（準最適）を生み出しますが、その差は小さいです。このトレードオフにより、それ otherwise 扱いが困難な問題を解くことが可能になります。
• 複数ボトルネック効果: 各反復で$k=3$のボトルネックエージェントを評価することが、探索の多様性と計算オーバーヘッドの間の最適なバランスを提供しました。

意義と主張

本論文は、この仕事が「現実世界のセットアップに適した実用的で大規模な TAPF に向けた確固たる一歩」を表すと主張しています。計算コストが高く密に結合された CBS アプローチから離れることで、著者らは、スケーラビリティを達成しつつ、解の品質を許容できない程度に犠牲にしないことを実証しました。

その意義は、CBS 衝突木の指数関数的な成長によって以前は制限されていた、現実的な時間制約内で数百から数千のエージェントを含む TAPF インスタンスを解ける能力にあります。このフレームワークのモジュール性により、ターゲット割り当てまたは経路探索アルゴリズムの将来の進歩を、他のコンポーネントを変更することなく統合することが可能です。著者らは、ターゲット改善と最終経路最適化の相互作用が重要であると強調しています。なぜなら、複雑で高密度な環境では、経路計画のみでは初期ターゲット割り当ての欠陥を補うことができないからです。