Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00122557" target="_blank" >RIV/00216224:14330/21:00122557 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games
Original language description
We design a new efficient strategy synthesis method applicable to adversarial patrolling problems on graphs with arbitrary-length edges and possibly imperfect intrusion detection. The core ingredient is an efficient algorithm for computing the value and the gradient of a function assigning to every strategy its "protection" achieved. This allows for designing an efficient strategy improvement algorithm by differentiable programming and optimization techniques. Our method is the first one applicable to real-world patrolling graphs of reasonable sizes. It outperforms the state-of-the-art strategy synthesis algorithm by a margin.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
<a href="/en/project/EF18_053%2F0016952" target="_blank" >EF18_053/0016952: Postdoc2MUNI</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021)
ISBN
—
ISSN
2640-3498
e-ISSN
—
Number of pages
11
Pages from-to
471-481
Publisher name
AUAI Press
Place of publication
Neuveden
Event location
Online
Event date
Jul 27, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—