Patrol Security Game: Defending Against Adversary with Freedom in Attack Timing, Location, and Duration

Patrolling and surveillance problems have been extensively studied in the fields of robotics (see the detailed survey by Basilico et al. (Basilico, 2022)) and operations research (Samanta et al., 2022). In non-strategic settings, algorithms are designed for traversing a specified region using centralized optimization to achieve specific objectives (Elmaliach et al., 2008; Portugal and Rocha, 2011; Iocchi et al., 2011; Stump and Michael, 2011; Liu et al., 2017). For example, Alamdari et al. (Alamdari et al., 2014) address the problem of minimizing the maximum duration between consecutive visits to a particular location, providing a $\log n$-approximation algorithm for general graphs. Subsequent research has expanded on these results for specific graph structures, such as chains and trees (Pasqualetti et al., 2012). Recently, this objective has been extended to multi-agent scenarios (Afshani et al., 2021, 2022).

In strategic settings, patrol strategies are designed to defend against intelligent intruders who seek to avoid detection. Consequently, many studies model patroller movements as Markov chains or random walks to introduce unpredictability into patrol routes (Grace and Baillieul, 2005; Patel et al., 2015; Duan et al., 2018; Cannata and Sgorbissa, 2011; Asghar and Smith, 2016), focusing on metrics such as efficiency or entropy. For instance, Patel et al. (Patel et al., 2015) investigate minimizing the first-passage time, while Duan et al. (Duan et al., 2018) examine maximizing the entropy of return times. Salih et al. (Çam, 2023) combine game theory with these approaches to estimate expected return times. These objectives can also be discussed in more advanced random walk settings (Branquinho et al., 2021; Dshalalow and White, 2021), corresponding to different defender models.

A more advanced strategic settings which explicitly define the interaction between defenders and attackers, called Stackelberg security games. In this field, Kiekintveld et al. (Kiekintveld et al., 2009) introduced a general framework for security resource allocation, which has since been widely applied in various security domains with differing scenarios (Li et al., 2020; Agmon et al., 2011; Basilico et al., 2009; Vorobeychik et al., 2012; Abdallah et al., 2021). Notable applications include the deployment of randomized checkpoints and canine patrol routes at airports (Pita et al., 2008), deployment scheduling for U.S. Federal Air Marshals (Tsai et al., 2009; Janssen et al., 2020), and the patrol schedules for U.S. Coast Guard operations (Fang et al., 2013; Shieh et al., 2012) and wildlife protected rangers (Yang et al., 2014; Kirkland et al., 2020). On the other hand, various adaptations of the security game model have been proposed to fit specific application scenarios by altering the utility functions and the dynamics of attacker-defender interactions. Vorobeychik et al. (Vorobeychik et al., 2014) introduced a discounted time factor in the attacker’s payoff function to account for the increased likelihood of detection over prolonged attack periods. Bošansk‘y et al. (Bošanskỳ et al., 2011) explored scenarios where targets move according to deterministic schedules, while Huang et al. (Huang and Zhu, 2020) introduced a dynamic game framework to model the interaction between a stealthy attacker and a proactive defender in cyber-physical systems. Song et al. (Song et al., 2023) investigated security games involving multiple heterogeneous defenders.

Addressing the scalability of these models remains a significant challenge as suggested in Hunt et al. (Hunt and Zhuang, 2024). Current solutions are often tailored to specific applications. For example, in the ASPEN framework (Jain et al., 2010), multiple patrollers are deployed, with each patroller’s strategy solved independently to prevent combinatorial explosion in schedule allocation. This approach has been extended in the RUGGED system (Jain et al., 2011) for road network security. Shieh et al. (Shieh et al., 2013) built on previous work, utilizing the Traveling Salesman Problem (TSP) as a heuristic tool to order the search space, providing efficient heuristic solutions for each patroller. Basilico et al. (Basilico et al., 2012) assumed the attacker requires a fixed period to execute an attack and employed reduction techniques to address scalability, though this approach is limited to unweighted graphs where the attacker cannot control the attack duration. More recently, Wang et al. (Wang et al., 2020) applied graph convolutional networks to model attacker behavior, using randomized block updates to reduce time complexity. Wang et al. (Wang, 2020) also examined the trade-offs between linear and non-linear formulations, analyzing the impact of linearization on scalability. However, due to the specificity of these designs, these approaches cannot be directly applied to all problems.

The problem of planning patrol routes is related to the general family of vehicle routing problems (VRPs) and traveling salesman problems (TSPs) with constraints (Ausiello et al., 2000; Laporte, 1992; Pillac et al., 2013; Yu and Liu, 2014). This is a huge literature thus we only introduce the most relevant papers.

TSP is a well-known NP-complete problem in combinatorial optimization and has been discussed in operation research (Angel et al., 1972; Kim and Park, 2004; Carter and Ragsdale, 2002). Christofides algorithm (Christofides, 1976) provides a tour whose length is less or equal to 1.5 times of the minimum possible. Additionally, there are two independent papers that provide polynomial-time approximation scheme (PTAS) for Euclidean TSP by Mitchell and Arora (Mitchell, 1999; Arora, 1996). There are many variations of TSP that consider multiple objectives (Bienstock et al., 1993; Awerbuch et al., 1995). In this work, one objective is to increase the randomness between generated tours. A close-related objective called “diversity” has been discussed recently with other combinatorial problems such as diverse vertex cover (Hanaka et al., 2021) or diverse spanning trees (Gao et al., 2022). However, to the best of our knowledge, TSP had not been studied in the terms of diversity or tours with high randomness. The other objective is related to minimize the maximal weighted latency among sites of the tour, which has been discussed in some works (Alamdari et al., 2014; Min and Radzik, 2017; Afshani et al., 2021, 2022). One difference is that this work generalizes the “weight latency” as functions rather than constant weights.

In recent years, the integration of Deep learning into combinatorial optimization problems has seen significant advances, including the TSP problem A pivotal development in this domain was introduced by Vinyals et al., who developed the Pointer Network (PN), a model that utilizes an attention mechanism to output a permutation of the input and trains to solve TSP (Vinyals et al., 2015). Building on this, Bello et al. enhanced the PN by employing an Actor-Critic algorithm trained through reinforcement learning, further refining the network’s ability to optimize combinatorial structures (Bello et al., 2016). The application of PN was further extended by Kool et al., who incorporated a transformer-like structure to tackle not only TSP but also the Vehicle Routing Problem (VRP), the Orienteering Problem (OP), and a stochastic variant of the Prize Collecting TSP (PCTSP).  (Kool et al., 2018). In addressing challenges associated with large graph sizes, Ma et al. (Ma et al., 2020) introduced a hierarchical structure that scales the model effectively, enabling it to manage and solve larger instances of combinatorial problems. Additionally, Hottung et al. (Hottung et al., [n. d.]) use of Variational Autoencoder (VAE) and explore the latent space for routing problems. Furthermore, Kim et al. (Kim et al., 2021) proposed a novel method for solving TSP that involves a seeding and revision process, which generates tours with an element of randomness and subsequently refines them to find superior routes.

In the model of full visibility, the attacker knows the exact position of the patroller among all sites. Denote $Z_{i,j,T}$ as the expected payoff if the attacker launches an attack at $j$ with the attack period $T$ when the patroller is at $i$. In any time slot $t$ during the attack, where $1\leq t\leq T$, there are only 3 possible events: the patroller comes to site $j$ (after visiting $i$) in the period of time 1 to $t-1$, the patroller comes exactly at time $t$, or the patroller comes after time $t$. In the first case, the attacker cannot collect utility at time $t$ since the attack is enforced to stop at $t^{\prime}$, where $t^{\prime}<t$ (the penalty is also paid at time $t^{\prime}$ too). In the second case, the attack is caught at time $t$ thus there is a penalty $M$ substrated from the attacker’s payoff. In the third case, the attacker collects utility $h_{j}(t)$. Thus, the expected payoff at time $t,1\leq t\leq T$, can be expressed as a closed form associated with $F$.

The total (expected) payoff during the whole attack period is $Z_{i,j,T}=\sum_{t=1}^{T}z_{i,j}(t)$, which is called as the payoff matrix. The attacker chooses an element of $Z$ with the highest payoff, which describes his strategy of when, where, and how long the attack lasts.

For the defender, the problem of choosing a best strategy can be formulated as a minimax problem:

For general utility function $h_{j}$ and penalty $M$, the Hessian matrix of $f$ is not guaranteed to be semi-definite thus $f(P)$ is not convex in general. However, in special cases $f(P)$ has strong connection with the expected hitting time matrix $A$.

If $M=0$ and the utility functions are all constant functions, then $f(P)$ is either $\infty$ or the maximum weighted expected hitting time of all pairs $(i,j)$, with the weight for $(i,j)$ as the constant of the utility function $h_{j}$.

At the defender’s side, minimizing the maximum of all pairwise expected hitting times is still an open question to the best of our knowledge. One can find a relevant work which provides a lower bound and discusses the complication for this question (Breen and Kirkland, 2017).

In this model, assume the attacker’s strategy is to attack site $j$ with the attack period $T$. Denote $z^{\prime}_{j}(t)$ as the utility he collects for every time $t$ where $1\leq t\leq T$,

By a similar discussion in Observation 4.1, one can infer that the best strategy for the attacker is to attack the site with the longest expected (weighted) return time if the utility functions are all constants and the penalty is zero. If all edges have weight one, the optimal defender strategy can be derived by constructing an ergodic Markov chain with stationary distribution $\pi^{*}$, where $\pi^{*}_{j}=\frac{h_{j}}{\sum_{i=1}^{n}h_{i}}$, since the expected return time of a site $j$ is $1/\pi^{*}_{j}$ (Serfozo, 2009).

In this case, the attacker has no information of the patroller’s trace thus it is meaningless for the attacker to choose when to launch an attack; instead, the payoff of attacking site $j$ is the expected payoff when the patroller is either at a random site $i$ or travels on a random edge $(i,j)$. For the following analysis, we only consider the attacks that starting at the time when the patroller is at exactly one of the sites. For general cases, it would underestimate the attacker’s expected payoff at most $\max_{i,j}\sum_{t=1}^{w_{ij}}h_{j}(t)$ utilities.

Denote $Z^{\prime\prime}_{j,T}$ as the cumulative expected payoff for attacking $j$ with period $T$ and $z^{\prime\prime}_{j}(t)$ is the expected payoff at time $t$. Assume the attack is launched at a random time slot, $z^{\prime\prime}_{j}(t)$ is

where $\pi$ is the stationary distribution with transition matrix $P$. Thus, the cumulative expected payoff is

Denote $\kappa_{i}$ as the Kemeny constant (Kemeny and Snell, 1960), the expected hitting time when the walk starts at $i$, $\kappa_{i}=\sum_{j=1}^{n}a_{i,j}\pi_{j}$. It is known that the Kemeny constant is independent of the start node (Kemeny and Snell, 1983). Thus, the Kemeny constant can be written as another formation

Equation 6 can be written as an expression with matrix $A$.

Now, suppose $f^{\prime\prime}(P)=\max_{j,T}Z^{\prime\prime}_{j,T}$ is the function maximizing the expected payoff, the following observation is shown. If $M=0$ and the utility functions are all constant functions, $f^{\prime\prime}(P)$ is either $\infty$ or the Kemeny constant multiplying with the maximum constant among all utility functions.

Observation 7 shows that when the penalty is zero with constant utility functions, the attacker’s best strategy is to attack the site with highest utility. From the defender side, it has to determine $P$ such that the Kemeny constant is minimized. When all edges have weight 1, a simple solution is to construct $P$ same as the adjacent matrix of a directed $n$-cycle in $G$ (Kirkland, 2010). In other cases, it has to minimize the Kemeny constant subject to a given stationary distribution (Patel et al., 2015).

When $M\gg h_{j}(t)$ for all sites $j$ and all time $t$, Equation 1 can be simplified as

Assume that the attacker has full visibility and all utility functions are constants.

At the defender side, it is beneficial to increase $\sum_{t=1}^{T}F_{t}(i,j)$ for all $(i,j)$ pairs. Thus, having a schedule which is more random could help in this case. This observation also works in other two attacker models.

The Algorithm TSP-based solution (TSP-b) is perturbing the optimal (or approximately optimal) deterministic EMR solutions by a parameter $\alpha$. Adjusting this skipping parameter $\alpha$ will balance the two criteria. Roughly speaking, the main idea is to traverse on a deterministic tour but each vertex is only visited with probability $\alpha$ (i.e., with probability $1-\alpha$ it is skipped). Obviously, Algorithm TSP-b generates a randomized schedule. Also, since the algorithm works with a metric (with triangular inequality), the total travel distance after one round along the tour is bounded by the original tour length. Hence, the expected reward can be bounded.

The following is the analysis of EMR and entropy rate for TSP-b when the utility functions are polynomial functions with the maximum degree $d$.

Algorithm Biased Random Walk (Bwalk) uses a biased random walk to decide the patrol schedule. Define matrix $W^{\prime}=(w^{\prime}(i,j))\in\mathbb{Z}^{n\times n}_{\geq 0}$. For each pair $(i,j)$,

where $\alpha$ is an input parameter. Define stochastic matrix $P^{\prime}$ as

Algorithm Walk on the State Graph (SG) with a parameter $\alpha$ generates the schedule by a state machine with the transition process as another random walk.

Given a graph, the tour of the graph can be treated as a rearrangement or permutation $\pi$ of the input nodes. We can formulate it as the Markov decision process(MDP).

At each time step $t$, the state consists of the sequence of action made from step $0$ to $t-1$, while the action space at time step $t$ is the remaining unvisited nodes. Our objective is to minimize the length of the action sequence made by MDP, so we define the negative tour length as our cumulative reward $R$ for each solution sequence. Now we can define the policy $p(\pi|g)$ which can generate the solution of instance $g$ parameterized by parameter $\theta$ as below:

where $p_{\theta}(\pi_{t}|g,\pi_{1:t-1})$ provide action $a_{t}$ at each time step $t$ on instance $g$. Overall, the model takes the input of the coordinates among all sites $X$ and put into the encoder. Then, the decoder starts to output the desired policy (i.e., a site) step by step recurrently till the sequence includes all the sites. The model structure of the encoder and decoder is shown at fig.  1 which is base on the work of Ma et al (Ma et al., 2020).

1. (1)

   Encoder: The encoder consists of a Graph convolutional Network (GCN) and a Long Short-Term Memory (LSTM) network. The GCN is responsible for processing the graph, encode the nodes coordinates into ”context” $X^{l}$. Meanwhile, the LSTM handles the trails, process the action sequences $\pi_{1:t-1}$ into hidden variable $h_{t}$ at each time step $t$. Both the context and hidden variable are passed to the decoder in the current step. Additionally, the hidden variable $h_{t}$ will pass to next time step encoder to process the sequence $\pi_{1:t+1}$. The GCN layer can be described as below:

   (15)

   $$x_{i}^{l}=\gamma x_{i}^{l-1}\Theta+(1-\gamma)\phi_{\theta}\left(\frac{1}{\left|\mathcal{N}(i)\right|}\left\{x_{j}^{l-1}\right\}_{j\in\mathcal{N}(i)\cup\{i\}}\right)$$

   Where $\gamma$ is the learnable weight, $\Theta$ is trainable parameters and $\phi_{\theta}$ is the aggregate function of adjacent nodes $\mathcal{N}(i)$ and node $x_{i}$.

2. (2)

   Decoder: The decoder is using an attention mechanism to generate the pointer which will point to a input node $x_{j}$ as a output action $a_{t}$, similar to pointer networks. The attention mechanism will provide a pointer vector $u_{t}^{(j)}$ than pass it through a softmax layer to get the distribution of the candidate nodes, which can be sampled or chosen greedily as output $a_{t}$.

   (16)

   $$u_{t}^{(j)}=\begin{Bmatrix}w^{\top}*\tanh(W_{r}r_{j}+W_{q}q)&\text{if }j\neq\pi_{t^{\prime}}\text{ , }\forall{t^{\prime}<t}\\ -\infty&\text{otherwise }\par\end{Bmatrix}$$

   The decoder will mask the nodes at attention mechanism if the candidate node $x_{j}\in\pi_{1:t-1}$. Here, $q$ represents the hidden variable $h_{t}$, and $r_{j}$ denotes the context $X_{j}^{l}$ from the encoder. Both $W_{r}$ and $W_{q}$ are trainable parameters, and $\pi_{t}$ can be expressed as fallow:

   (17)

   $$\pi_{t}=a_{t}\sim\mbox{softmax}(\mathbf{u}_{t})$$

To force the policy have more ability to sample the diverse solution, we add the entropy constrain to objective function.

Entropy : For each time step, the output of the solver will provide us a probability distribution of the candidate cities. Here, we define the entropy as below:

The entropy of the policy effectively captures the randomness of the solution. However, computing the accuracy entropy of the policy $p_{\theta}(\mathbf{\pi}|g)$ is computationally expensive. Therefore, we approximate it by summing the entropy computed at each time step $t$.

Training: To train the slover, we use the REINFORCE algorithm with rollout baseline $b$ . (Ma et al., 2020; Kool et al., 2018). The the objective function can be described as follows:

Where $L(\pi|s)=\sum_{t=1}^{N-1}\left\|x_{\pi_{t+1}}-x_{\pi_{t}}\right\|_{2}+\left\|x_{\pi_{N}}-x_{\pi_{1}}\right\|_{2}$ and $\alpha$ is the weight parameter of the constraint, with the importance of randomness increasing as the value of $\alpha$ grows. We use the ADAM optimizer to obtain the optimal parameter $\theta$ that minimizes this function. During training, we chose to use the central self-critic baseline introduced by Ma et al. (Ma et al., 2020). The $b(g)$ is expressed as

where the action $\tilde{\mathbf{a}}_{t}$ is picked by the greedy policy $p_{\theta}^{Greedy}$, which means each action is the candidate node that have the highest probability at each time step and $\tilde{\mathbf{s}}_{t}$ is the corresponding state, i.e. the instance $g$ and $\tilde{\mathbf{\pi}}_{1:t-1}$ we mention at Equation 14 .

For cases involving uniform utility weights, where the utility functions are consistent across all sites, directly applying the aforementioned model with an appropriate hyperparameter $\alpha$ yields the desired tours that effectively balance Expected Maximal Reward (EMR) and entropy. In scenarios with non-uniform utility weights, it is necessary to integrate the BGT algorithm (Min and Radzik, 2017) into the generated schedule. However, an intriguing observation about the BGT algorithm is that it visits each group, regardless of whether they have high or low weights, with equal frequency. Theoretically, this uniform visitation does not impact the analysis of the approximation factor, since the total number of groups is $O(\log n)$. Empirically, however, increasing the visitation frequency of high-weight sites can significantly enhance the overall EMR.

We present a method to carefully modify the BGT algorithm so that the overall EMR is empirically increased while preserving the $O(\log n)$ approximation factor. Notably, within the TSP-based solution procedure outlined in Section 5.1.2, modifying the BGT is unnecessary since the skipping parameter can be controlled concerning the weight coefficient of the sites (i.e., the skipping probability is inversely proportional to the site’s weight).

Algorithm 1 describes the DRL implementation that incorporates BGT. Let $G$ represent a graph instance. The graph’s diameter, denoted as $D$, is defined as the longest distance between any two nodes in $G$. For a given node $j$, let $w_{j}$ be the coefficient of the highest degree term in the utility function $h_{j}$ for node $j$. Define $w$ as the set containing all such coefficients $w_{j}$ for each node $j\in G$. Let $L$ denote the length of the sequence intended to be generated. The overall algorithm follows standard BGT procedures (Min and Radzik, 2017), with exceptions at Lines 11 and 16-17. In Line 11, the generated tour is replaced by our DRL model. In Lines 16-17, the visiting order for weight groups ${V_{i}}$ is determined by the ”inorder traversal of a complete binary tree.” Specifically, we construct a complete binary tree where the height corresponds to the number of groups. Groups are organized hierarchically: the group with the lowest weight is positioned at the root, the second lowest at the first level, and so forth, with each level filled with exactly the same group. The visiting order of each group follows the node sequence encountered in the traversal. See Fig 3 for an example.

Figure 4 reports the performance of algorithms under Expected maximum reward and Entropy rate. In this specific experiment, GPN-b has an additional version,GPN-b:I, that incorporates BGT with the inorder traversal method (see Section 6.2. In the y-axis, we scale the EMR as 1 if the maximum reward is generated by BGT. Each point represents the schedule which is generated by different algorithms and the digit aside from each point denotes the value of the input parameter $\alpha$. For example, in TSP-b, the skip probability is 0.2 as $\alpha=0.8$. For TSP-b and Bwalk, the lower value of $\alpha$ indicates the higher randomness of the schedule. For GPN-b,GPN-b:I, and SG, the higher the value of $\alpha$ indicates the higher randomness of the schedule.

The results in Figure 4 demonstrate that all proposed algorithms can balance the two criteria by adjusting the parameter $\alpha$. Notably, GPN-b:I exhibits greater efficiency than GPN-b regarding the trade-off between EMR and entropy, indicating that the inorder traversal method empirically outperforms the approach that directly utilizes BGT. Conversely, while SG achieves the highest entropy, its performance varies with different values of $\alpha$, indicating some instability.

The experiments are examined with the following variables; penalty values, the maximum degree of utility functions (1, 2, 3), and the attacker models (Full vis., Local vis., No vis.). The last figure reports the simulation result of Denver crime dataset. Each figure shows the attacker’s (expected) payoff under different penalties. Each realization has been run 10 times and the y-axis is the average attacker’s payoff with standard errors. We interpret an algorithm has better performance if and only if the attacker has the lower payoff in the schedule generated by this algorithm.

Generally speaking, the attacker payoff drops down when the penalty increased and with lower ability of the attacker (e.g., full vis. v.s. local vis.) the attacker payoff is also lower. In the experiments of constant utility functions (Figure 5,8,11), Although TSP-b performs the best in Full vis., minKC is comparable in Local and No vis.. This reflects our observation in Section 4, that the optimal solution has a strong correlation with the minimum hitting time.

In the experiments of non-constant utility functions (Figure 6, 7, 14), our algorithms clearly outperform the baselines in most cases. For example, the attacker’s payoff is around 4 for minKC but only around 0.25 for GPN-b in the case of linear utility functions, 2.18 penalty value. One possible reason is that minKC and maxEn are designed only for constant vertex weight and they are not suitable for non-constant utility functions. On the other hand, our algorithms focus on the two objectives: EMR and entropy rate, which are not limited to the constant utility functions. In the comparison of four proposed algorithms, SG performs the best in high penality scenarios with full and local vis. In these cases, the adversary can learn more if the visiting sequence has some correlation with the visiting history, which is the case in the other three algorithms. On the other hand, the performance of SG is not dominiated anymore in No vis. cases.

Figure 15 reports the scalability of the solutions. The settings are full visibility attacker model, constant utility functions, and 0 penalty value for demonstration. To compare the performance under different setups, all attacker’s expected payoff is divided by the payoff of the BGT patrol route. Since the number of constraints in minKC increases exponentially concerning the number of the sites, when the number of sites is more than 100, the solution cannot converge after 200k iterations (the solution minKC is calculated by CXYOPT in a desktop of i7-13700K 3.40 GHz with 96.0 GB RAM).

For other solutions, the four proposed algorithms have much better performance than maxEn, which has 1.2, 174.6, 132.8, and 132.9 attacker payoff in 50, 100, 150, and 200 sites respectively (those values are too high to compare in the plot thus we report the numbers here). Comparing within the proposed algorithms, GPN-b has the best performance and SG has the worst performance. One reason is that schedules generated by SG have higher randomness. When the number of sites increases which makes the topology become complicated, it favors patrol schedules with more delicate designed routes.