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: Game-theoretic Prediction and Planning via a Player Selection Network

基本信息

  • 论文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 (University of Texas at Austin)
  • 分类: cs.RO (Robotics), math.OC (Optimization and Control)
  • 发表时间: 2025年 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2505.00213

摘要

游戏理论规划框架虽然在建模多智能体交互方面效果显著,但需要求解大型优化问题,其变量数量随智能体数量增加,导致计算时间过长,限制了在大规模实时系统中的应用。为解决这一问题,本文提出:1) PSN Game - 一个基于学习的游戏理论预测和规划框架,通过学习玩家选择网络(PSN)来减少运行时间;2) 目标推理网络(GIN),使PSN能够在智能体意图未知的不完全信息博弈中使用。PSN输出玩家选择掩码,区分有影响力的玩家和不太相关的玩家,使自我智能体能够求解仅涉及选定玩家的较小规模掩码博弈。通过减少博弈中的玩家数量,进而减少相应优化问题中的变量数量,PSN直接降低了计算时间。

研究背景与动机

问题定义

游戏理论规划框架在多智能体系统中面临的核心问题是计算复杂性随智能体数量呈立方增长。如图2所示,使用现有求解器时,计算时间按O(N³)增长,其中N为玩家数量。这使得游戏理论方法在大规模实时系统中变得不实用。

研究重要性

  1. 实时性需求:自动驾驶、机器人导航等应用需要频繁重规划,计算效率至关重要
  2. 规模化挑战:现实场景中智能体数量往往很大(如密集交通环境)
  3. 人类行为启发:研究表明人类驾驶员在密集交通中会本能地优先考虑附近威胁车辆,而非监控所有车辆

现有方法局限性

现有玩家选择方法存在以下问题:

  1. 信息依赖性强:需要控制输入、成本函数等游戏特定信息
  2. 参数调优复杂:需要环境特定的参数调整
  3. 选择策略固化:基于简单启发式(如距离、梯度)的排序方法缺乏适应性

核心贡献

  1. 提出无监督玩家选择网络(PSN):使用可微分动态博弈求解器训练,支持通过选择掩码进行反向传播
  2. 构建监督目标推理网络(GIN):从历史轨迹推断智能体目标,使PSN适用于意图未知场景
  3. 开发递减时域框架:利用PSN通过求解缩减规模博弈高效识别均衡策略
  4. 实验验证:在多智能体仿真和真实人类轨迹数据集上验证,PSN Game有效将博弈规模减少50%-75%,实现显著加速

方法详解

任务定义

考虑N个智能体的有限时域离散时间开环纳什博弈,每个智能体i具有状态xkiRnx_k^i \in \mathbb{R}^n和控制输入ukiRmu_k^i \in \mathbb{R}^m。智能体状态转移遵循动力学方程: xk+1i=fi(xki,uki)x_{k+1}^i = f^i(x_k^i, u_k^i)

每个智能体的目标是最小化累积成本: Ji(x,u;θi)=k=0Tcki(xk,uk;θi)J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)

模型架构

1. 玩家选择网络(PSN)

PSN是一个神经网络,任务是推断掩码MiM^i以平衡性能与稀疏性。提供两个变体:

  • PSN-Full:输入为所有智能体的完整历史状态x0:Kx_{0:K}
  • PSN-Partial:输入为部分观测{h(xk)}k=0K\{h(x_k)\}_{k=0}^K(如仅位置信息)

网络结构

  • 使用GRU编码器(隐藏维度64)处理每个智能体的K步序列
  • MLP层:256→128→32(ReLU激活,dropout=0.3)
  • Sigmoid输出层产生连续掩码mji[0,1]m_j^i \in [0,1]

2. 掩码纳什博弈

定义玩家选择掩码Mi=(mji){0,1}N1M^i = (m_j^i) \in \{0,1\}^{N-1},其中:

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})\|$ ### 损失函数设计 PSN训练采用复合损失函数: **预测任务**: $$L_{Pred} = L_{Binary} + \sigma_1 L_{Sparsity} + \sigma_2 L_{Similarity}$$ **规划任务**: $$L_{Plan} = L_{Binary} + \sigma_3 L_{Sparsity} + \sigma_4 L_{Cost}$$ 其中: - $L_{Binary} = \frac{1}{N}\sum_{j=1}^N m_j^i(1-m_j^i)$:促使掩码趋向二值化 - $L_{Sparsity} = \frac{\|M^i\|_1}{N}$:鼓励选择更少智能体 - $L_{Similarity}$:鼓励选择能恢复观测轨迹的智能体子集 - $L_{Cost}$:鼓励选择适当智能体以最小化博弈成本 ### 递减时域实现 算法在每个时间步$k$: 1. 通过GIN推断智能体目标 2. 使用PSN获取自适应掩码$M_k^i$ 3. 求解掩码博弈获得OLNE策略 4. 执行第一步控制输入并更新状态 ## 实验设置 ### 数据集 **仿真场景**: - 4智能体场景:5m×5m环境 - 10智能体场景:7m×7m环境 - 20智能体场景:7m×7m环境(测试可扩展性) **真实数据**: - CITR行人数据集:7.5m×25.5m环境,10个行人 **博弈设置**: - 状态空间:4维(位置+速度) - 动力学:双积分器模型 - 成本函数:包含目标追踪、速度惩罚、控制成本和碰撞避免项 ### 评价指标 **预测任务**: - ADE (Average Displacement Error):平均位移误差 - FDE (Final Displacement Error):最终位移误差 - Consistency:选择一致性 **规划任务**: - Navigation Cost:导航成本 - Collision Cost:碰撞成本 - Control Cost:控制成本 - Minimum Distance:最小距离 - Trajectory Smoothness:轨迹平滑度 - Trajectory Length:轨迹长度 ### 对比方法 1. **PSN变体**:PSN-Threshold, PSN-Rank 2. **距离方法**:Distance, kNNs 3. **梯度方法**:Gradient, Hessian, Cost Evolution 4. **约束方法**:BF (Barrier Function), CBF (Control Barrier Function) ## 实验结果 ### 主要结果 #### 预测性能(表2) 在4智能体场景中: - PSN-Full ADE: 0.1834m (最优) - PSN-Partial ADE: 0.1876m - 最佳基线(Cost Evolution) ADE: 0.1861m 在10智能体场景中: - PSN-Partial ADE: 0.2213m (最优) - PSN-Full ADE: 0.2314m - 最佳基线(kNNs) ADE: 0.2343m #### 规划性能(表3) PSN在安全性指标上表现突出: - **碰撞成本**:在4和10智能体场景中均达到最优 - **最小距离**:在两个场景中均位列前三 - 相比完整博弈,安全性能退化轻微 ### 不完全信息博弈适应性 在目标未知场景中(表4-5),PSN配合GIN: - 预测指标保持前两名 - 规划指标均位列前三 - 安全性指标仍然最优 ### 可扩展性验证 使用10智能体训练的PSN在20智能体场景中: - PSN-Full ADE: 0.3108m (最优) - PSN-Partial ADE: 0.3152m (第二) - 无需重新训练即可适应更大规模场景 ### 真实数据泛化 在CITR行人数据集上: - PSN-Partial ADE: 0.4931m (最优) - PSN-Full ADE: 0.4966m - 甚至优于求解完整博弈的性能 ## 相关工作 ### 游戏理论规划 现有方法主要关注小规模环境(≤5智能体),使用Newton风格求解器迭代求解。复杂度随玩家数量立方增长,成为大规模实时系统的根本障碍。 ### 玩家选择方法 **阈值方法**:基于预定义距离阈值选择智能体,需要大量参数调优。 **排序方法**:选择top-k最有影响力的智能体,但固定数量选择可能过于激进或保守。 **本文优势**: 1. 仅需历史轨迹观测,无需特权信息 2. 无需在线参数调优 3. 自适应选择智能体数量 ## 结论与讨论 ### 主要结论 1. PSN Game成功将博弈规模减少50%-75%,实现显著计算加速 2. 在预测准确性和规划安全性方面优于现有基线方法 3. 具有良好的泛化能力,可适应更大规模场景和真实数据 ### 局限性 1. **连续掩码近似**:为支持反向传播使用连续掩码,运行时需阈值化转换 2. **训练数据依赖**:需要使用完整博弈生成的训练数据 3. **动力学模型假设**:实验主要基于双积分器模型 ### 未来方向 1. 扩展到更复杂的动力学模型 2. 研究其他类型的博弈参数推理 3. 探索端到端训练策略 ## 深度评价 ### 优点 1. **问题重要性**:解决了游戏理论规划中的核心计算瓶颈 2. **方法创新性**:首次将深度学习与博弈论结合进行玩家选择 3. **实验充分性**:涵盖仿真和真实数据,验证了多个假设 4. **实用价值**:提供了可直接集成到现有框架的通用机制 ### 不足 1. **理论分析缺乏**:未提供收敛性或近似误差的理论保证 2. **计算开销**:虽然减少了博弈求解时间,但增加了网络推理开销 3. **场景限制**:主要在导航类任务上验证,其他类型博弈的适用性未知 ### 影响力 1. **学术贡献**:为大规模多智能体系统提供了新的解决思路 2. **实际应用**:在自动驾驶、机器人群体等领域具有直接应用价值 3. **可复现性**:提供了详细的实现细节和参数设置 ### 适用场景 1. **密集多智能体环境**:如城市交通、人群导航 2. **实时性要求高的系统**:需要频繁重规划的动态环境 3. **部分可观测场景**:智能体意图未知的不完全信息博弈 ## 参考文献 论文引用了35篇相关文献,主要涵盖: - 游戏理论规划方法 [8, 28, 9, 15] - 多智能体交互建模 [17, 20, 21, 24] - 玩家选择启发式方法 [2, 27, 30] - 注意力机制和邻居选择 [3, 6, 32] --- 该论文在解决游戏理论规划计算复杂性方面做出了重要贡献,通过学习驱动的玩家选择显著提高了多智能体系统的计算效率,为大规模实时应用铺平了道路。