Multi-Agent Patrolling under Uncertainty and Threats

Abstract. We investigate a multi-agent patrolling problem in large stochastic environments where information is distributed alongside threats. The informa-tion and threat at each location are respectively modelled as a multi-state Markov chain, whose states are not observed until the location is visited by an agent. While agents obtain information at a location, they may suffer attacks from the threat at that location. The goal for the agents is to gather as much information as possible while mitigating the damage incurred. We formulate this problem as a Partially Observable Markov Decision Process (POMDP) and propose a com-putationally efficient algorithm to solve it. We empirically evaluate our algorithm in a simulated environment, and show that it outperforms a greedy algorithm up to 43 % for 10 agents in a large graph