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

Ishaan Mahajan 1 , Jon Arrizabalaga 2,‡ , Andrea Grillo 3,4,‡ , Fausto Vega 2,‡ , James Anderson 1,† , Zachary Manchester 2,† , and Brian Plancher 3 · 2026

Read TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics by Ishaan Mahajan 1 , Jon Arrizabalaga 2,‡ , Andrea Grillo 3,4,‡ , Fausto Vega 2,‡ , James Anderson 1,† , Zachary Manchester 2,† , and Brian Plancher 3 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13748.txt.

Introduction

Ishaan Mahajan and six colleagues introduce TinySDP, the first semidefinite coding solver built for on-chip systems. TinySDP mixes SDP cone casts into a cached-Riccati-based ADMM solver, using compute shape for on-chip ease. An after-the-fact rank-1 proof turns relaxed solutions into plain shape pledges at each timestep. On cul-de-sac and moving blocker dodging tests, TinySDP achieves crash-free driving with paths up to 73 percent shorter than state-of-the-art rivals. A drone test shows SDP limits held at real-time rates.

Catalog record

CREATORIshaan Mahajan 1 , Jon Arrizabalaga 2,‡ , Andrea Grillo 3,4,‡ , Fausto Vega 2,‡ , James Anderson 1,† , Zachary Manchester 2,† , and Brian Plancher 3
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45521
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13748

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics Ishaan Mahajan 1 , Jon Arrizabalaga 2,‡ , Andrea Grillo 3,4,‡ , Fausto Vega 2,‡ , James Anderson 1,† , Zachary Manchester 2,† , and Brian Plancher 3 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. Project Website: https://a2r-lab.org/TinySDP/ I Introduction Fig. 1: Front (top) and side (bottom) views of the Crazyflie running TinySDP online to avoid a moving arm. Left to right: before, during, and after avoiding the moving obstacle. Safe motion planning and control in dynamic environments remains a challenge in robotics. Model-predictive control (MPC) is attractive for this setting due to its ability to reason about system dynamics and constraints (e.g., obstacle avoidance), and has been demonstrated on a wide range of robotic problems across numerous tasks and scenarios [ 21 , 8 , 13 , 49 , 36 , 37 , 38 , 6 , 2 , 25 , 28 , 19 ] . Recent advances in embedded optimization have expanded the scope of MPC on resource-constrained platforms [ 14 , 24 , 20 ] , including the development of popular packages, e.g., OSQP [ 46 ] , CVXGEN [ 35 ] , ECOS [ 10 ] , SCS [ 39 ] . In particular, TinyMPC [ 38 ] demonstrated that constrained quadratic MPC can be solved at high rates on microcontrollers by exploiting the Riccati structure through a combination of offline caching and first-order methods. Building on this foundation, subsequent work [ 32 , 31 ] improved the robustness of the solver and added support for second-order cone constraints. Despite this progress, obstacle avoidance with formal guarantees remains an open problem in embedded MPC, particularly because obstacle constraints are inherently nonconvex. As such, existing real-time MPC implementations rely on conservative over-approximations or local convexifications that fail to capture global geometric structure and are fragile in practice (e.g., linearized distance constraints and tangent half-spaces [ 44 , 45 , 29 , 38 ] ). This is because solutions that satisfy such approximations can still tunnel through obstacles, requiring extensive heuristic tuning of scenario-specific safety margins, and often still fail in the presence of narrow passages, cul-de-sacs, or dynamic obstacles [ 53 , 47 ] . Similarly, while barrier function based methods are also widely used for obstacle avoidance and collision avoidance, crafting effective barrier functions also relies on significant tuning [ 1 , 52 , 51 ] . And, while Hamilton Jacobi (HJ) reachability tools can be used to construct tuning-free barrier functions, these tools do not scale well to high-dimensional systems [ 48 , 7 ] . More recently, learning-based barrier functions leveraging neural networks have been developed to overcome the dual scalability and tuning challenges. However, deploying the resulting moderate-sized neural networks for real-time applications is often infeasible on embedded platforms [ 9 , 27 ] . In contrast, semidefinite programming (SDP) provides a principled way to pose nonconvex geometric constraints as convex by lifting quadratic or polynomial constraints into higher-dimensional positive semidefinite cones, and has been successfully applied in offline motion planning and trajectory optimization [ 22 , 42 , 18 , 33 , 34 , 11 , 41 ] , globally optimal state estimation and localization [ 12 , 17 ] , and sum-of-squares optimization with tools like SOSTOOLS [ 40 ] . However, as with many of the prior techniques, general-purpose SDP solvers are computationally expensive and memory-intensive. As such, they are generally poorly suited for real-time receding horizon control, particularly for embedded applications [ 50 , 34 ] . In this work, we show that it is possible to overcome these challenges through careful exploitation of problem structure. We introduce TinySDP, the first semidefinite programming solver designed for real-time obstacle avoidance on embedded systems. Our approach uses a per-stage, convex, semidefinite relaxation of nonconvex, quadratic, disk-based obstacle avoidance constraints. These relaxations are small, structured, and compatible with Riccati-based MPC solvers, including cached variants [ 38 ] . We pair this with a simple rank-1 certificate that converts the relaxed solution into an explicit geometric safety guarantee at every timestep. When the certificate holds, it provably certifies that the true robot position avoids all obstacles, despite the use of an efficient convex relaxation. Our approach builds on prior observations that lifted convex relaxations are empirically tight in structured control problems [ 3 ] . In particular, lifted semidefinite formulations of linear-quadratic control problems recover low-rank solutions, providing exact certificates of optimality [ 4 , 30 ] . We evaluate TinySDP on two challenging benchmark tasks that are designed to expose common failure modes for standard formulations: 1) a static U-shaped cul-de-sac and, 2) multiple dynamic moving-gap scenarios. Through systematic comparisons, we show that our method is less conservative, with path lengths up to 73% shorter than baseline approaches, while also remaining certifiably collision-free at each timestep through the use of our a posteriori rank-1 safety certificate. We also implement the full solver within the TinyMPC framework [ 38 ] , and validate our algorithm through real-world hardware deployments on a Crazyflie 2.1 Brushless quadrotor at 25 Hz control rates, demonstrating that semidefinite constraints can be enforced at real-time rates for embedded robotic tasks. II Background We review prior work on embedded MPC, with emphasis on cached Riccati-based solvers and operator-splitting methods, as well as convex relaxations for nonconvex quadratic constraints, providing the foundation for TinySDP (Section III ). II-A Linear, Cached, and Riccati-Based MPC Solvers We highlight the components of the generic finite-horizon MPC problem that prevent a closed-form solution. Consider a discrete-time linear time-invariant system with state x_{k}\in\mathbb{R}^{n} and control input u_{k}\in\mathbb{R}^{m} at timestep k , x_{k+1}=Ax_{k}+Bu_{k}, where A\in\mathbb{R}^{n\times n} and B\in\mathbb{R}^{n\times m} define the system dynamics. Given a horizon length N , and assuming quadratic stage and terminal costs, for Q\succeq 0 , R\succ 0 , and Q_{f}\succeq 0 , define \ell(x_{k},u_{k})=x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k},\quad\ell_{f}(x_{N})=x_{N}^{\top}Q_{f}x_{N}, and admissible convex state and control sets, \mathcal{X},\mathcal{U} , the finite-horizon MPC problem is: \displaystyle\min_{\{x_{k},u_{k}\}}\quad \displaystyle\ell_{f}(x_{N})+\sum_{k=0}^{N-1}\ell(x_{k},u_{k}) (1a) s.t. \displaystyle x_{k+1}=Ax_{k}+Bu_{k}, (1b) \displaystyle{u_{k}\in\mathcal{U},}\quad{x_{k}\in\mathcal{X}}. (1c) In the absence of the constraints ( 1c ), the problem reduces to an unconstrained linear-quadratic regulator (LQR), which admits a closed-form solution via the discrete-time Riccati recursion [ 26 ] , producing an affine control law: u_{k}=-K_{k}x_{k}-d_{k}, (2) \displaystyle K_{k} \displaystyle=(R+B^{\top}P_{k+1}B)^{-1}B^{\top}P_{k+1}A, (3) \displaystyle d_{k} \displaystyle=(R+B^{\top}P_{k+1}B)^{-1}(B^{\top}p_{k+1}+r_{k}), \displaystyle P_{k} \displaystyle=Q+A^{\top}P_{k+1}A-A^{\top}P_{k+1}BK_{k}, \displaystyle p_{k} \displaystyle=q_{k}+A^{\top}p_{k+1}-A^{\top}P_{k+1}Bd_{k}. The presence of constraints destroys this structure, necessitating

Read the complete text