Guessing Winning Policies in LTL Synthesis by Semantic Learning

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00131847" target="_blank" >RIV/00216224:14330/23:00131847 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-031-37706-8_20" target="_blank" >http://dx.doi.org/10.1007/978-3-031-37706-8_20</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-37706-8_20" target="_blank" >10.1007/978-3-031-37706-8_20</a>

Result language

angličtina

Original language name

Guessing Winning Policies in LTL Synthesis by Semantic Learning

Original language description

We provide a learning-based technique for guessing a winning strategy in a parity game originating from an LTL synthesis problem. A cheaply obtained guess can be useful in several applications. Not only can the guessed strategy be applied as best-effort in cases where the game’s huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous LTL synthesis in several ways. Firstly, checking whether a guessed strategy is winning is easier than constructing one. Secondly, even if the guess is wrong in some places, it can be fixed by strategy iteration faster than constructing one from scratch. Thirdly, the guess can be used in on-the-fly approaches to prioritize exploration in the most fruitful directions. In contrast to previous works, we (i) reflect the highly structured logical information in game’s states, the so-called semantic labelling, coming from the recent LTL-to-automata translations, and (ii) learn to reflect it properly by learning from previously solved games, bringing the solving process closer to human-like reasoning.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Computer Aided Verification - 35th International Conference, CAV 2023, Proceedings, Part I

ISBN

9783031377051

ISSN

0302-9743

e-ISSN

—

Number of pages

25

Pages from-to

390-414

Publisher name

Springer

Place of publication

Cham

Event location

Paris, France

Event date

Jul 17, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001310786500020