Improving Adaptive Stress Testing: Reinforcement Learning using Monte Carlo Tree Search with Neural Network Policies

Abstract

Ved utvikling av et autonomt sikkerhetskritisk system er det avgjørende at den autonome agenten er i stand til å handle trygt i en lang rekke ulike scenarier. Hvert scenario avhenger av en rekke faktorer som kan inkludere vær og sikt, intern forsinkelse og støy, eksterne krefter, og møter med andre agenter. Dette resulterer i et tilnærmet uendelig antall mulige scenarier, og å teste systemet for alle scenarier blir svært vanskelig, spessielt for komplekse systemer. En måte å nærme seg dette problemet på er gjennom Adaptive Stress Testing (AST). AST er et rammeverk som brukes til å stressteste et sikkerhetskritisk system ved å endre variablene i et simulert miljø, og finne den mest sannsynlige sekvensen av miljøforstyrrelser som resulterer i et feilscenario.

AST søket etter den mest sannsynlige feiltilstanden bruker vanligvis Reinforcement Learning agent. Dette gjør vi også denne oppgaven, gjennom bruken av Monte Carlo Tree Search (MCTS). MCTS er en toppmoderne søkealgoritme som tilfeldig prøver et stort antall simulerte scenarier for å lage en heuristikk. Dette resulterer i lange søketider for testsystemer med kostbare simuleringer. I oppgaven vår ser vi på måter å forbedre effektiviteten til MCTS når det brukes på komplekse simulatorer, med en enkelt simuleringstid på 1 sekund eller mer.

I vår foreslåtte modell forbedrer vi effektiviteten til MCTS-søket gjennom to metoder. Det første trinnet er implementeringen av en policy for utrulling av nevrale nettverk og et verdinevralt nettverk. Utrullingspolicyen brukes til å forbedre belønningen av simulerte prøver, mens verdinettverket er opplært til å forutsi tilstandshandlingsverdien til mulige handlinger. Det andre trinnet i å forbedre effektiviteten er å periodisk lagre den interne tilstanden til simulatoren, slik at vi kan hoppe over beregningen av den gitte tilstanden i fremtidige simuleringer.

Den foreslåtte modellen brukes i eksperimenter på to simulatorer for å sammenligne virkningen av endringene som er gjort på MCTS. Til slutt bruker vi modellen vår for å stressteste kollisjonsunngåelsessystemet til milliAmpere 2, en autonom fergeprototype designet og bygget av NTNU.

When developing an autonomous safety-critical system, it is crucial that the autonomous agent is able to act safely in a wide range of different scenarios. Each scenario is defined by a range of factors that can include weather and visibility, internal delay and sensor noise, external forces, and encounters with other agents. This results in a virtually infinite number of possible scenarios, and testing the system for all scenarios becomes virtually impossible, especially for complex systems. One way to approach this problem is through Adaptive Stress Testing (AST). AST is a framework used to stress tests a safety-critical system by altering the variables of a simulated environment, finding the most likely sequence of environment disturbances that results in a failure scenario.

AST searches are most commonly directed using a reinforcement learning agent, which for this thesis are variations of Monte Carlo Tree Search (MCTS). MCTS is a state-of-the-art search algorithm that randomly samples a large number of simulated scenarios to create a heuristic. This results in long search times for testing systems with costly simulations. In our thesis, we look at ways to improve the efficiency of MCTS when applied to complex simulators, with a single simulation time of 1 second or more.

We address the long search times through our proposed model, Monte Carlo Forrest Search with Action Pruning (MCTS-AP). MCTS-AP aims to improve the efficiency of MCTS through two methods. The first method is the implementation of a neural network rollout policy and a value neural network. The rollout policy is used to improve the reward of simulated samples, while the value network is trained to predict the state-action value of the possible actions in a state. The second method is to periodically store the internal state of the simulator, allowing us to skip the calculation of the given state in future simulations.

The proposed model is applied in experiments to two simulators to compare the impact of the changes made to MCTS. Finally, we apply our model to stress test the collision avoidance system of the milliAmpere 2, an autonomous ferry prototype designed and built by NTNU.