自动化李雅普诺夫函数合成：基于平方和规划解决联合连通多智能体系统稳定性

1. 从“手算”到“自动”为什么我们需要自动化李雅普诺夫函数合成在分布式多智能体系统的研究中稳定性分析是基石。无论是无人机编队、机器人集群协同还是智能电网的频率同步我们最终都需要回答一个核心问题这个系统能稳定运行吗传统的答案是找到一个合适的李雅普诺夫函数。这就像给一个复杂的动态系统找到一个“能量函数”如果这个能量函数沿着系统轨迹是递减的那么系统就是稳定的。听起来很美好但问题在于对于非线性、高维、且网络拓扑时变的多智能体系统构造这样一个函数长期以来严重依赖研究者的数学直觉和“艺术性”的试错。尤其是当网络拓扑是联合连通时问题变得更加棘手——网络时断时续但在一段时间内整体保持连通这更贴近现实通信受限的场景。于是一个强烈的需求出现了能不能让计算机来帮我们做这件事这就是自动化李雅普诺夫函数合成的核心驱动力。它旨在将工程师从繁琐、易错且高度专业化的函数构造工作中解放出来将精力更多地投入到问题建模和算法设计上。而平方和规划正是实现这一自动化的关键数学工具。它允许我们将“寻找一个全局非负的多项式函数”这类无限维问题转化为一个可以高效求解的半定规划问题。简单来说就是把“找函数”变成了“解一个优化问题”而后者是计算机所擅长的。我最初接触这个方向是因为在做一个多机器人编队项目时被时变通信延迟和丢包搞得焦头烂额。手动设计的李雅普诺夫函数在固定拓扑下工作良好一旦拓扑切换证明过程就漏洞百出。那时我就在想有没有一种系统化的、可计算的方法来应对这种不确定性自动化合成正是这个问题的答案。它不仅是一个理论工具更是连接复杂系统理论与工程实践的一座桥梁。2. 核心挑战拆解联合连通拓扑下的稳定性证明为何困难要理解自动化合成的价值必须先明白手动构造在联合连通拓扑下面临的三大核心挑战。这不仅仅是计算量的问题更是思维模式的转变。2.1 拓扑时变性与公共李雅普诺夫函数的缺失在固定连通拓扑下我们通常可以基于图拉普拉斯矩阵的性质构造一个形式相对统一的李雅普诺夫函数例如 $V \frac{1}{2}x^T (L \otimes I)x$ 或其变体其中 $x$ 是状态向量$L$ 是拉普拉斯矩阵。这个函数能很好地捕捉智能体间的一致性误差。然而在联合连通场景下拓扑随时间切换记为 $L_{\sigma(t)}$其中 $\sigma(t)$ 是一个切换信号。这时为每一个可能的拓扑 $L_i$ 单独设计一个李雅普诺夫函数 $V_i$ 是相对容易的。但困难在于我们需要找到一个公共的李雅普诺夫函数 $V(x)$它对所有可能出现的拓扑都满足稳定性条件即其沿对应系统轨迹的导数负定。这就好比要求一件衣服无论天气是晴、雨还是风穿起来都舒适且得体。手动寻找这样一件“万能衣服”极其困难因为你需要同时满足多个可能是无穷多个不等式约束。2.2 函数形式的复杂性与参数化难题即使我们决定寻找一个公共的二次型函数 $V(x) x^T P x$$P$ 为正定矩阵在联合连通下确保 $\dot{V} x^T (PA_{\sigma(t)} A_{\sigma(t)}^T P) x$ 对所有 $\sigma(t)$ 负定等价于要求一组线性矩阵不等式同时成立。当系统非线性时我们需要考虑更复杂的函数形式如包含高阶项的多项式。如何参数化这个多项式函数它的次数应该选多少包含哪些交叉项这些选择没有普适规则严重依赖经验。选得太简单可能根本不存在这样的函数选得太复杂又会带来难以承受的计算复杂度。2.3 验证的全局性与数值可靠性即使我们凭直觉猜出了一个函数形式验证其是否满足李雅普诺夫条件也是一个全局性的非凸问题。你需要证明 $V(x)$ 在除原点外的整个状态空间都为正且 $\dot{V}(x)$ 为负。对于非线性多项式系统这等价于判断两个多项式是否全局非负。这是一个NP难问题。传统的数值仿真只能验证有限个点无法提供严格的证明。而平方和规划正是将“全局非负”这个难以处理的约束松弛为“可表示为平方和”这个可高效检验的充分条件从而为自动化验证和搜索打开了大门。3. 平方和规划将“直觉艺术”转化为“可计算优化”平方和规划是自动化合成的引擎。它的核心思想非常巧妙一个多项式如果是若干多项式的平方和那么它自然是全局非负的。虽然不是所有非负多项式都是平方和这就是著名的Hilbert第17问题但在许多工程应用中平方和条件是一个强大且实用的充分条件。3.1 从李雅普诺夫条件到SOS约束考虑一个多项式动力系统 $\dot{x} f(x)$我们想寻找一个多项式李雅普诺夫函数 $V(x)$满足$V(x)$ 正定在原点处为零其余处为正。$-\dot{V}(x) -\frac{\partial V}{\partial x} f(x)$ 正定。利用SOS我们将这些条件放松并表述为$V(x) - l_1(x) \in \text{SOS}$其中 $l_1(x)$ 是一个正定的“小量”多项式如 $\epsilon \sum x_i^2$用于强制 $V(x)$ 正定。$-\dot{V}(x) - l_2(x) \in \text{SOS}$同理$l_2(x)$ 用于强制负定性。这里$\text{SOS}$ 表示“平方和”多项式的集合。通过将 $V(x)$ 参数化为一个带未知系数的多项式例如所有次数不超过4的项上述条件就变成了关于这些未知系数的线性约束。再加上 $V(x)$ 本身需要是平方和的约束这本身也是一个线性矩阵不等式整个问题就转化成了一个半定规划问题。而SDP是可以利用内点法等算法高效、可靠求解的。3.2 应用于多智能体与联合连通拓扑对于线性多智能体系统 $\dot{x} - (L_{\sigma(t)} \otimes I) x$寻找一个公共的二次型李雅普诺夫函数 $V x^T (P \otimes I) x$ 的问题可以表述为寻找一个对称正定矩阵 $P$使得对于所有可能的拉普拉斯矩阵 $L_i \in \mathcal{L}$$\mathcal{L}$ 是有限拓扑集合都有 $$ P L_i L_i^T P \succ 0 \quad \forall i $$ 这正是一组线性矩阵不等式。即使对于非线性交互协议只要动力学方程是多项式形式的我们就可以将 $V(x)$ 参数化为一个关于所有智能体状态的多项式并将稳定性条件转化为一组SOS约束。对于联合连通我们需要这组约束对拓扑集合 $\mathcal{L}$ 中的每一个元素都成立。注意这里有一个关键的简化。理论上联合连通允许无限多种切换序列。但在自动化合成中我们通常处理一个有限的拓扑集合 $\mathcal{L}$。只要能为这个有限集合找到一个公共李雅普诺夫函数并且切换信号 $\sigma(t)$ 的 dwell time驻留时间满足一定条件即不是无限快切换就能保证系统在任意属于该集合的切换序列下指数稳定。这是将无限问题有限化的关键一步。4. 自动化合成的工作流程与实战工具链理论很美好但如何落地下面我结合常用的工具链拆解一个完整的自动化合成流程。这里以使用 MATLAB 的SOSTOOLS工具箱为例因为它与多项式优化和SDP求解器如 SeDuMi, SDPT3集成良好在学术界广泛应用。4.1 第一步问题建模与多项式系统描述假设我们有一个由3个智能体组成的系统每个智能体是一维积分器动力学 $\dot{x}i u_i$采用标准的共识协议 $u_i \sum{j \in N_i(t)} (x_j - x_i)$其中邻居集 $N_i(t)$ 随时间变化。我们考虑两个可能的拓扑拓扑A1-2, 2-3连通和拓扑B1-3连通。这是一个简单的联合连通例子因为拓扑A和B都不连通但它们的并集是全连通的。首先我们需要将系统动力学写成多项式形式。对于这个线性案例它已经是多项式。我们定义状态向量 $x [x_1, x_2, x_3]^T$。拓扑A和B对应的拉普拉斯矩阵分别为 $$ L_A \begin{bmatrix}1 -1 0 \ -1 2 -1 \ 0 -1 1 \end{bmatrix}, \quad L_B \begin{bmatrix}1 0 -1 \ 0 0 0 \ -1 0 1 \end{bmatrix} $$ 那么在拓扑A下的动力学为 $\dot{x} -L_A x$在拓扑B下为 $\dot{x} -L_B x$。4.2 第二步参数化李雅普诺夫函数并定义SOS变量我们决定搜索一个二次的公共李雅普诺夫函数 $V(x) x^T P x$其中 $P$ 是一个 $3 \times 3$ 的对称正定矩阵。在SOSTOOLS中我们首先声明多项式变量x1, x2, x3然后构造一个对称矩阵P的未知系数。更一般地如果搜索高阶多项式我们可以用monomials命令生成一组基例如所有次数不超过4的单项式然后将 $V(x)$ 表示为这些基的线性组合系数待定。% 示例代码框架 (SOSTOOLS) syms x1 x2 x3 real; x [x1; x2; x3]; % 定义未知的对称矩阵P P sym(p, [3, 3]); P tril(P) tril(P, -1).; % 使其对称 assume(P, real); V x. * P * x;4.3 第三步构造并求解SOS约束核心步骤是将李雅普诺夫条件转化为SOS约束。我们需要$V(x) - \epsilon (x_1^2x_2^2x_3^2)$ 是SOS保证正定性。对于拓扑A$-\frac{\partial V}{\partial x} (-L_A x) - \epsilon (x_1^2x_2^2x_3^2)$ 是SOS。对于拓扑B$-\frac{\partial V}{\partial x} (-L_B x) - \epsilon (x_1^2x_2^2x_3^2)$ 是SOS。这里的 $\epsilon$ 是一个小的正数如1e-4用于确保严格正定/负定。在SOSTOOLS中我们使用sosineq来声明这些不等式。% 续上例 epsilon 1e-4; % 定义SOS规划问题 prog sosprogram([x1, x2, x3]); % 声明P的未知系数为决策变量 [prog, P] sossymvar(prog, P); % 重新构造V V x. * P * x; % 约束1: V - epsilon*|x|^2 0 scaling_poly epsilon*(x1^2 x2^2 x3^2); prog sosineq(prog, V - scaling_poly); % 计算导数 dV_dx jacobian(V, x); % 约束2: 对于拓扑A f_A -L_A * x; dotV_A dV_dx * f_A; prog sosineq(prog, -dotV_A - scaling_poly); % 约束3: 对于拓扑B f_B -L_B * x; dotV_B dV_dx * f_B; prog sosineq(prog, -dotV_B - scaling_poly); % 设置SDP求解器并求解 prog sossolve(prog, sedumi); % 获取结果 P_sol sosgetsol(prog, P);4.4 第四步结果分析与验证求解完成后P_sol就是找到的公共正定矩阵。我们需要检查求解状态prog.info。如果求解成功我们可以计算P_sol的特征值以确保其正定性并绘制 $V(x)$ 和 $\dot{V}(x)$ 的曲面来直观验证。实操心得这一步最容易出问题的地方是数值条件。SDP求解器对问题的缩放很敏感。如果智能体状态量纲差异巨大比如位置和速度最好先进行归一化。另外初始选择的 $\epsilon$ 不能太大否则问题可能不可行也不能太小否则会导致数值病态。通常从1e-4开始尝试是安全的。如果求解失败可以尝试1增加李雅普诺夫函数的多项式次数2引入“松弛变量”或“乘子”通过S-procedure3检查拓扑集合是否真的允许存在公共二次型李雅普诺夫函数对于切换线性系统这等价于所有系统矩阵共享一个公共的二次型李雅普诺夫函数这是一个较强的条件。5. 从理论到实践的跃迁处理非线性与规模扩展前面的例子是线性的、小规模的。真正的挑战在于非线性系统和大量智能体。这里分享几个进阶实践中的关键点。5.1 非线性交互协议的处理假设智能体动力学为 $\dot{x}i f(x_i) \sum{j \in N_i} \phi(x_i, x_j)$其中 $f$ 和 $\phi$ 是多项式函数例如$f(x_i) x_i - x_i^3$ $\phi(x_i, x_j) (x_j - x_i)^3$。自动化合成的流程不变但 $V(x)$ 和 $\dot{V}(x)$ 会变成更高次的多项式。关键技巧不要盲目提高 $V(x)$ 的次数。应该先从二次型开始尝试。如果失败再尝试四次型。通常系统的“有效非线性度”决定了所需 $V(x)$ 的最低次数。一个实用的策略是先针对固定拓扑、平衡点附近线性化后的系统设计一个线性李雅普诺夫函数然后以此作为初始猜想在SOS规划中作为初始点或约束参考这能显著提高求解效率和成功率。5.2 应对大规模智能体系统的“维数灾难”当智能体数量 $N$ 很大时全状态多项式 $V(x)$ 的变量维数爆炸单项式数量随次数呈组合增长SDP问题的规模会变得无法求解。此时必须利用系统的结构特性。核心方法利用图结构与可分离性对于许多一致性协议智能体是对称的且李雅普诺夫函数可以取为各智能体“局部能量”之和的形式$V(x) \sum_{i1}^N V_l(x_i) \sum_{(i,j) \in \mathcal{E}} V_c(x_i, x_j)$。其中 $V_l$ 是局部项$V_c$ 是耦合项。我们可以参数化 $V_l$ 和 $V_c$ 为低维多项式例如只依赖于1个或2个变量而不是一个依赖于所有 $N$ 个变量的高维多项式。这样决策变量的数量就从 $O(N^d)$ 降到了 $O(1)$ 或 $O(N)$。在SOSTOOLS中这意味着我们声明 $V_l(s)$ 和 $V_c(s, t)$ 为关于标量变量 $s, t$ 的多项式。然后稳定性条件 $-\dot{V}(x)$ 是SOS的约束将转化为对 $V_l$ 和 $V_c$ 系数的、与 $N$ 无关的一组有限约束。这本质上是利用了系统的对称性和可分离性是处理大规模网络化系统的关键。5.3 联合连通拓扑的保守性与放宽技巧要求一个公共李雅普诺夫函数对所有拓扑都成立条件可能过于保守。特别是当拓扑集合 $\mathcal{L}$ 中的某些矩阵性质差异很大时可能根本不存在这样的公共二次型函数。放宽策略一使用多李雅普诺夫函数不再强求一个公共函数而是为每个拓扑 $L_i$ 寻找一个函数 $V_i(x)$并满足“切换衰减”条件当从拓扑 $i$ 切换到 $j$ 时有 $V_j(x) \leq \mu V_i(x)$其中 $\mu \geq 1$。如果切换不是无限频繁满足平均驻留时间条件系统仍能稳定。这组条件同样可以用SOS来表述但决策变量更多。放宽策略二引入路径依赖的积分型李雅普诺夫函数这是更前沿的方向例如构造 $V(x, t) x^T (\int_0^t \Phi^T(\tau, t) P \Phi(\tau, t) d\tau) x$其中 $\Phi$ 是状态转移矩阵。这类函数天然地包含了拓扑切换的历史信息。虽然其自动化合成更为复杂但能提供更小的保守性。目前的研究正在探索如何用数据驱动或在线学习的方法来近似这类函数。6. 常见陷阱与调试指南当SOS求解失败时即使流程正确你也可能会遇到求解器返回“不可行”或数值错误。以下是我在项目中总结的排查清单。问题1求解器报告“不可行”。可能原因A问题本身确实不可行。检查你的拓扑集合是否真的在联合连通意义下能稳定可以先用简单的线性矩阵不等式对于线性系统或仿真验证一下基本假设。可能原因B李雅普诺夫函数次数不够。尝试将 $V(x)$ 的最高次数提高2阶。例如从2次尝试到4次。可能原因C数值缩放问题。状态变量 $x_i$ 可能代表物理量位置、速度、角度它们的典型数值范围可能相差几个数量级。这会导致SDP问题的系数矩阵条件数极差。解决方案对状态进行归一化例如令 $\tilde{x}_i x_i / s_i$其中 $s_i$ 是该状态的典型尺度如最大期望值。可能原因D$\epsilon$ 设置过大。$\epsilon$ 强制了严格正定性。如果 $\epsilon$ 太大可能会“挤占”掉解空间。尝试将其减小到1e-6或更小。问题2求解成功但找到的 $V(x)$ 非常“畸形”例如系数极大或极小。这是典型的数值病态迹象。根本原因通常是问题条件数差。除了上述的变量缩放检查你的动力学方程中是否有非常小或非常大的物理常数尝试用无量纲化重新建模整个问题。有时引入一个微小的正则化项如最小化 $V(x)$ 的系数范数也能帮助得到更“平滑”的解。问题3对于大规模问题求解时间过长或内存不足。首先检查是否应用了第5.2节的可分离结构技巧。如果已经应用问题规模应该与 $N$ 无关。考虑稀疏性。许多大规模多智能体系统的耦合是局部的这会导致SDP问题的数据矩阵具有块对角或稀疏结构。使用支持稀疏矩阵的SDP求解器如 SDPA可以大幅提升性能。降低多项式次数。在精度和计算负担之间权衡。对于工程应用一个保守但可验证的简单李雅普诺夫函数远比一个精确但无法计算的高阶函数有用。问题4如何验证SOS解的正确性求解器给出的解是数值解。一个重要的后验验证步骤是将找到的 $V(x)$ 和 $-\dot{V}(x)$ 的表达式提取出来在一个密集的网格点上例如在单位球面上采样计算其最小值。如果所有采样点上的值都显著大于零比如大于1e-5那么我们可以对这个解有很高的信心。这是一种朴素的、但非常有效的数值验证手段。7. 超越稳定性自动化合成在性能分析与控制器设计中的应用自动化合成李雅普诺夫函数的能力其价值远不止于证明稳定性。它实际上为我们提供了一个强大的框架用于解决一系列更复杂的分析设计问题。性能指标优化我们不仅想要稳定还希望收敛快、超调小。这可以转化为寻找一个李雅普诺夫函数使得其衰减率 $\dot{V} \leq -\alpha V$ 中的 $\alpha$ 最大。这可以通过在SOS规划中引入一个待最大化的变量 $\alpha$ 来实现问题变成一个广义特征值问题或双线性矩阵不等式依然可以通过迭代的SOS方法求解。安全性与可达集分析给定一个安全集 $\mathcal{S} {x: h(x) \geq 0}$我们想证明从某个初始集 $\mathcal{X}_0$ 出发的所有轨迹都不会离开 $\mathcal{S}$。这可以通过寻找一个“屏障函数” $B(x)$ 来实现使得在 $\mathcal{X}_0$ 上 $B(x) \leq 0$在 $\mathcal{S}$ 的边界上 $B(x) 0$并且沿系统轨迹有 $\dot{B}(x) \leq 0$。这又是一个可以用SOS规划来搜索 $B(x)$ 的问题。分布式控制器协同设计更激动人心的应用是同时设计李雅普诺夫函数和控制器。例如对于系统 $\dot{x}i f_i(x_i) g_i(x_i)u_i$我们希望设计局部控制器 $u_i k_i(x_i, x{j \in N_i})$使得闭环系统稳定。我们可以将 $k_i$ 也参数化为多项式带未知系数然后将闭环系统的稳定性条件包含 $V$ 和 $k_i$ 的系数一起作为SOS约束进行优化。这实现了稳定性分析与控制器设计的统一自动化。在我参与的一个多机器人围捕项目中我们正是利用了这个思路。每个机器人的控制器是一个关于自身状态和邻居相对位置的多项式。通过自动化协同设计我们不仅得到了一个保证稳定性的控制器还通过优化性能指标使系统在避障和能量消耗之间取得了很好的平衡。整个过程几乎完全自动化只需提供机器人的动力学模型多项式近似和通信拓扑描述。自动化合成已经从纯理论工具逐步走向解决实际工程中那些高度复杂、手动难以处理的分析与设计问题。它要求工程师不仅懂控制理论还要懂优化和数值计算但这种跨领域的技能组合正是解决下一代智能系统挑战的关键。