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

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ABAFFY Michal BRÁZDIL Tomáš ŘEHÁK Vojtěch BOŠANSKÝ Branislav KUČERA Antonín KRČÁL Jan

Year of publication 2014
Type Article in Proceedings
Conference Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14)
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords patrolling games; stochastic games; epsilon-optimal strategy
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.