Article

Automated abstractions for patrolling security games

Authors:

Nicola Basilico,

Nicola GattiAuthors Info & Claims

AAAI'11: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence

Pages 1096 - 1101

Published: 07 August 2011 Publication History

Publisher Site

Abstract

Recently, there has been a significant interest in studying security games to provide tools for addressing resource allocation problems in security applications. Patrolling security games (PSGs) constitute a special class of security games wherein the resources are mobile. One of the most relevant open problems in security games is the design of scalable algorithms to tackle realistic scenarios. While the literature mainly focuses on heuristics and decomposition techniques (e.g., double oracle), in this paper we provide, to the best of our knowledge, the first study on the use of abstractions in security games (specifically for PSGs) to design scalable algorithms. We define some classes of abstractions and we provide parametric algorithms to automatically generate abstractions. We show that abstractions allow one to relax the constraint of patrolling strategies' Markovianity (customary in PSGs) and to solve large game instances. We additionally pose the problem to search for the optimal abstraction and we develop an anytime algorithm to find it.

References

[1]

Basilico, N.; Gatti, N.; Rossi, T.; Ceppi, S.; and Amigoni, F. 2009. Extending algorithms for mobile robot patrolling in the presence of adversaries to more realistic settings. In IAT, 557-564.

Crossref

Google Scholar

[2]

Basilico, N.; Gatti, N.; and Amigoni, F. 2009. Leader-follower strategies for robotic patrolling in environments with arbitrary topologies. In AAMAS, 57-64.

Crossref

Google Scholar

[3]

Conitzer, V., and Sandholm, T. 2006. Computing the optimal strategy to commit to. In EC, 82-90.

Crossref

Google Scholar

[4]

Gilpin, A., and Sandholm, T. 2007. Lossless abstraction of imperfect information games. J ACM 54(5).

Crossref

Google Scholar

[5]

Gilpin, A.; Sandholm, T.; and Sørensen, T. 2008. A heads-up no-limit texas hold'em poker player: discretized betting models and automatically generated equilibrium-finding programs. In AAMAS, 911-918.

Crossref

Google Scholar

[6]

Paruchuri, P.; Pearce, J.; Tambe, M.; Ordonez, F.; and Kraus, S. 2007. An efficient heuristic approach for security against multiple adversaries. In AAMAS, 311-318.

Crossref

Google Scholar

[7]

Paruchuri, P.; Pearce, J.; Marecki, J.; Tambe, M.; Ordonez, F.; and Kraus, S. 2008. Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games. In AAMAS, 895-902.

Crossref

Google Scholar

[8]

Pita, J.; Jain, M.; Marecki, J.; Ordonez, F.; Portway, C.; Tambe, M.; Western, C.; Paruchuri, P.; and Kraus, S. 2008. Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport. In AAMAS, 125-132.

Crossref

Google Scholar

[9]

Tsai, J.; Yin, Z.; Kwak, J.; Kempe, D.; Kiekintveld, C.; and Tambe, M. 2010. Urban security: Game-theoretic resource allocation in networked physical domains. In AAAI, 881 - 886.

Google Scholar

[10]

Vorobeychik, Y., and Wellman, M. 2008. Stochastic search methods for nash equilibrium approximation in simulation-based games. In AAMAS, 1055-1062.

Crossref

Google Scholar

Cited By

View all

Zhang BSandholm TLarochelle HRanzato MHadsell RBalcan MLin H(2020)Small nash equilibrium certificates in very large gamesProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496325(7161-7172)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496325
Kroer CSandholm T(2018)A unified framework for extensive-form game abstraction with boundsProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3326943.3327000(613-624)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3326943.3327000
Schlenker AThakoor OXu HFang FTambe MTran-Thanh LVayanos PVorobeychik YAndre EKoenig SDastani MSukthankar G(2018)Deceiving Cyber AdversariesProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237833(892-900)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237833
Show More Cited By

Recommendations

Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder

Security games are gaining significant interest in artificial intelligence. They are characterized by two players (a defender and an attacker) and by a set of targets the defender tries to protect from the attacker@?s intrusions by committing to a ...
Patrolling Games

A key operational problem for those charged with the security of vulnerable facilities (such as airports or art galleries) is the scheduling and deployment of patrols. Motivated by the problem of optimizing randomized, and thus unpredictable, patrols, ...
Introducing alarms in adversarial patrolling games: extended abstract
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

Adversarial patrolling games (APGs) can be modeled as Stackelberg games where a patroller and an intruder compete. The former moves with the aim of detecting an intrusion, while the latter tries to intrude without being detected. In this paper, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAAI'11: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence

August 2011

1883 pages

Publisher

AAAI Press

Publication History

Published: 07 August 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang BSandholm TLarochelle HRanzato MHadsell RBalcan MLin H(2020)Small nash equilibrium certificates in very large gamesProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496325(7161-7172)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496325
Kroer CSandholm T(2018)A unified framework for extensive-form game abstraction with boundsProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3326943.3327000(613-624)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3326943.3327000
Schlenker AThakoor OXu HFang FTambe MTran-Thanh LVayanos PVorobeychik YAndre EKoenig SDastani MSukthankar G(2018)Deceiving Cyber AdversariesProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237833(892-900)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237833
Nguyen TSinha AGholami SPlumptre AJoppa LTambe MDriciru MWanyama FRwetsiba ACritchlow RBeale CJonker CMarsella SThangarajah JTuyls K(2016)CAPTUREProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2937037(767-775)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2937037
Zhang CBucarey VMukhopadhyay ASinha AQian YVorobeychik YTambe MJonker CMarsella SThangarajah JTuyls K(2016)Using Abstractions to Solve Opportunistic Crime Security Games at ScaleProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2936956(196-204)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2936956
Kroer CSandholm TConitzer VBergemann DChen Y(2016)Imperfect-Recall Abstractions with Bounds in GamesProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940736(459-476)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940736
Vorobeychik YAn BTambe MSingh S(2014)Computing solutions in infinite-horizon discounted adversarial patrolling gamesProceedings of the Twenty-Fourth International Conferenc on International Conference on Automated Planning and Scheduling10.5555/3038794.3038831(314-322)Online publication date: 21-Jun-2014
https://dl.acm.org/doi/10.5555/3038794.3038831
Tsai JQian YVorobeychik YKiekintveld CTambe MGini MShehory OIto TJonker C(2013)Security games with contagionProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485134(1185-1186)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485134
Stranders RMunoz De Cote ERogers AJennings N(2013)Near-optimal continuous patrolling with teams of mobile information gathering agentsArtificial Intelligence10.1016/j.artint.2012.10.006195(63-105)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.artint.2012.10.006

Abstract

References

Cited By

Recommendations

Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder

Patrolling Games

Introducing alarms in adversarial patrolling games: extended abstract

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations