Combining Graph Contraction and Strategy Generation for Green Security Games
Combining Graph Contraction and Strategy Generation for Green Security Games
复制标题
结合图收缩和策略生成进行绿色安全博弈
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Christopher Kiekintveld
中科院分区：
文献类型：
--
作者：
Anjon Basak;Fei Fang;T. Nguyen;Christopher Kiekintveld
许多现实世界的安全问题可以使用Stackelberg安全游戏SSG进行建模，该游戏模拟防御者和攻击者之间的交互。绿色安全游戏关注环境犯罪，如防止偷猎、非法伐木或检测污染。在绿色安全游戏中，一个常见的问题是如何优化大型物理区域（如国家公园或其他保护区）的巡逻策略。巡逻策略可以建模为表示物理地形的图中的路径。然而，用一个详细的图来表示一个非常大的区域内可能的运动，通常会导致一个棘手的计算问题，因为潜在路径的数量非常大。虽然文献中已经探索了各种算法方法来解决基于大图的安全博弈，但可以解决的博弈规模仍然非常有限。在这里，我们介绍了解决大型基于图的安全博弈的抽象方法，并将这些方法与策略生成技术相结合。我们的经验证明，这些方法的组合结果显着改善解决时间与适度的影响解决质量。
Many real-world security problems can be modeled using Stackelberg security games SSG, which model the interactions between a defender and attacker. Green security games focus on environmental crime, such as preventing poaching, illegal logging, or detecting pollution. A common problem in green security games is to optimize patrolling strategies for a large physical area such as a national park or other protected area. Patrolling strategies can be modeled as paths in a graph that represents the physical terrain. However, having a detailed graph to represent possible movements in a very large area typically results in an intractable computational problem due to the extremely large number of potential paths. While a variety of algorithmic approaches have been explored in the literature to solve security games based on large graphs, the size of games that can be solved is still quite limited. Here, we introduce abstraction methods for solving large graph-based security games and integrate these methods with strategy generation techniques. We demonstrate empirically that the combination of these methods results in dramatic improvements in solution time with modest impact on solution quality.