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

doi:10.1007/978-3-031-16336-4_19

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 proceeding › Article in proceeding › Research › peer-review

1 Citation (Scopus)

128 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Quantitative Evaluation of Systems : 19th International Conference, QEST 2022, Proceedings
Editors	Erika Ábrahám, Marco Paolieri
Number of pages	18
Publisher	Springer
Publication date	2022
Pages	381-398
ISBN (Print)	9783031163357
DOIs	https://doi.org/10.1007/978-3-031-16336-4_19
Publication status	Published - 2022
Event	19th International Conference on Quantitative Evaluation of Systems, QEST 2022 - Warsaw, Poland Duration: 12 Sept 2022 → 16 Sept 2022

Conference

Conference	19th International Conference on Quantitative Evaluation of Systems, QEST 2022
Country/Territory	Poland
City	Warsaw
Period	12/09/2022 → 16/09/2022

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13479 LNCS
ISSN	0302-9743

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Keywords

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

Access to Document

10.1007/978-3-031-16336-4_19

2022-QEST-NymanAccepted author manuscript, 677 KB

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Jensen, Peter Gjøl ; Kiviriga, Andrej ; Guldstrand Larsen, Kim et al. / Monte Carlo Tree Search for Priced Timed Automata. Quantitative Evaluation of Systems: 19th International Conference, QEST 2022, Proceedings. editor / Erika Ábrahám ; Marco Paolieri. Springer, 2022. pp. 381-398 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13479 LNCS).

@inproceedings{4c277232731549fd961c645874faeb23,

title = "Monte Carlo Tree Search for Priced Timed Automata",

abstract = "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.",

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

author = "Jensen, {Peter Gj{\o}l} and Andrej Kiviriga and {Guldstrand Larsen}, Kim and Ulrik Nyman and Adriana Mija{\v c}ika and {H{\o}iriis Mortensen}, Jeppe",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 19th International Conference on Quantitative Evaluation of Systems, QEST 2022 ; Conference date: 12-09-2022 Through 16-09-2022",

year = "2022",

doi = "10.1007/978-3-031-16336-4_19",

language = "English",

isbn = "9783031163357",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "381--398",

editor = "Erika {\'A}brah{\'a}m and Marco Paolieri",

booktitle = "Quantitative Evaluation of Systems",

address = "Germany",

}

Jensen, PG , Kiviriga, A , Guldstrand Larsen, K , Nyman, U, Mijačika, A & Høiriis Mortensen, J 2022, Monte Carlo Tree Search for Priced Timed Automata. in E Ábrahám & M Paolieri (eds), Quantitative Evaluation of Systems: 19th International Conference, QEST 2022, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13479 LNCS, pp. 381-398, 19th International Conference on Quantitative Evaluation of Systems, QEST 2022, Warsaw, Poland, 12/09/2022. https://doi.org/10.1007/978-3-031-16336-4_19

Monte Carlo Tree Search for Priced Timed Automata. / Jensen, Peter Gjøl ; Kiviriga, Andrej ; Guldstrand Larsen, Kim et al.
Quantitative Evaluation of Systems: 19th International Conference, QEST 2022, Proceedings. ed. / Erika Ábrahám; Marco Paolieri. Springer, 2022. p. 381-398 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13479 LNCS).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - Monte Carlo Tree Search for Priced Timed Automata

AU - Jensen, Peter Gjøl

AU - Kiviriga, Andrej

AU - Guldstrand Larsen, Kim

AU - Nyman, Ulrik

AU - Mijačika, Adriana

AU - Høiriis Mortensen, Jeppe

PY - 2022

Y1 - 2022

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

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

KW - Model-checking

KW - Monte Carlo Tree Search (MCTS)

KW - Planning

KW - Priced Timed Automata (PTA)

KW - Upper confidence bounds for trees (UCT)

UR - http://www.scopus.com/inward/record.url?scp=85138993133&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-16336-4_19

DO - 10.1007/978-3-031-16336-4_19

M3 - Article in proceeding

AN - SCOPUS:85138993133

SN - 9783031163357

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 381

EP - 398

BT - Quantitative Evaluation of Systems

A2 - Ábrahám, Erika

A2 - Paolieri, Marco

PB - Springer

T2 - 19th International Conference on Quantitative Evaluation of Systems, QEST 2022

Y2 - 12 September 2022 through 16 September 2022

ER -

Jensen PG , Kiviriga A , Guldstrand Larsen K , Nyman U, Mijačika A, Høiriis Mortensen J. Monte Carlo Tree Search for Priced Timed Automata. In Ábrahám E, Paolieri M, editors, Quantitative Evaluation of Systems: 19th International Conference, QEST 2022, Proceedings. Springer. 2022. p. 381-398. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13479 LNCS). doi: 10.1007/978-3-031-16336-4_19