技術要約: DISPATCH - 協調的な異種マルチエージェントのための分散型・情報に基づいた空間計画およびタスク割り当て

問題定義

本論文は、マルチロボット配送、捜索救助、環境モニタリングなどの領域における、異種マルチエージェントシステムにおける空間的タスク割り当ての課題に取り組んでいる。核心となる問題は、$N$ 個の異種エージェントを、部分観測性の下で $m$ 個の空間的に分散したタスクに調整することである。

主な制約と特性は以下の通りである：

• 異種性（Heterogeneity）: エージェントは異なるサービス能力（スキルレベル）を持ち、タスクは多様なワークロード、重要度重み、および緊急性を持つ。適合性は選好ベクトルを通じてモデル化される。
• 空間コスト: エージェントは障害物のある複雑な2D環境をナビゲートする必要があり、移動コストと時間遅延が発生する。
• 公平性と効率性のトレードオフ: グリーディ（貪欲）または純粋に効率性を重視する方策（例：総移動距離の最小化）は、不平等なサービスをもたらすことが多い。つまり、一部のタスクには迅速かつ高品質なサービスが行われる一方で、他のタスクは長い遅延や不適切なマッチングに直面することになる。
• 部分観測性: エージェントはグローバルな状態情報にアクセスできず、局所的なセンシング半径内のエンティティのみを感知できる。

既存のアプローチは、中央集権的な調整と完全なグローバル情報を想定しているか、あるいは厳密な均衡ベースの公平性の参照点なしに報酬整形（reward shaping）に依存していることが多い。本論文は、アイゼンバーグ–ゲール（Eisenberg–Gale, EG）均衡理論（パレート効率性と羨望フリーを保証するもの）と、分散型かつ部分観測なマルチエージェント学習との間の溝を埋めることを目的としている。

手法

著者らは、公平性と効率性を統合する2つの補完的なアルゴリズムを提案している。

1. EG-MARL (集中学習・分散実行)

このフレームワークは、CTDE (Centralized Training with Decentralized Execution: 集中学習・分散実行) アーキテクチャを利用する。

• 学習フェーズ: 集中型クリティック（Critic）はグローバルな状態にアクセスし、空間的に修正されたアイゼンバーグ–ゲール（EG）凸計画問題を解く。このプログラムは、ユーティリティの加重対数和を最大化する。ここで、ユーティリティはエージェントとタスクの選好および距離による割引因子（$uji = (\alpha d_{ij}) \cdot \text{preference}_{ji}$）の関数として定義される。このプログラムの解は、「教師」または監督信号として機能する。
• 実行フェフェーズ: エージェントは局所的な観測のみを使用して独立して動作する。エージェントは、局所的なエージェント・エンティティ・グラフ（隣接エージェント、タスク、および障害物を表す）を処理するためにグラフニューラルネットワーク (GNN) を利用し、分散型方策を学習する。
• 報酬整形 (Reward Shaping): 学習プロセスは、探索ボーナス、ワークロードの進捗、完了ボーナス、およびEG割り当てターゲットから導出された特定の公平性整形項を含む複合的な報酬によって導かれる。

2. 確率的オンライン割り当て (Stochastic Online Assignment)

これは、中央集権的な通信を伴う設定（強力なオンライン・ベースラインとして機能する）のために設計された、協調的な探索および割り当てメカニズムである。

• メカニズム: エージェントは、グリッドベースのサンプリング戦略を用いて環境を協調的に探索する。新たに発見されたタスクの数 $k$ が閾値に達すると、アルゴリズムは部分集合ベースの割り当てを実行する。
• プロセス: 現在自由なエージェントの部分集合を列挙し、各部分集合に対して発見されたタスクに対するEG最適化問題を解き、均衡目的関数を最大化する部分集合を選択する。割り当てられたエージェントは即座にターゲットをサービスし、他のエージェントは探索を継続する。
• 目的: 組合せ爆発（$O\binom{N}{k}$）により計算コストは高いが、分散型の方策が、オンラインの集中調整されたEGソリューションにどの程度近づけるかというベンチマークを提供する。

主な貢献

1. 空間認識型アイゼンバーグ–ゲール・フレームワーク: 著者らは、ユーティリティの定式化に空間的な移動コストを組み込むことで、古典的なEGフレームワークを拡張し、均衡理論と実体化されたマルチエージェント・タスク割り当てを効果的に橋渡しした。
2. EG-MARL アルゴリズム: グラフベースの方策と空間認識型のEG割り当てを統合した、新しいCTDEフレームワーク。これにより、エージェントはEG均衡に導かれながら、部分観測下で公平性と移動効率を共同に最適化する分散型方策を学習できる。
3. 確率的オンライン割り当て: タスクが発見されるたびに、ガイドされた探索と部分集合ベースの公平な割り当てを行う協調メカニズムを提供し、オンラインの公平性・効率性のトレードオフにおける中央集権的なベースラインを確立する。
4. 実証的検証: 本アプローチは、様々なチームサイズ（3〜15エージェント）におけるMulti-Agent Particle Environment (MPE) シミュレーション、および異種ロボット（Summit-XL, TurtleBot3, Pioneerなど）を用いたWebotsベースの倉庫実証実験によって検証されている。

実験結果

評価では、EG-MARLおよびオンライン手法を、中央集権的なベースライン（Centralized EG、ハンガリアン法（功利主義的最適）、およびMin-Max Distance（公平性重視））と比較している。

• 後悔 (Regret): EG-MARLは、特に小規模なチームにおいて低い後悔（分散型と中央集約型EGの間のギャップ）を達成している。チームサイズが増加するにつれて後悔は増大するが、競争力のある水準を維持している。
• 公平性: 両方のEGベースの手法（EG-MARLおよびオンライン手法）は、公平性指標（変動係数およびJainの公平性指数）において、ハンガリアン法およびMin-Maxベースラインを一貫して上回っている。EGベースの手法は、よりバランスの取れたタスク結果を実現し、公平性・効率性のトレードオフ曲線において「左上」（高公平性、低完了時間）の領域に集まっている。
• 効率性: EG-MARLは、ほとんどの構成（N=7, 10）において最も速い完了時間を達成しており、多くの場合、中央集権的なEGソリューションよりも高速であるが、時として総移動距離がわずかに増加する場合がある。
• アブレーション研究: EGによる公平性整形報酬または探索報酬を取り除くと、公平性が低下し完了時間が増加した。これは、均衡に導かれた報酬構造の必要性を裏付けている。
• Webotsによる検証: 異種ロボットを用いた現実的な倉庫シナリオにおいて、中央集権的なEG割り当てが最も強力な全体的バランスを示し、ハンガリアン法やMin-Max法と比較して、競争力のある完了時間を維持しつつ、最高の公平性スコアを達成した。

意義と主張

本論文は、空間認識型のEG定式化が、異種能力を持つエージェントの分散型協調を効果的に導くことができると主張している。

• 理論的架け橋: 本研究は、EG均衡凸計画問題と、分散型かつ部分観測なマルチエージェント学習との間の接続を確立し、均衡概念が効果的な監督信号として機能できることを示した。
• 実践的なバランス: 結果は、分散型エージェントがグローバルな状態情報に依存することなく、パレート効率的かつ公平性を考慮した結果を近似できることを示唆している。
• 限界: 著者らは、確率的オンライン割り当ては、組合せ列挙のため大規模なチームでは計算負荷が高いこと、および、これは主にベースラインとして意図されたものであり、スケーラブルなデプロイメント・ソリューションではないことを謙虚に述べている。また、EG-MARLフレームワークは、理論的な近似アルゴリズムではなく、経験的に導かれた学習アプローチであることを認めている。

結論として、純粋な効率性はしばしば不平等を生むが、分散型学習に均衡ベースの公平性を統合することで、マルチエージェントシステムは動的で空間的な環境において、サービス品質と運用効率の堅牢なバランスを達成できる。