Automatic Synthesis of Efficient Regular Strategies in
Adversarial Patrolling Games

D 2018

Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

KLAŠKA, David, Antonín KUČERA, Tomáš LAMSER a Vojtěch ŘEHÁK

Základní údaje

Originální název

Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

Autoři

KLAŠKA, David (203 Česká republika, domácí), Antonín KUČERA (203 Česká republika, domácí), Tomáš LAMSER (203 Česká republika, domácí) a Vojtěch ŘEHÁK (203 Česká republika, garant, domácí)

Vydání

Richland, SC, Proceedings of the 2018 International Conference on Autonomous Agents & Multiagent Systems, od s. 659-666, 8 s. 2018

Nakladatel

International Foundation for Autonomous Agents and Multiagent Systems

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/18:00100830

Organizační jednotka

Fakulta informatiky

ISBN

978-1-5108-6808-3

ISSN

DOI

http://dx.doi.org/10.5555/3237383.3237481

UT WoS

000468231300081

Klíčová slova anglicky

patrolling games; single and multi-agent planning and scheduling

Štítky

core_A, firank_1, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 24. 9. 2019 15:31, doc. RNDr. Vojtěch Řehák, Ph.D.

Anotace

V originále

We give a polynomial-time algorithm for synthesizing efficient regular strategies in adversarial patrolling games with general topology. Regular strategies use finite memory to gather some relevant information about the history of Defender's moves which results in substantially better protection of the targets. So far, the scope of automatic strategy synthesis was limited to positional strategies (which ignore the history) or to regular strategies where the underlying finite-memory observer had to be supplied manually. Furthermore, the existing methods do not give any information on how far are the constructed strategies from being optimal. In this paper, we try to overcome these limitations. We develop a novel gradient-based algorithm for synthesizing regular strategies where the underlying finite-memory observers are constructed algorithmically. The running time of our algorithm is polynomial which makes the algorithm applicable to instances of realistic size. Furthermore, we develop an algorithm for computing an upper bound on the best achievable protection, and compare the quality of the constructed strategies against this bound. Thus, we can effectively measure the "distance'' of the constructed strategies from optimal strategies, and our experiments show that this distance is often quite small.

Návaznosti

GA18-11193S, projekt VaV

Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

MUNI/A/0854/2017, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII.

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

MUNI/A/1038/2017, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

KLAŠKA, David, Antonín KUČERA, Tomáš LAMSER a Vojtěch ŘEHÁK. Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games. Online. In Proceedings of the 2018 International Conference on Autonomous Agents & Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2018, s. 659-666. ISBN 978-1-5108-6808-3. Dostupné z: https://dx.doi.org/10.5555/3237383.3237481.

@inproceedings{1408461,
   author = {Klaška, David and Kučera, Antonín and Lamser, Tomáš and Řehák, Vojtěch},
   address = {Richland, SC},
   booktitle = {Proceedings of the 2018 International Conference on Autonomous Agents & Multiagent Systems},
   doi = {http://dx.doi.org/10.5555/3237383.3237481},
   keywords = {patrolling games; single and multi-agent planning and scheduling},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Richland, SC},
   isbn = {978-1-5108-6808-3},
   pages = {659-666},
   publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
   title = {Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games},
   url = {http://dl.acm.org/citation.cfm?id=3237383.3237481},
   year = {2018}
}

TY  - JOUR
ID  - 1408461
AU  - Klaška, David - Kučera, Antonín - Lamser, Tomáš - Řehák, Vojtěch
PY  - 2018
TI  - Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games
PB  - International Foundation for Autonomous Agents and Multiagent Systems
CY  - Richland, SC
SN  - 9781510868083
KW  - patrolling games
KW  - single and multi-agent planning and scheduling
UR  - http://dl.acm.org/citation.cfm?id=3237383.3237481
L2  - http://dl.acm.org/citation.cfm?id=3237383.3237481
N2  - We give a polynomial-time algorithm for synthesizing efficient regular strategies in adversarial patrolling games with general topology. Regular strategies use finite memory to gather some relevant information about the history of Defender's moves which results in substantially better protection of the targets. So far, the scope of automatic strategy synthesis was limited to positional strategies (which ignore the history) or to regular strategies where the underlying finite-memory observer had to be supplied manually. Furthermore, the existing methods do not give any information on how far are the constructed strategies from being optimal. In this paper, we try to overcome these limitations. We develop a novel gradient-based algorithm for synthesizing regular strategies where the underlying finite-memory observers are constructed algorithmically. The running time of our algorithm is polynomial which makes the algorithm applicable to instances of realistic size. Furthermore, we develop an algorithm for computing an upper bound on the best achievable protection, and compare the quality of the constructed strategies against this bound. Thus, we can effectively measure the "distance'' of the constructed strategies from optimal strategies, and our experiments show that this distance is often quite small.
ER  -

KLAŠKA, David, Antonín KUČERA, Tomáš LAMSER a Vojtěch ŘEHÁK. Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games. Online. In \textit{Proceedings of the 2018 International Conference on Autonomous Agents \&{} Multiagent Systems}. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2018, s.~659-666. ISBN~978-1-5108-6808-3. Dostupné z: https://dx.doi.org/10.5555/3237383.3237481.

Podrobný výpis o publikaci