Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

Résumé technique : Maximisation des probabilités d'atteinte et d'évitement pour les systèmes stochastiques linéaires via des architectures de commande

Formulation du problème
L'article traite du défi consistant à maximiser la probabilité d'atteinte-évitement (reach-avoid) pour des systèmes stochastiques linéaires sur un horizon temporel fini. Le système est défini par une dynamique contenant à la fois des états évoluant de manière déterministe ($x_d$) et des états évoluant de manière probabiliste ($x_s$), soumis à un bruit i.i.d. additif. L'objectif de commande est de trouver une politique qui maximise la probabilité que le système atteigne un ensemble cible $T$ tout en restant dans un ensemble sûr $S$ pendant une durée $[0, T]$, tout en satisfaisant des contraintes déterministes $G$ (telles que les limites d'entrée et les bornes d'état) à tout moment.

Les méthodes existantes font face à un compromis : les approches basées sur des bornes statistiques (ex: tubes stochastiques, MPC par scénarios) offrent une scalabilité mais donnent souvent des performances conservatrices, tandis que les méthodes d'optimisation directe (ex: processus de décision markoviens - MDP) fournissent des garanties serrées mais sont informatiquement insolubles pour des espaces d'états de haute dimension ou continus.

Méthodologie
Les auteurs proposent une architecture de commande à deux couches qui combine la scalabilité de la commande prédictive de modèle (MPC) avec l'optimalité de la programmation dynamique (DP). L'innovation centrale réside dans le traitement du système en boucle fermée (plante + MPC) comme un processus de décision markovien (MDP) où les « actions » sont des signaux de référence envoyés au MPC, plutôt que des entrées de commande directes.

1. Architecture à deux couches :

   • Couche inférieure (MPC) : Un contrôleur MPC suit les signaux de référence générés par la couche supérieure. Le MPC est conçu pour être agnostique à l'objectif d'atteinte-évitement stochastique ; son unique but est de garantir que le système satisfait les contraintes déterministes $G$ et les limites d'entrée $U$. Pour combler l'écart entre l'optimisation MPC en temps discret et la satisfaction des contraintes en temps continu, les auteurs dérivent des techniques de resserrement de contraintes (Lemme III.1) qui tiennent compte de la dynamique du système et du bruit sur l'intervalle d'échantillonnage.
   • Couche supérieure (Générateur de référence DP) : Une politique basée sur la DP opère à des intervalles de temps fixes ($\Delta t$). Elle sélectionne des séquences de référence (commandes) pour le MPC afin de maximiser la probabilité d'atteindre la cible tout en évitant les régions dangereuses. L'espace d'états de ce MDP est l'état du système $x_k$, et l'espace d'actions consiste en un ensemble fini de trajectoires de référence.

2. Gestion des espaces d'états continus et abstraction :
   Puisque l'espace d'états est continu, les auteurs emploient une abstraction par grille finie pour rendre la DP informatiquement traitable. Pour garantir que les garanties théoriques soient préservées malgré cette discrétisation, ils introduisent un cadre de robustification :

   • MPC Robuste (RMPC) : Le MPC est modifié pour générer des séquences d'entrée invariantes par rapport à l'état initial spécifique au sein d'une cellule de grille (partition). Cela est réalisé en initialisant la prédiction du MPC à partir du centre de la cellule plutôt qu'à partir de l'état mesuré, garantissant que la même séquence de commande est appliquée à tous les états au sein d'une partition.
   • Itération de valeur robuste : Les ensembles sûrs et cibles sont resserrés par un rayon $r$ (dérivé de la déviation maximale des trajectoires au sein d'un pas de temps) pour tenir compte des erreurs d'abstraction. L'algorithme DP est modifié pour calculer une borne inférieure de la probabilité d'atteinte-évitement en considérant les transitions les plus défavorables dans le voisinage de chaque cellule de grille.

Contributions clés

• Architecture de commande : L'article introduit une nouvelle architecture qui réduit la dimensionnalité de l'espace de planification de la DP de la dimension complète de l'état $n$ à la dimension de la composante évoluant de manière probabiliste $n_s$. Ceci est réalisé en exploitant l'évolution déterministe de $x_d$ et les capacités de suivi du MPC.
• Garanties théoriques : Les auteurs fournissent des certificats formels pour l'approche. Ils prouvent que l'architecture robustifiée garantit la satisfaction des contraintes en temps continu et que la valeur calculée par l'algorithme de DP robuste sert de borne inférieure stricte sur la probabilité réelle d'atteinte-évitement réalisée par le système (Théorème IV.4).
• Scalabilité et flexibilité : La méthode est démontrée comme étant scalable à des systèmes de plus haute dimension (spécifiquement un modèle de quadricoptère à 12D) et suffisamment flexible pour gérer des environnements complexes et encombrés.

Résultats
L'approche a été validée sur un modèle de quadricoptère 12D perturbé naviguant dans divers environnements encombrés (ex: labyrinthes, chemins en zigzag, champs d'obstacles).

• Performance : Dans un scénario de labyrinthe, l'architecture a atteint un taux de réussite de 40 %, surpassant de manière significative les bases conservatrices.
• Comparaison : À travers plusieurs scénarios, la probabilité d'atteinte-évitement empirique ($V_0(x_0)$) a systématiquement égalé ou dépassé la borne inférieure calculée par l'itération de valeur robuste ($\tilde{V}_0(x_0)$), validant ainsi les garanties théoriques. Par exemple, dans un environnement de type « zigzag », le taux de réussite empirique était de 44 % contre une borne inférieure théorique de 0,3 %.
• Compromis : L'article démontre également la capacité de l'architecture à résoudre des problèmes de commande optimale contraints. En ajustant un multiplicateur de Lagrange, le système peut arbitrer entre le coût de la trajectoire (maintenir la trajectoire proche d'un centre) et la probabilité d'atteinte-évitement, générant ainsi un front de Pareto de solutions.

Signification et affirmations
L'article affirme que ce travail comble le fossé entre l'optimalité théorique des méthodes basées sur les MDP et la scalabilité pratique du MPC. En découplant l'application de la sécurité (gérée par le MPC robuste) de l'optimisation probabiliste (gérée par le générateur de référence DP), les auteurs parviennent à une stratégie de commande qui est à la fois informatiquement faisable pour des systèmes de haute dimension et capable de fournir des certificats formels d'atteinte-évitement sans recourir à des bornes statistiques excessivement conservatrices. Les auteurs soulignent que leur méthode fournit des certificats formels pour les systèmes stochastiques, une caractéristique souvent absente des approches heuristiques scalables, tout en évitant l'intraitabilité informatique des solutions MDP à état complet.