High-profile, large-scale public events may be attractive targets for terrorist attacks. The security challenge for such events is exacerbated by their dynamic nature: the impact of an attack on different `targets', such as studio entrances, changes over time. In addition, the defender can relocate security resources among potential attack targets at any time, while the attacker may act at any time during the event. This study focuses on developing efficient patrolling algorithms for such dynamic domains, with continuous strategy spaces for both the defender and attacker. We propose SCOUT-A, which makes assumptions regarding relocation costs, exploits payoff representation, and computes optimal solutions efficiently. We furthermore propose SCOUT-C, to compute the exact optimal defender strategy for general cases despite the continuous strategy spaces. The experimental results demonstrate that our algorithms significantly outperform existing strategies.
国家自然科学基金(61202212)
Figure 5
(Color online) Minimax assignment
Time period | $q_i^t(S)$ | $q_j^t(S)$ | $q_l^t(S)$ |
Before $t_1$ | $a_i$ | $a_j$ | $a_l$ |
$[t_1, t_1 + d_{ij})$ | $a_i - 1$ | $a_j$ | $a_l$ |
$[t_1 + d_{ij}, t_2)$ | $a_i-1$ | $a_j +1$ | $a_l$ |
$[t_2, t_2 + d_{jl})$ | $a_i - 1$ | $a_j$ | $a_l$ |
After $t_2 + d_{jl}$ | $a_i - 1$ | $a_j$ | $a_l + 1$ |
|
---|
|
$V_i \leftarrow v_i(0), a_i \leftarrow 0$ |
|
${\rm left} \leftarrow m$ |
|
$i \leftarrow \arg\!\max_{i \in \mathcal{T} }V_i$, $a_i \leftarrow a_i + 1$, ${\rm left} \leftarrow {\rm left} - 1$, $V_i \leftarrow W_i^{a_i}(0)$ |
|
$t_m \leftarrow 0$, $k \leftarrow 0$ |
|
${\boldsymbol I} \leftarrow \emptyset$ |
|
|
$I_{ij} \leftarrow I_{ij}(A, t_m)$ |
|
${\boldsymbol I} \leftarrow {\boldsymbol I} \cup I_{ij}$ |
|
|
|
|
break |
|
$I_{ij} \leftarrow \min({\boldsymbol I})$ |
|
$\tau_k \leftarrow I_{ij}, t_m \leftarrow I_{ij}, a_i \leftarrow a_i - 1, a_j \leftarrow a_j + 1, c_{ij}^k \leftarrow 1, k \leftarrow k + 1$ |
|
|
Time period | $q_i^t(S)$ | $q_j^t(S)$ | $q_l^t(S)$ |
Before $t_3$ | $a_i$ | $a_j$ | $a_l$ |
$[t_3, t_3 + d_{il})$ | $a_i-1$ | $a_j$ | $a_l$ |
After $t_3 + d_{il}$ | $a_i - 1$ | $a_j$ | $a_l + 1$ |
|
---|
$\Psi \leftarrow \emptyset$ |
|
$\Psi \leftarrow \Psi \cup \{\theta({\rm Tr})\} \cup \{\theta({\rm Tr}) + d_{ij}\},$ where ${\rm Tr} = (i, j, a_i, a_j, \rho, \rho')$ |
|
run SCOUT-D, using $\Psi$ as the time points set |
鸟巢 | 奥林匹克公园 | 首体 | 工体 | 五棵松 | |
鸟巢 | – | 8 | 14 | 17 | 29 |
奥林匹克公园 | 8 | – | 20 | 24 | 33 |
首体 | 14 | 20 | – | 24 | 17 |
工体 | 17 | 24 | 24 | – | 36 |
五棵松 | 29 | 33 | 17 | 36 | – |