A Patrolling Game for Adversaries with Limited Observation Time
Ahmad Bilal Asghar, STEPHEN L. J. SMITH · 2018
In this paper we consider a robot patrolling scenario on a weighted graph where an intruder can observe the patrolling path and use the information gained by observation to attack the graph's vertices. We pose the problem of finding a patrolling strategy as a multi-stage two player game. The patroller commits to a strategy that is unknown to the intruder. The intruder observes the patroller's actions for a finite amount of time to learn the patroller's strategy and then decides to either attack or renege based on its confidence in the learned strategy. We characterize the expected payoffs for the players and show that finding a k-factor approximation to the optimal patrolling strategy is NP-hard even when the patroller's strategy set is constrained to time homogeneous Markov chains. We propose a search algorithm to find a patrolling policy in such scenarios and illustrate the trade off between hard to learn and hard to attack strategies through simulations.