Graph-patrolling problems in the adversarial domain typically embed models and assumptions about how hostile events, from which an environment must be protected, are generated at a specific time and location. Relying upon such attacker models prevents algorithms from synthesizing strategies that can generalize in different settings, providing good performance under different and uncertain scenarios. In this paper, we propose a first method to deal with adversarial patrolling using a data driven approach. We cast the problem in an RL setting where the reward function is based on the ability to neutralize attacks that can follow an unknown strategy and that, hence, can be viewed as a black box component. We apply a policy gradient framework for optimizing action probabilities under such a reward model showing how effective patrolling strategies can be obtained from repeated attack-defense interactions between a patrolling agent and an attacker. Our results show that the data driven patroller can effectively provide protection against multiple, diverse attacker behaviors.

Graph patrolling algorithms provide effective strategies for coordinating mobile robots in the context of autonomously surveilling valuable assets. Optimizing patrolling strategies often aims to minimize the time between subsequent visits to a vertex, a measure known in the literature as idleness. In the domain of multi-robot patrolling, two approaches have received the most attention so far. The first involves coordinating all robots to follow a shared patrolling strategy covering the entire graph, while the second approach partitions the environment into disjoint areas that are then assigned to individual robots. Starting from these existing solutions, this paper introduces a new method that bridges these two complementary approaches. Our technique splits the vertices of the graph into a partition that includes a shared portion of the environment patrolled collectively by all robots, along with disjoint areas allocated exclusively to individual robots. This problem is formulated in terms of minimizing the maximum weighted idleness of the graph and is shown to be NP-hard. We then describe an exact solution for the problem and propose various heuristics to efficiently compute solutions for large problem instances. We evaluate and compare the proposed techniques in simulation and demonstrate that, in most cases, our methods produce better patrolling strategies when compared to classic solutions. Moreover, for small problem instances where the exact solution can be found, we show that our proposed heuristic has a competitive performance ratio.

We present a novel algorithm to solve the stochastic orienteering problem with chance constraints that combines Monte Carlo Tree Search (MCTS) with a best arm identification (BAI) algorithm. This method extends our recently proposed solution that builds a search planning tree considering both an objective function to maximize, as well as a chance constraint on the failure probability, i.e., the probability of violating the assigned budget constraint. By combining these two approaches, we obtain a new planner that tunes the amount of tree search at run time. Extensive simulation results on our benchmark problems show that the new approach is significantly faster than the previous one, while incurring in just marginal decrements in terms of performance.

We study a patrolling problem where multiple agents are tasked with protecting an environment where one or more adversaries are trying to compromise targets of varying value. The objective of the patrollers is to move between targets to quickly spot when an attack is taking place and then diffuse it. Differently from most related literature, we do not assume that attackers have full knowledge of the strategies followed by the patrollers, but rather build a model at run time through repeated observations of how often they visit certain targets. We study three different solutions to this problem. The first two partition the environment using either a fast heuristic or an exact method that is significantly more time consuming. The third method, instead does not partition the environment, but rather lets every patroller roam over the entire environment. After having identified strengths and weaknesses of each method, we contrast their performances against attackers using different algorithms to decide whether to attack or not.

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.