Technical Summary: TinySDP

Problem Statement

Safe motion planning and control in dynamic environments remain a significant challenge for robotics, particularly on resource-constrained embedded systems. While Model-Predictive Control (MPC) is effective for reasoning about system dynamics and constraints, enforcing formal safety guarantees for nonconvex obstacle avoidance is difficult in real-time. Existing approaches often rely on conservative over-approximations (e.g., linearized distance constraints) or local convexifications that fail to capture global geometric structures. These methods are prone to failure in scenarios involving narrow passages, cul-de-sacs, or dynamic obstacles, often requiring extensive heuristic tuning of safety margins that inflate the robot's effective footprint. Conversely, while Semidefinite Programming (SDP) offers a principled framework for convexifying nonconvex geometric constraints via lifting, general-purpose SDP solvers are computationally expensive and memory-intensive, making them unsuitable for real-time receding-horizon control on microcontrollers.

Methodology

The authors introduce TinySDP, the first semidefinite programming solver designed specifically for embedded systems to enable real-time, certifiable obstacle avoidance. The approach integrates three core components:

1. Structured Lifting and Relaxation

TinySDP formulates the MPC problem using a per-stage, convex, semidefinite relaxation of nonconvex, quadratic, disk-based obstacle avoidance constraints.

• Lifting: The method lifts the geometric state (e.g., planar position $p_k$) into a higher-dimensional positive semidefinite (PSD) cone. Specifically, it introduces auxiliary variables for the outer products of states and inputs (e.g., $X_k = x_k x_k^\top$).
• Linearization: This lifting transforms quadratic obstacle constraints (e.g., $\|p_k - c_j\|^2 \geq r_j^2$) into linear affine inequalities in the lifted variables, while maintaining the linear dynamics of the system in the lifted space.
• Relaxation: The exact rank-1 constraint on the moment matrix is relaxed to a PSD constraint ($M_k \succeq 0$), rendering the problem convex.

2. Riccati-Based ADMM Solver

To solve the resulting convex problem efficiently on embedded hardware, the authors extend the TinyMPC framework (which uses cached Riccati recursions) to handle per-stage PSD constraints.

• Algorithm: The solver utilizes the Alternating Direction Method of Multipliers (ADMM).
• Primal Update: The primal subproblem is a lifted Linear Quadratic Regulator (LQR) problem. Crucially, the system dynamics remain linear in the lifted variables, allowing the use of efficient backward-forward Riccati sweeps with pre-computed, cached steady-state quantities.
• Slack and Dual Updates: The PSD constraints are handled via a projection step. At each ADMM iteration, the solver computes the Euclidean projection of a matrix onto the PSD cone (via eigen-decomposition and eigenvalue clamping) and updates the dual variables. This projection is performed per-stage, preserving the computational structure required for real-time execution.

3. A Posteriori Rank-1 Safety Certificate

To address the looseness introduced by the SDP relaxation, the paper proposes a simple, computationally cheap certificate evaluated at every timestep.

• Trace Gap: The certificate measures the "trace gap" ($\Delta_k$), defined as the difference between the trace of the lifted position block and the squared norm of the physical position ($\text{trace}(X^{(p)}_k) - \|p_k\|^2$).
• Certification Logic: If the lifted margin (the value of the linearized obstacle constraint) is non-negative and the trace gap is sufficiently small relative to this margin, the solution is certified to be collision-free.
• Fallback: If the certificate fails, the system discards the planned control input and executes a reactive fallback policy (stop-and-hover), ensuring that uncertified commands are never applied to the physical robot.

Key Contributions

1. TinySDP Solver: The development of the first embedded SDP solver that leverages cached Riccati structures to solve PSD-relaxed MPC problems in real-time.
2. Integration of Relaxation and Certification: A framework that couples efficient convex relaxation with an explicit, a posteriori geometric safety certificate, bridging the gap between theoretical optimality and practical safety guarantees.
3. Hardware Validation: Successful deployment on a Crazyflie 2.1 quadrotor (STM32F405 microcontroller) running at 25 Hz control rates, demonstrating that semidefinite constraints can be enforced on resource-constrained platforms.

Experimental Results

The authors evaluated TinySDP against state-of-the-art baselines (TinyMPC-LIN, TinyMPC-HOCBF, and RPCBF) in simulation and real-world hardware.

• Static U-Shaped Cul-de-Sac: In scenarios designed to cause deadlock for local methods, TinySDP achieved collision-free navigation with path lengths 31–73% shorter than the best-performing baseline (RPCBF). Baseline methods either collided (with zero safety margin) or required impractically large safety margins (up to 30× the drone's size) to succeed, which inflated the collision footprint and prevented reaching the goal.
• Dynamic Obstacle Avoidance: In dynamic scenarios with moving obstacles closing narrow passages, TinySDP successfully anticipated and avoided collisions. It produced paths 30% shorter than RPCBF and maintained higher precision (closer to the goal) than baselines.
• 3D Extension: The authors demonstrated that the lifting framework extends naturally to 3D spherical obstacles, successfully navigating dynamic 3D scenarios in simulation.
• Real-World Deployment: On the Crazyflie, the solver executed 5 ADMM iterations within ~14.8 ms (leaving ~25 ms margin in a 40 ms control period). The memory footprint was modest (approx. 1.47 KB static memory overhead for PSD logic). In five independent trials involving a moving robotic arm, the online safety certificate remained valid at every timestep, confirming the preservation of rank-1 geometry under real-world disturbances.

Significance and Claims

The paper claims that TinySDP demonstrates that semidefinite constraints are not inherently incompatible with real-time receding-horizon control on embedded systems. By exploiting specific problem structures (Riccati dynamics) and separating optimization from certification, the authors show that it is possible to move beyond conservative linear approximations without sacrificing computational tractability.

The work bridges the gap between offline semidefinite planning and practical embedded deployment. It suggests that richer convex safety models can be integrated into high-rate controllers if the solver design respects the underlying MPC structure. The authors position this as a step toward enabling "agile" edge robotics that can navigate complex, nonconvex environments with formal safety guarantees, rather than relying on heuristic tuning or learning-based methods that may be infeasible to deploy on small embedded platforms.

The authors remain modest regarding limitations, noting that the certificate provides a per-timestep check rather than a formal closed-loop recursive feasibility guarantee, and that extending the full 3D capability to microcontrollers remains a challenge due to increased computational costs for larger PSD projections.