提出新方法解决多机器人混合层级决策难题,可实时求解复杂协同任务。
Efficiently Solving Mixed-Hierarchy Games with Quasi-Policy Approximations
- 用近似策略消除高阶导数,简化混合层级博弈求解
- 算法在非线性约束下实现局部指数收敛,实测支持实时计算
- 适合需要高效多智能体协调的硬件部署场景
多机器人协同常呈现分层结构,部分机器人的决策依赖于其他机器人的行为规划。尽管博弈论为此类交互提供了理论框架,但现有求解器难以处理同时包含纳什与斯塔克尔伯格决策的混合信息结构。本文研究具有森林结构的N机器人混合层级博弈,其中每个机器人在其子树中作为斯塔克尔伯格领导者,不同分支间通过纳什均衡交互。我们推导出该类博弈的卡鲁施-库恩-塔克(KKT)一阶最优性条件,发现其涉及随层级深度增加而增长的高阶策略响应导数,直接求解不可行。为此,引入一种去除高阶策略导数的准策略近似,并开发了一种不精确牛顿法来高效求解近似后的KKT系统。证明了该算法在非二次目标和非线性约束下的局部指数收敛性。方法已实现于高性能Julia库MixedHierarchyGames.jl,在硬件与模拟多智能体实验中验证,成功实现复杂混合层级结构的实时收敛。
原文摘要 · Abstract (English)
Multi-robot coordination often exhibits hierarchical structure, with some robots' decisions depending on the planned behaviors of others. While game theory provides a principled framework for such interactions, existing solvers struggle to handle mixed information structures that combine simultaneous (Nash) and hierarchical (Stackelberg) decision-making. We study N-robot forest-structured mixed-hierarchy games, in which each robot acts as a Stackelberg leader over its subtree while robots in different branches interact via Nash equilibria. We derive the Karush-Kuhn-Tucker (KKT) first-order optimality conditions for this class of games and show that they involve increasingly high-order derivatives of robots' best-response policies as the hierarchy depth grows, rendering a direct solution intractable. To overcome this challenge, we introduce a quasi-policy approximation that removes higher-order policy derivatives and develop an inexact Newton method for efficiently solving the resulting approximated KKT systems. We prove local exponential convergence of the proposed algorithm for games with non-quadratic objectives and nonlinear constraints. The approach is implemented in a highly optimized Julia library (MixedHierarchyGames.jl) and evaluated in hardware and simulated multi-agent experiments, demonstrating real-time convergence for complex mixed-hierarchy information structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。