Alex Robotics
sky

Alex Robotics

Programmation dynamique, commande optimale et apprentissage par renforcement

Cette page présente des notes de cours sur les approches pour prendre des décisions intelligentes sous un cadre théorique unifié basé sur le principe de la programmation dynamique. Elle 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. Ces notes visent 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.

Capsule vidéos

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

Introduction

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.

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 (apprentissage par renforcement)

\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}