Regular Strategies and Strategy Improvement: Efficient Tools
for Solving Large Patrolling Problems

D 2016

Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

KUČERA, Antonín a Tomáš LAMSER

Základní údaje

Originální název

Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

Autoři

KUČERA, Antonín (203 Česká republika, garant, domácí) a Tomáš LAMSER (203 Česká republika, domácí)

Vydání

New York, Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, od s. 1171-1179, 9 s. 2016

Nakladatel

ACM

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í

tištěná verze "print"

Odkazy

ACM Digital Library

Kód RIV

RIV/00216224:14330/16:00088484

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-4239-1

ISSN

UT WoS

000465199800134

Klíčová slova anglicky

patrolling games; strategy synthesis

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 13. 5. 2020 19:32, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

In patrolling problems, the task is to compute an optimal strategy for a patroller who moves among vulnerable targets and aims at detecting possible intrusions. Previous approaches to this problem utilize non-linear programming to synthesize (sub)optimal patroller's strategies, which has a negative impact on their scalability. Further, the solution space is usually restricted to positional strategies or to strategies dependent on a bounded history of patroller's moves. In this paper we introduce regular strategies that utilize deterministic finite-state automata to collect some information about the whole history of patroller's moves, and show that regular strategies are strictly more powerful than strategies dependent on a bounded history. Further, we design a strategy improvement technique for regular strategies which completely avoids solving large non-linear programs. Intuitively, we start with some regular strategy, and then improve this strategy by performing a finite number of rounds, where each round produces another regular strategy obtained by combining the ``old'' one with a solution of a certain linear program. Our experiments demonstrate that, compared to the existing methods, our approach is applicable to patrolling problems of considerably larger size, and can quickly produces strategies of very good quality.

Návaznosti

GA15-17564S, projekt VaV

Název: Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů

Investor: Grantová agentura ČR, Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů

Citovat

KUČERA, Antonín a Tomáš LAMSER. Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems. In Catholijn M. Jonker, Stacy Marsella, John Thangarajah, Karl Tuyls. Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. New York: ACM, 2016, s. 1171-1179. ISBN 978-1-4503-4239-1.

@inproceedings{1366040,
   author = {Kučera, Antonín and Lamser, Tomáš},
   address = {New York},
   booktitle = {Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems},
   editor = {Catholijn M. Jonker, Stacy Marsella, John Thangarajah, Karl Tuyls},
   keywords = {patrolling games; strategy synthesis},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {New York},
   isbn = {978-1-4503-4239-1},
   pages = {1171-1179},
   publisher = {ACM},
   title = {Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems},
   url = {http://dl.acm.org/citation.cfm?id=2937095},
   year = {2016}
}

TY  - JOUR
ID  - 1366040
AU  - Kučera, Antonín - Lamser, Tomáš
PY  - 2016
TI  - Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems
PB  - ACM
CY  - New York
SN  - 9781450342391
KW  - patrolling games
KW  - strategy synthesis
UR  - http://dl.acm.org/citation.cfm?id=2937095
L2  - http://dl.acm.org/citation.cfm?id=2937095
N2  - In patrolling problems, the task is to compute an optimal strategy for a patroller who moves among vulnerable targets and aims at detecting possible intrusions. Previous approaches to this problem utilize non-linear programming to synthesize (sub)optimal patroller's strategies, which has a negative impact on their scalability. Further, the solution space is usually restricted to positional strategies or to strategies dependent on a bounded history of patroller's moves. In this paper we introduce regular strategies that utilize deterministic finite-state automata to collect some information about the whole history of patroller's moves, and show that regular strategies are strictly more powerful than strategies dependent on a bounded history. Further, we design a strategy improvement technique for regular strategies which completely avoids solving large non-linear programs. Intuitively, we start with some regular strategy, and then improve this strategy by performing a finite number of rounds, where each round produces another regular strategy obtained by combining the ``old'' one with a solution of a certain linear program. Our experiments demonstrate that, compared to the existing methods, our approach is applicable to patrolling problems of considerably larger size, and can quickly produces strategies of very good quality.
ER  -

KUČERA, Antonín a Tomáš LAMSER. Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems. In Catholijn M. Jonker, Stacy Marsella, John Thangarajah, Karl Tuyls. \textit{Proceedings of the 2016 International Conference on Autonomous Agents \&{} Multiagent Systems}. New York: ACM, 2016, s.~1171-1179. ISBN~978-1-4503-4239-1.

Podrobný výpis o publikaci