This paper considers the problem of multi-robot patrolling along an open polyline, for example a fence, in the presence of an adversary trying to penetrate through the fence. In this case, the robots' task is to maximize the probability of detecting penetrations. Previous work concerning multi-robot patrol in adversarial environments considered closed polygons. That situation is simpler to evaluate due to its symmetric nature. In contrast, if the robots patrol back and forth along a fence, then the frequency of their visits along the line is coherently non-uniform, making it easier to be exploited by an adversary. Moreover, previous work assumed perfect sensorial capabilities of the robots in the sense that if the adversary is in the sensorial range of the robot is will surely be detected. In this paper we address these two challenges. We first suggest a polynomial time algorithm for finding the probability of penetration detection in each point along the fence. We then show that by a small adjustment this algorithm can deal with the more realistic scenario, in which the robots have imperfect sensorial capabilities. Last, we demonstrate how the probability of penetration detection can be used as base for finding optimal patrol algorithms for the robots in both strong and weak adversarial environment.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com