Solving adversarial patrolling games with bounded error:
(extended abstract)

D 2014

Solving adversarial patrolling games with bounded error: (extended abstract)

ABAFFY, Michal, Tomáš BRÁZDIL, Vojtěch ŘEHÁK, Branislav BOŠANSKÝ, Antonín KUČERA et. al.

Základní údaje

Originální název

Solving adversarial patrolling games with bounded error: (extended abstract)

Autoři

ABAFFY, Michal (703 Slovensko, domácí), Tomáš BRÁZDIL (203 Česká republika, domácí), Vojtěch ŘEHÁK (203 Česká republika, garant, domácí), Branislav BOŠANSKÝ (203 Česká republika), Antonín KUČERA (203 Česká republika, domácí) a Jan KRČÁL (203 Česká republika, domácí)

Vydání

Richland, SC, USA, Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14), od s. 1617-1618, 2 s. 2014

Nakladatel

International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

paměťový nosič (CD, DVD, flash disk)

Kód RIV

RIV/00216224:14330/14:00073686

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-2738-1

Klíčová slova česky

patrolovací hry; stochastické hry; epsilon-optimální strategie

Klíčová slova anglicky

patrolling games; stochastic games; epsilon-optimal strategy

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 13. 6. 2014 16:04, doc. RNDr. Vojtěch Řehák, Ph.D.

Anotace

ORIG CZ

V originále

Patrolling games are partially observable games played by two players, the defender and the attacker. The defender aims for detecting intrusions into vulnerable targets by following randomized routes among them, the attacker strives to maximize the probability of a successful (undetected) intrusion. We show how to translate patrolling games into turn-based perfect information stochastic games with safety objectives so that optimal strategies in the perfect information games can be transferred back to patrolling games. We design, to the best of our knowledge, the best algorithm which can compute an epsilon-optimal strategy for the defender among all (history-dependent) strategies.

Česky

Patrolovací hry jsou hry dvou hráčů, kde jen jeden hráč má kompletní informaci o hře. Hráči jsou obránce a útočník. Obránce se snaží detekovat útok na zranitelný cíl tím, že mezi nimi prochází randomizovanou strategií. Útočník se snaží maximalizovat pravděpodobnost úspěšného (nezjištěných) vniknutí. Ukazujeme, jak převést patrolovací hry na tahové stochastické hry s úplnou informací tak, aby optimální strategie byly vzájemně převoditelné. Dále představujeme algoritmus pro výpočet strategie, která je epsilon-optimální ze všech strategií, které berou v potaz historii.

Návaznosti

GAP202/10/1469, projekt VaV

Název: Formální metody pro analýzu a verifikaci komplexních systémů

Investor: Grantová agentura ČR, Formální metody pro analýzu a verifikaci komplexních systémů

Citovat

ABAFFY, Michal, Tomáš BRÁZDIL, Vojtěch ŘEHÁK, Branislav BOŠANSKÝ, Antonín KUČERA a Jan KRČÁL. Solving adversarial patrolling games with bounded error: (extended abstract). In Alessio Lomuscio, Paul Scerri, Ana Bazzan, and Michael Huhns. Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14). Richland, SC, USA: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2014, s. 1617-1618. ISBN 978-1-4503-2738-1.

@inproceedings{1185661,
   author = {Abaffy, Michal and Brázdil, Tomáš and Řehák, Vojtěch and Bošanský, Branislav and Kučera, Antonín and Krčál, Jan},
   address = {Richland, SC, USA},
   booktitle = {Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14)},
   editor = {Alessio Lomuscio, Paul Scerri, Ana Bazzan, and Michael Huhns},
   keywords = {patrolling games; stochastic games; epsilon-optimal strategy},
   howpublished = {paměťový nosič},
   language = {eng},
   location = {Richland, SC, USA},
   isbn = {978-1-4503-2738-1},
   pages = {1617-1618},
   publisher = {International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)},
   title = {Solving adversarial patrolling games with bounded error: (extended abstract)},
   year = {2014}
}

TY  - JOUR
ID  - 1185661
AU  - Abaffy, Michal - Brázdil, Tomáš - Řehák, Vojtěch - Bošanský, Branislav - Kučera, Antonín - Krčál, Jan
PY  - 2014
TI  - Solving adversarial patrolling games with bounded error: (extended abstract)
PB  - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
CY  - Richland, SC, USA
SN  - 9781450327381
KW  - patrolling games
KW  - stochastic games
KW  - epsilon-optimal strategy
N2  - Patrolling games are partially observable games played by two players, the defender and the attacker. The defender aims for detecting intrusions into vulnerable targets by following randomized routes among them, the attacker strives to maximize the probability of a successful (undetected) intrusion. We show how to translate patrolling games into turn-based perfect information stochastic games with safety objectives so that optimal strategies in the perfect information games can be transferred back to patrolling games. We design, to the best of our knowledge, the best algorithm which can compute an epsilon-optimal strategy for the defender among all (history-dependent) strategies.
ER  -

ABAFFY, Michal, Tomáš BRÁZDIL, Vojtěch ŘEHÁK, Branislav BOŠANSKÝ, Antonín KUČERA a Jan KRČÁL. Solving adversarial patrolling games with bounded error: (extended abstract). In Alessio Lomuscio, Paul Scerri, Ana Bazzan, and Michael Huhns. \textit{Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14)}. Richland, SC, USA: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2014, s.~1617-1618. ISBN~978-1-4503-2738-1.

Podrobný výpis o publikaci