TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics
Source: arXiv:2605.13748 · Published 2026-05-13 · By Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo, Fausto Vega, James Anderson, Zachary Manchester et al.
TL;DR
TinySDP addresses the longstanding challenge of enforcing semidefinite programming (SDP) constraints for certifiable obstacle avoidance in real-time embedded model-predictive control (MPC). While SDP relaxations are powerful for convexifying nonconvex geometric constraints in motion planning, existing SDP solvers are computationally too demanding for embedded systems, particularly for agile robotics. TinySDP overcomes this by introducing a lifted MPC formulation that preserves Riccati recursion structure, combined with an efficient ADMM solver that interleaves Riccati updates with Euclidean projections onto positive semidefinite (PSD) cones. This enables real-time control with embedded constraints that certify obstacle avoidance robustly, even in complex dynamic and concave environments that cause failures in standard local or barrier-based MPC approaches.
Empirical evaluation on challenging benchmarks—a static cul-de-sac and dynamic moving-gap scenarios—demonstrates TinySDP's ability to navigate collision-free with path lengths up to 73% shorter than state-of-the-art sampling-based safety filters and 2–59% shorter than linearized MPC approaches with impractically large safety margins. The approach also exhibits sub-centimeter goal precision and a simple a posteriori rank-1 certificate to guarantee solution tightness and safety at each step. Crucially, TinySDP is deployed on a Crazyflie quadrotor running on a 168 MHz STM32F405 microcontroller, achieving 25 Hz control with full semidefinite constraints enforced onboard, demonstrating feasibility for real embedded robotics applications.
Key findings
- TinySDP achieves path length reductions of up to 73% compared to RPCBF baseline in static cul-de-sac scenarios (Table I).
- Rank-1 certificate ensures certifiable safety: zero collisions across all tested scenarios with explicit a posteriori bounds (Fig 5).
- Dynamic obstacle benchmark shows TinySDP paths 30% shorter than RPCBF and up to 43% shorter than tuned TinyMPC-HOCBF with large safety margins (Table II).
- Tuned TinyMPC-LIN requires 1.5 m conservative margin (17–30× robot size) to be safe, making it impractical for embedded robots.
- TinySDP runs on a Crazyflie microcontroller with a solve time of 14.8 ms per 40 ms control step, using only 272.4 KB flash and 139 KB RAM.
- ADMM solver capped at 5 iterations per timestep suffices for convergence and real-time operation.
- Lifted MPC formulation leverages cached Riccati recursion for efficiency, preserving computational structure allowing embedded feasibility.
- The safety certificate monitors trace gap and obstacle margin; fallback hover policy preserves safety when certification fails.
Threat model
The adversary is implicitly modeled as environmental and obstacle configurations that pose nonconvex collision risks to the robot. The system assumes accurate state and obstacle perception, with no direct adversarial attempts to spoof or corrupt sensor data. The adversary cannot breach the physical constraints or trick the solver beyond what nonconvex geometric constraints allow. The certification and fallback policy protect against solver failures or relaxation looseness but do not cover malicious sensor attacks.
Methodology — deep read
The authors start with a standard linear time-invariant discrete system model for MPC with quadratic costs and input bounds. Obstacles are modeled as unions of disks with a nonconvex quadratic safety constraint on planar position states.
They reformulate the MPC problem by lifting states and inputs into higher-dimensional moment variables representing second-order outer products, encoded as symmetric matrices constrained to be positive semidefinite (PSD). This transforms nonconvex quadratic constraints into convex linear constraints over PSD cones. The lifted variables include original states and controls plus their second-order moments, with per-stage semidefinite constraints enforced.
To solve the PSD-relaxed MPC, the authors embed the problem within an ADMM framework split to separately handle dynamics (primal update via a Riccati recursion) and PSD constraints (via Euclidean PSD projections). The primal step solves a quadratic subproblem with augmented terms from the dual variables leveraging cached steady-state Riccati quantities offline to accelerate on-device solves. The slack update projects stage moment matrices onto PSD cones via eigen-decomposition. The dual update applies scaled gradient ascent.
At runtime, the current state and obstacle geometry lift into the augmented variables. ADMM iterates between the primal Riccati-based update and PSD projections until convergence or iteration cap. The first control input is applied, and the horizon problem re-solved each timestep in a receding horizon manner.
To certify solution quality and ensure safety guarantees, an a posteriori rank-1 certificate is computed at each timestep, measuring the trace gap between the relaxed lifted position moment and the true physical state second moment. If the certificate conditions on trace gap and obstacle clearance margins hold, collision-freedom is guaranteed. If certification fails, the system falls back to a safe hover policy.
Evaluation was conducted on two challenging benchmarks designed to expose local method failures: a static U-shaped cul-de-sac and a dynamic moving-gap obstacle scenario. Comparisons included TinyMPC linearized constraints, control barrier functions, and RPCBF sampling-based safety filters using identical dynamics, horizons, and obstacle sets for fairness. Ablations explored safety margin effects. Additional 3D extension demos illustrated natural applicability to spherical obstacle avoidance.
Lastly, real-world deployment on a Crazyflie quadrotor with 12-dimensional state confirmed embedded feasibility. The STM32F405 MCU ran TinySDP onboard at 25 Hz with a 5-iteration ADMM budget, using 14.8 ms compute time per step. Memory footprints and solver components were tightly optimized to respect microcontroller constraints. The rank-1 certification was verified live to monitor safety online.
The paper provides detailed algorithmic steps (Algorithm 1 and 2), mathematical derivations of lifting, and dual updates, emphasizing computational efficiency and embedded-system considerations. One concrete example end-to-end: the dynamic obstacle avoidance scenario where TinySDP anticipates moving obstacles and modifies trajectory with certified safety guarantees, compared to baselines that fail collision avoidance unless large, impractical margins are used.
Technical innovations
- Introduction of a lifted semidefinite MPC formulation that preserves Riccati recursion structure enabling efficient embedded SDP solves.
- Integration of Euclidean PSD cone projections within cached-Riccati-based ADMM solver iterations for real-time operation on microcontrollers.
- Development of a novel simple a posteriori rank-1 safety certificate based on trace gaps that provides explicit geometric collision guarantees.
- Demonstration of resource-efficient implementation on a 168 MHz STM32F405 MCU with rigorous onboard certification and fallback safety monitor.
Baselines vs proposed
- RPCBF baseline: collision-free navigation, path length = 26.03 m (static), 27.33 m (dynamic) vs TinySDP: 17.95 m (static), 19.11 m (dynamic)
- TinyMPC-LIN (tuned 3.1 m margin): path length = 18.38 m (static) vs TinySDP: 17.95 m
- TinyMPC-HOCBF (tuned 3 m margin): path length = 33.80 m (dynamic) vs TinySDP: 19.11 m
- TinyMPC-LIN (tuned 1.5 m margin, dynamic): path length = 13.61 m vs TinySDP: 19.11 m (slightly longer but more precise goal convergence)
- Safety margins required for TinyMPC-LIN and TinyMPC-HOCBF to avoid collision: 1.5 m and 3 m respectively; impractically large for small-scale robot (~0.1 m size)
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2605.13748.
Fig 1: Front (top) and side (bottom) views of the Crazyflie running TinySDP online to avoid a moving arm. Left to right:
Fig 2: Static U-shape benchmark. Trajectories for TinySDP
Fig 3: Dynamic moving-gap benchmark. Time-lapse com-
Fig 4: 3D dynamic obstacle avoidance extension. TinySDP navigating two dynamic 3D sphere scenarios: Sweeping Barrier
Fig 5: Evolution of the Rank-1 certificate as the Crazyflie
Limitations
- The rank-1 certificate is sufficient but not necessary—certificate failures may reject safe solutions, requiring fallback policies.
- Certification logic is reactive, providing safety monitors rather than formal closed-loop guarantees under extreme dynamics or large model errors.
- 3D extensions increase PSD cone size and computational cost, potentially limiting embedability on constrained hardware.
- Evaluations focus on circular obstacles and quadratic constraints; generalization to arbitrary obstacles or richer constraint types is not fully explored.
- The dynamic obstacle scenarios, though challenging, are still limited in scale; scalability to denser, more cluttered environments remains to be demonstrated.
- No explicit adversarial or worst-case robustness analysis against unpredictable agent/obstacle behaviors.
Open questions / follow-ons
- Can the rank-1 safety certificate be generalized or strengthened to reduce false negatives without compromising soundness?
- How does TinySDP scale with increasing obstacle counts or higher-dimensional lifted spaces in real embedded hardware?
- Can the approach be integrated with perception-state uncertainty or probabilistic obstacle models for robust safety guarantees?
- What are the tradeoffs and performance implications of tighter versus looser semidefinite relaxations in dynamic and cluttered environments?
Why it matters for bot defense
For bot-defense and CAPTCHA practitioners, TinySDP's work offers insights into constructing efficient, certifiable convex relaxations of nonconvex constraints on resource-constrained embedded platforms. While the domain is robotics, similar semidefinite relaxations and ADMM-based solvers could inspire techniques to encode and enforce global, provable constraints in real-time systems with strict latency and memory budgets, such as bot-detection correlation rules or side-channel constraints in authentication flows.
The explicit a posteriori certification method is noteworthy for rapid safety verification, analogous to how CAPTCHA systems might certify challenge results. The use of structure-exploiting Riccati recursion and careful factorization caching points to principled solver designs that balance complexity and embedded feasibility, a critical consideration when deploying bot-defense algorithms on edge devices or browser sandboxes. Translating these solver design principles and safety certification strategies to bot-detection tasks may yield more robust, efficient, and formally verifiable defenses without heavy computation.
Cite
@article{arxiv2605_13748,
title={ TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics },
author={ Ishaan Mahajan and Jon Arrizabalaga and Andrea Grillo and Fausto Vega and James Anderson and Zachary Manchester and Brian Plancher },
journal={arXiv preprint arXiv:2605.13748},
year={ 2026 },
url={https://arxiv.org/abs/2605.13748}
}