Gal A. Kaminka's Publications

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

The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol

Noa Agmon, Vladimir Sadov, Gal A. Kaminka, and Sarit Kraus. The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol. In Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-08), pp. 55–62, 1, 2008.

Download

[PDF]367.9kB  

Abstract

This paper considers the problem of multi-robot patrolling around a closed area, in the presence of an adversary trying to penetrate the area. Previous work on planning in similar adversarial environments addressed worst-case settings, in which the adversary has full knowledge of the defending robots. It was shown that non deterministic algorithms may be effectively used to maximize the chances of blocking such a full-knowledge opponent, and such algorithms guarantee a “lower bound” to the performance of the team. However, an open question remains as to the impact of the knowledge of the opponent on the performance of the robots. This paper explores this question in depth and provides theoretical results, supported by extensive experiments with 68 human subjects concerning the compatibility of algorithms to the extent of information possessed by the subjects. First, we analytically examine the case of a zero-knowledge opponent - a different extreme - and show that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in which the adversary gained partial information, propose the combine algorithm that maximizes the expected probability of penetration detection along with minimizing the deviation between the probabilities of penetration detection along the perimeter, and support the performance of this algorithm in the experiments.

Additional Information

BibTeX

@InProceedings{aamas08noa,
  author = 	 {Noa Agmon and Vladimir Sadov and Gal A. Kaminka and Sarit Kraus}, 
  title = 	 {The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol}, 
  OPTcrossref =  {}, 
  OPTkey = 	 {}, 
  booktitle = AAMAS-08, 
  volume = {1},
  pages = 	 {55--62}, 
  year = 	 {2008}, 
  abstract = {This paper considers the problem of multi-robot patrolling around a closed area, 
  in the presence of an adversary trying to penetrate the area. Previous work on planning in 
  similar adversarial environments addressed worst-case settings, in which the adversary has full 
  knowledge of the defending robots.
 It was shown that non deterministic algorithms may be effectively used to maximize the chances of 
 blocking such a full-knowledge opponent, and such algorithms guarantee a ``lower bound'' to the 
 performance of the team. However, an open question remains as to the impact of the knowledge of the
 opponent on the performance of the robots. This paper explores this question
 in depth and provides theoretical results, supported by extensive experiments with 68 human subjects 
 concerning the compatibility of algorithms to the extent of information possessed by the subjects. 
 First, we analytically examine the case of a zero-knowledge opponent - a different extreme - and show 
 that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is 
 optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal
 algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in 
 which the adversary gained partial information, propose the combine algorithm that maximizes the 
 expected probability of penetration detection along with minimizing the deviation between the 
 probabilities of penetration detection along the perimeter, and support the performance of this 
 algorithm in the experiments.}, 
  wwwnote = {}, 
  OPTeditor = 	 {}, 
  OPTvolume = 	 {}, 
  OPTnumber = 	 {}, 
  OPTseries = 	 {}, 
  OPTaddress = 	 {}, 
  OPTmonth = 	 {}, 
  OPTorganization = {}, 
  OPTpublisher = {}, 
  OPTannote = 	 {} 
} 

Generated by bib2html.pl (written by Patrick Riley ) on Sun Oct 29, 2017 21:31:22