D 2021

Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games

KLAŠKA, David, Antonín KUČERA, Vojtěch ŘEHÁK and Vít MUSIL

Basic information

Original name

Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games

Authors

KLAŠKA, David (203 Czech Republic, belonging to the institution), Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution), Vojtěch ŘEHÁK (203 Czech Republic, belonging to the institution) and Vít MUSIL (203 Czech Republic, belonging to the institution)

Edition

Neuveden, Proceedings of 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021), p. 471-481, 11 pp. 2021

Publisher

AUAI Press

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

RIV identification code

RIV/00216224:14330/21:00122557

Organization unit

Faculty of Informatics

ISSN

Keywords in English

adversarial security games; strategy synthesis

Tags

Tags

International impact, Reviewed
Změněno: 14/3/2023 16:08, doc. RNDr. Vojtěch Řehák, Ph.D.

Abstract

V originále

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.

Links

CZ.02.2.69/0.0/0.0/18_053/0016952, interní kód MU
(CEP code: EF18_053/0016952)
Name: Postdoc2MUNI
Investor: Ministry of Education, Youth and Sports of the CR, Priority axis 2: Development of universities and human resources for research and development
EF18_053/0016952, research and development project
Name: Postdoc2MUNI
MUNI/A/1108/2020, interní kód MU
Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Acronym: SV-FI MAV X.)
Investor: Masaryk University
MUNI/A/1549/2020, interní kód MU
Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Acronym: SKOMU)
Investor: Masaryk University
0011629866, interní kód MU
Name: Models, Algorithms, and Tools for Solving Adversarial Security Problems
Investor: Ostatní - foreign