Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent

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

Download

[PDF]768.8kB  

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).

BibTeX

@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 Fri Aug 30, 2024 17:29:51