• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Noa Agmon, Sarit Kraus, and
Gal A. Kaminka. Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge
Opponent. Journal of Artificial Intelligence Research, 42:887–916, December 2011.
The paper
on the JAIR site
The problem of adversarial multi-robot patrol has gained interest in recent years, mainly due to its immediate relevance to various security applications. In this problem, robots are required to repeatedly visit a target area in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. When facing a strong adversary that knows the patrol strategy of the robots, if the robots use a deterministic patrol algorithm, then in many cases it is easy for the adversary to penetrate undetected (in fact, the adversary can guarantee penetration). Therefore this paper presents a non-deterministic patrol framework for the robots. Assuming that the strong adversary will take advantage of its knowledge and try to penetrate through the weakest spot of the patrol, we presents a polynomial-time algorithm framework for determining an optimal patrol for the robots, such that the probability of detecting the adversary in the patrol’s weakest spot is maximized. We build upon this framework and describe an optimal patrol strategy for several robotic models based on their movement abilities (directed or undirected) and sensing abilities (perfect or imperfect), and in different environment models - either patrol around a perimeter (closed polygon) or an open fence (open polyline).
@Article{jair11,
author={Noa Agmon and Sarit Kraus and Gal A. Kaminka},
title = {Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent},
journal = JAIR,
year = {2011},
OPTkey = {},
volume = {42},
OPTnumber = {},
pages = {887--916},
month = {December},
wwwnote = {The <a href="http://www.jair.org/papers/paper3365.html">paper on the JAIR site</a>},
OPTnote = {In press.},
OPTannote = {},
abstract = {The problem of adversarial multi-robot patrol has gained interest in
recent years, mainly due to its immediate relevance to various security
applications. In this problem, robots are required to repeatedly visit a
target area in a way that maximizes their chances of detecting an adversary
trying to penetrate through the patrol path. When facing a strong
adversary that knows the patrol strategy of the robots, if the robots
use a deterministic patrol algorithm, then in many cases it is easy for
the adversary to penetrate undetected (in fact, the adversary can guarantee
penetration). Therefore this paper presents a non-deterministic
patrol framework for the robots. Assuming that the strong adversary
will take advantage of its knowledge and try to penetrate through the
weakest spot of the patrol, we presents a polynomial-time algorithm
framework for determining an optimal patrol for the robots, such that
the probability of detecting the adversary in the patrol’s weakest spot
is maximized. We build upon this framework and describe an optimal
patrol strategy for several robotic models based on their movement
abilities (directed or undirected) and sensing abilities (perfect or imperfect),
and in different environment models - either patrol around a
perimeter (closed polygon) or an open fence (open polyline).}
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Feb 03, 2025 16:33:37