title: Multi-Agent Patrolling under Uncertainty and Threats.
abstract: We investigate a multi-agent patrolling problem where information is distributed alongside threats in environments with uncertainties. Specifically, the information and threat at each location are independently modelled as multi-state Markov chains, whose states are not observed until the location is visited by an agent. While agents will obtain information at a location, they may also suffer damage from the threat at that location. Therefore, the goal of the agents is to gather as much information as possible while mitigating the damage incurred. To address this challenge, we formulate the single-agent patrolling problem as a Partially Observable Markov Decision Process (POMDP) and propose a computationally efficient algorithm to solve this model. Building upon this, to compute patrols for multiple agents, the single-agent algorithm is extended for each agent with the aim of maximising its marginal contribution to the team. We empirically evaluate our algorithm on problems of multi-agent patrolling and show that it outperforms a baseline algorithm up to 44% for 10 agents and by 21% for 15 agents in large domains.
authors.affiliation: College of Mechatronics and Automation, National University of Defense Technology, Changsha, Hunan, 410073, China; School of Electronics and Computer Science, University of Southampton, Southampton, SO171BJ, United Kingdom.
authors.forename: Shaofei
authors.initials: S
authors.lastname: Chen
authors.affiliation: School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, 230026, China.
authors.forename: Feng
authors.initials: F
authors.lastname: Wu
authors.affiliation: College of Mechatronics and Automation, National University of Defense Technology, Changsha, Hunan, 410073, China.
authors.forename: Lincheng
authors.initials: L
authors.lastname: Shen
authors.affiliation: College of Mechatronics and Automation, National University of Defense Technology, Changsha, Hunan, 410073, China.
authors.forename: Jing
authors.initials: J
authors.lastname: Chen
authors.affiliation: School of Electronics and Computer Science, University of Southampton, Southampton, SO171BJ, United Kingdom.
authors.forename: Sarvapali D
authors.initials: SD
authors.lastname: Ramchurn
mesh_terms: D000465:Algorithms; D040362:Geographic Information Systems; D006801:Humans; D008390:Markov Chains; D008889:Military Personnel; D058998:Remote Sensing Technology / Q000379:methods; D035501:Uncertainty