Maintenir la viabilité ou la résilience d'un sytème :
les machines à vecteurs de support pour rompre la malédiction de la dimensionnalité ?


Thèse de doctorat de l'université Blaise Pascal, soutenue le 19 otobre 2007.
thèse slides

Jury



Résumé


La théorie de la viabilité propose des concepts et méthodes pour contrôler un système dynamique afin de le maintenir dans un ensemble de contraintes de viabilité. Les applications sont nombreuses en écologie, économie ou robotique, lorsqu'un système meurt ou se détériore lorsqu'il quitte une certaine zone de son espace d'états. A partir du calcul du noyau de viabilité ou du bassin de capture d'un système, elle permet de définir des politiques d'action qui maintiennent le système dans l'ensemble de contraintes choisi. Cependant, les algorithmes classiques d'approximation de noyaux de viabilité ou de bassins de capture présentent certaines limitations ; notamment, ils souffrent de la malédiction de la dimensionnalité et leur application est réservée à des problèmes en petite dimension (dans l'espace d'état et des contrôles). L'objectif de cette thèse est de développer des algorithmes d'approximation de noyaux de viabilité et de bassin de capture plus performants, en utilisant une méthode d'apprentissage statistique particulière : les machines à vecteurs de support (Support Vector Machines - SVMs).

Nous proposons un nouvel algorithme d'approximation d'un noyau de viabilité, basé sur l'algorithme de Patrick Saint-Pierre, qui utilise une méthode d'apprentissage pour définir la frontière du noyau. Après avoir rappelé les conditions mathématiques que la procédure doit respecter, nous considérons les SVMs dans ce contexte. Cette méthode d'apprentissage fournit une sorte de fonction barrière à la frontière du noyau, ce qui permet d'utiliser des méthodes d'optimisation pour trouver un contrôle viable, et ainsi de travailler dans des espaces de contrôle plus importants. Cette fonction "barrière" permet également de dériver des politiques de contrôle plus ou moins prudentes. Nous appliquons la procédure à un problème de gestion des pêches, en examinant quelles politiques de pêche permettent de garantir la viabilité d'un écosystème marin. Cet exemple illustre les performances de la méthode proposée : le système comporte 6 variables d'états et 51 variables de contrôle.

A partir de l'algorithme d'approximation d'un noyau de viabilité utilisant les SVMs, nous dérivons un algorithme d'approximation de bassin de capture et de résolution de problèmes d'atteinte d'une cible en un temps minimal. Approcher la fonction de temps minimal revient à rechercher le noyau de viabilité d'un système étendu. Nous présentons une procédure qui permet de rester dans l'espace d'état initial, et ainsi d'éviter le coût (en temps de calcul et espace mémoire) de l'addition d'une dimension supplémentaire. Nous décrivons deux variantes de l'algorithme : la première procédure donne une approximation qui converge par l'extérieur et la deuxième par l'intérieur. La comparaison des deux résultats donne une évaluation de l'erreur d'approximation. L'approximation par l'intérieur permet de définir un contrôleur qui garantit d'atteindre la cible en un temps minimal. La procédure peut être étendue au problème de minimisation d'une fonction de coût lorsque celle-ci respecte certaines conditions. Nous illustrons cet aspect sur le calcul de valeurs de résilience. Nous appliquons la procédure sur un problème de calcul de valeurs de résilience sur un modèle d'eutrophication des lacs.

Les algorithmes proposés permettent de résoudre le problème de l'augmentation exponentielle du temps de calcul avec la dimension de l'espace des contrôles mais souffrent toujours de la malédiction de la dimensionnalité pour l'espace d'état : la taille du vecteur d'apprentissage augmente exponentiellement avec la dimension de l'espace. Nous introduisons des techniques d'apprentissage actif pour sélectionner les états les plus "informatifs" pour définir la fonction SVM, et ainsi gagner en espace mémoire, tout en gardant une approximation précise du noyau. Nous illustrons la procédure sur un problème de conduite d'un vélo sur un circuit, système défini par six variables d'état.

Mots-Clés


Système dynamique, théorie de la viabilité, Support Vector Machines, contrôleur de viabilité, contrôle optimal, apprentissage actif.