Not a Lone Ranger: unleashing defender teamwork in security games

Game theory has become an important research area in handling complex security resource allocation and patrolling problems. Stackelberg Security Games (SSGs) have been used in modeling these types of problems via a defender and an attacker(s). Despite recent successful real-world deployments of SSGs, scale-up to handle defender teamwork remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, my thesis presents algorithms for solving defender teamwork in SSGs in two phases. As a first step, I focus on domains without execution uncertainty, in modeling and solving SSGs that incorporate teamwork among defender resources via three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. ❧ In the second stage of my thesis, I address execution uncertainty among defender resources that arises from the real world by integrating the powerful teamwork mechanisms offered by decentralized Markov Decision Problems (Dec-MDPs) into security games. My thesis offers the following novel contributions: (i) New model of security games with defender teams that coordinate under uncertainty; (ii) New algorithm based on column generation that utilizes Decentralized Markov Decision Processes (Dec-MDPs) to generate defender strategies that incorporate uncertainty; (iii) New techniques to handle global events (when one or more agents may leave the system) during defender execution; (iv) Heuristics that help scale up in the number of targets and resources to handle real-world scenarios; (v) Exploration of the robustness of randomized pure strategies. Different mechanisms, from both solving situations with and without execution uncertainty, may be used depending on the features of the domain. This thesis opens the door to a powerful combination of previous work in multiagent systems on teamwork and security games.

博弈论已成为解决复杂安全资源分配与巡逻问题的重要研究领域。斯塔克尔伯格安全博弈（Stackelberg Security Games, SSGs）已被用于通过防御方与进攻方对上述类型问题进行建模。尽管近期SSGs已在现实场景中实现成功部署，但针对防御方团队协作的规模化处理仍是该领域的核心挑战。现有最新技术无法适配多防御方需协调时序联合行动的应用场景。为应对这一挑战，本论文分两个阶段提出了用于解决SSGs中防御方团队协作问题的算法。首先，本文聚焦无执行不确定性的场景，通过三项创新特性对融入防御方资源团队协作的SSGs进行建模与求解：（i）列生成方法：通过求解旅行商问题生成节点有序网络，以此生成单个防御方策略；（ii）迭代奖励塑造机制：对多协作防御单元采用迭代奖励塑造，生成协同策略；（iii）紧致上界生成：通过求解仅遵循关键调度约束的安全博弈，生成更紧致的剪枝上界。其次，针对现实场景中防御方资源存在的执行不确定性问题，本文将分散式马尔可夫决策过程（Decentralized Markov Decision Processes, Dec-MDPs）所提供的高效团队协作机制融入安全博弈框架。本论文的创新贡献如下：（i）提出不确定性环境下具备协同能力的防御方团队安全博弈新模型；（ii）提出基于列生成的新算法，借助分散式马尔可夫决策过程（Dec-MDPs）生成融入不确定性的防御方策略；（iii）提出新的全局事件处理技术，用于应对防御方执行阶段中一名或多名智能体脱离系统的全局事件；（iv）提出启发式方法，可随目标与资源数量实现规模化扩展，适配现实应用场景；（v）对随机纯策略的鲁棒性展开研究。可根据应用场景的特性，选择对应执行不确定性场景或无执行不确定性场景下的求解机制。本论文为多智能体系统领域中团队协作与安全博弈的既有研究实现高效融合提供了可能。