⚡ electrical engineering

TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics

本文介绍了 TinySDP，这是首个专为嵌入式系统设计的半定规划求解器，它能够在微控制器上实现实时、可验证的模型预测控制，并在具有挑战性的动态环境中，相较于最先进基线方法，实现了更优越的无碰撞导航与路径效率。

原作者： Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo, Fausto Vega, James Anderson, Zachary Manchester, Brian Plancher

发布于 2026-05-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo, Fausto Vega, James Anderson, Zachary Manchester, Brian Plancher

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

想象一下，你正试图引导一架微小、超高速的无人机穿过迷宫。迷宫里有移动的墙壁（比如来回摆动的机械臂）和棘手的死胡同。你的目标是将无人机从A点引导至B点而不发生碰撞，并且必须在眨眼之间做出这些决策。

这就是论文TinySDP所应对的挑战。以下是他们如何利用简单的类比来解决这一问题的故事。

问题：“过于聪明”的大脑 vs. “微小”的大脑

在机器人领域，规划路径有两种方式：

“局部”方式（短视的司机）： 大多数现有无人机使用一种只向前看几步的方法。这就像一位司机只能看到正前方的车辆。如果那辆车移动了，他就会变道。但如果道路弯曲成死胡同（“死巷”）或者墙壁突然关闭，这位司机就会被困住或发生碰撞，因为他没有看到全局。为了安全起见，他们通常开得非常慢，并与所有物体保持巨大的距离，这使得行程漫长且低效。
“全局”方式（完美的数学家）： 有一种更强大的数学工具叫做半定规划（SDP）。这就像一位天才数学家，能够看到整个迷宫，计算所有可能的未来，并找到绝对完美、最短且能保证不碰撞的路径。
- 局限性： 这位天才太慢了，需要超级计算机。这就像试图在一只微小的手表上运行庞大的模拟程序。它根本无法适配无人机内部的小型计算机芯片。

解决方案：TinySDP

作者们创造了TinySDP，这就像是将那位天才数学家缩小，使其能够塞进一只微小的手表中，同时保持其大脑足够敏锐，能够瞬间解决迷宫问题。

以下是他们如何利用三个关键技巧做到的：

1. “影子”技巧（提升）

障碍物（如圆形墙壁）在数学上很棘手，因为它们是弯曲的。标准数学在小型芯片上处理曲线时很困难。

类比： 想象试图在一张由方形瓷砖制成的纸上画一个完美的圆。它是锯齿状的且很难画。但是，如果你把那张纸举到空中，并观察它在不同表面上投射的“影子”，那条曲线可能会看起来像一条直线或一个简单的形状。
论文的方法： 他们使用了一种数学上的“提升”，将棘手的曲线障碍物规则转化为更简单的直线格式，以便微型计算机能够轻松处理。他们称之为将问题“提升”到更高维度。

2. “缓存”捷径（Riccati 结构）

即使有了“影子”技巧，为飞行的每一步进行数学计算对于微型芯片来说仍然工作量过大。

类比： 想象你在解一个谜题，规则每秒都会发生轻微变化。与其每次都从头开始解整个谜题，不如意识到90%的拼图块是相同的。因此，你预先计算那90%的部分并将其放在口袋里（即“缓存”）。当谜题发生变化时，你只需要解决那10%的新内容。
论文的方法： 他们使用了一种称为Riccati 递归的技术，在离线状态下预先计算数学中枯燥、重复的部分。当无人机飞行时，它只需从口袋中取出这些预先计算好的数字，仅对当前时刻所需的微小新部分进行数学运算。这使其速度极快。

3. “安全徽章”（秩-1 证书）

这是最巧妙的部分。因为他们使用了“影子”技巧（松弛），数学可能会给出一个在纸面上看起来不错但在现实世界中实际上略有偏差的解。

类比： 想象一名保安正在检查访客的身份证。身份证看起来是真的，但有时伪造品看起来也完美无缺。保安需要一个特殊的扫描仪来100%确定。
论文的方法： 在数学解出路径后，TinySDP 会运行一个超快速的“安全检查”（称为秩-1 证书）。它会问：“我们的‘影子’技巧是否过度扭曲了现实？”
- 如果答案是是（数学过于宽松），无人机立即停止并悬停（一种“回退”策略），而不是发生碰撞。
- 如果答案是否，无人机获得“绿灯”并起飞。
- 在他们的测试中，这一检查几乎每次都通过了，证明路径确实是安全的。

结果：更快、更短、更安全

该团队在一款名为Crazyflie的微型无人机（大小约如手掌）上进行了测试，其内部装有非常小的计算机芯片。

死胡同测试： 在U形死胡同中，其他方法被困住或发生碰撞。TinySDP 找到了穿过的路径。
移动墙壁测试： 当一面墙壁横穿路径摆动时，其他方法发生碰撞或采取了巨大的宽幅绕行。TinySDP 预判了这一动作，并完美地挤过了缝隙。
效率： TinySDP 找到的路径比其他方法短了高达 73%。它不需要为了“安全”而绕巨大的圈子；因为它在数学上确信不会碰撞，所以可以采取直接路线。
实时性： 它在微型芯片上以每秒 25 次的速度运行，足以在现实生活中控制飞行中的无人机。

总结

TinySDP 是一种新方法，让小型、廉价的机器人能够利用“超级智能”的数学来避开障碍物。它结合了一个巧妙的数学技巧来简化问题，一个记忆捷径来加速处理，以及一个安全徽章来双重检查答案。这使得微型无人机能够安全、高效地飞越复杂、动态的环境，而这在以前被认为是如此小型计算机无法实现的。

技术摘要：TinySDP

问题陈述

在动态环境中的安全运动规划与控制仍然是机器人领域的一项重大挑战，尤其是在资源受限的嵌入式系统上。虽然模型预测控制（MPC）在推理系统动力学和约束方面行之有效，但在实时条件下对非凸障碍物避障施加形式化安全保证却十分困难。现有方法通常依赖保守的过近似（例如线性化距离约束）或局部凸化方法，这些方法无法捕捉全局几何结构。在涉及狭窄通道、死胡同或动态障碍物的场景中，这些方法容易失效，往往需要大量调整安全裕度，从而导致机器人有效足迹膨胀。相反，虽然半定规划（SDP）为通过提升（lifting）凸化非凸几何约束提供了原则性框架，但通用 SDP 求解器计算成本高昂且内存占用大，使其不适用于微控制器上的实时滚动时域控制。

方法论

作者提出了TinySDP，这是首个专为嵌入式系统设计、旨在实现实时、可验证障碍物避障的半定规划求解器。该方法整合了三个核心组件：

1. 结构化提升与松弛

TinySDP 利用基于每阶段的凸半定松弛，将非凸、二次型、基于圆盘的障碍物避障约束表述为 MPC 问题。

提升（Lifting）： 该方法将几何状态（例如平面位置 $p_k$ ）提升至更高维的半正定（PSD）锥中。具体而言，它引入了状态和输入外积的辅助变量（例如 $X_k = x_k x_k^\top$ ）。
线性化： 这种提升将二次障碍物约束（例如 $\|p_k - c_j\|^2 \geq r_j^2$ ）转化为提升变量中的线性仿射不等式，同时在提升空间中保持系统动力学的线性特性。
松弛（Relaxation）： 矩矩阵上的精确秩 1 约束被松弛为 PSD 约束（ $M_k \succeq 0$ ），从而使问题变为凸优化问题。

2. 基于 Riccati 的 ADMM 求解器

为了在嵌入式硬件上高效求解所得的凸问题，作者扩展了TinyMPC框架（该框架使用缓存的 Riccati 递归）以处理每阶段的 PSD 约束。

算法： 求解器采用交替方向乘子法（ADMM）。
原始更新： 原始子问题是一个提升后的线性二次型调节器（LQR）问题。关键在于，系统动力学在提升变量中保持线性，这使得能够利用预先计算并缓存的稳态量，进行高效的向后 - 向前 Riccati 扫描。
松弛与对偶更新： PSD 约束通过投影步骤处理。在每次 ADMM 迭代中，求解器计算矩阵到 PSD 锥的欧几里得投影（通过特征分解和特征值钳位），并更新对偶变量。该投影按阶段执行，保留了实时执行所需的计算结构。

3. 后验秩 1 安全证书

为了解决 SDP 松弛引入的松弛度问题，论文提出了一种在每个时间步评估的简单且计算廉价的证书。

迹间隙（Trace Gap）： 该证书测量“迹间隙”（ $\Delta_k$ ），定义为提升位置块的迹与物理位置范数平方之间的差值（ $\text{trace}(X^{(p)}_k) - \|p_k\|^2$ ）。
认证逻辑： 如果提升裕度（线性化障碍物约束的值）为非负，且迹间隙相对于该裕度足够小，则认证该解无碰撞。
回退机制： 如果证书验证失败，系统将丢弃计划的控制输入并执行反应式回退策略（停止并悬停），确保未认证的指令永远不会应用于物理机器人。

主要贡献

TinySDP 求解器： 开发了首个嵌入式 SDP 求解器，利用缓存的 Riccati 结构实时求解 PSD 松弛的 MPC 问题。
松弛与认证的集成： 一个将高效凸松弛与显式的、后验的几何安全证书相结合的框架，弥合了理论最优性与实际安全保证之间的差距。
硬件验证： 成功部署于运行在 25 Hz 控制频率下的 Crazyflie 2.1 四旋翼飞行器（STM32F405 微控制器）上，证明了半定约束可在资源受限的平台上强制执行。

实验结果

作者在仿真和真实世界硬件中将 TinySDP 与最先进基线方法（TinyMPC-LIN、TinyMPC-HOCBF 和 RPCBF）进行了评估。

静态 U 形死胡同： 在旨在导致局部方法陷入死锁的场景中，TinySDP 实现了无碰撞导航，其路径长度比表现最佳的基线方法（RPCBF）短 31–73%。基线方法要么发生碰撞（安全裕度为零），要么需要不切实际的大安全裕度（高达无人机尺寸的 30 倍）才能成功，这膨胀了碰撞足迹并阻碍了到达目标。
动态障碍物避障： 在移动障碍物封闭狭窄通道的动态场景中，TinySDP 成功预测并避免了碰撞。它生成的路径比 RPCBF短 30%，并且保持了比基线方法更高的精度（更接近目标）。
3D 扩展： 作者证明了提升框架可自然扩展到 3D 球形障碍物，并在仿真中成功导航了动态 3D 场景。
真实世界部署： 在 Crazyflie 上，求解器在约 14.8 毫秒内执行了 5 次 ADMM 迭代（在 40 毫秒的控制周期内保留了约 25 毫秒的余量）。内存占用适中（PSD 逻辑的静态内存开销约为 1.47 KB）。在涉及移动机械臂的五次独立试验中，在线安全证书在每个时间步均保持有效，证实了在实际世界干扰下秩 1 几何结构的保持。

意义与主张

论文声称，TinySDP证明了半定约束并非本质上与嵌入式系统上的实时滚动时域控制不相容。通过利用特定的问题结构（Riccati 动力学）并将优化与认证分离，作者表明，在不牺牲计算可行性的情况下，超越保守的线性近似是可能的。

这项工作弥合了离线半定规划与实际嵌入式部署之间的差距。它表明，如果求解器设计尊重底层的 MPC 结构，更丰富的凸安全模型可以集成到高速控制器中。作者将此定位为迈向实现“敏捷”边缘机器人的一步，这些机器人能够以形式化安全保证导航复杂的非凸环境，而不是依赖可能无法在小型嵌入式平台上部署的启发式调整或基于学习的方法。

作者对局限性保持谦逊，指出该证书提供的是每时间步检查，而非形式化的闭环递归可行性保证，并且由于较大的 PSD 投影带来的计算成本增加，将完整的 3D 能力扩展到微控制器仍然是一个挑战。