Standard
Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis. / Kretínský, Jan; Manta, Alexander
; Meggendorfer, Tobias.
Automated Technology for Verification and Analysis- 17th International Symposium, AVTA 2019, Proceedings. ed. / Yu-Fang Chen; Chih-Hong Cheng; Javier Esparza. 2019. p. 404-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11781 LNCS).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Harvard
Kretínský, J, Manta, A
& Meggendorfer, T 2019,
Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis. in Y-F Chen, C-H Cheng & J Esparza (eds),
Automated Technology for Verification and Analysis- 17th International Symposium, AVTA 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11781 LNCS, pp. 404-422.
https://doi.org/10.1007/978-3-030-31784-3_24APA
Kretínský, J., Manta, A.
, & Meggendorfer, T. (2019).
Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis. In Y.-F. Chen, C.-H. Cheng, & J. Esparza (Eds.),
Automated Technology for Verification and Analysis- 17th International Symposium, AVTA 2019, Proceedings (pp. 404-422). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11781 LNCS).
https://doi.org/10.1007/978-3-030-31784-3_24Vancouver
Kretínský J, Manta A
, Meggendorfer T.
Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis. In Chen YF, Cheng CH, Esparza J, editors, Automated Technology for Verification and Analysis- 17th International Symposium, AVTA 2019, Proceedings. 2019. p. 404-422. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-31784-3_24
Author
Bibtex
@inproceedings{c53a8d3ed7c843bebfcc06d70aedc40f,
title = "Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis.",
abstract = "We propose “semantic labelling” as a novel ingredient for solving games in the context of LTL synthesis. It exploits recent advances in the automata-based approach, yielding more information for each state of the generated parity game than the game graph can capture. We utilize this extra information to improve standard approaches as follows. (i) Compared to strategy improvement (SI) with random initial strategy, a more informed initialization often yields a winning strategy directly without any computation. (ii) This initialization makes SI also yield smaller solutions. (iii) While Q-learning on the game graph turns out not too efficient, Q-learning with the semantic information becomes competitive to SI. Since already the simplest heuristics achieve significant improvements the experimental results demonstrate the utility of semantic labelling. This extra information opens the door to more advanced learning approaches both for initialization and improvement of strategies.",
author = "Jan Kret{\'i}nsk{\'y} and Alexander Manta and Tobias Meggendorfer",
year = "2019",
month = oct,
day = "21",
doi = "10.1007/978-3-030-31784-3_24",
language = "English",
isbn = "9783030317836",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "404--422",
editor = "Yu-Fang Chen and Chih-Hong Cheng and Javier Esparza",
booktitle = "Automated Technology for Verification and Analysis- 17th International Symposium, AVTA 2019, Proceedings",
}
RIS
TY - GEN
T1 - Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis.
AU - Kretínský, Jan
AU - Manta, Alexander
AU - Meggendorfer, Tobias
PY - 2019/10/21
Y1 - 2019/10/21
N2 - We propose “semantic labelling” as a novel ingredient for solving games in the context of LTL synthesis. It exploits recent advances in the automata-based approach, yielding more information for each state of the generated parity game than the game graph can capture. We utilize this extra information to improve standard approaches as follows. (i) Compared to strategy improvement (SI) with random initial strategy, a more informed initialization often yields a winning strategy directly without any computation. (ii) This initialization makes SI also yield smaller solutions. (iii) While Q-learning on the game graph turns out not too efficient, Q-learning with the semantic information becomes competitive to SI. Since already the simplest heuristics achieve significant improvements the experimental results demonstrate the utility of semantic labelling. This extra information opens the door to more advanced learning approaches both for initialization and improvement of strategies.
AB - We propose “semantic labelling” as a novel ingredient for solving games in the context of LTL synthesis. It exploits recent advances in the automata-based approach, yielding more information for each state of the generated parity game than the game graph can capture. We utilize this extra information to improve standard approaches as follows. (i) Compared to strategy improvement (SI) with random initial strategy, a more informed initialization often yields a winning strategy directly without any computation. (ii) This initialization makes SI also yield smaller solutions. (iii) While Q-learning on the game graph turns out not too efficient, Q-learning with the semantic information becomes competitive to SI. Since already the simplest heuristics achieve significant improvements the experimental results demonstrate the utility of semantic labelling. This extra information opens the door to more advanced learning approaches both for initialization and improvement of strategies.
U2 - 10.1007/978-3-030-31784-3_24
DO - 10.1007/978-3-030-31784-3_24
M3 - Conference contribution/Paper
SN - 9783030317836
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 404
EP - 422
BT - Automated Technology for Verification and Analysis- 17th International Symposium, AVTA 2019, Proceedings
A2 - Chen, Yu-Fang
A2 - Cheng, Chih-Hong
A2 - Esparza, Javier
ER -
