Conformalized Data-Driven Reachability Analysis with PAC Guarantees

Each language version is independently generated for its own context, not a direct translation.

🚗 Le GPS qui ne se trompe jamais (même sans carte)

Imaginez que vous conduisez une voiture autonome dans une ville inconnue. Votre objectif est de savoir tous les endroits où la voiture pourrait se trouver dans 10 secondes, en tenant compte du fait que le moteur peut avoir des petits à-coups imprévisibles (le "bruit") et que vos capteurs ne sont pas parfaits.

C'est ce qu'on appelle l'analyse de "réachabilité" (Reachability Analysis). Il faut dessiner une "bulle de sécurité" autour de la voiture : si la bulle est assez grande, on est sûr à 100 % que la voiture ne sortira pas de cette zone, même si elle dérape un peu.

Le problème ? Souvent, on ne connaît pas la carte exacte de la ville (le modèle mathématique du système) ni la force exacte des vents contraires (le bruit).

🛠️ Le problème des anciennes méthodes

Les méthodes actuelles sont comme des conducteurs très prudents qui disent : "Je ne connais pas la force du vent, alors je vais supposer qu'il y a un ouragan constant !"

Soit ils ont besoin de connaître la limite exacte du bruit (ce qui est impossible dans la vraie vie).
Soit ils regardent les données passées et disent : "Le pire vent que j'ai vu était de 10 km/h, donc je vais supposer que ça ne dépassera jamais 10 km/h."
- Le piège : Si demain, il y a une rafale de 10,1 km/h (un événement rare), leur bulle de sécurité éclate et la voiture est en danger. Ils n'ont aucune garantie mathématique que ça n'arrivera pas.

✨ La solution : CDDR (La méthode "Apprendre puis Tester")

Les auteurs de ce papier proposent une nouvelle approche appelée CDDR. Imaginez que vous ne devinez plus la taille de la tempête, mais que vous faites un test de réalité avant de conduire.

Voici comment ça marche, étape par étape, avec une analogie simple :

1. La phase "Entraînement" (Le simulateur)
Vous lancez la voiture 5 000 fois dans un simulateur avec des conditions aléatoires. Vous notez à chaque fois de combien la voiture a dévié par rapport à sa trajectoire prévue.

Analogie : C'est comme un chef cuisinier qui teste 5 000 fois une recette pour voir à quel point le gâteau peut varier en taille selon les fourneaux.

2. La phase "Calibration" (Le test de sécurité)
Au lieu de prendre le pire cas observé (ce qui est risqué), vous utilisez une méthode statistique intelligente appelée LTT (Learn Then Test).

L'analogie du garde-barrière : Imaginez un garde-barrière qui doit décider de la taille de la bulle de sécurité. Il ne regarde pas juste le pire cas. Il dit : "Je veux être sûr à 95 % que ma bulle fonctionnera, et je veux avoir 95 % de confiance dans mon choix, même si je refais le test demain avec d'autres données."
C'est ce qu'on appelle une garantie PAC (Probablement Approximativement Correct). C'est une promesse mathématique très forte : "Même si vous tirez au hasard un autre lot de données pour calibrer, ma bulle sera toujours assez grande pour protéger la voiture."

3. La phase "Prédiction" (Le résultat)
Grâce à ce test, le système dessine une bulle de sécurité (un zonotope, pour les experts) qui s'adapte dynamiquement.

Si le bruit est uniforme (comme une pluie fine partout), la bulle est ronde.
Si le bruit est directionnel (comme un vent fort venant de l'Est), la bulle s'étire vers l'Est pour être plus précise, sans grossir inutilement dans les autres directions.

🌟 Pourquoi c'est révolutionnaire ?

Pas besoin de connaître les règles du jeu : Que la voiture soit une machine simple (linéaire) ou un système complexe et bizarre (non-linéaire, avec des frottements étranges), la méthode fonctionne. Elle n'a pas besoin de connaître la "formule" de la voiture.
Garantie solide : Contrairement aux anciennes méthodes qui peuvent échouer silencieusement si un événement rare survient, CDDR garantit mathématiquement que la voiture restera dans la zone de sécurité, même avec des données imparfaites.
Efficacité : En utilisant une astuce mathématique (la "fonction de score normalisée"), ils arrivent à rendre la bulle de sécurité beaucoup plus petite (donc plus précise) quand le bruit n'est pas le même partout, tout en gardant la garantie de sécurité.

🎯 En résumé

Ce papier propose un nouveau GPS de sécurité pour les robots et les voitures autonomes.

Avant : On dessinait une bulle énorme et imprécise, ou on prenait le risque de ne pas voir le pire cas.
Aujourd'hui (CDDR) : On utilise les données passées pour "tester" la taille de la bulle nécessaire. On obtient une bulle juste assez grande pour être sûre à 100 % (avec une très haute confiance) que le robot ne sortira pas, même si on ne connaît pas parfaitement les lois de la physique derrière lui.

C'est comme passer d'un conducteur qui panique et freine brusquement à un pilote qui connaît exactement la limite de sa voiture et sait naviguer en toute sécurité, même sur une route inconnue.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique

L'analyse de la faisabilité (reachability analysis) vise à calculer l'ensemble de tous les états qu'un système dynamique peut atteindre à partir d'un ensemble d'états initiaux et d'entrées données. C'est un outil fondamental pour la vérification de la sécurité des systèmes cyber-physiques.

Les méthodes existantes souffrent de limitations majeures :

Approches basées sur le modèle : Nécessitent un modèle explicite du système, souvent indisponible ou coûteux à obtenir.
Méthodes pilotées par les données existantes :
- Elles requièrent souvent des bornes de bruit de processus connues ( $Z_w$ ) ou des paramètres structurels spécifiques (comme les constantes de Lipschitz pour les systèmes non linéaires).
- Dans la pratique, les distributions de bruit sont souvent inconnues et les constantes de Lipschitz difficiles à estimer pour des systèmes non lisses.
- Les méthodes empiriques (basées sur le maximum des résidus d'entraînement) ne garantissent pas formellement la couverture si le jeu de données d'entraînement ne contient pas le pire cas, ce qui est impossible à vérifier avec des données finies.

L'objectif est donc de développer une méthode pilotée par les données, distribution-free (sans hypothèse sur la distribution du bruit), capable de fournir des garanties formelles de couverture même en présence de bruit inconnu et de dynamiques non linéaires complexes.

2. Méthodologie : CDDR (Conformalized Data-Driven Reachability)

Les auteurs proposent un cadre nommé CDDR, qui combine l'apprentissage de modèles avec la Conformal Prediction (Prédiction Conformée) via le protocole Learn Then Test (LTT).

A. Principes Fondamentaux

Approche "Learn Then Test" (LTT) : Contrairement à la prédiction conformée marginale standard (qui garantit une couverture moyenne conditionnelle à un seul jeu de calibration), LTT fournit une garantie PAC (Probably Approximately Correct). Cela signifie que la probabilité que la couverture réelle soit supérieure à $1-\alpha $est d'au moins$ 1-\delta$, sur l'ensemble des tirages possibles de données de calibration.
Découplage Modèle-Garantie : La précision du modèle (linéaire ou non) n'affecte pas la validité statistique de la garantie. Toute erreur de modélisation (linéarisation, non-linéarité non modélisée) est absorbée dans le résidu, qui est ensuite calibré statistiquement.

B. Procédure Algorithmique

Le cadre CDDR fonctionne en trois phases :

Apprentissage (Training) : Un modèle (linéaire global pour les LTI, ou affine local pour les non-linéaires) est ajusté sur un ensemble de données d'entraînement ( $D_{tr}$ ).
Calibration (Calibration) : Sur un ensemble de calibration ( $D_{cal}$ $D_{c a l}$ ), des scores de résidus (erreurs de prédiction) sont calculés.
- Un seuil $\hat{q}_k$ est sélectionné pour chaque pas de temps $k$ en utilisant le test LTT avec une correction de Bonferroni ( $\alpha/N, \delta/N$ ) pour garantir la couverture multi-étapes.
- Ce seuil définit un zonotope d'erreur conformée $Z^{CP}_k$ .
Propagation (Propagation) : Les ensembles de faisabilité sont propagés en utilisant le modèle appris et les zonotopes d'erreur conformés.
- Systèmes LTI : Utilisation d'une matrice de transition estimée.
- Systèmes LTI avec bruit de mesure : Le bruit de mesure est traité comme une incertitude bornée ( $Z_v$ ) connue, nécessitant une expansion de l'ensemble via une somme de Minkowski pour couvrir tous les états cohérents avec l'observation.
- Systèmes Non Linéaires : Utilisation de modèles affines locaux linéarisés autour d'une trajectoire nominale, sans exigence de continuité Lipschitzienne.

C. Fonction de Score et Anisotropie

Pour réduire le volume des ensembles de faisabilité (qui peuvent être trop conservateurs avec une norme $\ell_\infty$ isotrope), les auteurs proposent une fonction de score normalisée :
$s_{j,k} = \| T_k^{-1} r_{j,k} \|_\infty$
où $T_k$ est une matrice diagonale estimée à partir des données d'entraînement pour capturer l'anisotropie du bruit. Cela permet de réduire considérablement le volume tout en conservant la garantie PAC sans coût statistique supplémentaire.

3. Contributions Clés

Garantie PAC Formelle : Première méthode de faisabilité pilotée par les données offrant une garantie $(\alpha, \delta)$ -PAC valide sur la sélection aléatoire des données de calibration, sans hypothèse sur la distribution du bruit.
Applicabilité Générale : Le cadre s'applique à :
- Systèmes LTI avec bruit de processus inconnu.
- Systèmes LTI avec bruit de mesure borné.
- Systèmes non linéaires généraux, y compris ceux avec des dynamiques non-Lipschitziennes (ex: amortissement fractionnaire), là où les méthodes existantes échouent.
Optimisation Géométrique : Introduction d'une fonction de score normalisée exploitant l'anisotropie du bruit pour réduire le volume des ensembles de plusieurs ordres de grandeur tout en maintenant la garantie de sécurité.
Principe de Découplage : Démonstration que la validité de la couverture est indépendante de la précision du modèle sous-jacent.

4. Résultats Expérimentaux

Les expériences ont été menées sur deux systèmes :

Système 1 : Un système LTI 5D avec du bruit Gaussien et du bruit Student-t (à queues lourdes).
Système 2 : Un système non linéaire 2D avec amortissement fractionnaire (non-Lipschitz).

Comparaison avec les bases de référence :

Empirical-max (Emp.-max) : Utilise le maximum des résidus d'entraînement. Échoue à garantir la couverture formelle (taux d'échec > 0% sur les tirages aléatoires), surtout avec des bruits à queues lourdes.
Marginal CP : Offre une couverture marginale mais pas de garantie PAC (taux d'échec observé de 6,5% dans les tests).
CDDR (Proposé) :
- Couverture : Atteint 100% de couverture sur les trajectoires de test avec une garantie PAC stricte (taux d'échec de 0% sur 1000 tirages aléatoires).
- Volume : Bien que légèrement plus conservateur que le CP marginal (en raison de la robustesse PAC), il est nettement plus efficace que la méthode Emp.-max.
- Performance Anisotrope : Avec la fonction de score normalisée, le volume de l'ensemble de faisabilité est réduit de 4 ordres de grandeur par rapport à la version isotrope, tout en nécessitant le même nombre minimal de trajectoires de calibration.

5. Signification et Impact

Ce travail représente une avancée significative pour la sécurité des systèmes cyber-physiques :

Robustesse : Il élimine le besoin d'hypothèses restrictives sur le bruit ou la régularité du système, rendant l'analyse de faisabilité applicable à des scénarios réels complexes où les modèles exacts sont inconnus.
Fiabilité Statistique : En passant d'une garantie marginale (valable en moyenne) à une garantie PAC (valable avec haute probabilité sur n'importe quel jeu de calibration), il offre un niveau de confiance bien supérieur pour les applications critiques.
Efficacité : La capacité à gérer des dynamiques non-Lipschitziennes et à optimiser la géométrie des ensembles via l'anisotropie du bruit rend la méthode pratique et moins conservatrice que les approches purement déterministes ou empiriques.

En conclusion, CDDR établit un nouvel état de l'art pour l'analyse de faisabilité pilotée par les données, combinant rigueur statistique et flexibilité algorithmique.