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.

Automated abstractions for patrolling security games / N. Basilico, N. Gatti - In: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence[s.l] : AAAI, 2011 Aug 04. - pp. 1096-1101 (( convegno Twenty-Sixth AAAI Conference on Artificial Intelligence.

Automated abstractions for patrolling security games

N. Basilico;
2011

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.
Game theory; security; abstractions
Settore INF/01 - Informatica
Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni
http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3574
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
3574-16435-1-PB.pdf

accesso riservato

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 549.28 kB
Formato Adobe PDF
549.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/254080
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? ND
social impact