游戏理论规划框架虽然在建模多智能体交互方面效果显著,但需要求解大型优化问题,其变量数量随智能体数量增加,导致计算时间过长,限制了在大规模实时系统中的应用。为解决这一问题,本文提出:1) PSN Game - 一个基于学习的游戏理论预测和规划框架,通过学习玩家选择网络(PSN)来减少运行时间;2) 目标推理网络(GIN),使PSN能够在智能体意图未知的不完全信息博弈中使用。PSN输出玩家选择掩码,区分有影响力的玩家和不太相关的玩家,使自我智能体能够求解仅涉及选定玩家的较小规模掩码博弈。通过减少博弈中的玩家数量,进而减少相应优化问题中的变量数量,PSN直接降低了计算时间。
游戏理论规划框架在多智能体系统中面临的核心问题是计算复杂性随智能体数量呈立方增长。如图2所示,使用现有求解器时,计算时间按O(N³)增长,其中N为玩家数量。这使得游戏理论方法在大规模实时系统中变得不实用。
现有玩家选择方法存在以下问题:
考虑N个智能体的有限时域离散时间开环纳什博弈,每个智能体i具有状态和控制输入。智能体状态转移遵循动力学方程:
每个智能体的目标是最小化累积成本:
PSN是一个神经网络,任务是推断掩码以平衡性能与稀疏性。提供两个变体:
网络结构:
定义玩家选择掩码,其中:
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] --- 该论文在解决游戏理论规划计算复杂性方面做出了重要贡献,通过学习驱动的玩家选择显著提高了多智能体系统的计算效率,为大规模实时应用铺平了道路。