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, 9 s. ISBN 978-1-4503-4239-1.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy americké
Utajení není předmětem státního či obchodního tajemství
Forma vydání tištěná verze "print"
WWW ACM Digital Library
Kód RIV RIV/00216224:14330/16:00088484
Organizační jednotka Fakulta informatiky
ISBN 978-1-4503-4239-1
ISSN 1548-8403
Klíčová slova anglicky patrolling games; strategy synthesis
Štítky firank_1
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 27. 4. 2017 07:04.
Anotace
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 VaVNázev: Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů
Investor: Grantová agentura ČR, Standardní projekty
VytisknoutZobrazeno: 19. 10. 2019 04:48