Recognition: unknown
TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics
Pith reviewed 2026-05-14 18:04 UTC · model grok-4.3
The pith
TinySDP is an embedded semidefinite programming solver that runs real-time model predictive control with explicit collision-avoidance certificates on microcontrollers.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
TinySDP integrates positive-semidefinite cone projections into a cached-Riccati-based ADMM solver and pairs the solver with an a posteriori rank-1 certificate that converts each relaxed solution into explicit geometric guarantees at every time step, thereby enabling real-time model-predictive control on microcontrollers for nonconvex obstacle constraints.
What carries the argument
Cached-Riccati ADMM iteration that incorporates positive-semidefinite cone projections, combined with an a posteriori rank-1 certificate that extracts explicit geometric guarantees from the relaxed solution.
If this is right
- Collision-free navigation succeeds in cul-de-sac and dynamic-obstacle scenarios that cause local planners to fail.
- Paths are up to 73 percent shorter than those produced by state-of-the-art baselines.
- Semidefinite constraints are enforced at real-time rates on agile embedded platforms such as the Crazyflie quadrotor.
- The same framework directly supports model-predictive control with nonconvex geometric obstacle constraints.
Where Pith is reading between the lines
- The same solver structure could be applied to other nonconvex constraints that admit SDP relaxations, such as attitude or contact constraints.
- Certification at every step makes the controller suitable for safety-critical edge deployments where formal guarantees are required.
- Because the method is built around cached Riccati structure, it may scale to multi-robot coordination problems that share the same quadratic cost.
Load-bearing premise
That the positive-semidefinite projections inside the cached ADMM loop remain fast enough on microcontrollers while the rank-1 certificate reliably converts relaxed solutions into correct geometric constraints.
What would settle it
A run on the Crazyflie in which either the solver exceeds the real-time deadline or the generated trajectory collides with an obstacle in the cul-de-sac benchmark.
Figures
read the 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces TinySDP, the first SDP solver for embedded systems, which integrates positive-semidefinite cone projections into a cached-Riccati-based ADMM solver and uses an a posteriori rank-1 certificate to convert relaxed solutions into geometric guarantees for real-time MPC in robotics with nonconvex obstacles. It reports up to 73% shorter collision-free paths than baselines in benchmarks like cul-de-sac and dynamic obstacle avoidance, and validates the approach on a Crazyflie quadrotor for real-time performance.
Significance. If the performance claims and certificate reliability hold, this work would significantly advance certifiable optimization-based control for resource-constrained embedded robotics, enabling safer agile navigation where local methods fail.
major comments (2)
- [Abstract] Abstract: The quantitative claim of 'up to 73% shorter paths' is presented without error bars, full experimental protocol, or implementation details, making it difficult to assess the robustness of the benchmark improvements.
- [Abstract (a posteriori rank-1 certificate)] Abstract (a posteriori rank-1 certificate): The paper relies on the a posteriori rank-1 certificate to provide explicit collision-free guarantees from relaxed SDP solutions, but provides no analytic bound on the tightness for nonconvex obstacle constraints or coverage of failure cases where the relaxation admits higher-rank solutions or duality gaps; this is load-bearing for the collision-free navigation claims.
minor comments (1)
- [Abstract] The abstract mentions 'challenging benchmarks, e.g., cul-de-sac and dynamic obstacle avoidance scenarios' but does not specify the exact baselines compared against.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Positive-semidefinite cone projections combined with cached Riccati recursions inside ADMM remain computationally feasible at real-time rates on resource-constrained microcontrollers.
Reference graph
Works this paper leans on
-
[1]
Aaron D Ames, Xiangru Xu, Jessy W Grizzle, and Paulo Tabuada. Control barrier function based quadratic programs for safety critical systems.IEEE Transactions on Automatic Control, 62(8):3861–3876, 2016
work page 2016
-
[2]
Manel Ammour, Rodolfo Orjuela, and Michel Basset. A mpc combined decision making and trajectory plan- ning for autonomous vehicle collision avoidance.IEEE Transactions on Intelligent Transportation Systems, 23 (12):24805–24817, 2022
work page 2022
-
[3]
Bassam Bamieh. Linear-quadratic problems in sys- tems and controls via covariance representations and linear-conic duality: Finite-horizon case.arXiv preprint arXiv:2401.01422, 2024
-
[4]
Nicolas Boumal, Vladislav V oroninski, and Afonso S Bandeira. Deterministic guarantees for burer-monteiro factorizations of smooth semidefinite programs.Com- munications on Pure and Applied Mathematics, 73(3): 581–608, 2020
work page 2020
-
[5]
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers.Foundations and Trends® in Machine learning, 3(1):1–122, 2011
work page 2011
-
[6]
A collision-free mpc for whole-body dynamic locomotion and manipulation
Jia-Ruei Chiu, Jean-Pierre Sleiman, Mayank Mittal, Far- bod Farshidian, and Marco Hutter. A collision-free mpc for whole-body dynamic locomotion and manipulation. In2022 international conference on robotics and au- tomation (ICRA), pages 4686–4693. IEEE, 2022
work page 2022
-
[7]
Robust control barrier– value functions for safety-critical control
Jason J Choi, Donggun Lee, Koushil Sreenath, Claire J Tomlin, and Sylvia L Herbert. Robust control barrier– value functions for safety-critical control. In2021 60th IEEE Conference on Decision and Control (CDC), pages 6814–6821. IEEE, 2021
work page 2021
-
[8]
Mpc: Current practice and challenges.Control Engineering Practice, 20(4):328–342, 2012
Mark L Darby and Michael Nikolaou. Mpc: Current practice and challenges.Control Engineering Practice, 20(4):328–342, 2012
work page 2012
-
[9]
Safe nonlinear control using robust neural lyapunov- barrier functions
Charles Dawson, Zengyi Qin, Sicun Gao, and Chuchu Fan. Safe nonlinear control using robust neural lyapunov- barrier functions. In Aleksandra Faust, David Hsu, and Gerhard Neumann, editors,Proceedings of the 5th Conference on Robot Learning, volume 164 ofProceed- ings of Machine Learning Research, pages 1724–1735. PMLR, 08–11 Nov 2022. URL https://proceedi...
work page 2022
-
[10]
A. Domahidi, E. Chu, and S. Boyd. ECOS: An SOCP solver for embedded systems. InIEEE European Control Conference (ECC), 2013
work page 2013
-
[11]
Shiying Dong, Zhipeng Shen, Rudolf Reiter, Hailong Huang, Bingzhao Gao, Hong Chen, and Wen-Hua Chen. A fast semidefinite convex relaxation for optimal control problems with spatio-temporal constraints.arXiv preprint arXiv:2601.03055, 2026
-
[12]
Frederike D ¨umbgen, Connor Holmes, Ben Agro, and Timothy Barfoot. Toward globally optimal state esti- mation using automatically tightened semidefinite relax- ations.IEEE Transactions on Robotics, 40:4338–4358, 2024
work page 2024
-
[13]
Pampc: Perception-aware model predictive control for quadrotors
Davide Falanga, Philipp Foehn, Peng Lu, and Davide Scaramuzza. Pampc: Perception-aware model predictive control for quadrotors. In2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1–8. IEEE, 2018
work page 2018
-
[14]
Hand Joachim Ferreau, Stefan Alm ´er, Robin Ver- schueren, Moritz Diehl, Damian Frick, Alexander Dom- ahidi, JL Jerez, Giorgos Stathopoulos, and Colin Jones. Embedded optimization methods for industrial automatic control.IFAC-PapersOnLine, 50(1):13194–13209, 2017
work page 2017
-
[15]
Dieter Fox, Wolfram Burgard, and Sebastian Thrun. The dynamic window approach to collision avoidance.IEEE robotics & automation magazine, 4(1):23–33, 2002
work page 2002
-
[16]
Crazyflie 2.0 quadrotor as a platform for research and education in robotics and control engineering
Wojciech Giernacki, Mateusz Skwierczy ´nski, Wojciech Witwicki, Paweł Wro´nski, and Piotr Kozierski. Crazyflie 2.0 quadrotor as a platform for research and education in robotics and control engineering. In2017 22nd interna- tional conference on methods and models in automation and robotics (MMAR), pages 37–42. IEEE, 2017
work page 2017
-
[17]
Antoine Groudiev, Fabian Schramm, ´Elo¨ıse Berthier, Justin Carpentier, and Frederike D ¨umbgen. Sampling- based global optimal control and estimation via semidef- inite programming.arXiv preprint arXiv:2507.17572, 2025
-
[18]
Springer Science & Business Media, 2005
Didier Henrion and Andrea Garulli.Positive polynomials in control, volume 312. Springer Science & Business Media, 2005
work page 2005
-
[19]
Altro-c: A fast solver for conic model-predictive control
Brian E Jackson, Tarun Punnoose, Daniel Neamati, Kevin Tracy, Rianna Jitosho, and Zachary Manchester. Altro-c: A fast solver for conic model-predictive control. InIEEE International Conference on Robotics and Automation (ICRA), Xi’an, China, May 2021
work page 2021
-
[20]
Juan L Jerez, Paul J Goulart, Stefan Richter, George A Constantinides, Eric C Kerrigan, and Manfred Morari. Embedded online optimization for model predictive con- trol at megahertz rates.IEEE Transactions on Automatic Control, 59(12):3238–3251, 2014
work page 2014
- [21]
-
[22]
Global contact-rich planning with sparsity-rich semidefinite re- laxations
Shucheng Kang, Guorui Liu, and Heng Yang. Global contact-rich planning with sparsity-rich semidefinite re- laxations. InRobotics: Science and Systems (RSS), 2025
work page 2025
-
[23]
Luzia Knoedler, Oswin So, Ji Yin, Mitchell Black, Zachary Serlin, Panagiotis Tsiotras, Javier Alonso-Mora, and Chuchu Fan. Safety on the fly: Constructing robust safety filters via policy control barrier functions at run- time.IEEE Robotics and Automation Letters, 2025
work page 2025
-
[24]
First-order methods in em- bedded nonlinear model predictive control
Dimitris Kouzoupis, Hans Joachim Ferreau, Helfried Peyrl, and Moritz Diehl. First-order methods in em- bedded nonlinear model predictive control. In2015 European Control Conference (ECC), pages 2617–2622. IEEE, 2015
work page 2015
-
[25]
Scott Kuindersma, Robin Deits, Maurice Fallon, Andr ´es Valenzuela, Hongkai Dai, Frank Permenter, Twan Koolen, Pat Marion, and Russ Tedrake. Optimization- based locomotion planning, estimation, and control de- sign for the atlas humanoid robot.Autonomous robots, 40:429–455, 2016
work page 2016
-
[26]
Lewis, Draguna Vrabie, and V .L
Frank L. Lewis, Draguna Vrabie, and V .L. Syrmos. Optimal Control, 1 2012
work page 2012
-
[27]
Safe control under input limits with neural control barrier functions
Simin Liu, Changliu Liu, and John Dolan. Safe control under input limits with neural control barrier functions. InConference on Robot Learning, pages 1970–1980. PMLR, 2023
work page 1970
-
[28]
Xinfu Liu, Zuojun Shen, and Ping Lu. Entry trajectory optimization by second-order cone programming.Jour- nal of Guidance, Control, and Dynamics, 39(2):227–241, 2016
work page 2016
-
[29]
Tomas Lozano-Perez. Spatial planning: A configuration space approach.IEEE transactions on computers, 32(02): 108–120, 1983
work page 1983
-
[30]
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estima- tion: Gradient descent converges linearly for phase re- trieval and matrix completion. InInternational Confer- ence on Machine Learning, pages 3345–3354. PMLR, 2018
work page 2018
-
[31]
Robust and efficient embedded convex optimization through first-order adap- tive caching
Ishaan Mahajan and Brian Plancher. Robust and efficient embedded convex optimization through first-order adap- tive caching. InIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2025
work page 2025
-
[32]
Ishaan Mahajan, Khai Nguyen, Sam Schoedel, Elakhya Nedumaran, Moises Mata, Brian Plancher, and Zachary Manchester. Code generation and conic constraints for model-predictive control on microcontrollers with conic- tinympc, 2025
work page 2025
-
[33]
Anirudha Majumdar and Russ Tedrake. Funnel libraries for real-time robust feedback motion planning.The International Journal of Robotics Research, 36(8):947– 982, 2017
work page 2017
-
[34]
Motion planning around obstacles with convex optimization.Science robotics, 8(84):eadf7843, 2023
Tobia Marcucci, Mark Petersen, David von Wrangel, and Russ Tedrake. Motion planning around obstacles with convex optimization.Science robotics, 8(84):eadf7843, 2023
work page 2023
-
[35]
Jacob Mattingley and Stephen Boyd. Cvxgen: A code generator for embedded convex optimization.Optimiza- tion and Engineering, 13:1–27, 2012
work page 2012
-
[36]
KN McGuire, Christophe De Wagter, Karl Tuyls, HJ Kappen, and Guido CHE de Croon. Minimal nav- igation solution for a swarm of tiny flying robots to explore an unknown environment.Science Robotics, 4 (35):eaaw9710, 2019
work page 2019
-
[37]
Kunal S Narkhede, Abhijeet M Kulkarni, Dhruv A Thanki, and Ioannis Poulakakis. A sequential mpc approach to reactive planning for bipedal robots using safe corridors in highly cluttered environments.IEEE Robotics and Automation Letters, 7(4):11831–11838, 2022
work page 2022
-
[38]
Tinympc: Model- predictive control on resource-constrained microcon- trollers
Khai Nguyen, Sam Schoedel, Anoushka Alavilli, Brian Plancher, and Zachary Manchester. Tinympc: Model- predictive control on resource-constrained microcon- trollers. InIEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan, May. 2024
work page 2024
-
[39]
Brendan O’Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Op- timization Theory and Applications, 169(3):1042–1068, June 2016
work page 2016
-
[40]
Antonis Papachristodoulou, James Anderson, Giorgio Valmorbida, Stephen Prajna, Pete Seiler, Pablo Parrilo, Matthew M Peet, and Declan Jagt. Sostools version 4.00 sum of squares optimization toolbox for matlab.arXiv preprint arXiv:1310.4716, 2013
- [41]
-
[42]
URL https://github.com/alanpapalia/ Intro-Certifiable-Robotics
-
[43]
Exploiting algebraic structure in sum of squares programs
Pablo A Parrilo. Exploiting algebraic structure in sum of squares programs. InPositive polynomials in control, pages 181–194. Springer, 2005
work page 2005
-
[44]
Vignesh Rajagopal, Kasun Weerakoon Kulathun Mudiyanselage, Gershom Devake Seneviratne, Pon Aswin Sankaralingam, Mohamed Elnoor, Jing Liang, Rohan Chandra, and Dinesh Manocha. Dr. nav: Semantic-geometric representations for proactive dead-end recovery and navigation.arXiv preprint arXiv:2511.12778, 2025
-
[45]
Aircraft tra- jectory planning with collision avoidance using mixed integer linear programming
Arthur Richards and Jonathan P How. Aircraft tra- jectory planning with collision avoidance using mixed integer linear programming. InProceedings of the 2002 American control conference (IEEE Cat. No. CH37301), volume 3, pages 1936–1941. IEEE, 2002
work page 2002
-
[46]
Mixed integer programming for multi- vehicle path planning
Tom Schouwenaars, Bart De Moor, Eric Feron, and Jonathan How. Mixed integer programming for multi- vehicle path planning. In2001 European control confer- ence (ECC), pages 2603–2608. IEEE, 2001
work page 2001
-
[47]
Bartolomeo Stellato, Goran Banjac, Paul Goulart, Al- berto Bemporad, and Stephen Boyd. Osqp: an operator splitting solver for quadratic programs.Mathematical Programming Computation, 12(4):637–672, 2020. ISSN 1867-2957. doi: 10.1007/s12532-020-00179-2
-
[48]
Akshay Thirugnanam, Jun Zeng, and Koushil Sreenath. Safety-critical control and planning for obstacle avoid- ance between polytopes with control barrier functions. In2022 International Conference on Robotics and Au- tomation (ICRA), pages 286–292, 2022. doi: 10.1109/ ICRA46639.2022.9812334
-
[49]
Refining control barrier functions through hamilton-jacobi reachability
Sander Tonkens and Sylvia Herbert. Refining control barrier functions through hamilton-jacobi reachability. In 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 13355–13362. IEEE, 2022
work page 2022
-
[50]
Data-driven mpc for quadrotors
Guillem Torrente, Elia Kaufmann, Philipp F ¨ohn, and Davide Scaramuzza. Data-driven mpc for quadrotors. IEEE Robotics and Automation Letters, 2021
work page 2021
-
[51]
Semidefinite programming.SIAM review, 38(1):49–95, 1996
Lieven Vandenberghe and Stephen Boyd. Semidefinite programming.SIAM review, 38(1):49–95, 1996
work page 1996
-
[52]
Constructive safety using control barrier functions.IFAC Proceedings Vol- umes, 40(12):462–467, 2007
Peter Wieland and Frank Allg ¨ower. Constructive safety using control barrier functions.IFAC Proceedings Vol- umes, 40(12):462–467, 2007
work page 2007
-
[53]
High-order control barrier functions.IEEE Transactions on Automatic Control, 67 (7):3655–3662, 2021
Wei Xiao and Calin Belta. High-order control barrier functions.IEEE Transactions on Automatic Control, 67 (7):3655–3662, 2021
work page 2021
-
[54]
In: ACC (2021).https://doi.org/10
Jun Zeng, Bike Zhang, and Koushil Sreenath. Safety- critical model predictive control with discrete-time con- trol barrier function. In2021 American Control Con- ference (ACC), pages 3882–3889, 2021. doi: 10.23919/ ACC50511.2021.9483029
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.