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

Cette étude démontre la faisabilité temps réel d'une méthode de contrôle prédictif par modèle (MPC) utilisant un solveur à ensembles actifs (DAQP) sur un nano-drone Crazyflie 2.1 à 500 Hz, surpassant les solveurs ADMM en temps d'exécution et introduisant une méthode de sélection de données par PCA pour certifier la faisabilité temps réel hors ligne.

L'essentiel

Voici une explication simple et imagée de cette recherche scientifique, traduite en français pour le grand public.

🚁 Le Défi : Faire voler un drone avec un cerveau de calculatrice

Imaginez que vous essayez de faire voler un drone de la taille d'une main (un "nano-drone" comme le Crazyflie) dans une pièce remplie d'obstacles. Pour qu'il vole de manière autonome, stable et rapide, il doit prendre des décisions de pilotage des centaines de fois par seconde.

C'est là qu'intervient un outil mathématique puissant appelé MPC (Commande Prédictive). On peut le comparer à un chef d'orchestre très prévoyant. Au lieu de simplement réagir à ce qui se passe maintenant, ce chef regarde devant lui, imagine les prochaines mesures, et calcule la meilleure façon de jouer pour éviter les collisions et rester en rythme.

Le problème ? Ce chef d'orchestre est très exigeant. Pour faire ses calculs, il a besoin d'un cerveau très puissant (un gros ordinateur). Or, le drone est minuscule et son "cerveau" (le microcontrôleur) est aussi petit et faible qu'une calculatrice de poche. C'est comme essayer de faire tourner un jeu vidéo ultra-réaliste sur une vieille montre-bracelet : ça devrait être impossible !

🧠 La Solution : Un nouveau "stratège" plus rapide

Les chercheurs de l'Université de Linköping (en Suède) ont voulu tester si c'était possible. Ils ont comparé deux méthodes pour faire fonctionner ce "chef d'orchestre" sur le petit cerveau du drone :

1. L'ancienne méthode (TinyMPC) : C'est comme un coureur de fond. Il avance pas à pas, lentement mais sûrement, en ajustant sa course à chaque instant. C'est une méthode populaire, mais elle peut être lente.
2. La nouvelle méthode (DAQP) : C'est un stratège en échecs. Au lieu de marcher pas à pas, il regarde l'échiquier entier, identifie les pièges (les contraintes) et saute directement vers la meilleure solution possible en éliminant les mauvaises options très vite. C'est ce qu'on appelle une méthode "d'ensemble actif" (active-set).

Le résultat surprenant ?
Même si la méthode du "stratège" (DAQP) semble plus complexe mathématiquement, elle s'est révélée plus rapide que le "coureur" sur le petit cerveau du drone. Elle a réussi à prendre des décisions 500 fois par seconde, ce qui est une performance record pour un appareil aussi petit.

🔍 L'Analogie de la "Carte au Trésor" (La Certification)

Mais il y a un autre défi : comment être sûr à 100 % que le drone ne va pas planter au moment le plus critique ?

Imaginez que vous devez vérifier si un pilote peut gérer toutes les tempêtes possibles.

• L'ancienne façon de faire : Vous faites voler le drone dans des milliers de tempêtes différentes au hasard, espérant qu'il ne rate jamais. C'est long, coûteux et vous ne pouvez jamais être certain d'avoir tout testé.
• La nouvelle méthode de l'article : Les chercheurs ont utilisé une technique intelligente appelée PCA (Analyse en Composantes Principales).
  • Imaginez que vous avez un énorme tas de données sur les mouvements du drone.
  • La PCA agit comme un filtre magique qui dit : "Attends, le drone ne fait jamais ce mouvement bizarre ici, c'est physiquement impossible. Concentrons-nous seulement sur les mouvements réalistes."
  • En réduisant le tas de problèmes à tester aux seuls cas réalistes, ils ont pu prouver mathématiquement, avant même le premier vol, que le drone serait toujours en sécurité. C'est comme avoir une carte au trésor qui vous dit exactement où sont les pièges, au lieu de chercher au hasard.

🏆 Les Résultats Concrets

1. Vitesse : La nouvelle méthode (DAQP) est plus rapide que l'ancienne (TinyMPC) sur le matériel limité du drone.
2. Sécurité : Grâce à leur nouvelle méthode de "filtre" (PCA), ils peuvent certifier que le logiciel ne va pas planter, même dans les pires cas de figure, avant de le mettre sur le drone.
3. Vol réel : Ils ont fait voler le drone en lui demandant de faire des figures complexes (comme un "8" dans les airs) et le système a tenu le coup, prouvant que l'approche fonctionne dans la vraie vie.

💡 En résumé

Cette recherche nous dit que même avec un matériel très limité (comme un petit drone), on peut faire des choses très intelligentes si on choisit le bon "algorithme" (le bon cerveau) et si on utilise des outils intelligents pour prédire les problèmes avant qu'ils n'arrivent.

C'est un peu comme si on apprenait à un enfant à résoudre des énigmes complexes non pas en lui donnant un super-ordinateur, mais en lui apprenant une astuce de logique qui lui permet de trouver la réponse plus vite que n'importe quel adulte avec une calculatrice. Cela ouvre la porte à des robots plus petits, plus agiles et plus sûrs pour l'avenir.

Résumé technique

Voici un résumé technique détaillé de l'article « On Real-Time Feasibility of High-Rate MPC using an Active-Set Method on Nano-Quadcopters », présenté en français.

1. Problématique

Le déploiement de la commande prédictive de modèle (MPC) sur des plateformes aériennes à l'échelle nanométrique, comme le quadricoptère Crazyflie 2.1, se heurte à des limitations computationnelles sévères des microcontrôleurs embarqués (MCU). Bien que la MPC soit idéale pour gérer les contraintes d'état et d'entrée dans des environnements complexes, son coût de calcul est souvent trop élevé pour les boucles de contrôle internes (stabilisation) nécessitant des fréquences d'échantillonnage élevées (ex: 500 Hz).

La littérature récente a démontré la faisabilité de la MPC en temps réel sur ces plateformes en utilisant des méthodes de premier ordre (comme l'algorithme ADMM implémenté dans le solveur TinyMPC). Cependant, les méthodes de second ordre, et plus spécifiquement les méthodes d'ensemble actif (active-set), n'avaient pas encore été démontrées avec succès pour la boucle de contrôle interne d'un système à 12 états sur un MCU contraint, ni certifiées pour leur temps d'exécution pire cas (WCET).

2. Méthodologie

Les auteurs ont conçu et évalué une implémentation MPC en temps réel sur un Crazyflie 2.1 équipé d'un microcontrôleur STM32F405 (Cortex-M4 à 168 MHz).

• Modélisation et Contrôle :

  • Un contrôleur MPC linéaire à horizon glissant a été conçu pour un modèle dynamique à 12 états (position, vitesse, attitude, vitesses angulaires).
  • La fréquence de contrôle est fixée à 500 Hz avec une longueur d'horizon de $N=15$.
  • Le problème d'optimisation quadratique (QP) sous-jacent est résolu en ligne à bord.

• Comparaison des Solveurs :

  • DAQP : Implémentation d'un solveur QP à ensemble actif dual (Dual Active-Set QP Solver). C'est une méthode de second ordre.
  • TinyMPC : Solveur basé sur la méthode ADMM (premier ordre), utilisé comme référence de l'état de l'art.
  • Les deux solveurs utilisent les mêmes matrices de pondération et la même configuration de problème (tels que définis dans le firmware TinyMPC existant) pour garantir une comparaison équitable.

• Certification Temps Réel et Sélection de Données :

  • Les auteurs appliquent un cadre d'analyse de complexité temporelle (WCET) basé sur la certification de l'ensemble actif.
  • Nouveauté clé : Introduction d'une méthode de sélection de jeu de paramètres basée sur l'Analyse en Composantes Principales (PCA). Au lieu d'utiliser une boîte englobante conservatrice (axis-aligned box) dans l'espace d'état qui contient de nombreuses combinaisons non physiques, la PCA est utilisée pour identifier un hyper-rectangle tourné plus représentatif des trajectoires réellement parcourues par le drone. Cela réduit la taille de l'ensemble de paramètres à certifier.

3. Contributions Clés

1. Première démonstration d'un solveur à ensemble actif dual (DAQP) en boucle basse : Réussite du déploiement d'un contrôleur MPC à 500 Hz sur un Crazyflie 2.1, résolvant un problème à 12 états entièrement embarqué.
2. Benchmark expérimental DAQP vs TinyMPC : Une comparaison directe montre que la méthode à ensemble actif (généralement considérée comme plus complexe) est systématiquement plus rapide que la méthode ADMM sur le matériel contraint pour les enveloppes de vol testées.
3. Certification temps réel par PCA : Développement d'une stratégie de sélection de données pilotée par les données (via PCA) pour améliorer l'efficacité computationnelle de la procédure de certification hors ligne. Cette méthode permet de rejeter ou d'accepter la faisabilité temps réel avant le vol, en se concentrant sur les régions d'état pertinentes.
4. Analyse de la complexité : Application du cadre d'analyse WCET (Arnström et al., 2024) pour fournir des garanties formelles sur le temps d'exécution pire cas, dépassant les simples mesures empiriques.

4. Résultats Expérimentaux

• Performance Computationnelle :

  • Les histogrammes des différences de temps d'exécution montrent que DAQP est toujours plus rapide que TinyMPC pour tous les échantillons testés.
  • L'utilisation d'une distribution uniforme pour tester les solveurs (méthode 1) a tendance à sous-estimer le pire cas pour les solveurs à ensemble actif, tandis que la méthode basée sur la partition de l'espace d'état (méthode 2) révèle les véritables limites.
  • Avec la sélection de paramètres basée sur la PCA, le temps d'exécution pire cas (WCET) pour DAQP a été mesuré à 1375 µs, ce qui est compatible avec la contrainte de 2 ms (500 Hz). Sans PCA, l'approche conservatrice aurait pu indiquer une violation des contraintes temps réel.

• Performance de Contrôle :

  • Les deux contrôleurs (DAQP et TinyMPC) respectent la contrainte temps réel en vol.
  • Cependant, avec les paramètres de réglage (tuning) originaux du firmware TinyMPC, les deux contrôleurs présentent une erreur de suivi d'altitude (dûe à une compensation statique de la gravité imparfaite).
  • La réduction du poids de l'entrée ($R$) dans la fonction de coût améliore le suivi de l'altitude mais augmente le temps de calcul. Pour un réglage très agressif ($R=50$), DAQP viole la contrainte temps réel de 500 Hz lors des manœuvres descendantes, confirmant la capacité de l'outil de certification à prédire ces échecs.

5. Signification et Conclusion

Cet article démontre que les méthodes d'ensemble actif de second ordre, souvent considérées comme trop lourdes pour les microcontrôleurs embarqués, sont en réalité des alternatives hautement compétitives, voire supérieures, aux méthodes de premier ordre (comme ADMM) pour le contrôle haute fréquence de systèmes contraints.

L'apport majeur réside dans la combinaison de la performance computationnelle de DAQP avec une certification temps réel rigoureuse. L'utilisation de la PCA pour réduire l'espace de certification permet d'obtenir des garanties de temps réel moins conservatrices et plus réalistes, facilitant ainsi le déploiement fiable de l'optimisation embarquée sur des robots autonomes aux ressources limitées. Ce travail ouvre la voie à une utilisation plus large de la MPC avancée sur des plateformes nanométriques, en assurant à la fois la performance et la sécurité opérationnelle.