Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration
作者: Hao-Tsung Yang, Ting-Kai Weng, Ting-Yu Chang, Kin Sum Liu, Shan Lin, Jie Gao, Shih-Yu Tsai
分类: cs.AI, cs.GT, cs.RO
发布日期: 2024-10-21
备注: Under review of TCPS
💡 一句话要点
提出巡逻安全博弈模型，解决攻击者自由选择攻击时间、地点和时长的机器人巡逻问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 巡逻安全博弈 Stackelberg博弈 机器人巡逻 双准则优化 深度强化学习
📋 核心要点
- 现有机器人巡逻方法难以应对攻击者在时间、地点和时长上具有完全自由度的复杂攻击场景。
- 论文将巡逻问题建模为Stackelberg博弈，通过优化巡逻策略最小化攻击者收益，并考虑了奖励和熵的双重目标。
- 实验结果表明，所提出的算法和深度强化学习模型在合成和真实数据集上均优于现有方法，验证了有效性。
📝 摘要（中文）
本文研究了巡逻安全博弈（PSG），这是一个建模为扩展式Stackelberg博弈的机器人巡逻问题，其中攻击者可以自由决定攻击的时间、地点和持续时间。我们的目标是设计一个具有无限时间范围的巡逻方案，以最小化攻击者的收益。我们证明了PSG可以转化为具有闭式目标函数的组合极小极大问题。通过将防御者的策略限制为时间同质的一阶马尔可夫链（即巡逻者的下一步行动仅取决于其当前位置），我们证明了在零惩罚情况下，最优解要么是最小化预期命中时间，要么是返回时间，具体取决于攻击者模型，并且这些解可以有效地计算。此外，我们观察到，在高惩罚情况下，增加巡逻计划的随机性可以降低攻击者的预期收益。然而，在其他情况下，极小极大问题变为非凸。为了解决这个问题，我们提出了一个包含两个目标的双准则优化问题：预期最大奖励和熵。我们提出了三种基于图的算法和一个深度强化学习模型，旨在有效地平衡这两个目标之间的权衡。值得注意的是，第三种算法可以识别最优的确定性巡逻计划，但其运行时间随着巡逻点数量的增加呈指数增长。实验结果验证了我们解决方案的有效性和可扩展性，表明我们的方法在合成和真实世界的犯罪数据集上优于最先进的基线。
🔬 方法详解
问题定义：论文旨在解决机器人巡逻安全博弈（PSG）问题，该问题中攻击者可以自由选择攻击的时间、地点和持续时间，而防御者（巡逻机器人）的目标是设计最优的巡逻策略以最小化攻击者的收益。现有方法通常假设攻击是即时的或者攻击持续时间是固定的，无法有效应对攻击者具有完全自由度的场景。此外，如何平衡巡逻的效率（最大化奖励）和随机性（增加攻击难度）也是一个挑战。
核心思路：论文的核心思路是将PSG建模为一个扩展式Stackelberg博弈，并将其转化为一个组合极小极大问题。通过限制防御者的策略为时间同质的一阶马尔可夫链，可以在特定情况下（零惩罚）找到最优解。对于更一般的情况，论文提出了一个双准则优化问题，同时考虑最大化预期奖励和熵，以平衡巡逻的效率和随机性。这样设计的目的是为了使巡逻策略既能有效地覆盖关键区域，又能增加攻击者预测巡逻路线的难度。
技术框架：整体框架包括以下几个阶段：1) 将巡逻问题建模为扩展式Stackelberg博弈；2) 将博弈问题转化为组合极小极大问题；3) 在特定条件下（零惩罚）推导出最优解的解析形式；4) 对于一般情况，构建双准则优化问题，目标是最大化预期奖励和熵；5) 提出三种基于图的算法和一个深度强化学习模型来求解双准则优化问题。其中，基于图的算法包括确定性巡逻策略搜索算法（在巡逻点数量较少时可以找到最优解），以及启发式算法。
关键创新：论文的关键创新在于：1) 将攻击者具有完全自由度的巡逻问题建模为扩展式Stackelberg博弈，更真实地反映了实际场景；2) 提出了双准则优化问题，同时考虑了巡逻的效率和随机性，克服了传统方法只关注单一目标的局限性；3) 设计了多种算法和深度强化学习模型来求解该优化问题，并验证了其有效性。与现有方法的本质区别在于，论文的方法能够更好地应对攻击者具有高度灵活性的复杂攻击场景。
关键设计：在双准则优化问题中，需要平衡预期最大奖励和熵。奖励函数的设计取决于具体的应用场景，例如可以是巡逻覆盖的关键区域的价值。熵的计算基于巡逻路线的概率分布，用于衡量巡逻路线的随机性。深度强化学习模型采用Actor-Critic架构，Actor网络用于生成巡逻策略，Critic网络用于评估策略的价值。损失函数包括奖励损失和熵损失，通过调整权重来平衡两个目标。
🖼️ 关键图片
📊 实验亮点
实验结果表明，所提出的算法和深度强化学习模型在合成数据集和真实世界的犯罪数据集上均优于现有基线方法。例如，在某些场景下，所提出的算法可以将攻击者的预期收益降低15%以上。此外，实验还验证了增加巡逻策略的随机性可以有效降低攻击者的收益，特别是在高惩罚情况下。第三种算法虽然计算复杂度较高，但在巡逻点数量较少时可以找到最优的确定性巡逻策略。
🎯 应用场景
该研究成果可应用于多种安全巡逻场景，例如：边境巡逻、城市安防、重要基础设施保护等。通过优化巡逻策略，可以有效降低攻击事件发生的概率，提高安全防护水平，具有重要的实际应用价值和潜在的社会效益。未来，该研究可以进一步扩展到多智能体协同巡逻、动态环境下的巡逻策略调整等方面。
📄 摘要（原文）
We explored the Patrol Security Game (PSG), a robotic patrolling problem modeled as an extensive-form Stackelberg game, where the attacker determines the timing, location, and duration of their attack. Our objective is to devise a patrolling schedule with an infinite time horizon that minimizes the attacker's payoff. We demonstrated that PSG can be transformed into a combinatorial minimax problem with a closed-form objective function. By constraining the defender's strategy to a time-homogeneous first-order Markov chain (i.e., the patroller's next move depends solely on their current location), we proved that the optimal solution in cases of zero penalty involves either minimizing the expected hitting time or return time, depending on the attacker model, and that these solutions can be computed efficiently. Additionally, we observed that increasing the randomness in the patrol schedule reduces the attacker's expected payoff in high-penalty cases. However, the minimax problem becomes non-convex in other scenarios. To address this, we formulated a bi-criteria optimization problem incorporating two objectives: expected maximum reward and entropy. We proposed three graph-based algorithms and one deep reinforcement learning model, designed to efficiently balance the trade-off between these two objectives. Notably, the third algorithm can identify the optimal deterministic patrol schedule, though its runtime grows exponentially with the number of patrol spots. Experimental results validate the effectiveness and scalability of our solutions, demonstrating that our approaches outperform state-of-the-art baselines on both synthetic and real-world crime datasets.