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

Engineering notes

TinySDP is suitable for applications in agile robotics where rapid and reliable decision-making is critical, such as drone navigation in dynamic environments. Its real-time capability allows it to effectively handle complex obstacle avoidance problems.

Chinese explanation / 中文解读

TinySDP是一种设计用于嵌入式系统的半正定规划求解器，能够实现实时的模型预测控制，并解决非凸障碍约束的问题。它结合了缓存的Riccati基础的ADMM求解器和后验的秩-1证书，确保每个时间步都能提供几何保证。通过在Crazyflie四旋翼上的验证，TinySDP能够提高碰撞避免能力且路径更短。

Original abstract

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.

Links and sources

• Official / arXiv page
• PDF from original source

Comments