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

Dit artikel beschrijft een experimentele studie waarin een dual active-set solver (DAQP) met succes op 500 Hz wordt uitgevoerd op een Crazyflie 2.1 nano-quadcopter, wat een snellere en betrouwbaardere real-time Model Predictive Control mogelijk maakt dan bestaande ADMM-benaderingen op beperkte hardware.

De kern

De Super-Brain op een Vliegende Munt: Hoe een Klein Drone-Computertje Sneller Rekenen Leerde

Stel je voor dat je een drone hebt die zo klein is als een muntstuk (een "Crazyflie"). Deze drone moet vliegen, maar hij is onstabiel: als je hem niet constant corrigeert, valt hij direct naar beneden. Om dit te voorkomen, heeft hij een "hersenen" nodig die elke seconde duizenden berekeningen maakt om te beslissen: "Moet ik mijn linkerwiel harder draaien? Moet ik iets naar voren hellen?"

Dit is wat Model Predictive Control (MPC) doet. Het is als een super-intelligente piloot die niet alleen kijkt waar hij nu is, maar ook voorspelt waar hij over 1 seconde, 2 seconde en 3 seconde zal zijn, en dan de beste route kiest om veilig en snel te blijven vliegen.

Het probleem? De computer aan boord van deze mini-drone is heel zwak. Het is alsof je probeert een zware video-game te draaien op een oude rekenmachine. Meestal is de computer te traag om die complexe berekeningen snel genoeg te maken, waardoor MPC te zwaar is voor zulke kleine drones.

De Oplossing: Een Slimme Rekenstrategie

De auteurs van dit paper hebben een experiment gedaan met twee verschillende manieren om die "hersenen" te laten werken:

1. TinyMPC (De Algemeen Bekende Manier): Dit is een methode die vaak wordt gebruikt. Het is als een student die stap voor stap een moeilijke wiskundetoets maakt, maar die soms vastloopt en veel tijd verspilt aan het controleren van zijn werk.
2. DAQP (De Nieuwe, Slimme Manier): Dit is een "Dual Active-Set" methode. Stel je voor dat je een doolhof moet vinden. De oude methode loopt elke gang af. De nieuwe methode (DAQP) heeft een kaart en weet precies welke paden niet leiden naar de uitgang, zodat hij die direct overslaat. Hij focust alleen op de paden die werken.

Wat hebben ze ontdekt?

• Snelheidswonder: Ze hebben de nieuwe methode (DAQP) op de kleine drone geïnstalleerd. Het resultaat? De drone kon nu 500 keer per seconde beslissingen nemen! Dat is razendsnel.
• De Vergelijking: Ze hebben de twee methoden tegen elkaar laten racen. De nieuwe methode (DAQP) was overal sneller dan de oude (TinyMPC). Zelfs op die kleine, zwakke computer was de "slimme kaartlezer" beter dan de "stap-voor-stap student".
• De Veiligheidstest (De "Certificering"): Het grootste risico bij zo'n snelle computer is dat hij soms vastloopt als het te moeilijk wordt (bijvoorbeeld bij een plotselinge windvlaag). De auteurs hebben een nieuwe manier bedacht om dit van tevoren te testen.
  • De Analogie: Stel je voor dat je een auto wilt testen. Je kunt hem 10.000 keer op een willekeurige weg laten rijden (dat duurt lang en is duur). Of je kunt een slimme computer gebruiken die precies weet welke wegen de auto het vaakst rijdt (bijvoorbeeld alleen de snelweg, niet de modderpaden).
  • Ze gebruikten PCA (een statistische techniek) om te kijken welke situaties de drone echt tegenkomt tijdens vliegen. In plaats van te testen op alle mogelijke situaties (inclusief onmogelijke, zoals een drone die achteruit vliegt), testten ze alleen op de realistische scenario's. Hierdoor konden ze met zekerheid zeggen: "Ja, deze software is veilig en snel genoeg, zelfs in de ergste situatie die we verwachten."

Waarom is dit belangrijk?

Vroeger dachten mensen dat je voor zulke snelle, veilige drones alleen simpele, minder slimme besturingssystemen kon gebruiken. Dit paper bewijst dat je zelfs de "slimste" besturing (MPC) op de kleinste, goedkoopste computers kunt laten draaien, zolang je maar de juiste rekenmethode kiest.

Samengevat in één zin:
De auteurs hebben bewezen dat je met een slimme rekenstrategie en een slimme testmethode een mini-drone kunt laten vliegen met de intelligentie van een raceauto, zelfs als hij op een batterij van een horloge draait.

Dit opent de deur voor drones die in de toekomst niet alleen vliegen, maar ook zelfstandig door dichte bossen kunnen navigeren, obstakels kunnen ontwijken en complexe reddingsmissies kunnen uitvoeren, allemaal zonder zware, dure computers aan boord.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On Real-Time Feasibility of High-Rate MPC using an Active-Set Method on Nano-Quadcopters" in het Nederlands.

Titel: Real-time haalbaarheid van High-Rate MPC met een Active-Set-methode op Nano-Quadcopters

Auteurs: J. Wikner, D. Arnström, D. Axehill (Linköping University, Zweden)

---

1. Probleemstelling

Model Predictive Control (MPC) is een krachtige regelparadigma voor complexe systemen, vooral vanwege het vermogen om harde constraints (beperkingen) voor toestandsvariabelen en ingangen expliciet te behandelen. Dit is essentieel voor het veilig en agressief manoeuvreren van kleine, wendbare robots zoals nano-quadcopters.

Het grootste obstakel voor het toepassen van MPC op deze platforms is de severe computatiebeperking van de aan boord aanwezige microcontrollers (MCU's). Traditioneel wordt MPC niet gebruikt voor de lage-lus (low-level) stabilisatie van dergelijke systemen vanwege de hoge rekentijd. Bestaande oplossingen op de Crazyflie 2.1 (een populaire nano-quadcopter) gebruiken vaak eerste-orde methoden (zoals ADMM) of beperken actieve-set methoden tot hogere regellagen. Er is nog geen gedocumenteerd succes van een tweede-orde actieve-set methode die de uitdagende binnenste regellus (inner loop) van een 12-toestandsysteem op 500 Hz regelt op een beperkte MCU. Daarnaast ontbreekt er vaak een formele real-time certificering (waarbij de ergste uitvoeringstijd, WCET, vooraf wordt bewezen) voor deze specifieke toepassing.

2. Methodologie

De auteurs presenteren een experimentele studie waarbij een Dual Active-Set QP-oplosser (DAQP) wordt geïmplementeerd voor de lage-lus regeling van een Crazyflie 2.1.

• Hardware: De regeling draait volledig onboard op een STM32F405 Cortex-M4 MCU (168 MHz, 196 kB SRAM).
• Regelprobleem: Een lineair MPC-probleem met een model van 12 toestandsvariabelen (positie, snelheid, attitude, hoeksnelheid) en 4 ingangen (motorcommando's). De regelfrequentie is 500 Hz met een voorspellingshorizon van $N=15$.
• Vergelijking: De prestaties van DAQP worden direct vergeleken met TinyMPC, een state-of-the-art op ADMM gebaseerde solver die specifiek voor deze hardware is ontworpen.
• Certificering: Om de real-time haalbaarheid te garanderen, wordt een WCET-analyseframework (Arnström et al., 2024) gebruikt. In plaats van de hele parameter ruimte willekeurig te testen, introduceren de auteurs een datagedreven aanpak:
  • Er wordt gebruik gemaakt van Principal Component Analysis (PCA) op meetdata van een testvlucht.
  • Dit resulteert in een "geroteerde hyper-rechthoek" (een kleiner, representatiever parametergebied) in plaats van een conservatieve, as-georiënteerde doos.
  • Hierdoor kan de ergste uitvoeringstijd (WCET) efficiënter en nauwkeuriger worden bepaald voor het specifieke vluchtgedrag.

3. Belangrijkste Bijdragen

1. Eerste implementatie van DAQP voor lage-lus MPC: Het is de eerste keer dat een dual active-set solver succesvol wordt gebruikt voor de lage-lus regeling (500 Hz) van een 12-toestands nano-quadcopter op een resource-beperkte MCU.
2. Benchmarking: Een kwalitatieve en kwantitatieve vergelijking toont aan dat de complexere tweede-orde active-set methode (DAQP) consistent sneller is dan de ADMM-gebaseerde TinyMPC op deze specifieke hardware, zelfs binnen de strenge real-time eisen.
3. Verbeterde Real-time Certificering: De toepassing van het WCET-framework op deze applicatie, gecombineerd met de PCA-gebaseerde selectie van het parametergebied. Dit maakt het mogelijk om ontwerpen al in de ontwerpfase te valideren of te verwerpen op basis van real-time haalbaarheid.
4. Data-gedreven efficiëntie: De PCA-methode verkleint het te certificeren parametergebied aanzienlijk, wat de rekentijd voor de certificering verlaagt en de conservatisme van de analyse reduceert zonder de veiligheid te compromitteren.

4. Resultaten

• Uitvoeringstijd: De histogrammen en cumulatieve verdelingsfuncties (CDF) tonen aan dat DAQP in alle geteste gevallen sneller is dan TinyMPC. Het verschil in uitvoeringstijd is strikt positief ten gunste van DAQP.
• Real-time Haalbaarheid: Met de originele instellingen (tuning) van TinyMPC slaagden beide controllers erin om de 500 Hz eis te halen tijdens vlucht, hoewel DAQP een grotere marge had.
• Regelprestaties: Bij het testen met een agressievere tuning (verlaging van de gewichtsparameter $R$ voor de ingang) verbeterde de trackingprestatie (minder fout in hoogte), maar bij de meest agressieve instelling ($R=50$) werd de real-time eis van 500 Hz geschonden tijdens steile dalingen.
• Effect van PCA:
  • Bij de originele tuning bleek DAQP real-time haalbaar te zijn binnen het PCA-gebied ($\Theta^{900}_{pca}$), terwijl een te conservatief gebied ($\Theta_b$) zou suggereren dat de solver faalt.
  • Bij de agressieve tuning ($R=100$) toonde de analyse met het PCA-gebied ($\Theta^{100}_{pca}$) correct aan dat de real-time eisen zouden worden geschonden, wat de voorspellende kracht van de methode bevestigt.

5. Betekenis en Conclusie

De studie bewijst dat tweede-orde active-set methoden (zoals DAQP) een zeer competitief alternatief zijn voor eerste-orde methoden (zoals ADMM) op resource-beperkte hardware, mits zorgvuldig geïmplementeerd.

De belangrijkste implicaties zijn:

• Betrouwbaarheid: Het vermogen om real-time certificering toe te passen op embedded MPC-systemen verhoogt de betrouwbaarheid van autonome systemen.
• Efficiëntie: De combinatie van een snellere solver en een slimme, datagedreven selectie van het testgebied (via PCA) maakt het mogelijk om complexere regelaars op kleinere hardware te draaien dan voorheen mogelijk leek.
• Toekomst: Dit opent de deur voor meer geavanceerde regelingstechnieken op nano-robots, waarbij de focus verschuift van "kan het draaien?" naar "hoe goed kan het presteren?", met de zekerheid dat de real-time eisen gegarandeerd worden.

Kortom, dit werk legt de basis voor het gebruik van geavanceerde, wiskundig robuuste optimalisatie-algoritmen in de uiterste rand van de computercapaciteit van nano-vliegmachines.