Wednesday, 23 de April de 2014

Ficha del recurso:

Fuente:

Vínculo original en ARTIFICIAL INTELLIGENCE, 184 78-123; 10.1016/j.artint.2012.03.003 JUN 2012
Basilico, N; Gatti, N; Amigoni, F

Última actualización:

Thursday, 28 de June de 2012

Entrada en el observatorio:

Thursday, 28 de June de 2012

Idioma:

Inglés

Archivado en:


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 strategy. To reach their goals, players use resources such as patrollers and intruders. Security games are Stackelberg games where the appropriate solution concept is the leader-follower equilibrium. Current algorithms for solving these games are applicable when the underlying game is in normal form (i.e., each player has a single decision node). In this paper, we define and study security games with an extensive-form infinite-horizon underlying game, where decision nodes are potentially infinite. We introduce a novel scenario where the attacker can undertake actions during the execution of the defender's strategy. We call this new game class patrolling security games (PSGs), since its most prominent application is patrolling enviro! nments against intruders. We show that PSGs cannot be reduced to security games studied so far and we highlight their generality in tackling adversarial patrolling on arbitrary graphs. We then design algorithms to solve large instances with single patroller and single intruder. (C) 2012 Elsevier B.V. All rights reserved.