Learn Smarter, Not Harder: Improving Uppaal Stratego through Preprocessing

Terndrup, Kasper Kohsel ; Sillesen, Simon Vandel

4. term

Software, Master

2018

97

UPPAAL STRATEGO kan automatisk udlede næsten optimale strategier for Priced Timed Markov Decision Processes (modeller, der kombinerer tid, omkostninger og tilfældighed). I praksis kan modeldele, som ikke påvirker den bedste strategi, alligevel udvide tilstandsrummet og forstyrre søgningen. Denne afhandling foreslår et præbehandlingstrin til UPPAAL STRATEGO, der finder og reducerer sådanne irrelevante eller redundante elementer. Trinnet anvender Principal Component Analysis (hovedkomponentanalyse, PCA) eller Fast Correlation-Based Filter (hurtigt korrelationsbaseret filter, FCBF), to metoder til variabeludvælgelse, som identificerer variable med ringe unik information, med henblik på at forenkle modellen før syntese. Gennem en række eksperimenter viser vi, at præbehandling kan forbedre strategisyntesen, ved at give bedre ydeevne for strategierne og strategier af mindre størrelse. Resultaterne taler for at tilføje præbehandlingsfunktioner i den fremtidige udvikling af UPPAAL STRATEGO.

UPPAAL STRATEGO automatically synthesizes near-optimal strategies for Priced Timed Markov Decision Processes (models that combine timing, costs, and randomness). In practice, model parts that do not influence the best strategy can still expand the state space and distract the search. This thesis adds a preprocessing step to the UPPAAL STRATEGO workflow to detect and reduce such irrelevant or redundant elements. The step applies Principal Component Analysis (PCA) or Fast Correlation-Based Filter (FCBF), two feature-selection methods that identify variables carrying little unique information, with the aim of simplifying the model before synthesis. Through a series of experiments, we show that preprocessing can improve strategy synthesis, yielding better strategy performance and smaller strategies. These results support adding preprocessing capabilities in future versions of UPPAAL STRATEGO.

[This abstract was generated with the help of AI]

uppaal ; stratego ; strategy ; preprocessing ; reduction ; ptmdp ; timed automata ; markov decision process ; fast correlation based filter ; principal component analysis ; synthesis ; machine learning ; feature irrelevance ; feature redundancy ; feature selection ; feature extraction

Download
View record in AAU Student Projects