Monte Carlo Tree Search for Priced Timed Automata

Peter Gjøl Jensen, Andrej Kiviriga*, Kim Guldstrand Larsen, Ulrik Nyman, Adriana Mijačika, Jeppe Høiriis Mortensen


Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

1 Citationer (Scopus)
59 Downloads (Pure)


Priced timed automata (PTA) were introduced in the early 2000s to allow for generic modelling of resource-consumption problems for systems with real-time constraints. Optimal schedules for allocation of resources may here be recast as optimal reachability problems. In the setting of PTA this problem has been shown decidable and efficient symbolic reachability algorithms have been developed. Moreover, PTA has been successfully applied in a variety of applications. Still, we believe that using techniques from the planning community may provide further improvements. Thus, in this paper we consider exploiting Monte Carlo Tree Search (MCTS), adapting it to problems formulated as PTA reachability problems. We evaluate our approach on a large benchmark set of PTAs modelling either Task graph or Job-shop scheduling problems. We discuss and implement different complete and incomplete exploration policies and study their performance on the benchmark. In addition, we experiment with both well-established and our novel MTCS-based optimizations of PTA and study their impact. We compare our method to the existing symbolic optimal reachability engines for PTAs and demonstrate that our method (1) finds near-optimal plans, and (2) can construct plans for problems infeasible to solve with existing symbolic planners for PTA.

TitelQuantitative Evaluation of Systems : 19th International Conference, QEST 2022, Proceedings
RedaktørerErika Ábrahám, Marco Paolieri
Antal sider18
ISBN (Trykt)9783031163357
StatusUdgivet - 2022
Begivenhed19th International Conference on Quantitative Evaluation of Systems, QEST 2022 - Warsaw, Polen
Varighed: 12 sep. 202216 sep. 2022


Konference19th International Conference on Quantitative Evaluation of Systems, QEST 2022
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind13479 LNCS

Bibliografisk note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.


Dyk ned i forskningsemnerne om 'Monte Carlo Tree Search for Priced Timed Automata'. Sammen danner de et unikt fingeraftryk.