Algorithms for Multi-Robot Patrolling

Last updated on Apr 26, 2023
Multiple robots patrolling a mock fence in the MAVERICK lab.

Patrolling is a canonical task for robots, where one or more robots are required to pass over a target work area, and visit every point in the area repeatedly. Historically, this was thought to be the same as Repeated Coverage, i.e., carrying out Robot Coverage again and again, but the two tasks are not the same. Indeed, our work has led to distinguishing two types of patrolling problems: Frequency-Based Patrolling, and Adversarial Patrolling.

Frequency-Based Patrolling

In frequency-based patrolling, the objective is defined in terms of the frequency of visiting the points in the work area. For example, we may want to minimize the variance in the visit frequencies of different points, so that all points in the area are visited with the same frequency (or as close to it as possible). Or, we may want to minimize the mean (average) frequency of visits to points. These are different criteria, and the resulting patrolling trajectories would be different. The task becomes more challenging when patrolling open polylines (e.g., border fences), because robots must travel on the same line repeatedly, inherently limiting their ability to meet some criteria (e.g., uniformity is all but impossible).

Dr. Yehuda Elmaliach’s dissertation has essentially started this area, and provided the first definitions and algorithms for multi-robot patrolling of areas and of open polylines:

Here’s a video of synchronous fence patrolling demonstrating the fence patrol in action:

Adversarial Patrolling

Prof. Noa Agmon, Prof. Sarit Kraus and I collaborated on a variant of the patrolling problem, where the goal of the patrolling robots is to capture an adversary, by being physically present in the point where the adversary is present. The patrolling robots do not know when and where the adversary will attempt to pass. The adversary can observe the patrolling robots and may therefore have some prior knowledge of their motion patterns (even if probabilistic).

Some relevant papers listed here; see Prof. Noa Agmon’s Publications for more:

multi-robot systems patrolling