Rechercher

sur ce site


Accueil du site > Equipes_Fr_En_It > Commands-fr

COMMANDS

COMMANDS (Equipe Inria-Saclay Ile-de-France, CMAP) :

Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems Controle, Optimisation, Modèles, Méthodes et Applications pour les Systèmes Dynamiques non linéaires

Voir aussi : Le site de l’équipe Inria COMMANDS

Responsable :

- J. Frédéric BONNANS, Directeur de Recherche Inria.

Chercheur :

- Pierre MARTINON, Chargé de Recherche Inria
- Axel KRÖNER, Chercheur contractuel

Assistante administrative des équipes Inria

- Jessica GAMEIRO

Ingénieur de recherche

- Olivier TISSOT

Chercheurs Doctorants :

- Benjamin HEYMANN (1ère année)
- Nicolas GREBILLE (2nde année)
- Florine BLEUSE (1ère année)

Anciens Doctorants et Post-doctorants

- Laurent PFEIFFER
- Xavier DUPUIS
- Zhiping RAO
- Philip Jonathan GRABER
- Athéna PICARELLI
- Cristopher HERMOSILLA
- Mohammed ASSELAOU

Activités de recherche :

L’objectif de cette équipe est le développement d’algorithmes pour l’optimisation de systèmes dynamiques, et leur application à des problèmes issus soit de systèmes techniques, soit de modèles économiques. Les dynamiques considérées sont soit déterministes, soit stochastiques, et en temps discret ou continu.

Les applications des algorithmes considérés portent sur l’optimisation de trajectoires aérospatiales, la gestion optimale de stocks d’énergie, l’optimisation de portefeuille, les processus de production.

Axes de recherche

- L’optimisation de trajectoires de systèmes décrits par des équations différentielles, par les méthodes de discrétisation directe combinées aux algorithmes de points intérieurs, comme par les algorithmes de tir.
- La résolution des problèmes de commande optimale déterministe par résolution numérique de l’équation HJB (Hamilton-Jacobi-Bellman)
- Le contrôle stochastique et les schémas spécifiques de résolution de l’équation HJB du second ordre associée
- La programmation stochastique

A - Optimisation de trajectoires

Pour ces problèmes d’optimisation dynamique déterministe, en temps continu, l’approche trajectorielle consiste à centrer l’analyse comme les algorithmes sur la trajectoire (par opposition à l’approche HJB par exemple). Les applications concernent en particulier les systèmes de dimension trop élevée pour faire appel à l’approche HJB : trajectoires d’avions et de fusée, génie chimique, robots par exemple.

1. Méthodes directes

Dans le cadre de la thèse de J. Laurent-Varin , l’équipe a développé des algorithmes de minimisation par points intérieurs, bien adaptés par exemple aux problèmes de rentrée atmosphérique. Les performances intrinsèques des algorithmes de points intérieurs, combinées à la structure spécifique de l’algèbre linéaire issue des problèmes dynamiques, permet d’obtenir des méthodes rapides et générales. Un résultat important est la qualité pratique de l’estimation d’erreur et la possibilité de raffinement de la discrétisation au cours de l’algorithme. La question théorique sous-jacente est l’estimation d’erreur due à la pénalisation logarithmique, pour le problème continu et l’ordre de grandeur des pas, sur chaque arc (défini par les contraintes actives) et au voisinage des points de jonction. F. Bonnans et F. Alvarez (Universidad de Chile) ont obtenu des résultats préliminaires dans cette direction.

2. Méthodes de tir

Les méthodes de tir, basées sur des algorithmes de Newton, et éventuellement combinées à des méthodes d’homotopie, permettent un calcul numérique très précis de la solution. P. Martinon a étudié les approches par homotopie simpliciale. Nous étudions le caractère bien posé de ces méthodes et leur stabilité numérique, ainsi que la possibilité d’automatiser les transitions entre différentes structures d’ensembles de contraintes actives afin de systématiser la mise en oeuvre des méthodes de tir. Certains résultats obtenus dans le cadre de la thèse de A. Hermant fournissent un cadre théorique dans le cas de hamiltoniens fortement convexes.

3. Problèmes de lanceurs

Le problème d’ascension optimale de lanceurs spatiaux conduit naturellement à une formulation comportant un arc singulier, qui pour des trajectoires verticales se réduit au classique problème de Goddard. Il est donc utile d’étudier ce type de problème pour lequel nous proposons des algorithmes efficaces. F. Bonnans, E. Trélat et P. Martinon étudient les possibilités d’extension, notamment en présence de contraintes de retombées d’étages.

4. Développements théoriques

Les questions d’analyse de sensibilité et de convergence des algorithmes sont intimement liées à celles de l’analyse locale de ces problèmes. Ainsi le caractère bien posé des algorithmes de tir s’obtient typiquement en vérifiant qu’un certain problème quadratique tangent est fortement convexe. F. Bonnans et A. Hermant ont progressé sur ces questions pour des problèmes avec hamiltonien satisfaisant la condition de Legendre-Clebsch forte (avec contraintes sur l’état ou mixtes). En l’absence de la condition de Legendre-Clebsch forte (et pour des trajectoires comportant des arcs singuliers), la question reste largement ouverte. Par ailleurs, l’existence de trajectoires singulières étant une source de divergence possible des algorithmes, des résultats de Y. Chitour, F. Jean et E. Trélat démontrent la possibilité d’éviter ces problèmes dans un cadre générique. Ils développent actuellement des méthodes de planification de trajectoires utilisant ces résultats de généricité.

B - Résolution des problèmes de commande optimale déterministe par résolution numérique de l’équation HJB (Hamilton-Jacobi-Bellman)

Une autre approche pour les problèmes de commande consiste à remarquer d’abord que la fonction valeur (celle qui à chaque valeur de l’état initial associe la valeur du coût optimal du problème) est solution, dans un sens généralisé, d’une EDP appelée Hamilton-Jacobi-Bellman (HJB). Ces équations apparaissent aussi dans plusieurs autres domaines intéressants : propagation de fronts, imagerie, ... etc

1. Études théoriques des équations HJB

Une partie de notre activité porte sur l’étude des équations HJB provenant des problèmes de contrôle optimal déterministes avec contraintes sur l’état (exemple : rentrée atmosphérique en temps minimal avec contraintes de charge et/ou de flux thermique). Lorsque le problème n’est pas supposé être contrôlable partout, la fonction valeur qui est discontinue, n’est plus l’unique solution de viscosité de l’équation HJB (ni au sens de Soner, ni même celui de Ishii-Koïke). H. Zidani et O. Bokanowski (Paris 7) étudie un sens plus général qui permet de caractériser la fonction valeur. Ce sens se base sur des notions d’épi-dérivées déjà utilisées pour des problèmes similaires par Frankowska et al. La reconstruction des trajectoires optimales, à partir du calcul de la fonction valeur, reste un problème ouvert.

2. Schémas anti-diffusifs pour les équations HJB

Du fait que dans nos problèmes de commande la fonction valeur est discontinue, une approximation de l’équation HJB par des schémas "monotones" n’est pas raisonnable à cause du problème de la diffusion numérique qui cache la discontinuité. Or, cette discontinuité représente (dans nos problèmes) l’interface séparant le domaine des trajectoires admissibles de celui des trajectoires prohibées. Dans le cadre de la thèse de N. Megdich, nous nous intéressons à développer et étudier des schémas anti-diffusifs pour les équations HJB et plus généralement pour la propagation de fronts. N. Megdich et H. Zidani (en collaboration avec O. Bokanowski) ont récemment étudié une généralisation du schéma Ultra-bee pour des équations HJB du premier ordre, et obtenu, en dimension 1, un résultat de convergence et une estimation d’erreur, dans le cas d’une condition initiale éventuellement discontinue. Ce résultat semble être une avancée importante, puisque c’est le premier schéma explicite non-monotone dont on obtient une preuve de convergence vers la solution de viscosité, et une estimation d’erreur et ceci même dans le cas discontinu. Les tests numériques réalisés en dimension 2 ou 3, pour le calcul de bassins de capture ou de domaines de viabilité, sont très encourageants.

Notons aussi que le caractère anti-diffusif du schéma a permis de concevoir des codes rapides sur des grilles adaptatives ou des grilles creuses.

C - Analyse numérique d’équations HJB provenant du contrôle stochastique.

L’approche HJB pour les problèmes de contrôle stochastiques aboutit aussi à la résolution d’équations HJB. La difficulté spécifique (additionnelle) de ces équations vient du fait qu’elles sont du second ordre, et que le terme de diffusion peut être dégénéré.

1- Schémas de différences finies

F. Bonnans et H. Zidani ont proposé et analysé la classe de schémas numériques dite différences finies généralisées (DFG). Ces schémas généralisent en effet les méthodes usuelles de différences finies classiques. Ces derniers ne sont monotones, et donc valides, que si la matrice de covariance mise à l’échelle est diagonale dominante. Nous généralisons ce résultat en fournissant, étant donné l’ensemble des points voisins pouvant intervenir dans le schéma, un moyen de calculer la classe de matrices de covariances consistantes. En dimension 2, F. Bonnans, E. Ottenwaelter et H. Zidani ont obtenu une implémentation rapide DFG. En particulier, la décomposition (ou approximation) de la matrice de covariance en diffusions élémentaires pointant vers des points de la grille, peut être effectuée en $O(p)$ opérations, où $p$ est une mesure de l’écart maximal entre points (de la grille) pouvant intervenir dans le schéma. L’application de ce schéma à la résolution d’un problème de surcouverture en dimension 2, a donné des résultats très satisfaisants.

2- Estimations d’erreur

Comme dans tous les problèmes d’approximation numérique, il est important d’avoir des estimations de l’erreur d’approximation, afin de garantir la qualité des solutions approchées calculées. Pour les équations HJB du premier ordre, ces estimations sont établies et connues depuis les années 80s. Le cas de l’ordre 2 est beaucoup plus complexes et les premiers résultats sont apparus (seulement) à partir de la fin des années 90’s. F. Bonnans, S. Maroso et H. Zidani ont étendu des résultats obtenus par Krylov, Barles et Jackobsen , dans le cas d’équations HJB avec Hamiltonien convexe, à des cas plus généraux comme les équations de Isaac (provenant du jeux différentiels), les inéquations variationnelles associées au contrôle impulsionnel, ou encore les problèmes de contrôle avec des variables de commande non bornées.

D - Programmation stochastique

Ces problèmes d’optimisation dynamique avec incertitude, en temps discrets, surgissent dans une foule de problèmes industriels : gestion de réserves de gaz, des réserves hydrauliques, investissement, etc. La tendance récente est de prendre en compte les opérations de couverture financière, et aussi d’affiner le critère en y incluant des mesures de risque.

1. Méthodes de décomposition

L’approche par scénarios conduit à des problèmes d’optimisation de très grande taille, qui par dualité se ramènent à des problèmes convexes. Nous étudions de nouvelles variantes des algorithmes de faisceau permettant de traiter ces problèmes de grande dimension. Ces travaux sont menés en collaboration avec C. Sagastizàbal (IMPA), dans le cadre de la thèse de G. Emiel.

2. Programmation dynamique duale Dans le cas de problèmes convexes, la programmation dynamique duale fournit une alternative efficace au choix habituel entre discrétisation de l’espace d’état et tirage d’aléas. Elles peuvent se combiner avec la discrétisation partielle de l’espace d’état dans le cas de convexité partielle. L’analyse de convergence dans ce cas est encore largement ouverte.

3. Règles de décision et formulations robustes

Cette approche consiste à paramaîtriser la commande en fonction des aléas, le plus simple étant la règle linéaire dans laquelle la commande est fonction affine de combinaison des aléas. Le grand avantage de cette approche est (si le problème d’origine est convexe) la convexité du problème d’optimisation des paramètres. Travaux menés en collaboration avec J. Ph. Vial (Ordecsys) dans le cadre de la thèse de R. Apparigliato.


CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 00 Fax: +33 1 69 33 46 46