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

📄 arXiv: 2605.13748v1 📥 PDF

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

分类: cs.RO, eess.SY

发布日期: 2026-05-13

备注: Accepted to Robotics: Science and Systems (RSS) 2026. 11 pages, 5 figures, 2 tables. Project website: https://a2r-lab.org/TinySDP/

💡 一句话要点

TinySDP：用于可认证和敏捷边缘机器人的实时半定规划求解器

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱二：RL算法与架构 (RL & Architecture)

关键词: 半定规划 嵌入式系统 实时控制 运动规划 模型预测控制

📋 核心要点

  1. 现有半定规划求解器计算量大，难以在资源受限的嵌入式系统上实现实时控制，限制了其在机器人运动规划中的应用。
  2. TinySDP通过将正半定锥投影集成到缓存Riccati的ADMM求解器中，并结合后验秩1证书，实现了嵌入式系统上的高效半定规划。
  3. 实验表明，TinySDP在复杂场景下能实现比现有方法更短的无碰撞路径，并在四旋翼飞行器上验证了其实时性。

📝 摘要（中文）

半定规划(SDP)为运动规划中非凸几何约束的凸松弛提供了一个有效的框架，但现有的求解器计算成本过高，无法进行实时控制，尤其是在资源受限的嵌入式系统上。为了解决这一差距，我们推出了TinySDP，这是第一个专为嵌入式系统设计的半定规划求解器，能够在微控制器上进行实时模型预测控制(MPC)，解决具有非凸障碍约束的问题。我们的方法将正半定锥投影集成到基于缓存Riccati的ADMM求解器中，利用计算结构来实现嵌入式系统的可处理性。我们将此求解器与后验秩1证书配对，该证书将松弛解转换为每个时间步的显式几何保证。在具有挑战性的基准测试中，例如，在死胡同和动态避障场景中，这些场景会导致局部方法失效，TinySDP实现了无碰撞导航，其路径比最先进的基线短73%。我们在Crazyflie四旋翼飞行器上验证了我们的方法，证明了半定约束可以以实时速率强制执行，以实现敏捷的嵌入式机器人。

🔬 方法详解

问题定义：论文旨在解决嵌入式系统上实时半定规划求解的难题，特别是在机器人运动规划中处理非凸障碍约束时。现有SDP求解器计算复杂度高，难以满足实时性要求，限制了其在资源受限的机器人平台上的应用。

核心思路：TinySDP的核心思路是针对嵌入式系统的特点，设计高效的SDP求解器。通过将正半定锥投影集成到基于缓存Riccati的ADMM求解器中，并利用问题的计算结构，降低计算复杂度，提高求解速度。同时，采用后验秩1证书，将松弛解转换为显式的几何保证，确保解的有效性。

技术框架：TinySDP的整体框架包括：1) 问题建模：将机器人运动规划问题转化为带有非凸约束的优化问题，并进行凸松弛；2) SDP求解：使用基于缓存Riccati的ADMM求解器求解松弛后的SDP问题；3) 证书验证：利用后验秩1证书验证解的有效性，并将其转化为显式的几何保证；4) 运动控制：根据求解结果，控制机器人进行运动。

关键创新：TinySDP的关键创新在于其针对嵌入式系统设计的SDP求解器。与现有通用SDP求解器相比，TinySDP更加高效，能够在资源受限的平台上实现实时求解。此外，后验秩1证书的使用，保证了松弛解的有效性，避免了因松弛引入的误差。

关键设计：TinySDP的关键设计包括：1) 基于缓存Riccati的ADMM求解器：利用Riccati递归的结构，缓存中间计算结果，减少重复计算；2) 正半定锥投影：高效地将解投影到正半定锥上，保证解的有效性；3) 后验秩1证书：验证解的秩是否为1，从而判断松弛是否有效。具体参数设置和损失函数的设计取决于具体的运动规划问题。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，TinySDP在具有挑战性的场景下，例如死胡同和动态避障，能够实现比现有方法更短的无碰撞路径，路径缩短高达73%。在Crazyflie四旋翼飞行器上的实验验证了TinySDP的实时性，证明了其能够在嵌入式系统上以实时速率强制执行半定约束，实现敏捷的机器人控制。

🎯 应用场景

TinySDP在资源受限的机器人平台上具有广泛的应用前景，例如无人机、移动机器人、自动驾驶等。它可以用于解决复杂的运动规划问题，例如避障、路径规划、轨迹优化等。通过实时求解SDP问题，TinySDP可以提高机器人的自主性和适应性，使其能够在复杂环境中安全可靠地运行。未来，TinySDP有望应用于更多领域，例如智能制造、医疗机器人等。

📄 摘要（原文）

Semidefinite programming (SDP) provides a principled framework for convex relaxations of nonconvex geometric constraints in motion planning, yet existing solvers are too computationally expensive for real-time control, particularly on resource-constrained embedded systems. To address this gap, we introduce TinySDP, the first semidefinite programming solver designed for embedded systems, enabling real-time model-predictive control (MPC) on microcontrollers for problems with nonconvex obstacle constraints. Our approach integrates positive-semidefinite cone projections into a cached-Riccati-based ADMM solver, leveraging computational structure for embedded tractability. We pair this solver with an a posteriori rank-1 certificate that converts relaxed solutions into explicit geometric guarantees at each timestep. On challenging benchmarks, e.g., cul-de-sac and dynamic obstacle avoidance scenarios that induce failures in local methods, TinySDP achieves collision-free navigation with up to 73% shorter paths than state-of-the-art baselines. We validate our approach on a Crazyflie quadrotor, demonstrating that semidefinite constraints can be enforced at real-time rates for agile embedded robotics.