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

Ishaan Mahajan1, Jon Arrizabalaga2,‡, Andrea Grillo3,4,‡, Fausto Vega2,‡, James Anderson1,†, Zachary Manchester2,†, and Brian Plancher3

1Columbia University, USA 2Massachusetts Institute of Technology, USA 3Dartmouth College, USA 4Ecole Polytechnique Federale de Lausanne (EPFL), Switzerland

‡Equal contribution    †Equal advising

Paper Code

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.

TinySDP 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 such as 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 the approach on a Crazyflie quadrotor, demonstrating that semidefinite constraints can be enforced at real-time rates for agile embedded robotics.

Experiments

We designed the evaluation around obstacle-avoidance geometries that are known to break local and reactive methods: a static U-shaped cul-de-sac, a dynamic moving-gap benchmark, dynamic 3D sphere scenarios, and embedded Crazyflie deployment. We compare TinySDP against TinyMPC-LIN, TinyMPC-HOCBF, and RPCBF under matched dynamics, input bounds, horizon length, and obstacle geometry. Zero-margin baselines are reported directly, and tuned-margin variants are included to show the best-case performance local methods can reach when given impractically large safety buffers.

Simulation: Static U-Shape Cul-de-Sac

TinySDP consistently escapes the cul-de-sac and reaches the true goal across all four initial conditions. The zero-margin linearized and HOCBF baselines fail in every case, while tuned TinyMPC-LIN requires a margin large enough to push the optimizer away from the actual goal. RPCBF remains safe but is substantially more conservative.

Static U-shape trajectories across four start conditions, comparing TinySDP, RPCBF, TinyMPC-LIN, and TinyMPC-HOCBF.
Static U-shape benchmark. TinySDP consistently navigates the cul-de-sac to reach the goal. RPCBF is safe but conservative, while the linearized and HOCBF baselines either crash, get stuck, or require impractically large margins.
Start: Inside
MethodPath LenGoal DistSafe
TinySDP (ours)17.950.006✓
RPCBF26.030.091✓
TinyMPC-LIN (m=3.1m)18.381.400✓
TinyMPC-LIN (m=0m)——✗
TinyMPC-HOCBF (m=3m)——✗
TinyMPC-HOCBF (m=0m)——✗
Start: Outside Center
MethodPath LenGoal DistSafe
TinySDP (ours)10.150.021✓
RPCBF31.030.093✓
TinyMPC-LIN (m=3.1m)24.581.400✓
TinyMPC-LIN (m=0m)——✗
TinyMPC-HOCBF (m=3m)——✗
TinyMPC-HOCBF (m=0m)——✗
Start: Edge Up
MethodPath LenGoal DistSafe
TinySDP (ours)9.930.023✓
RPCBF36.810.132✓
TinyMPC-LIN (m=3.1m)18.581.400✓
TinyMPC-LIN (m=0m)——✗
TinyMPC-HOCBF (m=3m)——✗
TinyMPC-HOCBF (m=0m)——✗
Start: Edge Down
MethodPath LenGoal DistSafe
TinySDP (ours)9.930.023✓
RPCBF36.250.108✓
TinyMPC-LIN (m=3.1m)23.641.400✓
TinyMPC-LIN (m=0m)——✗
TinyMPC-HOCBF (m=3m)——✗
TinyMPC-HOCBF (m=0m)——✗

Simulation: Dynamic Obstacles

In the moving-gap benchmark, TinySDP anticipates the obstacle motion and deviates early enough to keep positive clearance. The zero-margin local baselines collide, while tuned-margin variants achieve safety only by inflating the obstacle footprint far beyond what is usable on small agile platforms.

Dynamic moving-gap benchmark comparing TinySDP, RPCBF, TinyMPC-LIN, and TinyMPC-HOCBF.
Dynamic moving-gap benchmark. TinySDP actively negotiates the moving obstacle while maintaining goal accuracy. RPCBF remains safe but conservative, and the tuned local baselines rely on large margins.
Dynamic obstacle results.
Method Goal Dist Safe
TinySDP (ours) 0.018 ✓
RPCBF 0.069 ✓
TinyMPC-LIN (m=1.5m) 0.023 ✓
TinyMPC-LIN (m=0m) — ✗
TinyMPC-HOCBF (m=3m) 0.077 ✓
TinyMPC-HOCBF (m=0m) — ✗

Simulation: Extension to 3D Obstacle Avoidance

The same PSD lifting extends naturally from planar disks to 3D spheres. We illustrate this on two dynamic sphere scenarios: Sweeping Barrier, where a lateral sweep blocks the direct route, and Vertical Gate, where a time-varying opening forces a timed ascent-descent maneuver.

Sweeping barrier 3D diagnostic views.
Sweeping Barrier. TinySDP executes an early nonplanar deviation to avoid moving spheres.
Vertical gate 3D diagnostic views.
Vertical Gate. TinySDP times a 3D ascent-descent maneuver through a changing spherical gap.

Real-World Deployment: Crazyflie Safety Certificate

On Crazyflie hardware, TinySDP runs onboard in the control loop while maintaining the rank-1 certificate online. The deployed solver enforces the PSD constraint on the lifted planar position block and keeps the trace-gap certificate valid throughout flight.

Crazyflie hardware deployment with moving obstacle.
Crazyflie deployment. TinySDP runs onboard and reacts to the moving obstacle while tracking the commanded path.
Rank-1 certificate evolution during Crazyflie deployment.
Rank-1 certificate during deployment. The lifted margin stays positive while the trace gap remains near zero, providing an online certificate of geometric safety.

Citation

BibTeX

@misc{mahajan2026tinysdp,
  title        = {TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics},
  author       = {Mahajan, Ishaan and Arrizabalaga, Jon and Grillo, Andrea and Vega, Fausto and Anderson, James and Manchester, Zachary and Plancher, Brian},
  year         = {2026},
  note         = {arXiv version},
  url          = {https://github.com/A2R-Lab/TinySDP}
}