Time-Varying Graph Patrolling Against Attackers with Locally Limited and Imperfect Observation Models

Abstract

The use of autonomous robots for surveillance is one of the most interesting applications of graph-patrolling algorithms. In recent years, considerable effort has been devoted to tackling the problem of efficiently computing effective patrolling strategies. One of the mainstream approaches is adversarial patrolling, where a model of a strategic attacker is explicitly taken into account. A common assumption made by these techniques is to consider a worst-case attacker, characterized by ubiquitous and perfect observation capabilities. Motivated by the domain of robotic applications, we instead consider a more realistic and limited attacker model capable of gathering noisy observations in a locally limited range of the environment. We assume that the modeled attacker follows a behavior induced by its observations. Thus, we devise a randomized patrolling strategy based on Markov chains that makes observations reveal very little information, while still maintaining a reasonable level of protection in the environment. Our experimental results obtained in simulation confirm time-variance as a practical approach for our objective.