Learning Optimal Scheduling for Time Uncertain Settings
Authors
Taankvist, Jakob Haahr ; Jensen, Peter Gjøl
Term
4. term
Education
Publication year
2014
Submitted on
2014-06-10
Pages
50
Abstract
Mange beslutningsproblemer i usikre, tidsafhængige systemer kan beskrives som Markov-beslutningsprocesser med tid og pris (omkostning). I dette arbejde præsenterer vi en metode, der automatisk lærer strategier, så den forventede omkostning bliver så lav som mulig. Metoden bygger på forstærkningslæring og kan lære næsten optimale strategier for Duration Probabilistic Automata (DPA), en formel model for tidslige, probabilistiske systemer. Den kan i vidt omfang også anvendes på den bredere klasse af prissatte tids-Markov-beslutningsprocesser. Vi udvikler flere varianter af centrale trin i læringsalgoritmen og undersøger empirisk, hvordan de påvirker de strategier, der bliver syntetiseret. I vores undersøgelser overgår metoderne tidligere kendte automatiske værktøjer til at syntetisere planlæggere (schedulers) for DPA: køretiden forbedres med cirka en størrelsesorden, samtidig med at der opnås de samme planlæggere, med beslutningsgrænser der afviger med højst 0,5. Alle metoderne er implementeret i værktøjet UPPAAL. Det gør det muligt at syntetisere strategier til omkostningsbegrænsede nåbarhedsmål i spil og samtidig opnå (næsten) optimal forventet omkostning.
Many decision problems in uncertain, time-dependent systems can be modeled as Markov decision processes with time and price (cost). We present a method that automatically learns strategies that minimize the expected cost. Our approach is based on reinforcement learning and can learn near-optimal strategies for Duration Probabilistic Automata (DPA), a formal model of timed probabilistic systems. It is also largely applicable to the broader class of Priced Time Markov Decision Processes. We develop several variants for key steps of the learning algorithm and empirically study how they affect the synthesized strategies. In our experiments, the proposed methods outperform previously known automated tools for synthesizing schedulers for DPA: running time improves by about an order of magnitude while producing essentially the same schedulers, with decision boundaries differing by at most 0.5. All methods are implemented in the UPPAAL tool. This enables the synthesis of strategies for cost-bounded reachability objectives in games while achieving a (near-) optimal expected cost.
[This abstract was generated with the help of AI]
Documents