2025-11-12T02:22:29.481811

PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network

Qiu, Ouano, Palafox et al.

While game-theoretic planning frameworks are effective at modeling multi-agent interactions, they require solving large optimization problems where the number of variables increases with the number of agents, resulting in long computation times that limit their use in large-scale, real-time systems. To address this issue, we propose 1) PSN Game: a learning-based, game-theoretic prediction and planning framework that reduces runtime by learning a Player Selection Network (PSN); and 2) a Goal Inference Network (GIN) that makes it possible to use the PSN in incomplete information games where agents' intentions are unknown. A PSN outputs a player selection mask that distinguishes influential players from less relevant ones, enabling the ego player to solve a smaller, masked game involving only selected players. By reducing the number of players in the game, and therefore reducing the number of variables in the corresponding optimization problem, PSN directly lowers computation time. The PSN Game framework is more flexible than existing player selection methods as it 1) relies solely on observations of players' past trajectories, without requiring full state, action, or other game-specific information; and 2) requires no online parameter tuning. Experiments in both simulated scenarios and human trajectory datasets demonstrate that PSNs outperform baseline selection methods in 1) prediction accuracy; and 2) planning safety. PSNs also generalize effectively to real-world scenarios in which agents' objectives are unknown without fine-tuning. By selecting only the most relevant players for decision-making, PSN Game offers a general mechanism for reducing planning complexity that can be seamlessly integrated into existing multi-agent planning frameworks.

academic

PSN Game: プレイヤー選択ネットワークを用いたゲーム理論的予測と計画

基本情報

論文ID: 2505.00213
タイトル: PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network
著者: Tianyu Qiu, Eric Ouano, Fernando Palafox, Christian Ellis, David Fridovich-Keil (テキサス大学オースティン校)
分類: cs.RO (ロボティクス), math.OC (最適化と制御)
発表時期: 2025年 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2505.00213

要約

ゲーム理論計画フレームワークは多エージェント相互作用のモデリングにおいて有効であるが、大規模な最適化問題を解く必要があり、変数数がエージェント数の増加に伴って増加するため、計算時間が過度に長くなり、大規模リアルタイムシステムへの応用が制限されている。この問題を解決するため、本論文は以下を提案する：1) PSN Game - プレイヤー選択ネットワーク(PSN)を学習することにより実行時間を削減する学習ベースのゲーム理論的予測・計画フレームワーク；2) 目標推論ネットワーク(GIN)により、PSNがエージェント意図が未知の不完全情報ゲームで使用可能にする。PSNはプレイヤー選択マスクを出力し、影響力のあるプレイヤーとあまり関連性のないプレイヤーを区別し、自己エージェントが選択されたプレイヤーのみを含む小規模なマスクゲームを解くことを可能にする。ゲーム内のプレイヤー数を削減することにより、対応する最適化問題の変数数が減少し、PSNは直接的に計算時間を削減する。

研究背景と動機

問題定義

ゲーム理論計画フレームワークが多エージェントシステムで直面する核心的な問題は、計算複雑性がエージェント数に対して立方的に増加することである。図2に示すように、既存のソルバーを使用する場合、計算時間はO(N³)で増加する。ここでNはプレイヤー数である。これにより、ゲーム理論的手法は大規模リアルタイムシステムにおいて実用的でなくなる。

研究の重要性

リアルタイム性の要求：自動運転、ロボット航法などの応用では頻繁な再計画が必要であり、計算効率が重要である
スケーラビリティの課題：実際のシナリオではエージェント数が多い傾向にある（例：密集交通環境）
人間行動からの着想：研究により、人間ドライバーは密集交通では本能的に近くの脅威車両を優先し、すべての車両を監視しないことが示されている

既存手法の限界

既存のプレイヤー選択手法には以下の問題がある：

情報依存性が強い：制御入力、コスト関数などのゲーム固有情報が必要
パラメータ調整が複雑：環境固有のパラメータ調整が必要
選択戦略が固定化：距離や勾配などの単純なヒューリスティックに基づくランキング手法は適応性に欠ける

核心的貢献

教師なしプレイヤー選択ネットワーク(PSN)の提案：微分可能な動的ゲームソルバーで訓練され、選択マスクを通じた逆伝播をサポート
監督付き目標推論ネットワーク(GIN)の構築：履歴軌跡からエージェント目標を推論し、意図が未知のシナリオでPSNを適用可能にする
減少時間領域フレームワークの開発：PSNを利用して縮小規模ゲームを解くことにより効率的に均衡戦略を特定
実験検証：多エージェントシミュレーションと実際の人間軌跡データセット上での検証により、PSN Gameがゲーム規模を50%-75%削減し、顕著な高速化を実現することを確認

方法の詳細

タスク定義

N個のエージェントの有限時間領域離散時間オープンループナッシュゲームを考える。各エージェントiは状態 $x_k^i \in \mathbb{R}^n$ と制御入力 $u_k^i \in \mathbb{R}^m$ を有する。エージェント状態遷移は動力学方程式に従う： $x_{k+1}^i = f^i(x_k^i, u_k^i)$

各エージェントの目標は累積コストを最小化することである： $J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)$

モデルアーキテクチャ

1. プレイヤー選択ネットワーク(PSN)

PSNは性能とスパース性のバランスを取るマスク $M^i$ を推論するニューラルネットワークである。2つのバリアントを提供する：

PSN-Full：入力は全エージェントの完全な履歴状態 $x_{0:K}$
PSN-Partial：入力は部分観測 $\{h(x_k)\}_{k=0}^K$ （例：位置情報のみ）

ネットワーク構造：

GRUエンコーダ（隠れ次元64）を使用して各エージェントのK段階シーケンスを処理
MLP層：256→128→32（ReLU活性化、ドロップアウト=0.3）
Sigmoid出力層が連続マスク $m_j^i \in [0,1]$ を生成

2. マスクナッシュゲーム

プレイヤー選択マスク $M^i = (m_j^i) \in \{0,1\}^{N-1}$ を定義する。ここで： $m_j^i = \begin{cases} 1, & \text{エージェントjがゲームに含まれる} \\ 0, & \text{エージェントjが除外される} \end{cases}$

マスクゲーム $\Gamma^i(\tilde{x}_0, \tilde{f}; \theta, M^i)$ はエージェントiに最も関連するエージェントパラメータと状態のみを保持する。

3. 目標推論ネットワーク(GIN)

GINはデータ駆動型ネットワークであり、部分軌跡観測からエージェント目標 $p_g^i$ を推論する：

入力：履歴軌跡 $\{h(x_k)\}_{k=0}^K$
出力：2D目標位置 $p_g^i$
損失関数：平均二乗誤差 $L_{Goal} = \frac{1}{|D| \cdot N}\sum_{d \in D}\sum_{i \in [N]} \|p_{g,ref}^i - G_\phi(x_{0:K})\|$