MiniSolver: High-Performance Embedded NMPC Library

MiniSolver is a professional-grade, header-only C++17 library for solving Nonlinear Model Predictive Control (NMPC) problems.

Engineered specifically for embedded robotics and autonomous driving, it combines the flexibility of Python-based symbolic modeling with the raw performance of highly optimized, template-generated C++ code. It explicitly guarantees Zero Dynamic Memory Allocation (Zero-Malloc) during the solve phase, making it deterministic and safe for hard real-time systems.

---

🚀 Key Features

⚡ Blazing Fast Performance

• Riccati Recursion: Utilizes a specialized block-tridiagonal linear solver ($O(N)$ complexity) tailored for optimal control structures.
• SQP-RTI Support: Real-Time Iteration (SQP-RTI) mode allows for >1 kHz control loops by performing a single quadratic programming sub-step per control tick.
• Analytical Derivatives: Uses SymPy to generate flattened, algebraically simplified C++ code for Jacobians and Hessians at compile-time, eliminating runtime overhead.
• 🔥 Fused Riccati Kernels: Unlike solvers that use generic matrix libraries, MiniSolver uses Python (SymPy) to symbolically fuse the Riccati backward pass (Q + A'PA) into a single, flattened C++ function. This eliminates all loop overhead and explicitly bypasses multiplication by zero, achieving perfect sparsity exploitation for small-to-medium systems ($N_x < 20$).

🛡️ Embedded Safety & Robustness

• Zero-Malloc Guarantee: All memory is allocated on the stack (or .bss) via std::array and C++ templates (MAX_N). No new/malloc calls occur during the solve() loop.
• Robust Interior Point Method (IPM):
  • Mehrotra Predictor-Corrector: Drastically reduces iteration counts by utilizing higher-order corrections.
  • Filter Line Search: Ensures global convergence without the tedious tuning of merit function parameters.
  • Feasibility Restoration: Automatically triggers a minimum-norm recovery phase if the solver encounters infeasible warm starts.

🔧 Advanced Solver Capabilities

• Second Order Correction (SOC): Handles highly nonlinear constraints (e.g., tight obstacle avoidance) by curving the search step.
• Native Soft Constraints: Supports L1 (Exact) and L2 (Quadratic) soft constraints via Dual Regularization, allowing for relaxation without increasing the problem dimensions (slack variables are handled implicitly).
• Iterative Refinement: High-precision mode that uses full-precision residuals to correct regularization errors in the linear solver.

---

📊 Performance Benchmarks

Benchmarks performed on an Intel Core i7 (Single Thread) for a Kinematic Bicycle Model with Obstacle Avoidance ($N_x=6, N_u=2, N=50$).

Strategy	Integrator	Line Search	Avg Time	Iterations	Status
TURBO	Euler	Filter	~0.8 ms	10-15	Approx
ROBUST (Rec)	RK4	Filter	~2.4 ms	23	Optimal
STABLE	RK4	Merit	~3.0 ms	46	Optimal
ADAPTIVE	RK4	Filter	~25.0 ms	300*	Feasible

> Adaptive strategy may stagnate on feasible but high-cost solutions in scenarios with bad initial guesses (e.g., straight-line initialization).

---

🛠️ Quick Start

Prerequisites

• CMake >= 3.10
• C++17 Compiler (GCC/Clang)
• Python 3 + SymPy (pip install sympy)
• (Optional) Eigen3 (Default backend, can be swapped for built-in MiniMatrix)

1. Define Your Model (Python)

Define your Optimal Control Problem (OCP) using the Python DSL. This generates the optimized C++ headers.

# my_model.py
from minisolver.MiniModel import OptimalControlModel
import sympy as sp

model = OptimalControlModel(name="DroneModel")

# 1. Define Variables
px, py, vz = model.state("px", "py", "vz")
thrust = model.control("thrust")

# 2. Dynamics (f(x,u))
model.set_dynamics(px, vx) # ... assume vx defined
model.set_dynamics(py, vy)
model.set_dynamics(vz, thrust - 9.81)

# 3. Objective (Least Squares)
model.minimize( 10.0 * (px - 0.0)**2 ) # Target x=0
model.minimize( 0.1 * thrust**2 )      # Regularization

# 4. Constraints
model.subject_to( thrust <= 20.0 )     # Hard Constraint
# Soft Constraint (L1 Penalty via Dual Regularization)
model.subject_to( vz <= 5.0, weight=100.0, loss='L1' )

# 5. Generate C++ Code
model.generate("include/model")

2. Solve in C++

Include the generated header and the solver.

#include "model/drone_model.h"
#include "minisolver/solver/solver.h"

using namespace minisolver;

int main() {
    // Instantiate solver with Max Horizon N=100
    MiniSolver<DroneModel, 100> solver(50, Backend::CPU_SERIAL);
    
    // Set Initial Condition
    solver.set_initial_state("px", -10.0);
    
    // Configure for Robustness
    solver.config.barrier_strategy = BarrierStrategy::MEHROTRA;
    solver.config.enable_soc = true;
    
    // Solve
    SolverStatus status = solver.solve();
    
    // Retrieve Optimal Control
    std::vector<double> u_opt = solver.get_control(0);
}

3. Build & Run

MiniSolver includes a one-click build script that handles dependency checking, code generation, and compilation.

./build.sh

📦 Embedded Deployment

1. Generate your model headers on a PC: python3 generate_model.py
2. Copy the minisolver/ include folder and your generated headers to your MCU project.
3. Define USE_CUSTOM_MATRIX to remove Eigen3 dependency.
4. Compile with -O3. No external libraries required.

---

📂 Project Structure

• include/core/: Core types (KnotPoint), memory-safe containers (Trajectory), and Matrix Abstraction Layer (MiniMatrix/Eigen).
• include/solver/: The main MiniSolver class orchestrating the IPM loop.
• include/algorithms/: Numerical engines:
  • RiccatiSolver: Block-tridiagonal linear system solver.
  • LineSearch: Filter and Merit function strategies.
• python/minisolver/: The MiniModel DSL and C++ code generator.
• tools/:
  • auto_tuner.cpp: Monte-Carlo search for optimal solver configurations.
  • replay_solver.cpp: Debugging tool to replay serialized solver states.
  • benchmark_suite/: comprehensive performance testing.

🤝 License & Citation

MiniSolver is licensed under the Apache 2.0 License.

If you use this software in academic work, please refer to CITATION.cff.

Maintained by Edward Qu.