Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder
- 作者：Nicola Basilico ; Nicola Gatti ; ngatti@elet.polimi.it ; Francesco Amigoni
- 关键词：Security games ; Adversarial patrolling ; Algorithmic game theory
- 刊名：Artificial Intelligence
- 出版年：2012
- 期刊代码：11_00043702
- 类别：cp
- 出版时间：June, 2012
- 卷：184-185
- 期：Complete
- 页码：78-123
- 文件大小：1081 K
摘要
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 environments 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.