  Multi-agent patrolling is a key problem in a variety of domains such as
intrusion detection, area surveillance, and policing which involves repeated
visits by a group of agents to specified points in an environment. While the
problem is well-studied, most works do not provide performance guarantees and
either do not consider agent attrition or impose significant communication
requirements to enable adaptation. In this work, we present the Adaptive
Heuristic-based Patrolling Algorithm, which is capable of adaptation to agent
loss using minimal communication by taking advantage of Voronoi partitioning,
and which meets guaranteed performance bounds. Additionally, we provide new
centralized and distributed mathematical programming formulations of the
patrolling problem, analyze the properties of Voronoi partitioning, and
finally, show the value of our adaptive heuristic algorithm by comparison with
various benchmark algorithms using physical robots and simulation based on the
Robot Operating System (ROS) 2.
