提出基于排名的博弈模型,让多智能体在资源竞争中高效协作与决策。
Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games
- 引入序数排名机制,用局部信息替代全局信息指导策略。
- 在真实道路网络上,基于序数排名的策略优于全局排名策略,且泛化能力更强。
- 适用于无人机物流、巡逻等自主移动场景中的多智能体博弈问题。
团队寻路问题(TOP)广泛应用于自动驾驶、空中物流和监控等多智能体调度与路径规划任务。现有方法假设所有智能体合作达成单一目标,无法适用于奖励稀缺的竞争环境。本文提出随机奖赏收集寻路博弈(SPCOG),扩展了TOP以支持具有能量约束和随机转移的自利智能体在图上的规划。理论分析表明,在完全图和星型图上,SPCOG存在唯一纯纳什均衡,且与等价TOP的最优路径解一致。提出序数排名(Ordinal Rank, OR)作为智能体全局排名及其拓扑邻域内位置的紧凑表示。实证评估在真实道路网络图上进行,针对动态与静态奖赏分布,结果显示:在参数共享设置下,基于局部信息并以序数排名为条件的策略优于依赖全局信息的策略,说明序数排名在图上多智能体博弈中具有强归纳偏置;同时,其对大规模智能体数量的泛化性能显著优于全局排名策略。最后,提出虚构序数响应学习(FORL)算法,通过熵正则化实现独立学习环境下奖赏收集博弈的收敛策略。
原文摘要 · Abstract (English)
The Team Orienteering Problem (TOP) generalizes many real-world multi-agent scheduling and routing tasks that occur in autonomous mobility, aerial logistics, and surveillance applications. While many flavors of the TOP exist for planning in multi-agent systems, they assume that all the agents cooperate toward a single objective; therefore, they do not extend to settings when they compete in reward-scarce environments. We propose Stochastic Prize-Collecting Orienteering Games (SPCOG) as an extension of the TOP to plan in the presence of self-interested agents operating on a graph, under energy constraints and stochastic transitions. A theoretical discussion on complete and star graphs establishes that there is a unique pure Nash equilibrium in SPCOGs that coincides with the optimal routing solution of an equivalent TOP under rank-based conflict resolution. We propose the concept of Ordinal Rank (OR) as a concise representation of an agents' global rank and its location within a topological, well-defined neighborhood. Empirical evaluations conducted on real-world, road-network graphs under both dynamic and stationary prize distributions show that in parameter-sharing settings, the policies that leverage local information can outperform those policies leverage global information when the former is conditioned on the OR rather than the global rank, indicating that the OR acts as a strong inductive bias in multi-agent games on graphs. The OR-conditioned policies also generalize much better to games with large number of agents compared to global-rank conditioned policies. Finally, we also propose we propose Fictitious Ordinal Response Learning (FORL) as an entropy-regulated algorithm to obtain convergent policies in independent-learning settings in prize-collecting games on graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。