技術要約: GraphChase: 都市ネットワークセキュリティゲームのためのプラットフォームおよびベンチマーク

問題定義

都市ネットワークセキュリティゲーム（UNSG）は、法執行機関（追跡者）が、都市の道路ネットワークを通じて脱出を図る犯罪者（逃走者）を阻止するために、限られたリソースを戦略的に配分するシナリオをモデル化したものである。2人プレイのゼロサムゲームについては大きな進展が見られるものの、UNSGを解くことは、協力、競争、および不完全情報を含むマルチプレイヤーゲームとしての性質上、特有の課題を提示している。

現在の分野は、主に以下の3つの制限に直面している：

1. 標準化の欠如: 統一された実験プラットフォームが存在しないため、実装の不一致、データ構造の不整合、およびアルゴリズムのクロス評価の困難さが生じている。
2. リアリズムとスケーラビリティのトレードオフ: 最適化手法は、重み付き移動時間をモデル化するために混合整数線形計画法（MILP）に依存することが多いが、大規模なネットワークへのスケーリングに失敗する。逆に、最先端（SOTA）の学習ベースの手法は、トレーニングを容易にするために環境を非重みのグラフに簡略化する傾向があり、現実世界の道路セグメントの異質性（例：長さや制限速度の差異）を無視している。
3. Sim-to-Realギャップ: 既存のアプローチは、重み付きグラフへの展開において堅牢性とスケーラビリティに苦慮しており、簡略化されたトレーニング環境と現実的な条件との間の汎化ギャップを浮き彫りにしている。

手法: GraphChaseプラットフォーム

これらの課題に対処するため、著者らはUNSG研究を標準化し、現実的な環境でのシミュレーションをサポートするために設計されたオープンソースプラットフォームであるGraphChaseを導入する。本プラットフォームは、環境、エージェント、およびソルバーを分離したモジュール式アーキテクチャを採用している。

コアコンポーネント

1. ゲームモジュール（環境）:

   • グラフ表現: 道路ネットワークをグラフ $G=(V, E, \omega)$ としてモデル化し、有向および無向エッジの両方をサポートする。これは、$\omega(u, v)$ が連続的な移動時間を表す重み付きエッジを扱う。
   • 状態表現: エージェントは頂点またはエッジ上に位置し、タプル $(u, v, \delta)$ として表現される（$\delta$ は頂点 $u$ からの距離）。これにより、離散時間ステップの枠組み内での連続的な移動が可能になる。
   • ダイナミクス: ハイブリッド意思決定メカニズムを使用する。エージェントはタイムステップの開始時、および頂点に到達した瞬間に意思決定を行う。ゲームは、捕獲（距離 $\le \epsilon$）、脱出（出口ノードへの到達）、またはタイムアウト（$T$）によって終了する。
   • 情報構造: 追跡者と逃走者の両方に対する完全観測から部分観測に至る4つの情報シナリオをサポートし、追跡者間の独立的または協調的な意思決定を可能にする。

2. エージェントモジュール:

   • 方策表現（ニューラルまたはヒューリスティック）および軌跡収集のための統一されたインターフェースを提供する。
   • 環境との相互作用、前処理、およびバッチ構築をカプセル化するRunnerを導入し、効率的なデータ収集のためにベクトル化されたロールアウトをサポートする。
   • PSRO（Policy-Space Response Oracles）のようなフレームワークのための、方策のクローニングや永続性を含む反復的なゲーム理論的学習をサポートする。

3. ソルバーモジュール:

   • 最善応答（Best-Response）トレーニングのためのプラグアンドプレイの最適化器（例：PPO, MAPPO）を実装する。
   • 最善応答オーラクル（RLまたはヒューリスティック）とメタソルバー（例：射影レプリケータ力学）に分解される、ゲーム理論的学習フレームワーク、特にPSROをサポートする。
   • コアとなるゲームロジックを変更することなく、カスタムソルバーの実装を可能にする。

ベンチマークプロトコル

GraphChaseは、以下のものを含む標準化されたベンチマークプロトコルを確立している：

• アルゴリズム: CFR-MIX、NSG-NFSP、NSGZero、Pretrained PSRO、Grasperを含むSOTAアルゴリズムの統合。
• 実行モード: パスベースの実行（逃走者がゲーム開始前にターゲットとなる出口と経路を選択する）と、ステップ単位の実行（エージェントが各意思決定ポイントでアクションをサンプリングする）の両方をサポート。
• 評価指標:
  • ワーストケース・ユーティリティ: すべての逃走者パスを列挙して、追跡者の最小ユーティリティを見出す。
  • 疑似ワーストケース・ユーティリティ: 大規模なグラフを扱うために、各出口に対してパスをサンプリングすることでワーストケースを近似する。
  • 可視化: 軌跡と意思決定プロセスを分析するためのツール。

主な貢献

1. 統一プラットフォーム: 環境をアルゴリズムから分離したGraphChaseの開発により、不適合の問題を解決し、同一のタスク上での戦略の公平なクロス評価を可能にした。
2. ベンチマークの確立: 複数のディープラーニングベースのアルゴリズムを統一されたフレームワーク内に統合し、多様なゲーム構成における信頼できるベースラインを提供し、性能指標を確立した。
3. Sim-to-Realギャップの解明: 実験を通じて、現在の手法がスケーラビリティと堅牢性に重大な限界に直面していること、特に非重みのグラフと比較して重みの付いた道路ネットワークに展開された際に性能低下が生じることを実証した。

実験結果

著者らは、プラットフォームの検証およびアルゴリズムの評価を行うため、48コアCPUと8基のNVIDIA A30 GPUを備えたサーバー上で実験を行った。

• 再現性と正確性: GraphChaseは、5x5および7x7のグリッドグラフにおいて、元の文献（Pretrained PSRO, Grasper, NSGZero, NSG-NFSP, CFR-MIX）の結果を正常に再現した。本プラットフォームは、元のコードベース（Grasperなど）の非効率性を解消し、一貫したロジックを維持しつつ、より優れたトレーニング性能を実現した。
• 計算効率: ベクトル化された環境設計により、GraphChaseは全体的なサンプリングのスループットを1.38倍向上させ、逃走者の最善応答計算を1.96倍、追跡者の計算を1.72倍加速させた。
• 実世界のトポロジー・ベンチマーク: 6つの実世界のマップ（シンガポール、マンハッタン、ムンバイなど）を用いたテストにより、性能のばらつきが明らかになった。アルゴリズムは一部のトポロジーでは高いユーティリティを達成したが、ノード数・エッジ数が多い、あるいはタイムホライゾンが長いマンハッタンやタイムズスクエアのような複雑な環境では苦戦した。
• 堅牢性の評価:
  • ホライゾン・シフト: $T=4$ でトレーニングされた方策は、$T=8$ でテストした際に大幅なユーティリティの低下を示し、タイムホライゾンの変化に対する限定的な堅牢性を示した。
  • エッジ重みの変動: 非重みグラフでトレーニングされた方策は、重み付きグラフでテストした際に大幅な性能劣化を経験し、エッジコストの異質性に対する堅牢性の欠如を浮き彫りにした。
• スケーラビリティ: 既存のアルゴリズムは100x100のグリッドでのトレーニングに失敗し、30x30のグリッドですら、意思決定に必要なパス列挙の指数関数的な爆発により停滞した。これは、現在のソルバーにおけるスケーラビリティの障壁を強調している。
• ステップ単位の方策実行: ムンバイのマップ（非重みおよび重み付き）を用いた実験は、GraphChaseがステップ単位のPPO方策を訓練・評価できることを示した。ヒューリスティックな防御者はヒューリスティックな攻撃者に対して良好な成績を収めたが、PPO攻撃者には苦戦した。また、PPO防御者は重み付きグラフにおいて低い捕獲率を示し、現実的な重み付きトポロジー上での学習の難しさを裏付けた。

意義と主張

本論文は、GraphChaseがUNSGに特化した初のオープンソースプラットフォームであり、理論的なゲーム解決と現実的な都市セキュリティアプリケーションの間の溝を埋める、柔軟なマルチプレイヤーゲーム環境を提供すると主張している。

• 標準化: 統一されたインターフェースを提供することでUNSG研究の参入障壁を下げ、スケーラブルで現実的なセキュリティ課題に焦点を当てたコミュニティを育成する。
• 現実的なモデリング: 重み付きグラフとハイブリッドな意思決定をサポートすることで、従来の非重みモデルよりも、現実のシナリオ（例：交通パターン）の動的な性質をより良く捉える。
• マルチプレイヤーゲームのテストベッド: 本プラットフォームは、アンチ・ポーチング（密猟防止）や敵対的チームゲームなどのより広い領域にも適用可能な、複雑なマルチプレイヤー設定におけるナッシュ均衡（NE）およびチーム・マックスミン均衡（TME）を計算するためのテストベッドとして機能する。
• 限界の特定: 本研究は「Sim-to-Real」の汎化ギャップを明示的に定量化しており、現在のSOTAアルゴリズムがエッジコストの重みや大規模ネットワークに対して堅牢ではないことを示し、グローバルなアクション空間の探索から脱却した新しいアプローチの開発を促している。

著者らは、GraphChaseを脱出計画を助けるためのツールではなく、公共安全戦略を改善するための防御的計画および評価ツールとして位置づけている。