Optimisation dynamique des temps d’arrêts en station

Optimisation dynamique des temps d’arrêts en station

Etat de l’art sur l’optimisation dynamique

Dans des conditions réelles d’exploitation, des perturbations de trafic influencent les temps de parcours des trains, ainsi que les horaires d’arrivées et de départs en stations. Une régulation de trafic est utilisée pour gérer ces perturbations de trafic et permettre aux trains de respecter au maximum la table horaire initiale. Ainsi, un aléa subi par un train peut être propagé à d’autres trains présents sur le réseau pour respecter les   contraintes techniques d’exploitation définies par l’exploitant. Dans cette section, une table horaire est dite robuste si celle-ci a la capacité d’absorber les aléas de trafic qui se produisent en temps réel. Un grand nombre d’études ont été dédiées à la conception de tables horaires robustes comme [173], [174],[175] ou encore [176]. Cependant, aucune planification hors-ligne ne peut être assez robuste pour absorber tous les types d’aléas sans compromettre les performances de la table horaire. De fait, il est nécessaire de modifier en temps réel le planning horaire initial pour s’adapter aux modifications imposées par les perturbations de trafic. Néanmoins, dans la pratique, la robustesse d’une table horaire est largement dépendante de la régulation de trafic utilisée. En 2015, Corman [177] a établi un état de l’art très exhaustif des travaux concernant les différentes approches employées dans la littérature pour effectuer une replanification en temps réel des tables horaires de lignes ferroviaires. De cette étude, plusieurs enseignements peuvent être tirés. D’une part, il est nécessaire d’avoir une bonne connaissance en temps réel du système ferroviaire à replanifier (position, profil de vitesse, aléas de trafic,…). Ce premier point est un pré-requis indispensable pour envisager une replanification efficace. D’autre part, une vision probabiliste des états futurs du système est obligatoire pour obtenir une aide à la décision pertinente et précise. En effet, sans connaissance de l’évolution future du réseau ferroviaire, l’optimalité de la replanification ne peut être assurée et est même fortement compromise, puisque cela revient à effectuer une étude statique d’un système dynamique en connaissant uniquement les informations du système au pas de temps courant. Cette vision probabiliste est assimilable à la capacité d’anticiper l’évolution du système pour effectuer la replanification. En outre, [177] met en lumière que la nature de la modélisation influence également les performances de la replanification, que ce soit pour l’atteinte des objectifs initiaux, la rapidité de la prise de décision ou le degré de précision de la planification (optimalité de la prise de décision sur un horizon temporel). Enfin, cette étude démontre surtout qu’il existe une très grande quantité d’approches différentes pour réaliser une même macro-tâche. Chacun de ces travaux présente des spécificités, des avantages et désavantages qui dépendent avant tout des informations disponibles pour effectuer une replanification optimale en temps réel ainsi que des objectifs visés. De fait, aucune méthode universelle ne résulte de cet état de l’art, pour effectuer une optimisation dynamique des temps d’arrêt en station dans une ligne ferroviaire de type métro automatique. L’optimisation temps réel des temps d’arrêt en station semble donc être liée à deux contraintes majeures : la rapidité d’exécution de la boucle d’optimisation et la connaissance probabiliste de l’évolution future de l’état du système. Il a alors été choisi d’étudier la possibilité d’utiliser une approche par apprentissage par renforcement (AR) pour réaliser cette tâche d’optimisation en temps réel.

Définition de l’apprentissage par renforcement

De tous temps, l’homme a utilisé un système de récompense/punition (également appelés renforceurs) pour conditionner les actions des animaux qu’il souhaitait domestiquer. En associant ces signaux de renforcement aux actions de l’animal, il est possible de lui faire adopter des comportements différents suivant la nature du renforceur : l’animal va chercher à maximiser les récompenses reçues et à minimiser ses punitions [178]. Le cerveau humain exploite ce principe de récompense/punition à travers la sécrétion de dopamine produite par les ganglions de la base afin de renforcer les connections synaptiques entre les neurones. Les travaux de Berridge et Robinson [179] constituent en ce sens une étude intéressante sur le fonctionnement neuro-chimique du système nerveux humain. L’apprentissage par renforcement définit l’interaction entre un agent et son environnement : dans un état sn de l’environnement, l’agent choisit et exécute une action an ce qui provoque une transition vers l’état sn+1. L’agent reçoit alors le signal de renforcement rn correspondant au bénéfice que l’action an a eu sur l’atteinte de l’objectif de l’agent. Ce signal de renforcement est ensuite utilisé pour améliorer la politique de décision, à savoir, la séquence d’action optimale à effectuer pour maximiser les récompenses reçues et ainsi atteindre l’objectif fixé. Dans cette section, un épisode est défini comme une série d’expériences permettant à un agent de partir d’un état initial et d’arriver à un état terminal. L’agent se déplace d’état en état en effectuant des actions et en observant les signaux de renforcement qui vont orienter sa recherche d’une politique optimale.

Processus de décision markovien

En 1957, Bellman pose les bases de l’apprentissage par renforcement en introduisant la notion de programmation dynamique, dans le but de concevoir des méthodes de contrôle optimal pour des systèmes dynamiques discrets et stochastiques. Dans [180], il explicite la notion de processus de décision markovien (PDM), afin de caractériser l’évolution d’un système suivant une succession d’états distincts, où les actions entreprises dépendent d’une fonction probabiliste de transition. La figure 4.17 illustre le déroulement d’un PDM pour un agent qui part d’un état initial s0 pour atteindre un état final sn. Chacune des actions entreprises dans les différents états amène l’agent à recevoir une récompense. s0 s1 r0 s2 sn−1 r2 sn rn a0 a1 an−1 Figure 4.17 – Illustration d’un processus de décision markovien. En 1988, Sutton et Barto effectuent une formalisation mathématique des algorithmes d’apprentissage par renforcement et généralisent le principe de commande optimale par l’utilisation de PDM [181], [182]. Un PDM se caractérise par le fait que l’agent doit résoudre séquentiellement des problèmes de décisions, où chaque décision courante influence la résolution des problèmes suivants et également, par l’incertitude des conséquences de chacune des actions possibles dans un état donné. Ce type de problème est formalisé mathématiquement par le quadruplet {S, A, P, R}, où S est l’ensemble des états du système, A est l’ensemble des actions pouvant être accomplies par l’agent, P est une fonction de transition représentant la probabilité pour l’agent de se retrouver dans l’état suivant s 0 après avoir effectué l’action a dans un état s et R est la fonction de récompense du système représentant la probabilité pour l’agent de recevoir une récompense r en ayant effectué l’action a dans un état s. Une variable T représentant l’axe temporel des décisions peut également être introduite lorsque l’évolution du système ou les paramètres du PDM sont dépendants du temps [183]. Un problème dépendant du temps se caractérise notamment par le principe de causalité : il n’est pas possible de revenir en arrière une fois qu’une action a été effectuée. La résolution d’un PDM consiste alors à contrôler l’agent pour qu’il effectue les actions lui permettant d’optimiser les récompenses reçues tout au long de son interaction avec l’environnement. La notion de politique ou stratégie, notée π, est introduite pour qualifier la décision qui amène l’agent à effectuer une action dans un état donné. Un état du système est alors défini par (4.24), où π(st) représente l’action effectuée dans l’état st sous la politique π. st+1 = P(st , π(st)) = P(st , at) (4.24) 

Critères de performance

La définition de critères de performance ambitionne de caractériser la politique suivie par l’agent apprenant. Différents critères de performances peuvent être employés pour évaluer une politique en mesurant le cumul des signaux de renforcement espérés le long d’une trajectoire. Un critère fini Cf est une somme des récompenses immédiates et futures qui assigne le même poids à toutes les étapes de la trajectoire tandis qu’un critère actualisé Ca introduit la notion de facteur de dépréciation pour régler l’importance des récompenses futures par rapport aux récompenses immédiates. L’expression de l’espérance du critère fini est rappelée par l’équation (4.25) où m est la longueur de la trajectoire à optimiser. L’expression du critère actualisé est donnée par l’équation 4.26. Cf = E[ Xm n=0 rn|π, s0] (4.25) Ca = E[ X inf n=0 γ n rn|π, s0] (4.26)  Le facteur γ simule la confiance que l’on peut avoir dans l’estimation d’une récompense future probable ; plus la valeur de γ est élevée, plus l’agent aura confiance dans la vision à long terme des récompenses reçues en suivant la trajectoire définie par la politique π. Le critère actualisé est particulièrement utilisé pour traiter les PDM où il existe une forte incertitude sur les décisions prises sur un horizon lointain en suivant la politique courante. Dans notre étude, l’utilisation de ce critère permet de probabiliser la vision à long terme et est donc privilégiée par rapport au critère fini. D’autres critères comme le critère total (cumul des récompenses obtenues sur un temps infiniment long) et le critère moyen (moyenne des récompenses sur l’horizon de prédiction) peuvent également être employés mais ne sont pas développés ici, car ils ne présentent pas d’intérêt pour l’étude.