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 continuously patrolling such environments. We first define a general class of multi-agent information gathering problems in which vehicles are represented by information gathering agents autonomous entities that direct their activity towards collecting information 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 abstract measure of reward, which encodes the properties of the agents' sensors, and the spatial and temporal properties of the measured phenomena. Concrete instantiations of this class of problems include monitoring environmental phenomena (temperature, pressure, etc.), disaster response, and patrolling environments to prevent intrusions from (non-strategic) attackers. In more detail, we derive a single-agent divide and conquer algorithm to compute a continuous patrol (an infinitely long path in the graph) that yields a near-optimal amount of observation value. This algorithm recursively decomposes the graph, until high-quality paths in the resulting components can be computed outright by a greedy algorithm. It then constructs a patrol by concatenating these paths using dynamic programming. For multiple agents, the algorithm sequentially computes patrols for each agent in a greedy fashion, in order to maximise its marginal contribution to the team. Moreover, to achieve robustness, we develop algorithms for repairing patrols when one or more agents fail or the graph changes. For both the single- and the multi-agent case, we give theoretical guarantees (lower bounds on the solution quality and an upper bound on the computational complexity in the size of the graph and the number agents) on the performance of the algorithms. We benchmark the single- and multi-agent algorithm against the state of the art and demonstrate that it typically performs 35% and 33% better in terms of average and minimum solution quality respectively. (C) 2012 Elsevier B.V. All rights reserved.