Reinforcement learning for train dispatching : A study on the possibility to use reinforcement learning to optimize train ordering and minimize train delays in disrupted situations, inside the r ail simulator OSRD

Autor: Popescu, Teodora
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Druh dokumentu: Text
Popis: Train dispatching is a complex process, especially when the train traffic is disrupted, as the decisions taken by the dispatchers can have substantial consequences on the delays of the trains. The most frequent dispatching decisions consists in changing the order of trains at convergence points, where two tracks unite to become a single track. Choosing the right train order is crucial, as the trains cannot bypass each other again while they are on the single track after the convergence point. The OSRD team of SNCF R´eseau has designed the rail simulator OSRD (Open Source Railway Designer), which can simulate any traffic situation. The goal of this degree project was to study if reinforcement learning could be implemented in that simulator to find optimal ordering policies under traffic disruptions. A thorough literature review was carried out to identify what reinforcement learning models have already been used in the literature to handle similar problems. None of the models seen in the literature could directly be adapted to the OSRD simulator but key features which seemed to be necessary to build an efficient reinforcement learning model in OSRD were determined. Based on those features and on the specificities of OSRD, a custom reinforcement learning model (states, actions, rewards) was created. This model was then implemented into a Python reinforcement learning environment after designing an interactive simulation module which enabled communication between the Python reinforcement learning environment and OSRD. After ensuring that the model was running and enabled interacting with an OSRD simulation to retrieve decisions from it and take decisions which modified the train order, the study focused on what reinforcement learning algorithms could be used to implement a reinforcement learning algorithm which learns based on the implemented reinforcement learning model. Another in-depth literature review was performed on the existing reinforcement learning algorithms, and it was concluded that the most suitable algorithms for the project would be a policy gradient algorithm like REINFORCE and an evolutionary algorithm like the cross-entropy method. Both algorithms were then implemented but only the cross-entropy method achieved results. It was found out that the cross-entropy method converges very fast to the FIFO (First In First Out) method which always lets the first train arrived pass the convergence. The FIFO method was then compared with the actual best policies for the 50 disrupted simulations used as train set, using two scoring methods to make the comparison. The conclusion was that the FIFO policy was to some extent similar to the best policies but it was the optimal policy for only half of the simulations, even if its relative difference with the scores achieved by the best policies was acceptable. The differences between the best policy and the FIFO policy were analyzed in detail to find where the differences lied and to understand the rules applied by the best policies. Finally, even if the result achieved with the cross-entropy method did not correspond to an optimal policy nor to a complicated policy, it was concluded that reinforcement learning may still be relevant with a more complex simulation setup. However, the method used in this degree project still needs to be improved in order to achieve solutions which are closer to the optimal ones.
Tågbeställning är en komplicerad process, särskilt när tågtrafiken är störd, eftersom de beslut som fattas av tågbeställarna kan få betydande konsekvenser för tågens förseningar. De vanligaste besluten i fråga om tågplanering består i att ¨andra tågens ordning vid konvergenspunkter, där två spår förenas till ett enda spår. Det ¨ar viktigt att välja rätt tågordning eftersom tågen inte kan köra förbi varandra igen när de befinner sig på det enda spåret efter konvergenspunkten. OSRD-teamet vid SNCF R´eseau har utformat järnvägssimulatorn OSRD (Open Source Railway Designer), som kan simulera alla trafiksituationer. Målet med detta examensarbete var att undersöka om förstärkningsinlärning kan implementeras i den simulatorn för att hitta optimala beställningsprinciper vid trafikstörningar. En grundlig litteraturgenomgång genomfördes för att identifiera vilka förstärkningsinlärningsmodeller som redan har använts i litteraturen för att hantera liknande problem. Ingen av modellerna i litteraturen kunde direkt anpassas till OSRD-simulatorn, men man fastställde de viktigaste egenskaper som verkade vara nödvändiga för att bygga en effektiv förstärkningsinlärningsmodell i OSRD. På grundval av dessa egenskaper och OSRD:s särdrag skapades en anpassad modell för förstärkningsinlärning (tillstånd, åtgärder, belöningar). Denna modell implementerades sedan i en Python-miljö för förstärkningsinlärning efter att en interaktiv simuleringsmodul utformats som möjliggjorde kommunikation mellan Python-miljön för förstärkningsinlärning och OSRD. Efter att ha säkerställt att modellen var igång och möjliggjorde interaktion med en OSRD-simulering för att hämta beslut från den och fatta beslut som ändrade tågordningen, fokuserade studien på vilka algoritmer för förstärkningsinlärning som kunde användas för att genomföra en algoritm för förstärkningsinlärning som lär sig utifrån den genomförda modellen för förstärkningsinlärning. En annan djupgående litteraturstudie genomfördes om de befintliga algoritmerna för förstärkningsinlärning, och slutsatsen blev att de lämpligaste algoritmerna för projektet skulle vara en policygradientalgoritm som REINFORCE och en evolutionär algoritm som cross-entropy-metoden. Båda algoritmerna genomfördes sedan, men endast cross-entropy-metoden gav resultat. Det visade sig att crossentropimetoden konvergerar mycket snabbt mot FIFO-metoden (First In First Out) som alltid låter det första tåget passera konvergensen. FIFO-metoden jämfördes sedan med de bästa strategierna för de 50 störda simuleringar som användes som tåguppsättning, med hjälp av två poängsättningsmetoder för att göra jämförelsen. Slutsatsen var att FIFO-metoden i viss mån liknade de bästa metoderna, men att den var den optimala metoden för endast hälften av simuleringarna, även om dess relativa skillnad i förhållande till de poäng som uppnåddes av de bästa metoderna var acceptabel. Skillnaderna mellan den bästa policyn och FIFO-policyn har analyserats i detalj för att finna var skillnaderna ligger och för att förstå de regler som tillämpas av de bästa policyn. Slutligen, även om det resultat som uppnåddes med metoden för korsentropi inte motsvarade en optimal eller komplicerad policy, drogs slutsatsen att förstärkningsinlärning fortfarande kan vara relevant i en större infrastruktur, och om det tar mindre tid att träna och köra än att direkt beräkna den bästa policyn genom att prova alla tillgängliga policyer. Den metod som användes i detta examensarbete behöver dock fortfarande förbättras för att uppnå lösningar som ligger närmare de optimala lösningarna.
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: