💻 computer science

A Fast Convergent Algorithm for Solving Non-convex Partially-Decoupled Generalized Nash Equilibrium Problems

本文介绍了 FALCON，这是一种快速收敛算法，它利用序贯凸规划和势博弈重构来解决多智能体最优控制中具有非凸性、部分解耦的广义纳什均衡问题，并保证能全局收敛至开环纳什均衡。

原作者： Bennet Outland, Vishala Arya

发布于 2026-06-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Bennet Outland, Vishala Arya

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一场高风险的捉迷藏游戏，参与者不仅是人类，还有自主机器人、自动驾驶汽车或航天器。在这些场景中，每个人都在根据自己的目标追求胜利（或生存），但他们的运动是紧密相连的。如果一辆车突然转向，它会改变其他所有人可选的路径。在数学世界中，这被称为非凸微分博弈（Non-Convex Differential Game）。

问题的难点在于，这类博弈极其难以求解。这就像是在一个充满了深谷、陡峭悬崖和隐藏洞穴的复杂地形中寻找最低点（非凸性）。大多数现有的算法就像是在小山谷里迷路的徒步者，它们以为自己已经到达了底部，却不知附近还存在更深的谷底。或者，它们可能会尝试走捷径，结果却导致坠入悬崖（违反安全规则）。

本文介绍了一种名为 FALCON 的新算法（全称：用于开环纳什均衡的快速增广拉格朗日凸化算法，Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria）。你可以把 FALCON 想象成一位超级聪明且谨慎的向导，它能帮助一群玩家在最混乱、最危险的环境中找到各自的最佳策略。

以下是 FALCON 的工作原理，通过简单的概念进行拆解：

1. “部分解耦”的博弈

首先，作者提出了一个合理的假设：虽然玩家们会相互影响彼此的目标和安全规则，但他们并不会直接控制对方的引擎。

类比： 想象一群正在比赛的自行车手。选手 A 的踩踏动作并不会物理性地推动选手 B 的自行车。然而，如果选手 A 挡住了路径，选手 B 就必须改变路线以避免碰撞。FALCON 假设每个玩家的“物理特性”是独立的，但“交通规则”（约束条件）是将他们联系在一起的。这在不丢失问题本质的前提下简化了数学计算。

2. “平滑化”技巧（凸化）

核心难点在于博弈的地形是凹凸不平且崎岖不平的。FALCON 使用了一种称为**序列凸规划（Sequential Convex Programming）**的技术。

类比： 想象你正试图让一个小球滚向一张揉皱的纸片的底部。预测路径几乎是不可能的。FALCON 会取一张小而平整的纸（“信任区域”），将其覆盖在揉皱的区域之上。在这块小而平坦的纸上，路径是直线（凸的）。算法在平整的纸面上解决这个简单的路径问题，迈出一步，然后将平整的纸移动到新位置，如此循环往复。
安全网： 为了确保玩家不会走出纸面掉入“悬崖”（即数学失效的地方），FALCON 使用了**信任区域（Trust Region）**机制。它规定：“你只能在这一小圈范围内移动。”如果这一步看起来效果很好，圆圈就会变大；如果效果不好，圆圈就会缩小。

3. “连续安全”带

这类算法的一个常见问题是，它们只在特定的时刻检查安全规则（比如每秒钟才检查一次汽车的速度）。但如果汽车在两次检查之间发生了危险的转向怎么办？

类比： FALCON 不仅仅在每一秒的开始和结束时检查速度，它还增加了一个“安全带”来持续监测车辆。它创建了一个虚拟变量，用于累积两次检查之间发生的任何微小的违规行为。如果车辆哪怕只是轻微地偏离了边界，这条“安全带”就会收紧，迫使算法修正路径。这确保了方案在每一个瞬间都是安全的，而不仅仅是在检查点。

4. “团队谈判者”（增广拉格朗日）

由于玩家拥有共享的约束条件（例如“不要撞到彼此”），他们需要一种协商机制。

类比： FALCON 使用了一个数学上的“谈判者”（拉格朗日乘子）。如果玩家 A 离玩家 B 太近，谈判者就会提高“惩罚价格”。随后，玩家 A 会调整自己的路径以降低该价格。算法会不断调整这些价格，直到每个人都达到一种平衡状态——在这种状态下，任何人都不会想改变自己的策略，因为改变只会让情况变得更糟。这种平衡状态被称为纳什均衡（Nash Equilibrium）。

5. 实验结果：赛车、走廊与太空

作者通过三个极具挑战性的场景测试了 FALCON，以证明其有效性：

F1 赛车游戏： 两辆赛车正在一个急弯处竞速。
- 结果： FALON 比以往的方法更快、更可靠。当其他算法在复杂的初始位置陷入困境或无法找到解时，FALCON 100% 地找到了获胜策略。它成功地计算出赛车应如何争夺位置，既能阻截对手又不发生碰撞。
狭窄走廊： 三个机器人试图挤过一个有两个狭窄瓶颈处的走廊。
- 结果： 机器人必须完美协作。它们不能盲目冲刺，而是必须轮流通过。FALCON 让它们展现出了智能行为：它们自然地排成一列，在保持通信范围的同时，有序地通过狭窄处。
太空博弈（女士、强盗与卫兵）： 一颗高价值卫星（“女士”）正被一名攻击者（“强盗”）追逐，而一名保护者（“卫兵”）试图阻挡攻击者。
- 结果： 这是在太空中进行的复杂 3D 舞蹈。FALCON 计算出了各种轨迹：包括卫兵成功拦截强盗从而让女士逃脱的情况，以及尽管有卫兵阻拦，强盗仍设法靠近女士的情况。它同时处理了复杂的物理特性和碰撞规避问题。

总结

FALCON 是一种求解复杂多智能体博弈的新型、快速且可靠的方法。它保证了只要解存在，算法就一定能找到它（全局收敛性）。它确保了方案在每一个时间点都是安全的，而不仅仅是在检查点。通过将一个崎岖、难以求解的谜题转化为一系列微小的、易于处理的平坦谜题，FALCON 让自主系统能够在现实世界中做出智能、安全且具有协作性的决策。

技术摘要：用于非凸部分解耦广义纳什均衡问题的 FALCON 算法

问题描述

本文研究了解决航空航天和机器人领域中多智能体最优控制问题的挑战，具体将其建模为非凸微分博弈。作者专注于一种被称为**部分解耦广义纳什均衡问题（PDGNEPs）**的特定子类。

在此公式化设定中， $N$ 个智能体旨在最小化各自的代价函数 $J_i$ ，并受限于：

可分离动力学： 每个智能体 $i$ 的演化遵循其自身的动力学方程 $\dot{x}_i(t) = f(x_i(t), u_i(t))$ ，该方程独立于其他智能体的控制或状态。
耦合约束： 智能体通过共享的等式和不等式约束 $C(X, \Upsilon) \leq 0$ 进行耦合，这些约束可能依赖于所有智能体的轨迹。
目标： 寻找一个开环纳什均衡（Open-Loop Nash Equilibrium），其定义为这样一组策略：在给定他人策略的情况下，没有任何智能体可以通过单方面改变策略来改善其代价。

现有方法面临局限性：迭代线性二次型博弈（iLQGames）缺乏原生的约束处理能力；增广拉格朗日博弈（ALGAMES）虽然表现有所提升，但在处理紧致非凸性时较为吃力；而微分博弈序列二次规划（DG-SQP）虽然提供了收敛保证，但在高度非凸场景下往往面临高昂的计算成本和数值不稳定性。

方法论：FALCON 算法

作者提出了 FALCON（用于开环纳什均衡的快速增广拉格朗日凸化算法），该算法结合了**序列凸规划（SCP）与增广拉格朗日（Augmented Lagrangian）**框架。其核心方法如下：

1. 连续时间约束强制执行

为了解决离散化 SCP 求解器中常见的采样间约束违规问题，作者使用**外罚函数（exterior-penalty）**方法对约束进行了重新表述。

利用三次惩罚函数 $q(z) = [z]_+^3$ （因其具有 $C^2$ 光滑性而被选中）定义了一个连续时间维度的约束违规度量 $\Lambda_i(t)$ 。
一个增广状态变量 $y_i(t)$ 用于累积这种违规量。
约束的执行不仅限于离散节点，还通过限制 $y_i$ 在节点之间的累积量，在整个连续时域内确保满足点对点的约束，从而在理论界限 $\delta(\varepsilon)$ 内保证点对点约束的满足。

2. 增广拉格朗日与上图（Epigraph）重构

为了处理非凸目标和约束：

上图形式： 非凸代价函数 $J_i$ 通过上图变量 $\tau_i$ 被转移到约束中，即在满足 $J_i \leq \tau_i$ 的条件下最小化 $\tau_i$ 。这使得目标函数可以被线性化，同时将非凸性保留在约束中。
增广拉格朗日： 构建了一个增广拉格朗日函数 $L_i$ ，其中包含了针对动力学约束和耦合约束的拉格朗日乘子（ $\lambda, \mu$ ）及惩罚权重（ $\omega$ ）。

3. 序列凸化 (SCvx*)

非凸博弈通过求解一系列凸子问题来迭代近似：

线性化： 在参考轨迹 $\bar{z}$ 周围对动力学和约束进行线性化。
松弛： 引入虚拟控制（ $\xi$ ）和虚拟缓冲（ $\zeta$ ）变量，以减轻由线性化引起的人为不可行性。
置信域： 置信域约束 $\|z - \bar{z}\|_\infty \leq r$ 确保近似过程保持有效。
势博弈重构： 生成的凸子问题被构建为一个变分广义纳什均衡（v-GNE）。通过构建一个强凸势函数 $\Phi_k$ （各部分惩罚目标之和），该子问题可以作为**二阶锥规划（SOCP）**高效求解。

4. 算法循环

算法通过以下步骤迭代：

连续线性化： 创建凸子问题。
步长接受： 使用联合势能比 $\rho_k$ （比较实际代价减少量与预测代价减少量）评估步长的“质量”。如果 $\rho_k$ 超过阈值，则接受该步长。
乘子更新： 根据约束违规情况和用户定义的容差 $\delta_k$ 更新拉格朗日乘子和惩罚权重。
置信域调整： 根据接受率动态调整置信域半径 $r$ （收缩或扩张）。

核心贡献

算法开发： 引入了 FALCON，这是一种通过结合序列凸化与增广拉格朗日技术来解决非凸 PDGNEP 的新颖算法。
理论保证： 在温和的假设（有界加速度、利普希茨连续性、 $C^2$ 光滑性）下，证明了其向开环纳什均衡的全局收敛性。所求解在连续时间意义下保证是动力学可行且近似耦合可行的。
连续时间安全性： 提供了一种严谨的公式化方法，用于在离散节点之间连续地强制执行约束，防止了采样间隔内的安全违规。
效率： 证明了通过将内层循环转化为可通过高效 SOCP 求解的势博弈，可以解决该问题，从而避免了以往 DG-SQP 方法的计算瓶颈。

数值结果

作者在三个不同的非凸微分博弈场景下验证了 FALCON：

F1 奥斯汀赛车（2 名玩家）：
- 场景： 两辆赛车在 F1 奥斯汀赛道的急弯处进行比赛。
- 表现： 在各种初始条件下，FALCON 实现了 100% 的收敛率，而 DG-SQP 仅在 72% 的情况下收敛。
- 速度： FALCON 显著更快，平均计算时间为 0.873 秒，而 DG-SQP 为 50.021 秒。在相同的标准下，ALGAMES 在此困难案例中未能收敛。
狭窄通道（3 名玩家）：
- 场景： 三个单轮智能体在带有两个瓶颈点的走廊中导航，同时保持碰撞规避和通信范围约束。
- 观察： 该算法成功处理了非凸环境，展示了涌现出的协作行为（例如，智能体有序通过瓶颈点），同时严格遵守连续时间约束。
航天器 Lady-Bandit-Guard（3 名玩家）：
- 场景： 一个涉及 $R^6$ （Clohessy-Wiltshire-Hill 动力学）的异构博弈，包含“Lady”（高价值资产）、“Bandit”（攻击者）和“Guard”（防御者）。
- 观察： FALCON 解决了复杂的追逃防御博弈，成功模拟了防御者阻挡攻击者以允许资产逃脱的场景，并处理了交战几何结构中的非凸性。

重要性与主张

本文声称 FALCON 代表了通过弥合计算效率与理论收敛保证之间的鸿沟，在解决非凸微分博弈方面取得了重大进展。

差异化： 与 iLQGames 不同，FALCON 原生支持状态和控制约束。与 DG-SQP 不同，它在不牺牲收敛保证的前提下，在高度非凸的设置中提供了更优的数值性能和鲁棒性。
安全性： 连续时间约束公式被强调为关键特性，对于不允许采样间违规的安全关键型航空航天应用至关重要。
可扩展性： 通过将内层循环简化为可通过 SOCP 求解的势博弈，该方法为复杂多智能体系统提供了一种可扩展的方法。

作者总结道，FALCON 提供了一个稳健、快速且具有理论基础的框架，用于解决非凸微分博弈，使其适用于复杂的航空航天任务，如追逐-逃逸、受控空间行动和协作引导。