Optimal patrolling strategies for trees and complete networks
Optimal patrolling strategies for trees and complete networks
复制标题
树木和完整网络的最佳巡逻策略
DOI：
10.1016/j.ejor.2023.05.033
复制
发表时间：
2023
影响因子：
6.4
通讯作者：
Lidbetter, Thomas
中科院分区：
文献类型：
--
作者：
Bui, Thuy;Lidbetter, Thomas
提出了一种网络连续巡逻游戏的解决方案。在这个零和游戏中，攻击者选择一个时间和地点在固定的时间内攻击一个网络。巡逻者在网络中巡逻，目的是以最大概率拦截攻击。我们的主要结果是证明了最近关于树木最优巡逻策略的猜想。该猜想断言，一种称为e -巡逻策略的特殊巡逻策略对所有树状网络都是最优的。这个猜想以前已知在有限的一类特殊情况下是正确的。电子巡逻策略具有易于计算和实施的优点。我们通过提出攻击者的ε-最优策略来证明这一猜想，该策略为任意接近e -巡逻策略所提供的下界的博弈值提供上界。在某些情况下，我们还解决了完整网络的巡逻博弈问题。
We present solutions to a continuous patrolling game played on network. In this zero-sum game, an Attacker chooses a time and place to attack a network for a fixed amount of time. A Patroller patrols the network with the aim of intercepting the attack with maximum probability. Our main result is the proof of a recent conjecture on the optimal patrolling strategy for trees. The conjecture asserts that a particular patrolling strategy called the E-patrolling strategy is optimal for all tree networks. The conjecture was previously known to be true in a limited class of special cases. The E-patrolling strategy has the advantage of being straightforward to calculate and implement. We prove the conjecture by presenting ε-optimal strategies for the Attacker which provide upper bounds for the value of the game that come arbitrarily close to the lower bound provided by the E-patrolling strategy. We also solve the patrolling game in some cases for complete networks.
登录
查看更多内容
优化定期巡逻，防止线路和其他网络上的短时间攻击
影响因子：
6.4
作者：
S. Alpern;T. Lidbetter;K. Papadaki
通讯作者：
K. Papadaki
影响因子：
6.4
作者：
N. Zoroa;M. Fernández;P. Zoroa
通讯作者：
P. Zoroa
搜索具有不对称旅行时间的树上的游戏
DOI：
10.1137/090781115
发表时间：
2010
期刊：
SIAM J. Control. Optim.
影响因子：
--
作者：
S. Alpern
通讯作者：
S. Alpern
DOI：
10.1287/moor.2018.0978
发表时间：
2016-07
期刊：
Math. Oper. Res.
影响因子：
--
作者：
R. Fokkink;T. Lidbetter;L. V'egh
通讯作者：
R. Fokkink;T. Lidbetter;L. V'egh
技术说明 - 周界的最佳巡逻
影响因子：
2.7
作者：
Kyle Y. Lin
通讯作者：
Kyle Y. Lin