On Real-Time Feasibility of High-Rate MPC using an Active-Set Method on Nano-Quadcopters

This paper demonstrates the successful real-time deployment of a dual active-set solver (DAQP) for high-frequency (500 Hz) Model Predictive Control on a resource-constrained nano-quadcopter, showing superior execution times compared to ADMM-based methods and introducing a data-driven approach to certify real-time feasibility offline.

The Gist

Imagine you have a tiny, incredibly agile drone, about the size of a hummingbird, called a Crazyflie. This drone is so small that its "brain" (the microcontroller) is as weak as a basic calculator compared to the powerful computers in your phone or laptop.

Now, imagine you want this tiny drone to fly itself through a complex obstacle course, dodging walls and staying perfectly stable. To do this safely, it needs a super-smart pilot inside it that can make thousands of decisions every second. This pilot is called Model Predictive Control (MPC).

Think of MPC as a chess player who looks 15 moves ahead. Before making a move, it simulates the future: "If I tilt left, I might hit that wall. If I tilt right, I'll be safe." It solves a massive math puzzle every single millisecond to decide the best action.

The Problem:
The drone's brain is too small to solve these massive math puzzles fast enough. Usually, engineers have to use "lazy" shortcuts (simpler math methods) to make it work, but these shortcuts aren't perfect. They might make the drone wobble or crash in tight spots.

The Solution in this Paper:
The researchers decided to try a different, more powerful math method called a Dual Active-Set Solver (specifically, a tool called DAQP). Think of this method as a highly skilled, precise mechanic who can fix a car engine faster and better than a general handyman, but usually, this mechanic is too slow for a tiny drone.

The team managed to squeeze this "precise mechanic" onto the tiny drone's brain. Here is what they discovered, explained through analogies:

1. The Race: The "Precise Mechanic" vs. The "Fast Runner"

Previously, people used a method called TinyMPC (based on a technique called ADMM). Imagine TinyMPC as a fast runner who sprints but sometimes stumbles or takes a slightly wrong path.
The new method, DAQP, is like a marathon runner with a GPS. It might seem more complicated, but it actually finds the solution faster and more accurately on this specific tiny hardware.

• The Result: In a race of 500 steps per second (500 Hz), the "Precise Mechanic" (DAQP) beat the "Fast Runner" (TinyMPC) every single time. It solved the math puzzles faster, leaving more time for the drone to actually fly.

2. The "Crystal Ball" (Real-Time Certification)

The biggest fear in robotics is: "What if the math takes too long during a tricky part of the flight?" If the math takes 2 milliseconds instead of 1, the drone crashes.
To fix this, the researchers created a "Crystal Ball" (a tool called WCET analysis).

• How it works: Instead of just guessing or testing the drone a few times, they mathematically proved exactly how long the worst-case scenario would take.
• The Analogy: Imagine you are packing for a trip. Instead of just throwing clothes in a bag and hoping it fits, you use a scanner that tells you, "This bag will hold exactly 50 shirts, but if you try to fit 51, it will burst." They used this scanner to prove the drone's brain would not burst before they even took off.

3. The "Smart Filter" (PCA)

The "Crystal Ball" is powerful, but it can be slow to run if you check every possible situation the drone might face (like checking every single grain of sand on a beach).
The researchers introduced a Smart Filter using a technique called Principal Component Analysis (PCA).

• The Analogy: Imagine you want to know the weather for the whole year. Instead of checking every single day, you look at the data and realize, "Oh, it's mostly just 'Sunny' or 'Rainy'." You filter out the weird, impossible combinations (like "Snowing in the Sahara Desert").
• The Result: By filtering out the impossible scenarios, they could run their "Crystal Ball" test much faster and still be 100% sure the drone was safe.

The Big Picture

This paper is a breakthrough because it proves that tiny, weak computers can run very smart, complex control systems if you choose the right tools.

• Before: Tiny drones had to use "dumb" pilots to stay safe.
• Now: They can use "smart" pilots that make split-second, perfect decisions.
• Why it matters: This opens the door for tiny drones to fly in crowded cities, inside buildings, or rescue people in disasters, because they can now react fast enough to avoid crashing.

In short: The researchers taught a tiny drone's weak brain to think like a grandmaster chess player, proved it wouldn't get overwhelmed, and showed that this new way of thinking is actually faster than the old ways.

Technical Summary

Here is a detailed technical summary of the paper "On Real-Time Feasibility of High-Rate MPC using an Active-Set Method on Nano-Quadcopters."

1. Problem Statement

Deploying Model Predictive Control (MPC) on resource-constrained nano-scale aerial platforms (specifically the Crazyflie 2.1) is challenging due to severe computational limitations. While MPC is ideal for handling constraints and ensuring safety in agile robots, its high computational cost often precludes its use in low-level, high-frequency control loops on Microcontroller Units (MCUs).

• The Gap: Previous works have utilized first-order methods (like ADMM) for low-level control or active-set methods only for high-level control. There was no prior demonstration of a second-order dual active-set solver running at high frequencies (500 Hz) for the challenging inner-loop control of a 12-state nano-quadcopter.
• The Challenge: Ensuring real-time feasibility requires not just fast execution but also worst-case execution time (WCET) certification to guarantee the solver never misses a deadline, a task complicated by the combinatorial nature of active-set algorithms.

2. Methodology

The authors implemented and benchmarked a low-level MPC controller on a Crazyflie 2.1 equipped with an STM32F405 Cortex-M4 MCU (168 MHz, 196kB SRAM).

A. Control System Design

• Plant Model: A 12-state linear time-invariant (LTI) model representing position, velocity, attitude (Rodriguez parameters), and angular velocity.
• MPC Formulation: A receding horizon control problem with a horizon length $N=15$, solved at 500 Hz.
• Solver Implementation:
  • Primary Solver: DAQP (Dual Active-Set QP solver), a second-order method. It uses an empty initial working set (no warm-start) to facilitate rigorous offline certification.
  • Benchmark Solver: TinyMPC, a state-of-the-art ADMM-based solver previously deployed on this platform.
  • Configuration: Both solvers used identical MPC tuning matrices ($Q, R, F, G$) derived from the TinyMPC firmware to ensure a fair comparison.

B. Real-Time Certification Framework

To address the difficulty of certifying active-set solvers, the authors employed a complexity certification framework (based on Arnström et al., 2024):

1. Parameter Space Partitioning: The state space is divided into regions where the active-set sequence remains constant.
2. Offline Analysis: The framework analyzes the solver's behavior in each region to determine the exact number of iterations and execution time.
3. Data-Driven Set Selection (PCA): Instead of using a conservative, axis-aligned bounding box of the state space (which includes non-physical states), the authors used Principal Component Analysis (PCA) on flight data to construct a tighter, rotated hyper-rectangle ($\Theta_p$). This reduces the parameter set size, making the certification process computationally tractable and less conservative.

3. Key Contributions

1. First High-Rate Active-Set Deployment: Successfully demonstrated a dual active-set solver (DAQP) controlling a 12-state nano-quadcopter at 500 Hz onboard an STM32F405.
2. Performance Benchmarking: Provided a direct comparison between DAQP and TinyMPC. Results showed that the more complex second-order active-set method is consistently faster than the first-order ADMM method for the specific flight envelopes tested.
3. Novel Certification Strategy: Introduced a PCA-based data-driven set selection method. This allows for the offline certification of real-time feasibility by narrowing the parameter space to physically reachable states, enabling the rejection of infeasible designs before flight.
4. WCET Analysis Application: Applied the WCET analysis framework to a real-world, resource-limited application, demonstrating its ability to predict when a controller will violate real-time constraints (e.g., when tuning parameters are made too aggressive).

4. Experimental Results

• Execution Time Comparison:
  • Using 1.17 million sampled points, DAQP was strictly faster than TinyMPC in all instances.
  • The histogram of execution time differences ($\tau_{TinyMPC} - \tau_{DAQP}$) was strictly positive, confirming DAQP's superiority in this specific context.
  • Uniform sampling (Method 2) failed to reveal the worst-case scenarios for the active-set solver, whereas the complexity-certification-based sampling (Method 1) correctly identified the worst-case bounds.
• Flight Experiments:
  • Both solvers met the 500 Hz requirement with the original tuning.
  • Tracking Performance: With the original tuning, both controllers exhibited altitude tracking errors (attributed to gravity compensation issues in the nominal input $u_0$).
  • Aggressive Tuning: When the control weight $R$ was reduced to improve tracking, DAQP violated the 500 Hz real-time requirement during aggressive maneuvers, leading to undershoot.
• Certification Validation:
  • Using the PCA-derived set $\Theta^{900}_{pca}$, the WCET was calculated as 1375 $\mu$s, confirming feasibility.
  • When the tuning was changed to a more aggressive $R=100$, the certification framework correctly predicted that the controller would violate real-time requirements on the new parameter set, matching the experimental failure observed in flight.

5. Significance and Conclusion

This paper challenges the prevailing assumption that first-order methods (like ADMM) are the only viable option for MPC on nano-quadcopters. It proves that second-order active-set methods can be more computationally efficient for specific, constrained problems due to their ability to exploit problem structure and converge in fewer iterations.

The work establishes a robust pipeline for reliable embedded optimization:

1. Performance: Active-set solvers can outperform ADMM on resource-constrained hardware.
2. Safety: The combination of PCA-based parameter reduction and WCET analysis allows engineers to certify real-time feasibility offline, rejecting designs that are too computationally heavy before they are ever deployed on hardware.

This opens new avenues for deploying high-performance, constraint-aware control strategies on tiny, low-power autonomous systems.