Robustness Analysis of Multi-Agent Patrolling Strategies using Reinforcement Learning

Abstract. Patrolling an environment involves a team of agents whose goal usually consists in continuously visiting the most relevant areas as fast as possible. In this paper, we follow up on the work by Santana et al. who formulated this problem in terms of a reinforcement learning problem, where agents individually learn an MDP using Q-Learning to patrol their environment. We propose another definition of the state space and of the reward function associated with the MDP of an agent. Experimental evaluation shows that our approach substantially improves the previous RL method in some situations (graph topology and number of agents). Moreover, it is observed that such an RL approach is able to cope efficiently with most of the situations caused by the removal of agents during a patrolling simulation.