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

*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

45 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.

Original languageEnglish
Title of host publicationQuantitative Evaluation of Systems : 19th International Conference, QEST 2022, Proceedings
EditorsErika Ábrahám, Marco Paolieri
Number of pages18
Publication date2022
ISBN (Print)9783031163357
Publication statusPublished - 2022
Event19th International Conference on Quantitative Evaluation of Systems, QEST 2022 - Warsaw, Poland
Duration: 12 Sept 202216 Sept 2022


Conference19th International Conference on Quantitative Evaluation of Systems, QEST 2022
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13479 LNCS

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.


  • Model-checking
  • Monte Carlo Tree Search (MCTS)
  • Planning
  • Priced Timed Automata (PTA)
  • Upper confidence bounds for trees (UCT)


Dive into the research topics of 'Monte Carlo Tree Search for Priced Timed Automata'. Together they form a unique fingerprint.

Cite this