Alex Robotics
sky

GR08XX Apprentissage et commande

Apprentissage par renforcement et commande optimale

Pourquoi ce cours?

  • Comprendre les fondements de l’apprentissage par renforcement et la commande optimale
  • Faire les liens avec la science des asservissements;
  • Apprendre à utiliser des algorithmes pour synthétiser des politiques optimales

Du choix des forces dans un robot jusqu'au choix de la pièce à déplacer dans un jeu d'échec.

Quoi?

  • Principe d’optimalité: Équations de Bellman, fonction coût/récompense, contraintes, etc.
  • Modèle d’évolution: Équations différentielles, Chaînes de Markov, Échantillonnage.
  • Techniques de solution: Programmation dynamique, LQR, Apprentissage par Renforcement.

Quand et où?

UdeS Automne 2024, Horaire et locaux à venir!

Une approche unifiée pour la science de la prise de decision en temps réel.

Le but du cours est de faire le lien entre le domaine des asservissements et les algorithmes de décision basé sur l’IA. Le cours présentera les outils pour vous permettre de de traduire un problème de décisions en temps réel sous la représentation mathématique adapté pour synthétiser et optimiser une politique de décision, avec des applications dans plusieurs domaines de la robotique à la finance.

Vidéo de présentation du cours

Capsules vidéos

Une série de capsules vidéos associés est disponible au lien à droite:

Introduction

Ce cours présente les approches pour prendre des décisions intelligentes sous un cadre théorique unifié basé sur le principe de la programmation dynamique. Il vise d'abord a établir les liens entre les approches issues du domaine de l'ingénierie (la science des asservissements et la commande optimale) et les approches issues des sciences informatiques (recherche opérationnelle et l'apprentissage par renforcement) qui ont en fait les même bases mathématiques. Il vise principalement à donner à un lecteur issue du domaine de l'ingénierie les bases pour comprendre et utiliser les approches numériques issues des sciences informatiques, comme l'apprentissage par renforcement, qui permettent de calculer des politiques décisionnelles optimales.

Plusieurs problèmes en apparence très différents:

sont en fait des problèmes qu'on peut analyser et résoudre avec les mêmes outils mathématiques:

Plan du cours

Partie 1 - Notions de base avec des cours magistraux (50%):

La première partie comportera des leçons magistrales qui présenteront les notions de base. L’emphase sera sur la compréhension des équations fondamentales illustrées avec plusieurs exemples dans des domaines variés. La première partie comportera 3 devoirs et se terminera à mi-session.

Partie 2 – Projet au choix de l’étudiant (50%) :

La seconde partie comportera des séminaires introduisant aux méthodes avancées et du mentorat pour le travail sur le projet. La seule évaluation sera un projet de session avec un sujet qui sera au choix des étudiants et pourra porter sur une problématique provenant d’un projet de recherche, un projet de fin de baccalauréat, etc.

Contenu Détaillé

Semaines Sujets Travaux
TBD

Introduction

  • Programmation dynamique
  • Applications et exemples (contrôle, navigation, finance, game AI, etc.)
TBD

Principe d’optimalité

  • Fonction de coût, contraintes et objectifs
  • Équations de Bellman
  • Équation HJB
  • Solution analytique pour les systèmes linéaires avec un coût quadratique (LQR)
  • Formulation MiniMax pour le contrôle robuste
  • Formulation Probabiliste
TBD

Modélisation

  • États discrets vs états continus
  • Temps discret vs temps continus
  • Évolution déterministe vs évolution stochastique
  • Modèle d’état; Équation différentielles; Équation de différences; Chaînes de Markov;
  • Graphiques de transitions;
TBD

Méthode de synthèse / apprentissage

  • Méthodes hors-ligne
    • Itération de valeur (value iteration)
    • Itération de loi de commande (policy iteration)
  • Apprentissage par renforcement (méthodes adaptative)
    • Différence temporelle
    • Q-Learning
    • Policy gradient
  • Méthode en-ligne avec heuristiques
    • Rollout
    • MPC
TBD

Méthodes avancées

  • Approximation de fonctions
  • Deep-reinforcement learning

Projet de session

  • Un projet au choix de l'étudiant impliquant des notions du cours.
  • L’évaluation du projet consistera en une présentation finale devant la classe

Programmation dynamique

La programmation dynamique est un principe mathématique pour optimiser des décisions qui sont prises en séquence après avoir observé l'état d'un système. Le principe peut être utilisé autant pour analyser un système asservis classique, comme contrôler la position d'un moteur en choisissant la tension appliquée à ses bornes, que pour des problèmes probabiliste dans un contexte de finance, comme choisir quand acheter ou vendre une action en observant l'évolution de son prix, ou bien un problème d'IA comme choisir la pièce à déplacer lors d'une partie d'échec en observant la position des pièces sur l'échiquier.

Formulation du problème

Un comportement défini par une loi de commande à concevoir

On s'intéresse au problème de concevoir une loi de commande, qui consiste en une fonction $c$ qui détermine l'action $u$ à prendre en fonction de l'état $x$ d'un système observé, et possiblement du temps $t$: \begin{align} u = c( x, t ) \end{align} Cette loi de commande va être implémenté dans un agent qui observe l'état $x$ d'un système et agit en conséquence sur ce système pour l'influencer, formant ainsi une boucle comme illustré à la figure XXX.

Un objectif formulé comme la minimisation d'un coût

Ensuite, notre loi de commande sera conçue de sorte à atteindre un objectif qui sera exprimé mathématiquement comme la minimisation d'un coût additif qui dépend de la trajectoire du système et les actions utilisée: \begin{align} J=\int_0^{t_f}g(x,u,t) dt + h(x_f,t_f) \end{align} où $g$ est un coût cumulatif sur la trajectoire du système, $h$ est un coût terminal et $t_f$ est un horizon de temps. La forme cumulative de la fonction coût est centrale pour utiliser le principe de la programmation dynamique, mais ce n'est pas vraiment restrictif car pratiquement tout les objectifs peuvent être formulés comme la minimisation d'une fonction de coût avec cette forme. Lorsque que notre agent prend les meilleurs décisions possible en fonction de l'objectif on dira que sa loi de commande est optimale au sens qu'elle minimise la fonction de coût.

Coût à venir
Politique optimale

Minimiser un coût ou maximiser une récompense?

On peut alternativement formuler l'objectif comme le problème de maximiser une récompense. Les deux approches sont équivalentes et interchangeables. Typiquement le domaine de la commande optimale utilise la formulation de minimiser un coût, qui est souvent relié à l'erreur par rapport à une trajectoire cible. Alternativement, le domaine de l'apprentissage par renforcement préfère optimiser une récompense, qui est souvent par exemple le pointage dans un jeux pour lequel une IA est développé.

Exemples de contextes

Loi de commande pour un robot

Un exemple d'asservissement classique serait un bras robotique où l'action $u$ déterminée par la loi de commande correspond à un vecteur de couples à appliquer dans les moteurs électriques. Cette action sera calculée en fonction de l'état actuel du robot, donc ici un vecteur de positions et vitesses de ses diverses articulations. L'objectif serait formulé comme la minimisation de l'erreur de position du robot par rapport à une position cible et potentiellement d'une pénalité pour utiliser beaucoup d'énergie. Typiquement notre solution de loi de commande serait ici une équation analytique.

Algorithme de navigation

Un exemple de prise de décision à plus haut niveau serait de choisir un trajet sur une carte. La loi de commande déterminerait ici quelle direction prendre en fonction de la position actuelle sur la carte. L'objectif d'atteindre la destination le plus rapidement possible pourrait être formuler comme la minimisation du temps écoulé avant d'atteindre celle-ci. La loi de commande (qui serait une solution globale) pourrait être sous la forme d'une table de correspondance où est en mémoire la direction optimale à prendre pour chaque intersection sur laquelle on peut se trouver sur la carte.

Algorithme d'investissement

Un exemple dans un tout autre contexte serait pour un algorithme d'investissement. L'action de la loi de commande serait ici d'acheter ou non une action en fonction d'une observation de son prix. L'objectif pourrait ici être formuler comme la maximisation des gains financiers. La loi de commande serait ici un seuil de prix, qui pourrait varier en fonction du temps, en dessous duquel l'agent décide d'acheter l'action.

Formulation en temps discret

La plupart des outils pour travailler avec ce genre de problèmes sont mieux adapté à une approche de type temps discret. Ces notes vont donc présenter les principes et les algorithmes d'abord avec une approche à temps discret ou un index $k$ indique l'étape actuelle. Il est possible de convertir une problème à temps continu en problème à temps discret en introduisant un pas de temps $dt$ et en considérant que les décisions sont prises en séquence à chaque période de temps $dt$. Alternativement, une approche pour travailler directement en temps continue est présentée à la section \ref{sec:dp_cont}. De plus, pour plusieurs types de problèmes la nature de l'évolution du système est discrètes, par exemple une partie d'échec. La formulation des problèmes en temps discret est donc très générale et s'applique a un grand nombre de problèmes. Le problème équivalent à résoudre en temps discret est de déterminer les lois de commande $c_k$, qui dictent l'action $u$ à prendre lorsque l'état du système est de $x$ à l'étape $k$: \begin{align} u_k = c_k( x_k ) \end{align} de sorte à minimiser un coût additif de la forme: \begin{align} J = \sum_{k=0}^{N-1} g_k(x_k, u_k) + g_N( x_N ) \end{align} où $N$ est l'horizon qui représente ici un nombre d'étape. De plus ici l'évolution du système est représentée par une équation de différence: \begin{align} x_{k+1} = f_k( x_k, u_k) \end{align} Si on reforme tout le problème en une seule équation mathématique: \begin{align} J^*(x_0) = \min_{c_0, ... c_k, ... c_{N-1}} \left[ \sum_{k=0}^{N-1} g_k(x_k, u_k) + g_N( x_N ) \right] \quad \text{avec} \quad x_{k+1} = f_k( x_k, c_k(x_k) ) \end{align} on cherche les fonctions $c_k$, i.e. les loi de commandes, qui vont minimiser le coût cumulatif sur la trajectoire du système, avec l'évolution qui est définit par une dynamique $f_k$ et les lois de commandes $c_k$.

Algorithme de programmation dynamique exacte

\begin{align} J^*_N(x_N) &= g_N(x_N) \\ J^*_k(x_k) &= \min_{u_k \in U_k(x_k)} \left[ g_k(x_k , u_k ) + J^*_{k+1}( \underbrace{ f_k(x_k , u_k ) }_{x_{k+1}} ) \right] \\ c^*_k(x_k) &= arg\min_{u_k\in U_k(x_k)} \left[ g_k(x_k , u_k ) + J^*_{k+1}( \underbrace{ f_k(x_k , u_k ) }_{x_{k+1}} ) \right] \label{eq:exactdp} \end{align}

Variations sur un thème de programmation dynamique

Stochastique

\begin{align} J^*_k(x_k) = \min_{u_k} {\color{red} E_{w_k} } &\left[ g_k(x_k , u_k , w_k ) + J^*_{k+1}( \underbrace{ f_k(x_k , u_k , w_k ) }_{x_{k+1}} ) \right] \end{align}

Robuste

\begin{align} J^*_k(x_k) = \min_{u_k} {\color{red} \max_{w_k} } &\left[ g_k(x_k , u_k , w_k ) + J^*_{k+1}( \underbrace{ f_k(x_k , u_k , w_k ) }_{x_{k+1}} ) \right] \end{align}

À horizon de temps infini

\begin{align} J^*(x) = \min_{u} &\left[ g(x , u ) + {\color{red}\alpha} J^*( \underbrace{ f(x , u ) }_{x_{k+1}} ) \right] \end{align}

Sans modèles (Q-Learning)

\begin{align} Q^*(x, u ) = g(x , u ) + \min_{u_{k+1}} &\left[ Q^*( \underbrace{ f(x , u ) }_{x_{k+1}} , u_{k+1} ) \right] \end{align}

À temps continu

\begin{align} 0 = \min_{u} \left[ g(x , u ) + \frac{\partial J^*(x,t)}{\partial x } \underbrace{ f(x , u , t) ) }_{\dot{x}} \right] \label{eq:hjb} \end{align}