Near-Optimal Continuous Patrolling with Teams of Mobile Information Gathering Agents

Autonomous unmanned vehicles equipped with sensors are rapidly becoming the de facto means of achieving situational awareness — the ability to make sense of, and predict what is happening in an environment. Particularly in environments that are subject to continuous change, the use of such teams to maintain accurate and up-to-date situational awareness is a challenging problem. To perform well, the vehicles need to patrol their environment continuously and in a coordinated manner. To address this challenge, we develop a near-optimal multi-agent algorithm for con-tinuously patrolling such environments. We first define a general class of multi-agent information gathering problems in which vehicles are represented by information gath-ering agents — autonomous entities that direct their activity towards collecting infor-mation with the aim of providing accurate and up-to-date situational awareness. These agents move on a graph, while taking measurements with the aim of maximising the cumulative discounted observation value over time. Here, observation value is an ab-stract measure of reward, which encodes the properties of the agents ’ sensors, and th