Delayed and time-variant patrolling strategies against attackers with local observation capabilities

Surveillance of graph-represented environments is an application of autonomous patrolling robots that received remarkable attention during the last years. In this problem setting, computing a patrolling strategy is a central task to guarantee an effective protection level. Literature provides a vast set of methods where the patrolling strategies explicitly consider the presence of a rational adversary and fully informed attacker, which is characterized by worst-case (for the patroller) observation capabilities. In this work, we consider an attacker that does not have any prior knowledge on the environment and the patrolling strategy. Instead, we assume that the attacker can only access local observations on the vertex potentially under attack. We study the definition of patrolling strategies under the assumption that the attacker, when planning an attack on a particular location, tries to forecast the arrivals of the patroller on that particular location. We model our patrolling strategies with Markov chains where we seek the generation of arrivals that are difficult to forecast. To this end we introduce time-variance in the transition matrix used to determine the patrollers movements on the graph-represented environment.