Solving Adversarial Patrolling Games with Bounded Error

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 time needed to complete an intrusion at each target is finite, and the aim of the attacker is to maximize the probability of a successful (i. e. , undetected) intrusion. The attacker knows the defender's strategy and may observe her moves and her current position. 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 first algorithm which can compute an ε -optimal strategy for the defender among all (history-dependent) strategies.

Authors

• Vojtech Rehak

Keywords

No keywords are indexed for this paper.