Hamilton-Jacobi-Bellman Equation (HJB)

Aussi appelé: HJB, HJB equation
Catégorie: Control › Feedback control
Mots-clés: optimal-control, dynamic-programming, value-function, pde, safety

L'équation aux dérivées partielles dont la solution est la fonction de valeur optimale d'un problème de commande optimale en temps continu ; la forme en temps continu du principe d'optimalité de Bellman.

Définition

L'équation de Hamilton-Jacobi-Bellman (HJB) (Hamilton-Jacobi-Bellman equation) est l'équivalent en temps continu de l'équation de Bellman. Pour un système de dynamique ẋ = f(x, u), de coût courant ℓ(x, u) et de coût terminal φ(x), le coût restant optimal V(x, t) satisfait −∂V/∂t = min over u of [ ℓ(x, u) + ∇V(x, t) · f(x, u) ], avec V(x, T) = φ(x) à l'instant final. L'équation découle du principe d'optimalité de Bellman : le meilleur coût depuis un état quelconque est égal au coût du meilleur premier pas infinitésimal plus le coût optimal depuis l'endroit où ce pas mène. Une fois V connue, la commande optimale en tout état est le u qui atteint le minimum, si bien que la solution donne une loi de rétroaction sur tout l'espace d'états, et pas seulement une trajectoire.

Pour les systèmes stochastiques entraînés par du bruit, dx = f(x, u) dt + σ(x) dW, l'équation gagne un terme du second ordre, ½ tr(σσᵀ ∇²V), qui rend compte de la diffusion. Les problèmes à horizon infini et actualisés donnent une forme stationnaire sans dérivée temporelle. Pour une dynamique linéaire et un coût quadratique, V est quadratique et l'équation HJB se ramène à l'équation de Riccati qui sous-tend le régulateur linéaire quadratique. En général, V n'a pas besoin d'être différentiable, et la bonne notion de solution est la solution de viscosité introduite par Crandall et Lions en 1983. Le principe du maximum de Pontriaguine est l'approche complémentaire : il donne des conditions nécessaires le long d'une seule trajectoire optimale plutôt qu'une fonction de valeur sur tous les états.

Le principal obstacle est le fléau de la dimension : les solveurs sur grille croissent exponentiellement avec la dimension de l'état, si bien que les solutions exactes ne sont praticables que pour des systèmes à quelques états. De nombreuses méthodes robotiques peuvent se lire comme des moyens de contourner cet obstacle. La programmation dynamique différentielle et iLQR développent la fonction de valeur localement le long d'une trajectoire ; la commande par intégrale de chemin utilise une transformation qui rend linéaire l'équation HJB stochastique ; les méthodes d'apprentissage profond approchent V par des réseaux de neurones, par exemple en résolvant des équations différentielles stochastiques progressives-rétrogrades équivalentes. Une équation étroitement liée, l'équation de Hamilton-Jacobi-Isaacs, décrit les jeux à deux joueurs et sous-tend l'analyse d'atteignabilité de Hamilton-Jacobi (Hamilton-Jacobi reachability), qui calcule des ensembles d'états à partir desquels un système peut être maintenu en sécurité malgré des perturbations.

Pourquoi c'est important

L'équation HJB est le point de référence théorique de la commande optimale par rétroaction en temps continu. Elle relie la LQR, l'optimisation de trajectoire, les méthodes par intégrale de chemin, la sûreté fondée sur l'atteignabilité et l'apprentissage par renforcement en temps continu, et elle explique pourquoi la commande optimale exacte est limitée aux systèmes de faible dimension.

Applications principales

Dérivation de contrôleurs optimaux par rétroaction, dont la LQR via l'équation de Riccati
Analyse d'atteignabilité de Hamilton-Jacobi pour la vérification de sûreté et les ensembles sûrs
Commande optimale stochastique par intégrale de chemin et à base d'échantillonnage
Apprentissage par renforcement en temps continu et approximation de la fonction de valeur
Solveurs neuronaux et solveurs d'EDS progressives-rétrogrades pour la commande optimale en grande dimension

En pratique

Une équipe qui conçoit un contrôleur de sécurité pour un petit robot terrestre le modélise comme un véhicule de type Dubins à trois états soumis à une perturbation bornée. Elle résout l'équation d'atteignabilité de Hamilton-Jacobi associée sur une grille en position et en cap avec une boîte à outils d'ensembles de niveau, ce qui donne une fonction de valeur dont l'ensemble de niveau zéro marque les états à partir desquels une collision peut toujours être évitée. Hors ligne, le calcul prend quelques minutes ; en ligne, le robot consulte la valeur et son gradient à l'état courant pour décider quand passer outre le planificateur nominal. Pour un manipulateur comptant beaucoup plus d'états, la même approche sur grille serait irréalisable, et l'équipe se rabat donc sur des méthodes locales comme iLQR ou des approximations apprises de la valeur.

Idées reçues

L'équation HJB n'a qu'un intérêt théorique — elle est résolue directement pour des systèmes de faible dimension en analyse d'atteignabilité et sous-tend des méthodes pratiques comme la LQR, la DDP et MPPI
La fonction de valeur est toujours lisse — dans de nombreux problèmes, V présente des points anguleux, et l'équation doit être comprise au sens de la viscosité
L'équation HJB et le principe du maximum de Pontriaguine donnent la même chose — HJB donne une fonction de valeur et une loi de rétroaction sur tous les états, tandis que Pontriaguine donne des conditions nécessaires le long d'une trajectoire

Qui devrait le savoir

Ingénieurs en commande travaillant sur la commande optimale et la commande sûre
Chercheurs en analyse d'atteignabilité et en vérification de sûreté
Chercheurs en apprentissage par renforcement travaillant en temps continu
Étudiants de master et doctorants en automatique et en robotique

Technologies associées

Régulateur linéaire quadratique (Linear-Quadratic Regulator, LQR)
Équation de Riccati (Riccati Equation)
Principe du maximum de Pontriaguine (Pontryagin's Maximum Principle)
Méthodes des ensembles de niveau (Level Set Methods)
Atteignabilité de Hamilton-Jacobi (Hamilton-Jacobi Reachability)
Équations différentielles stochastiques progressives-rétrogrades (Forward-Backward Stochastic Differential Equations)

Termes associés

Projets associés

NASA Ogma: NASA runtime monitor generator for safe robotics and flight systems

Vidéos

Nonlinear Control: Hamilton Jacobi Bellman (HJB) and Dynamic Programming: Steve Brunton