⚡ electrical engineering

Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions

Cet article présente un algorithme permettant de calculer des bornes supérieures et inférieures garanties pour les fonctions de valeur de l'analyse de faisabilité Hamilton-Jacobi, assurant ainsi des sur-approximations et sous-approximations sûres des ensembles de retour, complété par une méthode de raffinement pour améliorer la précision de ces bornes.

Auteurs originaux : Ihab Tabbara, Eliya Badr, Hussein Sibai

Publié 2026-03-31

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Ihab Tabbara, Eliya Badr, Hussein Sibai

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes le capitaine d'un navire (un système de contrôle, comme une voiture autonome ou un robot chirurgical) naviguant dans une mer pleine d'îles dangereuses (les zones d'échec) et cherchant à atteindre un trésor (la cible). Votre objectif est double : ne jamais toucher les îles et atteindre le trésor.

Le problème, c'est que la mer est immense et continue. Pour la cartographier, nous devons la diviser en une grille de petits carrés (comme une carte au trésor quadrillée). C'est là que les méthodes traditionnelles échouent souvent : elles dessinent leur carte en se basant sur les centres de ces carrés, mais elles oublient de vérifier les bords. Résultat ? Une carte qui peut sembler sûre alors qu'elle cache des écueils, ou inversement, qui vous dit qu'une zone est dangereuse alors qu'elle est en fait sûre. C'est comme si votre GPS vous disait "tournez à gauche" alors que vous allez droit dans un mur, simplement parce qu'il a mal calculé la précision de votre position.

Voici comment les auteurs de cette recherche ont résolu ce problème, expliqué simplement :

1. Le Dilemme de la Carte Floue

Les méthodes classiques utilisent une grille pour calculer les trajets possibles. Mais comme le monde réel est lisse et continu, alors que la grille est faite de blocs rigides, il y a toujours une petite erreur de calcul (comme essayer de dessiner un cercle parfait avec des carrés Lego).

Le risque : Vous pourriez penser qu'une zone est sûre (vous pouvez atteindre le trésor), alors qu'en réalité, si vous êtes au bord du carré, vous pourriez heurter un obstacle.
L'objectif : Créer une carte qui ne se trompe jamais. Si elle dit "sûr", c'est 100% sûr. Si elle dit "dangereux", c'est 100% dangereux.

2. La Solution : Deux Cartes, Une Sûre et Une Prudente

Au lieu de dessiner une seule carte floue, l'algorithme proposé dessine deux cartes simultanément pour chaque petit carré de la grille :

La Carte "Pessimiste" (La limite basse) : C'est la version la plus prudente. Elle suppose le pire des scénarios pour chaque mouvement. Si cette carte dit "c'est sûr", alors c'est garanti sûr, même si vous êtes au bord du carré. C'est votre filet de sécurité.
La Carte "Optimiste" (La limite haute) : C'est la version qui imagine le meilleur des scénarios. Si cette carte dit "c'est dangereux", alors c'est garanti dangereux.

En comparant ces deux cartes, l'algorithme crée une "zone grise" :

Si la carte pessimiste dit "sûr", alors tout le carré est sûr.
Si la carte optimiste dit "dangereux", alors tout le carré est dangereux.
Si les deux cartes sont en désaccord (l'une dit peut-être, l'autre non), alors le carré est incertain.

3. L'Intelligence Artificielle du "Arrêt Anticipé"

Calculer ces cartes prend beaucoup de temps, comme essayer de résoudre un puzzle géant. Souvent, on arrête le calcul avant la fin pour gagner du temps. Le problème, c'est que s'arrêter trop tôt rend la carte fausse.

Les auteurs ont inventé une astuce mathématique : ils ajoutent un "bonus de sécurité" (une correction) à la carte pessimiste à chaque fois qu'ils arrêtent le calcul. C'est comme si, en arrêtant de compter les pièces du puzzle, vous ajoutiez automatiquement une marge de sécurité supplémentaire pour compenser les pièces manquantes. Ainsi, même si vous arrêtez le calcul en cours de route, votre carte "sûre" reste fiable.

4. Le Loupe Magique (Raffinement Adaptatif)

Parfois, la zone grise (l'incertitude) est trop grande. Imaginez que vous avez un carré de 10 mètres de large qui est "incertain". C'est trop gros pour prendre une décision.
L'algorithme utilise alors une loupe magique :

Il repère les carrés incertains.
Il les coupe en deux (ou en quatre) pour les rendre plus petits.
Il recalcule les deux cartes (pessimiste et optimiste) sur ces nouveaux petits carrés.
Il recommence jusqu'à ce que chaque carré soit clairement "sûr" ou "dangereux".

C'est comme zoomer sur une photo floue : plus on zoome, plus les détails deviennent clairs, sans avoir besoin de zoomer sur toute la photo d'un coup (ce qui serait trop lent).

En Résumé

Cette recherche propose une méthode pour cartographier la sécurité des robots et des véhicules autonomes avec une précision mathématique absolue.

Elle ne se contente pas de dire "probablement sûr".
Elle donne des garanties solides (des bornes supérieures et inférieures).
Elle s'adapte intelligemment, en ne zoomant que sur les zones douteuses.

C'est comme avoir un navigateur qui ne se contente pas de vous dire "la route est libre", mais qui vous garantit : "Même si vous déviez de quelques centimètres, vous ne toucherez jamais un obstacle, et voici exactement jusqu'où vous pouvez aller en toute sécurité."

1. Problématique

L'analyse de la faisabilité (reachability) basée sur l'équation de Hamilton-Jacobi (HJ) est un outil fondamental pour la vérification de la sécurité et la synthèse de contrôle des systèmes non linéaires. L'objectif est de déterminer l'ensemble des états initiaux (l'ensemble de retour arrière ou BRS, et l'ensemble de poursuite-évitement ou RAS) à partir desquels un système peut soit éviter un ensemble d'échec $F$ , soit atteindre une cible $T$ tout en évitant $F$ .

Cependant, les méthodes classiques de résolution numérique de l'équation aux dérivées partielles (EDP) de HJ sur des grilles discrètes souffrent de limitations majeures :

Erreurs de discrétisation non prises en compte : Les solutions approchées ne garantissent pas que les ensembles calculés sur-approximent le BRS (pour les spécifications d'évitement) ou sous-approximent le RAS (pour les spécifications de poursuite-évitement).
Manque de garanties formelles : En raison des erreurs de grille, il est possible de classer à tort un état dangereux comme sûr, ou inversement.
Arrêt prématuré de l'itération : Les algorithmes d'itération de valeur doivent souvent être arrêtés avant convergence, ce qui introduit des erreurs supplémentaires non quantifiées dans les méthodes existantes.

L'article propose de résoudre ces problèmes en développant un cadre capable de calculer des bornes supérieures et inférieures sonores (sound bounds) sur la fonction de valeur de HJ, garantissant ainsi des approximations conservatrices et correctes des ensembles de sécurité.

2. Méthodologie

La méthode proposée repose sur une abstraction discrète du système continu et le calcul de deux fonctions de valeur distinctes sur une grille.

A. Abstraction Discrète et Bornes Locales

Le système dynamique continu est discrétisé en une grille finie $G$ . Pour chaque cellule $s$ de la grille :

Les fonctions de défaillance $l(x)$ et de récompense $r(x)$ sont bornées localement en utilisant les constantes de Lipschitz ( $L_l, L_r$ ) et le rayon de la cellule. Cela permet de définir des valeurs minimales ( $\underline{l}, \underline{r}$ ) et maximales ( $\overline{l}, \overline{r}$ ) pour chaque cellule.
Une relation de transition non déterministe $\Delta$ est construite en sur-approximant l'ensemble des états atteignables à partir d'une cellule sous une action donnée, en tenant compte de la constante de Lipschitz de la dynamique $f$ .

B. Calcul des Bornes de Valeur

L'algorithme calcule deux fonctions de valeur sur l'espace d'états discret $S$ :

$V^\gamma$ (Borne supérieure) : Représente la meilleure mesure de poursuite-évitement possible (scénario le plus favorable). Elle est calculée en prenant le maximum sur les actions et le minimum sur les successeurs possibles (pour garantir la sécurité).
$\underline{V}^\gamma$ (Borne inférieure) : Représente la pire mesure possible (scénario le plus défavorable). Elle est calculée en prenant le minimum sur les successeurs pour garantir que même dans le pire cas, la sécurité est maintenue.

Ces fonctions satisfont des équations de Bellman spécifiques qui sont des contractions, garantissant l'existence de points fixes uniques.

C. Gestion de l'Arrêt Prématuré (Early Stopping)

Un apport majeur de la méthode est la capacité à arrêter l'itération de valeur avant la convergence complète tout en maintenant les garanties de sécurité :

Pour la borne inférieure ( $\underline{V}^\gamma$ ), un terme de correction est ajouté à la valeur calculée à l'itération $k$ . Ce terme dépend de la variation minimale entre les itérations successives ( $\delta_k$ ) et du facteur d'actualisation $\gamma$ . Cela garantit que la valeur corrigée reste une sous-approximation sonore de la vraie fonction de valeur.
Pour la borne supérieure, il est prouvé que si l'initialisation est appropriée (basée sur la fonction de défaillance), chaque itération fournit une sur-approximation valide, même avant convergence.

D. Algorithme de Raffinement Adaptatif

Pour les cellules où les bornes calculées ne permettent pas de classer l'état comme sûr ou dangereux (c'est-à-dire lorsque la borne inférieure est $\le 0$ et la borne supérieure $> 0$ ), un algorithme de raffinement (Algorithme 2) est déclenché :

Ces cellules "non classées" sont divisées en sous-cellules plus petites le long de leur plus grande dimension.
Le processus d'itération de valeur est relancé sur la grille raffinée.
Cela permet d'obtenir des approximations plus précises (des ensembles RAS et BRS plus fins) sans sur-dimensionner toute la grille.

3. Contributions Clés

Algorithmes de bornes sonores : Présentation d'un algorithme calculant des bornes supérieures et inférieures rigoureuses pour les fonctions de valeur HJ, garantissant une sur-approximation du BRS et une sous-approximation du RAS, même avec des erreurs de discrétisation.
Gestion de l'arrêt prématuré : Démonstration théorique que les bornes restent valides même si l'itération de valeur est arrêtée avant convergence, grâce à un terme de correction mathématiquement justifié.
Raffinement adaptatif local : Développement d'une stratégie de raffinement de grille qui ne divise que les cellules incertaines, optimisant ainsi le compromis entre précision et coût computationnel.
Validation comparative : Démonstration expérimentale que la méthode surpasse les outils existants (comme ROCS 2.0 et les solveurs HJ classiques) en termes de taille de l'ensemble de sécurité calculé et de garanties formelles.

4. Résultats Expérimentaux

Les auteurs ont validé leur approche sur deux études de cas :

Voiture de Dubins : Un modèle de véhicule avec des contraintes de courbure.
Évasion 3D : Un scénario d'évitement de collision entre un poursuivant et un évadant.

Résultats observés :

Précision et Sécurité : Contrairement aux solveurs HJ classiques qui peuvent étiqueter à tort des états dangereux comme sûrs (surtout avec des grilles grossières), la méthode proposée ne commet jamais d'erreur de classification sur les cellules classées.
Efficacité du raffinement : L'algorithme de raffinement permet d'affiner progressivement la frontière entre les zones sûres et dangereuses, réduisant le nombre de cellules "grises" (non classées).
Comparaison avec ROCS 2.0 : Sur le cas de la voiture de Dubins, la méthode proposée a calculé un ensemble de poursuite-évitement (RAS) plus grand que ROCS 2.0, tout en offrant des bornes de valeur (et non seulement une classification binaire) et en étant plus rapide pour des résolutions équivalentes.
Impact du facteur d'actualisation ( $\gamma$ ) : L'utilisation d'un $\gamma < 1$ permet une interprétation quantitative du temps de convergence, tandis que $\gamma = 1$ est nécessaire pour les problèmes d'évitement pur (avoid-only) afin de garantir la classification des états sûrs.

5. Signification et Impact

Cet article apporte une contribution significative à la vérification formelle des systèmes de contrôle non linéaires :

Fiabilité accrue : En fournissant des garanties mathématiques sur les bornes des ensembles de sécurité, la méthode élimine le risque de faux positifs (considérer un état dangereux comme sûr), ce qui est critique pour les applications de sécurité (véhicules autonomes, robots chirurgicaux).
Flexibilité : La capacité à gérer l'arrêt prématuré de l'itération de valeur rend l'algorithme plus pratique pour les systèmes complexes où la convergence complète est trop coûteuse.
Optimisation des ressources : Le raffinement adaptatif permet de concentrer les ressources de calcul uniquement sur les zones frontières incertaines, offrant une meilleure précision là où elle est nécessaire sans exploser la complexité computationnelle globale.

En résumé, ce travail transforme l'analyse de faisabilité de HJ d'une approche purement approximative en une méthode rigoureuse et certifiable, capable de fournir des marges de sécurité quantifiées pour des systèmes dynamiques complexes.