自动优化防守者记忆分配，提升对抗巡逻策略的实战效果。
Memory Assignment for Finite-Memory Strategies in Adversarial Patrolling Games
- 通过迭代调整各位置的记忆分配，实现策略优化
- 在多个巡逻模型中验证，显著提升防御性能
- 可对接任意黑盒优化工具，通用性强
对抗巡逻游戏是安全博弈的一个子类，其中防守方在多个地点间移动以保护脆弱目标。核心算法问题是如何构建防守策略，使攻击方造成的最大损失最小化。本文聚焦于有限记忆（又称正则）防守策略，这类策略在实验中表现优于其他类型。有限记忆策略可视为在有限状态集上的位置策略，每个状态由一个位置和一个整数记忆值组成。现有算法虽能优化状态间的转移概率，但需手动指定各位置的可用记忆大小，而记忆分配本身是一个长期未解的难题，严重限制了有限记忆策略的应用。本文提出一种通用方法，通过迭代方式动态调整记忆分配，可与任意黑盒策略优化工具结合使用。在多种实验设置下评估该方法，证明其在不同巡逻模型中的鲁棒性与有效性。
原文摘要 · Abstract (English)
Adversarial Patrolling games form a subclass of Security games where a Defender moves between locations, guarding vulnerable targets. The main algorithmic problem is constructing a strategy for the Defender that minimizes the worst damage an Attacker can cause. We focus on the class of finite-memory (also known as regular) Defender's strategies that experimentally outperformed other competing classes. A finite-memory strategy can be seen as a positional strategy on a finite set of states. Each state consists of a pair of a location and a certain integer value--called memory. Existing algorithms improve the transitional probabilities between the states but require that the available memory size itself is assigned at each location manually. Choosing the right memory assignment is a well-known open and hard problem that hinders the usability of finite-memory strategies. We solve this issue by developing a general method that iteratively changes the memory assignment. Our algorithm can be used in connection with any black-box strategy optimization tool. We evaluate our method on various experiments and show its robustness by solving instances of various patrolling models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。