Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games

KLAŠKA, David, Antonín KUČERA, Vojtěch ŘEHÁK and Vít MUSIL. Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games. Online. In de Campos, Cassio and Maathuis, Marloes H. Proceedings of 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021). Neuveden: AUAI Press, 2021, p. 471-481. ISSN 2640-3498.

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:

URL

RIV identification code

RIV/00216224:14330/21:00122557

Organization unit

Faculty of Informatics

ISSN

Keywords in English

adversarial security games; strategy synthesis

Tags

core_A, firank_A, formela-conference

Tags

International impact, Reviewed

---

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