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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	ABAFFY Michal BRÁZDIL Tomáš ŘEHÁK Vojtěch BOŠANSKÝ Branislav KUČERA Antonín KRČÁL Jan
Rok publikování	2014
Druh	Článek ve sborníku
Konference	Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	patrolling games; stochastic games; epsilon-optimal strategy
Popis	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.
Související projekty:	Formální metody pro analýzu a verifikaci komplexních systémů