M A S A R Y K U N I V E R S I T Y F A C U L T Y O F I N F O R M A T I C S Memory Distribution in Regular Patrolling Strategies B A C H E L O R ' S T H E S I S Vojtěch Kůr Brno, Fall 2024 Declaration Hereby, I declar e that this thesis is my or iginal author ial wor k, which I have worked out on my own. All sources, references, and literature used or excerpted dur ing the elabor ation of this work are properly cited and listed in complete reference to the due source. In the preparation of this thesis, I used the following AI tools: • Gr ammar ly for syntax and grammar checking, and for improving my writing style, • ChatGPT for data pr ocessing and visualization, and for limited code generation. I declare that I used these tools according to the principles of academic integrity. I checked the content and take full r esponsibility for it. Vojtech Kur Supervisor: doc. RNDr . Vojtěch Řehák, Ph.D. Consultant: RNDr. Vít Musil, Ph.D. Acknowledgments I would like to t hank Vojt ěch Řehák for his great guidance, support, and approach. I am especially grateful for his insistence on not over-engineering. I would also like t o t hank Vít Musil for helping me with my thesis. His insights into optimization were incredibly hopeful in preparing my work. I would like to thank all the people who have supported me in my studies, especially my lovely parents, close family, and friends. Let this work serve ad maiorem Dei gloriam. Remember that unless the Lord keep the cit y, he watches in vain that keeps it. Abstract 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. Keywords Strategy synthesis, Security Games, Adversarial Patrolling Contents Introduction 1 1 Adversarial Patrolling Games 5 1.1 Patrolling Graph 5 1.2 Defender's Strategy 5 1.3 Attacker's Strategy 6 1.4 Protection Value 6 1.5 Requirements on the Patrolling Model 7 1.6 Target Types 7 1.6.1 Hard-constrained targets 7 1.6.2 Blind targets 8 1.6.3 Linear targets 8 1.7 Sufficient Condition for Second Requirement 8 1.8 Strategy Types 10 2 The Problem of Memory Assignment 11 2.1 Deterministic Strategies 12 2.2 Memoryless Strategies 14 2.3 Finite-memory Strategies 14 2.4 Suboptimal Memory Assignment 15 3 The Method 17 3.1 Attacks Profiles 17 3.2 Strategy Expansion 20 3.3 Bounded Number of States 21 4 Experiments 23 4.1 Setup 23 4.1.1 Terminating the optimization process 24 4.1.2 Changing the epochs 24 4.1.3 Hyperparameters of the tools 24 4.2 Solving Toy Examples 24 4.2.1 Finding the optimal memory assignment 25 4.2.2 Finding the optimal strategy 26 v 4.2.3 Summary 27 4.3 Patrolling Offices 28 4.3.1 One floor 29 4.3.2 Two floors 30 4.3.3 Three floors 31 4.3.4 Summary 32 4.4 Patrolling Blinded Offices 33 4.4.1 Results 34 4.5 Patrolling Airports 35 4.5.1 Uniform values of gates 36 4.5.2 Random values of gates 36 4.5.3 Summary 37 4.6 Patrolling Large Terrains 38 4.6.1 Results 4 0 5 Conclusion 42 Bibliography 43 vi Introduction This work follows the patrolling games line of work studying non-cooperative games where a mobile Defender guards resources against an Attacker. In adversarial patrolling [1, 2, 3, 4, 5, 6, 7], the Attacker knows the Defender's strategy and observes his locations. The solution concept is based on Stackelberg equilibrium. The Defender commits to a strategy a, and the Attacker chooses a counter-strategy TT that maximizes the expected Attacker's utility against a. Intuitively, the value Val(cr) denotes the damage caused by the best Attacker, and the precise definition of Val depends on the underlying patrolling model. The environment where the agents play can be described by a Markov decision process. If the environment is not fully known, the problem becomes one of reinforcement learning, where the agent learns the strategy through interaction with the environment, using either model-free (e.g., Qlearning) or model-based (e.g., using a learned model to simulate outcomes) approaches. We focus on the cases when the environment is fully known both to the Defender and the Attacker. An example of such an environment is an oriented graph that typically describes the topology of the terrain. This concept is also used in the domain of planning. Another aspect is the time frame in which the game is evaluated, which plays a critical role in shaping the agent's behavior. We focus on an infinitehorizon model, where the Attacker can wait as long as needed to exploit the best opportunity that maximizes the damage on the targets. This is especially suitable for uninterrupted services where the Defender represents many consecutive patrol shifts or a robot that is expected to run for a long time. For general topologies, the existence of the optimal Defender's strategy is PSPACE-complete [8]. Additionally, determining an e-optimal strategy for e < l/2n, where n represents the number of vertices, is NP-hard [9]. Therefore, no polynomial algorithm can guarantee (sub)optimality in general (unless P = NP). Finding suitable heuristics applicable to real-world scenarios is of great importance. Prior works focus on constructing positional strategies where the Defender makes a randomized choice of the next location based only on the current location [4, 10, 11, 12]. However, positional strategies fail to provide 1 optimal protection even in a simple setting; see Figure 3.1 or [13]. To increase the strategy expressivity, Antonín Kučera and Tomáš Lamser [13] introduced a class of regular strategies, where the Defender is equipped with a suitable finite­state automaton. In each location, the distribution over the next locations is determined by the state of the automaton after feeding it with the current history of locations. T he authors proved that regular strategies offer better protection than positional strategies, even if the positional strategy depends on the last k locations. T hey also present a strategy synthesis algorithm for regular strategies. However, this approach's main limitation is that the finite­state automaton must be supplied manually to achieve strong strategies. The idea of regular strategies was followed by finite-memory strategies where the finite­state automaton is abstracted into finite integer memory denoted M [14]. The Defender chooses the new location based on the current location and memory and also selects (possibly randomly) the new memory value. Finite­memory strategies can also be seen as positional strategies on the set of states consisting of the pairs of the location and a memory integer between 1 and M. In this view, the state space increases dramatically, limiting the usability and performance of optimization algorithms. In fact, the size of the memory does not necessarily need to be the same in each location, i.e., the states can be set as C = {(v,i) \ v G V, 1 < i < mem(i/)}, where V is a set of locations and mem: V —>• N is certain memory-assignment function. Recent works provide well­performing optimization algorithms for finitememory strategies and various patrolling models [14, 15, 16, 17]. However, they all assume that a suitable memory assignment is given as an input. Currently, this is the main bottleneck of these algorithms, and the results depend heavily on the choice of mem. All the published experiments either use uniform memory assignment with increasing M (that hits the limits of the algorithms already for M < 10) or use carefully handcrafted assignment mem based on the expert knowledge of the problem at hand. T o the best of our knowledge, no approach automates memory assignment for general topologies. Klaška et al. [15] state that choosing the optimal set of configurations is an open and hard problem. Our Contribution We propose a smart general heuristic algorithm that dynamically adjusts the memory assignment for finite­memory strategies without any expert knowledge. Our method works with any differentiable value function and any black­box strategy optimization tool. In combination, our memory assignment algorithm, together with any strategy synthesis algorithm, yields a 2 general and fully automated method for a strong finite-memory Defender's strategy. We evaluate our method on several benchmarks and for various patrolling models. Our automated approach outperforms the manual memory assignment when mem is chosen to be uniform with increasing M in both speed and attained protection value. Furthermore, our method is on par with expertly handcrafted memory assignments. Related Work This work contributes to the field of security games, which focuses on the optimal allocation of limited security resources to achieve effective target coverage, see monograph [18]. Patrolling games are a specialized type of security game where the Defender is mobile; see survey works [19, 20, 21, 22]. Most existing patrolling models can be categorized as either regular or adversarial. Regular patrolling [23, 24, 25] is akin to surveillance, where the Defender's goal is to quickly discover incidents by minimizing the time between consecutive visits to each target. In this model, the Defender typically employs a strategy involving a single path or cycle that visits all targets. In contrast, adversarial patrolling [1, 2, 3, 4, 5, 6, 7, 22] focuses on protecting targets from an Attacker who seeks to exploit the best opportunities to maximize damage. This model is generally framed within the context of Stackelberg equilibrium [26, 27]. The Defender's strategies are often randomized to prevent the Attacker from predicting future moves, and the Defender aims to maximize the probability of detecting an attack. The adversarial approach is particularly relevant in scenarios where a certain level of protection must be maintained, even if incidents occur at the most inconvenient times. For patrolling scenarios of bounded duration, such as an eight-hour shift of a human ranger, finite-horizon models are sufficient. In contrast, infinitehorizon models are used when the duration is potentially unbounded or the bound is large, like 24/7 surveillance, etc. There are also studies combining both by introducing a discount factor [28]. The model can also be distinguished by prior knowledge about the environment, which can be either fully known to all players or needs to be discovered during patrolling. The difference between models with finite or infinite horizon and known or unknown environments has a substantial impact on strategy synthesis techniques. For finite horizon models with known environments, mathematical programming is the primary technique [4, 5]. Reinforcement learning has been largely successful for patrolling scenarios with a finite horizon and unknown environment, such as green security games [29, 30, 31, 32]. Gradient descent methods for finite-memory strategies are used extensively for 3 infinite horizon models with known environments [14, 15, 16, 17]. Practical applications of security games include the deployment of police checkpoints at Los Angeles International Airport [33], the scheduling of federal air marshals on domestic airline flights across the U.S. [34], and the strategic arrangement of city guards in the Los Angeles Metro [35], positioning of U.S. Coast Guard patrols to secure critical locations [36], as well as the initiatives for wildlife protection in Uganda [37]. 4 Chapter 1 Adversarial Patrolling Games First, we recall the standard notions of a patrolling graph, the Defender's and Attacker's strategy, and their value, and we fix the notation. Then, we formulate the requirements of our algorithm for the underlying patrolling model and show how existing patrolling models fit our framework. We assume familiarity with basic notions of calculus, linear algebra, probability theory, and finite-state discrete-time Markov chains. 1.1 Patrolling Graph A patrolling graph is a tuple G = (V, T, E, time), where • V is a non-empty set of locations (admissible Defender's positions): • T C V is a non-empty set of targets: • £ C K x is a set of edges (admissible Defender's moves): • time: E —>• N specifies the traversal time of an edge. For technical reasons, we require that for every u € V, there is v £ V such that (u, v) G E. In the sequel, let G be a patrolling graph. 1.2 Defender's Strategy In general, the Defender can choose the next location randomly based on the whole history of previously visited locations. However, general strategies may not be finitely representable. We focus on finite-memory Defender's strategies, which were shown to achieve the same limit protection as general strategies in two different patrolling models; see [15] and [17]. Moreover, both positional and finite deterministic strategies can be seen as a subclass of finite-memory strategies, see Section 1.8. 5 In finite-memory strategies, the Defender is equipped with an integer variable M called memory. A state of the Defender is a pair (v, i) G V x N. Afinite-memorystrategy of the Defender can be seen as positional on a fixed finite set of states, i.e., it forms a discrete-time Markov chain on V x N. To prevent the state space blow up, different amounts of memory can be allocated to each location. Hence, we define the memory assignment as a function mem: V —> N and a set of Defender's states C = {(v, i) \v eV,l • [0,1] where J2yec a (x -> V) = 1 f°r each x G C and that u —>• v whenever a((u, i), (v,j)) > 0. Intuitively, if the Defender is currently on a location u with memory value i, the next state (v,j) is chosen with probability a((u,i), (v,j)) which means that the Defender changes the memory value to j and starts traversing from u to v. The second condition ensures that the strategy respects the topology of the terrain. For every finite sequence of states h = (ci,...,cn ), we use PCT 'c [/i] to denote the probability of executing h when the Defender starts patrolling in the state c G C and follows the strategy a. That is, P°"'c [/i] = 0 if c\ ^ c, and PCT 'c [/i] = Y\?=o a (.c i> otherwise. 1.3 Attacker's Strategy In the patrolling graph, the time is spent traversing the edges. In adversarial models, the Attacker is assumed to perfectly observe the Defender's moves and can determine the next edge taken by the Defender immediately after its departure. For the Attacker, this is the best moment to attack because delaying the attack could only lower the attack's gain. Furthermore, the Attacker is allowed to attack only once in a single run. An observation is a sequence of states o = (ci, • • • , cn , cn + i). Intuitively, ci is the initial state of the Defender, cn is the current state of the Defender, and c n + i is the state chosen as the next one according to the Defender's strategy. The set of all observations is denoted by £1. Formally, an Attacker's strategy is a function TT: Q —>• T U {wait}. Since the Attacker is allowed to attack only once, it is required that if 7r(o) G T, then TT(O') = wait for every prefix d of o. 1.4 Protection Value Let a be a finite-memory Defender's strategy and IT an Attacker's strategy. Let us fix an initial state c where the Defender starts patrolling. The G expected damage the Attacker causes by attacking r after observing o is denoted as V(O,T \ a). The expected damage caused by the Attacker is defined as Val(a, c, TT) = J2 pCT 'C [°] -V(o,ir(o) \ a). (1.2) oeO,7r(o)eT The Defender/Attacker aims to minimize/maximize the damage, and hence we define Val(cr) = min Val(cr, c) = min sup Val(cr, c, TT) . (1-3) By Val(G), we denote the limit value of the best Defender's strategy or formally Val(G) = infCT Val(c). 1.5 Requirements on the Patrolling Model For our algorithm, we require two properties of the underlying patrolling model. Given a state space C, we require that for every e G C x C and T £ T the value T>(e, r | a) can be effectively calculated, and that V(e, r | a) is a differentiable function with respect to a whose gradient can also be evaluated. Let a be a Defender's strategy and let BSCC(a) denote all subsets of states corresponding to bottom strongly connected components of the Markov chain determined by a. For every B G BSCC(a), let us denote by Val(cr | B) the value max P(e, r I a). T<=T,e£BxB,a(e)>0 Our second requirement is that Val(cr) can be expressed as Val(a) = min Val(a I B). (1.4) BGBSCC(a) Note that if a is irreducible, then Val(a) = Val(a | C). 1.6 Target Types We will now present examples of defining the value V(e, r | a) that were shown to fit our general framework. 1.6.1 Hard-constrained targets One way of defining the damage on targets is to model a scenario where the Attacker needs to perform some actions (e.g. picking a lock) to successfully 7 complete an attack. If the target is visited in time, the Defender 'catches' the Attacker, and the damage is zero. Otherwise, the Attacker 'steals' the cost of the target. Here, d{r) denotes the time it takes to complete an attack on r and OL {T) its cost. The value V(O,T \ a) is then defined as the probability that the Defender does not visit r in the next d{r) time units multiplied by a{r). We call this type of target hard-constrained. Within the context of finite­memory strategies, this model was first introduced by David Klaška and Antonín Kučera and Tomáš Lamser and Vojtěch Řehák [14] and later used in [15, 16]. 1.6.2 Blind targets The hard­constrained model can be extended by introducing a level of uncertainty where the ongoing attack is discovered only with probability j3{r) upon each visit of the target. We call these targets blinded and appear in [15, 16]. 1.6.3 Linear targets Another target type models a situation where the actual damage depends on the time elapsed since initiating the attack till the Defender's visit, e.g., a fire or punching a hole in a fuel tank. Here, the target r is assigned a value V(T), which denotes the damage caused for every time unit while the target is under attack. Hence, the expected damage V(o, r | a) equals the expected time it takes to visit r multiplied by V(T). If the probability of visiting r after o is zero, then V(o, r | a) = oo. We call this type of targets linear. It was introduced in [17]. 1.7 Sufficient Condition for Second Requirement The proofs that hard­constrained, blinded, and linear targets are eligible for our general framework are provided in the works where they were presented. In general, it can be seen that a sufficient condition for (1.4) is that the damage on targets depends only on the current state and the future. That is, for every observation o = (ci,..., cn , c n + i ) and target r it holds V(O,T | a) = V((cn,cN+1),T I a) . (1.5) We offer a proof sketch to show that this argument can be made in general. Proof. Recall that we want to prove that for every strategy a on a set of states C it holds mmin sup > P C T ' c [ o l -T>(o, 7r(o) I a) = min max V(e,r I a) . r ' ­ 4 i BeBSCC(a) T€T e&BxB n ° ) 6 T 0 8 For the purposes of the proof, let us denote by M the right-hand side of the equation, i.e., M = mmB£BSSC(a) Val(cr | B). Also recall that the left-hand side is Val(cr) = minc Val(cr, c) = sup„. Val(<7, c, TT). We will first show that Val(a) < M. It is sufficient to show that there is a state c G C, such that Val(cr, c) < M. Let us choose any B G BSCC(a) such that Val(cr | B) = M and c as any state in B. Now we aim to show that Val(cr, c, TT) < Val(a | B) for every Attacker's strategy TT. Let TT be any strategy of the Attacker. Using (1.5) we can write Val(a,c,7r) = £ •V((cn,cn+i)Mo) I 0. Namely (cn ,cn + i) 0. From that it follows V((cn, cn + i), 7r(o) | cr) < Val(cr | S) for all observations with positive probability. Using this, we can write Val(a, c, TT) < J2 p f 7 ' C H •V a l ( C T IB ) = V a l ( ^ IB ) J2 p C T ' C H • ?r(o)eT 7r(o)eT The desired inequality follows from the fact that the sum of probabilities of the observations where the Attacker attacks is at most 1. Formally, it is true that E p C T ' c H < i , ?r(o)eT which follows from the fact that the Attacker is allowed to attack only once in a run. For the second inequality Val(cr) > M , it is sufficient to show that there is a strategy of the Attacker ir such that Val(cr, c, TT) > M for every c G C. We now show how to construct such a strategy. For every bottom strongly connected component B, choose any TB G T and e# G B x B such that Val(cr | B) = V(eB,TB \ cr) and cr(es) > 0. Now, fix an observation (ci,..., cn , cn_|_i). Let i be the smallest index such that (Q, Cj+i) is equal to some e#. If no index has this property or i < n, then the Attacker waits. Otherwise (cn , c n + i ) is equal to a unique e# and the Attacker attacks TBLet c G C be a state where the Defender starts patrolling. The proof builds on two basic properties of discrete-time Markov chains. No matter the starting state, the Defender will eventually visit some bottom strongly connected component B. Here, the Defender will eventually visit e# with 9 probability 1 and the Attacker attacks TB- Since M is chosen as the minimum over Val(cr | B), no matter which bottom strongly connected the Defender visits, the Attacker will achieve value at least M, which concludes the proof. 1.8 Strategy Types Here, we define positional and deterministic strategies as subtypes of finitememory strategies. Let a be a finite-memory strategy on a set of states C. If there is at most one state for every location in the graph, then we say that a is positional or memoryless. If for every state x there is a state y such that a(x,y) = 1, then we say that a is deterministic. Note that a can be both memoryless and deterministic. Finally, we demonstrate how to transform a deterministic strategy represented by a finite cycle of locations into a finite-memory strategy. Given a finite cycle of vertices vo,... ,vn where every (vi, Vj+i) £ E and VQ = vn, we can construct a deterministic finite-memory strategy a with the set of states C = {(vi, i) | 0 < i < n} and cr((u, i), (v,j)) = 1 if j = (i + 1) mod n and 0 otherwise. 10 Chapter 2 The Problem of Memory Assignment This chapter provides motivation for solving the problem automatically and iteratively, as we do in our method. Recall that the two main approaches to memory assignment: 1. Trying uniform memory of various sizes: 2. Using expertly hand-crafted memory assignment. The issue with uniform memory is that there is no way to tell for which value of the memory the tool will output the best strategy. Theoretically, having a higher memory cannot be worse than having a lower memory. While that is true in theory, the complete opposite oftentimes happens in practice. The main issue is that the time of optimization increases radically in the number of states. This unpredictability makes it completely unusable for online use. We verify these claims experimentally in Chapter 4. The issue with hand-crafting memory assignments is that they require deep expert knowledge. Moreover, it is hard to find general bounds or guidelines. This is because the optimal memory assignment may differ substantially even on the same underlying patrolling graph, just by changing the properties of the targets. In this chapter, we show exactly that: different optimal strategies requiring different memory assignments on a single topology. We demonstrate that some easy properties of the graph (e.g. degree) do not bound the memory needed. Finally, both of these approaches may practically fail because the memory needed for the optimal strategy is too high. In that case, even though the tool would use the optimal memory assignment, it would not find the optimal strategy in a reasonable time. That is why we also show that a small increase in memory may significantly improve the value of strategies over memoryless baselines. 11 For notation purposes, let Sk = (V, T, E, time) be a patrolling graph where (V, E) is an undirected star with k leaves. We denote the leaf locations v\,..., Vk and the internal location as M. All the leaf locations are targets, and the internal location is a non-target. All edges have the same unit length. Formally, V = {v1}..., vk, M}, E = {(M, Vi), (vi} M) | 1 < i < k}, T = V \ {M}, and timeie) = 1 for every e £ E. 2.1 Deterministic Strategies We start with instances where the optimal policy for the Defender is to cycle around the graph. We show that changing the properties of the targets can affect the best deterministic strategy and its memory, even on a single topology. Consider S3 where all targets are hard-constrained with unit cost. Suppose first that all targets have an attack length greater or equal to 6. Observe that a deterministic strategy o\ represented by a cycle v\ —>• M —> V2 —> M —> V3 —> M —>• v\ has a length equal to 6. Therefore, from every point, any location is visited in 6 steps. The graph is fully covered, and the Attacker steals nothing, i.e., Val(o'i) = 0. This strategy cannot be realized as memoryless since the Defender's steps differ at M depending on the history. Having just three states at M is sufficient to remember which target to visit in the next step. In the leaf locations, there is no need to remember anything since they are visited only once during the cycle. Hence, o~\ needs 3 states for M and 1 for all the targets. Now suppose that d(v\) = 4 and d{vi) = d(vs) = 8. The strategy cr\ is no longer optimal. In fact, the strategy o\ achieves the worst possible protection since a successful attack is always possible. To see this, note that as the Defender leaves v\ and goes to M, the Attacker can initiate the attack on v\ and has guaranteed that the Defender visits V2 and V3 before returning to v\. This happens in exactly 6 steps, but by then, the Attacker has already finished the Attack since d{v\) = 4. Formally, we state that V((Vl,M),Vl ICTI)= 1. To achieve optimal protection, the Defender must return to v\ after every visit of one of the other targets. Hence, the optimal strategy 02 performs a cycle v\ —>• M —>• V2 —> M —>• v\ —>• M —>• V3 —>• M —>• v\. Moreover, V2 and V3 are also fully protected since they are visited once on a cycle of length 8. For 02, the Defender needs to know in v\ whether to go to V2 or V3 after M. On the other hand, there is no need to remember anything in V2 or V3. Finally, in M the Defender needs 4 states for each direction. Hence 02 needs 2 states in vi, 4 states in M and 1 in both V2 and V3. To better see this, observe that in the cycle of 02, there are 2 occurrences of v\ and 4 occurrences of M. This is because the subsequent steps differ for each of the 12 (a) ^(^2) = 6 d{v^) = 6 optimal deterministic strategy 01 (b) ^(^2) = 8 ^(^3) = 8 optimal deterministic strategy 02 Figure 2.1: The optimal deterministic strategies require different memory allocations, which may exceed the degree of the vertices. The goal is to patrol a graph (a) with three targets and an internal location M. The targets are hard-constrained, with attack lengths set to 6. The optimal strategy is to cycle around the graph since the cycle's length is 6. This is represented as 01, which requires 3 different states at M. In (b), the attack lengths are modified. The strategy 02 achieves perfect protection since v\ is always visited every 4 steps, and both vi and V3 are visited once on the cycle of length 8. Strategy 02 needs 4 states in M and 2 states in v\. occurrences. We could also write the cycle of 02 as v\ —>• M —>• V2 —>• M' —> v[ —> M" —>• V3 —>• M'" —> v\. Note that in both v\ and M , the number of states is higher than the degree of the location. Both settings and their respective optimal strategies are visualized in Figure 2.1. As we can see, there are cases in which a deterministic strategy is optimal and memory is needed. However, the Defender may need to return to vertices with smaller attack lengths. This can cause the optimal policies to be highly sophisticated and with a substantial increase in memory. 13 (a) ^(^2) = 3 ^(^3) = 3 optimal memoryless strategy 03 Figure 2.2: Example where the optimal strategy is memoryless. The goal is to patrol a graph (a) with 3 targets and internal location M. The targets are hard-constrained, with attack lengths equal to 3. Since the defender can visit only two targets in three steps, randomization is needed. The optimal strategy 04 is positional with uniform distribution in M. The value of 03 is the probability of not visiting a vertex from M, which is 2/3. 2.2 Memoryless Strategies Here, we show instances where all deterministic strategies fail to achieve optimal protection, and the optimal strategy may be represented as memo- ryless. We stay with S3 but change the attack lengths of the targets to 3. We claim that any deterministic strategy has value 1. Observe that as the Defender leaves a target Vi for M, the Defender visits only one of the targets in the next 3 steps. If the strategy is deterministic, the Attacker knows which target the Defender will visit and can initiate an inevitably successful attack on any of the other two targets. This implies that, regardless of history, the Defender needs to be able to visit every target from M in the next step. Clearly, the optimal distribution does not depend on the history. Hence, some positional strategy 03 suffices for optimality, and by symmetry, it is clear that the optimal distribution is uniform. See Figure (2.2) for visual representation. What is the value of 03 ? To assess the value, note that for each vi the probability of not visiting Vi from M in the next step is exactly 1 — 1/3 = 2/3. Since M is at most two steps from everywhere, the probability of not vising Vi from every edge e is at most 2/3. From that it follows that V(e,Vi J 03) < 2/3 for every edge and target Vi, and thus Val(a) < 2/3. Moreover, V((M,vi),vi | 03) = 2/3, which shows that Val(a) = 2/3. 2.3 Finite-memory Strategies We naturally follow with an example where both deterministic and memoryless strategies do not suffice for optimality, and the optimal value is achieved 14 (a) ^(^2) = 4 ^(^3) = 4 optimal finite-history strategy 04 Figure 2.3: Example where the optimal strategy requires remembering the history. The goal is to patrol a graph (a) with 3 targets and internal location M. The targets are hard-constrained, with attack lengths equal to 4. The optimal strategy 04 remembers the last target visited and in M chooses between the other two not visited last time. This achieves Val(0s) = 1/2, but the strategy needs 3 states in M. by a finite-memory strategy. We can stay with the same graph S3 but let us increase the attack length of all targets to 4. In this case, the attack lengths are still too small for a deterministic cycle, and hence, all deterministic strategies have a value of 1. Moreover, by symmetry, it is easy to see that the best memoryless strategy must be 03. Even though there was an increase in attack length, 03 also achieves value 2/3. This is because the expected damage of attacking v\ as the Defender moves from M to V2 is still 2/3. Can the Defender do better? Yes, if the Defender is able to remember the last target visited. In the middle location M, the strategy 04 remembers the last location visited (one of the targets), and the next target is chosen uniformly between the other two targets. It is also easy to verify that Val(04) = 1/2. This strategy then needs a special state in M for each of the targets since the subsequent steps differ. See Figure (2.3) to see how 0*4 is represented as a finite-memory strategy. 2.4 Suboptimal Memory Assignment In the following example, we demonstrate that even with suboptimal memory, the value of the best memoryless strategy can be significantly improved. Let us recall the graph £ 3 with d(vi) = 4, and d{v2) = ^(^3) = 8. The optimal deterministic strategy 02 requires mem(wi) > 2 and mem(M) > 4. We now demonstrate that with suboptimal memory mem'(M) = 3 and mem'(vi) = 1, we can still improve the value of the best positional strategy by more than 40 %. First, let us discuss the value of the best positional strategy 0%. By 15 (a) memoryless strategy o§ (b) finite-history strategy a-? best for p » 0.458 = Val(a6) best for p » 0.268 = Val(a7) Figure 2.4: The goal is to patrol a graph with 3 targets and internal location M . The targets are hard-constrained with d(v\) = 4 and d(v2) = d(v2) = 8. A deterministic strategy achieving Val = 0 needs four states in M and two in v\. The strategy with suboptimal memory (b) beats the memoryless strategy (a). symmetry, it is clear that cre(M, V2) = a§(M,vz) will hold. Let us denote by p the value cre(M, V2) + CTQ(M, V3). Hence cre(M, V2) = a§(M,vz) = | and a(M, v\) = 1 — p. The value of the best attack on v\ is the probability of not visiting v\ after M , which is p. The value of the best attack on V2 is the probability of not visiting V2 from M three times in a row, which is (1 — | ) 3 . By symmetry, the same is true for V3. The optimal strategy must have Val(cr6) = p = (1 — | ) 3 which holds for p 0.458. Now we consider a finite-memory strategy 07 on mem', which goes from vi deterministically to a state (M, 1), which decides uniformly between V2 and V3. From V2 the strategy goes to (M, 2). From there, 07 goes to V3 with probability p and to v\ with probability 1 — p. Analogically, in V3 the strategy goes to (M, 3) and there it decides between V2 with probability p and with probability 1 — p. It is easy to see that the best attacks on v\ have value p. For V2, the best moment to initiate the attack is when the Defender goes from (M, 1) to V3. To prevent the Defender from visiting V3 in the next 8 steps, the following steps must be M i —>• V3 —>• M 3 —>• v\ —>• M i —>• W3 —>• M 3 —>• v\. This happens with probability |(1 — p)2 . The optimal strategy must have Val(cr7) = p = |(1 — p)2 which holds for p « 0.268. The structure of both erg and (77 is drawn in Figure 2.4. As we can see, adding at least some memory may greatly decrease (here by more than 40 %) the value of the best positional strategy. 16 Chapter 3 The Method Here, we describe our method for solving the problem of choosing a suitable memory assignment. Our method works with any black-box optimization tool that improves the transitional probabilities and with any patrolling model that fits our general framework. Recall that the algorithms introduced in [15, 16, 17] are eligible instances of such black-boxes. The algorithm is initialized with the memory assignment menii that assigns 1 to each location. That is, we start with a memoryless strategy. Then, we run the optimization tool and collect the resulting strategy o\. From this, we run the core procedure ADJUSTMEMORYASSIGNMENT that outputs a new memory assignment m e n i 2 . The memory assignment m e n i 2 is then used for initialization for the tool, and we collect a new strategy 03. This process continues for as long as the strategy value improves. We also introduce a procedure EXPANDSTRATEGY that enables us to transform the resulting strategy a\ to an equivalent strategy 02 on m e n i 2 . The strategy 02 can then be used to warm-start the optimization process of the tool. Finally, we also provide a variant of the algorithm if the number of states of the resulting strategy is bounded. 3.1 Attacks Profiles Now, we describe the core procedure ADJUSTMEMORYASSIGNMENT of our algorithm that decides how much memory should be added to which location. Intuitively, the procedure estimates the number of different 'behaviors' of each state that, on their own, could improve the current value. Let us illustrate the idea in a simple example. Consider a patrolling graph depicted in Figure 3.1 with two targets A and B that are hardconstrained with d = 4 and a = 1. We start with mem = 1. The state space is C = {(A,1),(X,1),(B,1)}. For brevity, let us write v for (v, 1) since the memory value is constant. In this example, from the end loca- 17 (a) PB (b) positional strategy optimal for PA=PB = 1/2 PA optimal (c) finite-memory (L4 strategy Figure 3.1: Patrolling on a graph (a) with three locations. End locations represent targets with costs of 1 and attack lengths equal to 4. Positional strategies (b) are parametrized by a single variable p. Due to symmetry, the optimality is reached for p = 0.5. The optimal strategy (b) is deterministic and needs two states in X. tions, the Defender always returns to X, and hence the strategy depends only on complementary probabilities o~(X, A) and o~(X, B), which we denote by PA and PB, for short. The best moment to attack A is when the Defender starts traversing from X to B. Then the probability of not visiting A in d{A) = 4 time units is exactly ps and hence V((X,B), A \ a) = ps- Analogically, the best moment to attack B is when the Defender starts traversing from X to A and T>((X, A), B \ a) = PA- The value Val(cr) is then the maximum of both the attack values, i.e. Val(cr) = III&X{PA,PB} which is minimized when a(X, A) = a(X, B) = 0.5 with Val(a) = 0.5. We have reached the optimal value of positional strategies, and the question is whether the Defender can do better. The answer is positive since a finite deterministic strategy that moves from one end to the other, and back represents a cycle of length 4. Hence, every attack is discovered in time, achieving the optimal value 0. This strategy can be represented by a finitememory strategy on memory assignment menidet with menidet(A) = 2 and memdet(J4) = memd e t (B) = 1. In practice, a reasonable optimization tool should output a strategy close to a. Now, the key question is how to infer menidet from a. The idea is to consider gradients of all the maximal attacks w.r.t. the parameters of strategy a. Any strategy a can be modeled as Softmax of unconstrained parameters. In the case of our example, we need just two real parameters, say (XA,XB), SO that Using the chain rule, the partial derivatives of the maximal attacks w.r.t. Softmax(XA,XB) = (PA,PB)- 18 the parameters XA, XB are &D((X,B),A | a) dV((X,B),A \ a) = -PAPB and = PAPB OXA OXB and dV({X, A),B | a) 9V((X, A), B \ a) a = PAPB and = -PAPBOXA OXB We can see that the problem lies in the fact that for the attack on A, the gradient of the parameters is (up to a scale) (—1,1), while for the attack on B it is (1, —1), which is in the exact opposite direction. Hence, the value can no longer improve since the competing gradients 'cancel each other out'. This is exactly the place where we need to add a more memory value for X, one memory value to prioritize B (if the previous location was A) to cover the attack on B, and the second memory value to go to A (if the previous location was B) in order to cover the attack on A. Formally, we fix a set of eligible attacks £ C (C x C) x T, corresponding to the attacks with close to maximal value. For an attack (e, T) G £ and a state c G C, we consider the gradient of the attack value with respect to the outgoing probabilities of c V7 T V I ^ (&D(e,T\a) dV(e,r\a)\ VCTX>(e, T \ 0. Assuming that the strategy probabilities are parametrized by the Softmax of x(c) = (xi,... ,xn), the gradient of the attack value with respect to the strategy parameters is given by where J is the Jacobian of the Softmax. The attack profile of (e,r) and c is then the sign of this vector Vxrc\V(e,T \ a). We define profiles to be a function that assigns each state c the set of all (different) attack profiles belonging to c from £. Formally, profiles(c) = {sign(Vz(c)X>(e,T | a)) | (e,r) G £}. The new memory assignment m e n i 2 is then defined as meni2(ti) = ^ |profiles(u,i)|. (3-3) l(e,r | a)): Add profile to profiles(c); foreach u G V do mem'(ti) 0: foreach i G {1,..., mem(w)} do mem'(v) •(— mem'(v) + |profiles(u, i)|; return mem', profiles: Algorithm 1: Pseudocode of the core procedure of our method. The input is a current strategy a on memory assignment mem with a threshold e > 0 for the set of eligible attacks S. The result is the new memory assignment mem' and function profiles, which assigns each state the set of all its attack profiles. 3.2 Strategy Expansion In [15, 16, 17], the parameters of the strategy are randomly initialized at the start of the optimization. However, it is also possible to warm-start from parameters provided by the user. This may be useful because we add memory only to some locations. Hence, it is possible that in the new strategy, some of the locations where we did not add memory could have the same optimal probabilities. By warm-starting, we would preserve these probabilities, saving time in optimization. For that reason, we describe how to create a new strategy 02 from o\ given the profile function resulting from ADJUSTMEMORYASSIGNMENT. For notation purposes, let copies(c) = |profiles(c)|. The idea is to expand the strategy o\ such that every c has now exactly copies(c) copies of c that preserves the value of the strategy. If copies(c) = 1 for all but one state X which has copies(A) = 2, the procedure is simple. We create an identical copy X' of the state X. That is, we add a new state with the same outgoing probabilities as X. Then, every incoming edge to X gets halved between X and X'. In Figure 3.2, we show how this works on the positional strategy from Figure 3.1. In general, let C denote the new set of states induced by the new memory assignment m e n i 2 . For every state c G C, let c\,..., cc o p i e s (c ) denote the corresponding new states in C. Each Cj has the same distribution over C" 20 expanded strategy \V\ on the number of states for each (jj. Let the current memory assignment be menii and a. We run ADJUSTMEMORYASSIGNMENT and collect the resulting m e m 2 and attack profiles. If J2vmem 2(v ) ^ L, we simply output m e n i 2 . Otherwise, for each attack profile, we sum the total value of the attacks with the given profile. That is, for each state c and an attack profile 7 £ profile(c), we define the value of 7 as val(7,c)= v (e,r\a). (e,r)e£ Bign(VJ.(c)X»(e,T| ^~ -'2/5 1/5 Figure 3.3: Demonstration of strategy expansion. The original strategy a\ is memoryless. Locations a and b both get two copies, resulting in expanded strategy 02 • The outgoing probabilities from c and a to 6 are halved between the two 6s (from probability 1 to 1/2). The outgoing probability from b to a is halved between the two as (from 4/5 to 2/5 to each copy). must have a profile with an attack of maximal value. Then we flatten all the attack profiles into a single set V = UC {(7)C ) I 7 £ profiles'(c)}. After that, we take the L — \C\ highest items from V where the order is given first by val and secondly by the order on the states (if more profiles of the same state have the same value, the order does not matter). Let us denote by #(c) the number of occurrences of a state c among the L — \C\ maximal items of V. Finally, the new memory assignment m e m 2 is For strategy expansion, the value 1 + #(c) corresponds to copies(c). mem2(u) E 1+ #(«.*)• l 2k mem(vi) > k both (optimal) Size auto expand auto expand auto expand k = 1 100.0 100.0 100.0 100.0 100.0 100.0 k = 2 89.0 78.5 54.5 31.5 54.5 31.5 k = 3 90.5 87.0 75.0 38.5 75.0 38.5 k = 4 99.5 99.0 49.5 44.0 49.5 44.0 k = 5 100.0 97.5 42.5 39.5 42.5 39.5 Table 4.1: Percentage of runs where each method found the correct memory assignment for the special locations v\ and M, as well as for both simultaneously (optimal assignment). Finding the required memory for M is easier due to its central role in the strategy. The method performs better without strategy expansion, as expand preserves local minima, making it more difficult for the algorithm to escape suboptimal memory assignment. location M (for more, see Chapter 2). We show how our method helps the tool find the optimal deterministic strategies on Sk- We also explain where it fails and demonstrate some essential properties of our iterative approach. We slightly generalize the case on S3 where d(v\) = 4 and d{v2) = d(v3) = 8. The generalization is on a graph Sk+i, where d(v\) = 4 and d{vi) = 4k for 2 < i < k + 1. The defender needs to perform a cycle of length 4k of the form vi -> M -> v2 -> M -> vi ->• • • • ->• vi ->• M ->• Vk -> M ->• vi . This requires mem(wi) > k and mem(M) > 2k. The other targets need just one memory value. We ran the algorithm for k ranging from 1 to 5. 4.2.1 Finding the optimal memory assignment In Table 4.1, we report the percentage of runs in which each method found the memory needed for M, and similarly for v\. The last statistics show the percentage of runs when both conditions are met; in this case, we have the optimal memory assignment. For both auto and expand, finding the memory for the middle location M is much easier than for v\. This result is intuitive since there is 'more going on' in M. Also note that when mem(wi) > k, then also mem(M) > 2k. The results also show that our method is more successful in finding the optimal memory without strategy expansion. The reason for this is that as strategy expansion preserves the probabilities, it also preserves the local minima. Let us note that the setting from Figure 3.1 corresponds to S2 in this case. In Figure 3.2, we demonstrated the expansion of the best positional strategy. Suppose that, without any changes to the expanded 25 Size opti opt2 opt4 opt5 auto expand k = 1 100.0 100.0 100.0 100.0 100.0 100.0 100.0 k = 2 56.0 98.0 100.0 100.0 100.0 53.5 31.5 k = 3 13.5 66.5 88.0 97.0 99.5 75.0 38.5 k = 4 0.0 1.5 6.0 6.0 2.0 0.0 2.0 k = 5 0.0 0.0 0.0 0.0 0.0 0.0 0.0 Table 4.2: Percentage of runs with Val = 0 for different memory assignments, optj assigns i multiple of the minimal optimal memory needed. Our method is more successful without strategy expansion. Adding excess memory increases the probability of finding the global optimum, but up to the limits of the current tools. strategy, we run ADJUSTMEMORYASSIGNMENT again. Recall that X has two profiles in the original strategy, resulting in two new copies of X in the expanded strategy. Observe that if we do not change the strategy, then both new Xs will also have two copies, the same as X in the original strategy. Moreover, the number of profiles for A and B also stays 1. This may be surprising since there are two outgoing edges from A and B. However, they lead to identical states w.r.t. probabilities over locations in all steps. Hence, A and B still have only one profile. The problem for k > 1 is that even after changing the memory and starting a new epoch, the strategy stays at the same local minimum throughout the whole epoch. New memory is not added since the value is not improving, and the run eventually terminates. The opposite question can be raised: why should it work? That is due to the optimizer and noise, which are reset when starting a new epoch. 4.2.2 Finding the optimal strategy In Table 4.2, we report the percentage of runs where the optimal strategy with Val = 0 was found. We report five baselines optj which denote a constant memory assignment with mem(wi) = ik, mem(M) = ik and mem(vj) = i. Simply put, we assign i multiple of the minimal memory needed to find the optimal strategy. Let us focus first on the columns with optj. Here, the results are intuitive. The optimal deterministic strategy gets increasingly complex and, hence, harder to find. As noted in [15, 14], adding excess memory increases the chances of finding the global minima. However, the tool finds the optimal strategy very rarely for k = 4 and never for k = 5. For our method without strategy expansion, the results are a bit weird. Finding it for k = 1 is trivial; for k = 2, it performs slightly worse than opti, and then it is way more successful for k = 3. For the case with strategy 26 expansion, the algorithm performs the worst on k = 2 but better than opti for k = 3. It finds the optimal strategy 4 times for k = 4 and naturally fails for k = 5. Note that for k = 2 and 3, the numbers are almost exactly equal to the percentage of runs in which the methods find the optimal memory assignment. This is counterintuitive because it implies that if we found the optimal memory, we also found the optimal strategy. The main reason for this is that in both auto methods, if we find the optimal memory assignment, we typically find more than necessary, and the effect is similar to that with opt5. Another reason is that both versions of our method allow more 'tries' to find global minima. In the case without expansion, if we find sufficient memory but not the optimal strategy while still improving the value at least somewhat, we add even more memory and start a new epoch. This explain why there is 75% in the case for k = 3, but only 53.5% for k = 2. In the smaller graph, the tool is much more likely to find the absolutely best strategy on the smaller memory (o~6 in Section 2.4), which is a strong local minimum in the state space of higher memory. Hence, the problem is that if the tool converges to this minimum with more memory, it is unlikely to improve the value and terminate the run. In the larger graph, converging to the local minima is harder. If the algorithm converges to the same local minima in the larger state space, the value can still be improved by the threshold and get another chance to find the global optimum. With strategy expansion, the situation is somewhat different. By inspecting the values through the runs, we observe an interesting phenomenon where the value stagnates and suddenly drifts away to the global minimum. We observed this with constant memory assignment and on different graphs as well. In the runs with strategy expansion, we give this phenomenon more steps to appear. There are 20 steps of patience before the plateau; then, we expand the strategy, and a new epoch begins. Then, even if the value improves below the threshold and another begins, we are still virtually around the same local minima, albeit in bigger state space. This gives us at least 500 additional steps before terminating the run. Since the graph is small, they are executed before timeout. 4.2.3 Summary These toy examples show some important features of how our method works with the tools. Namely: • Our method significantly helps find the global minima: • Our method without strategy expansion is more probable to find extreme values: 27 Figure 4.1: A building with three floors. The goal is to patrol offices (squares). The corridors (circles) connect the offices on the same floor. The floors are connected by staircases, which take 10 units of time to traverse. The traversal time between corridors is 2, and the time between offices and corridors is 5, as it involves opening the door and searching the office. • Strategy expansion can preserve the local minima. Because of the complexity of the setting, the features are amplified. We look for a highly complex deterministic strategy in a very tight setting. However, this gives us a good intuition about the heuristics, and in the benchmarks that follow, we can explain the results in light of this. 4.3 Patrolling Offices We move to a benchmark introduced in [15] that also appeared in [16]. The goal is to patrol offices in an office building. For completeness, we recall the topology in Figure 4.1. So far, this benchmark has been used to compare the quality of the tools optimizing the transition probabilities. We now explore how our automatic method enhances the quality and usability of a fixed tool. Here, all the targets (offices) are hard-constrained, with an attack length precisely equal to the shortest cycle visiting the entire building. The offices 28 Floor Memory 1 2 3 Floor Memory 1 2 3 m = 1 m = 2 m = 3 m = 4 m = 5 m = 6 m = 7 m = 8 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 78.5 0.0 0.0 87.0 0.0 0.0 88.5 0.0 0.0 85.0 0.0 0.0 87.0 0.0 0.0 m = 1 m = 2 m = 3 m = 4 m = 5 m = 6 m = 7 m = 8 1.00 1.00 1.00 0.75 0.73 0.82 0.64 0.72 0.81 0.00 0.73 0.90 0.00 0.75 1.00 0.00 0.77 1.06 0.00 0.82 1.13 0.00 0.87 1.17 auto expand 14.0 7.0 0.0 3.5 0.0 0.0 auto 0.00 0.00 0.81 expand 0.00 0.72 0.78 (a) % of runs with Val = 0 (b) min Val found (normalized) Table 4.3: Percentage of runs that reached Val = 0 (a), and minimal Val found for each building (b), normalized by minimal Val for m = 1. Both our auto and expand methods find the optimal strategy for 1-floor, and only auto finds it for 2-floor. Our methods achieve the best minimal values on all floors. have equal value. The building is parametrized by the number of floors, and each floor has 4 corridors that join the offices. For short, we use n-floor to denote a building with n floors. Uniform memory assignment is used where every location is given m memory values and m ranges from 1 to 8. We ran the experiments for buildings with one, two, and three floors. In the original paper of [15], only a 1-floor building is evaluated. We report the percentage of runs that reached Val = 0 in Table 4.3 (a). In Table 4.3 (b), we report the minimal value found, normalized by the minimal value for m = 1. Below, we discuss the results for each number of floors separately. 4.3.1 One floor The results for 1-floor are intuitive. With sufficient memory (m > 4), the strategy is found in at least 75 % of the runs, and it gets more probable with excess memory. Suboptimal memory m £ {2,3} helps improve the baseline value of memoryless strategies. Our auto method is more successful without strategy expansion, precisely in 14% of runs. Because it is a still rather smaller graph, it is easier to converge close to some local minima, and here, the expansion has a harder time drifting from it. Nevertheless, it is successful in 3.5 % of the runs. 29 Memory 15s 30s 45s 90s 180s m = 4 0.0 43.0 78.0 78.5 78.5 m = 5 0.0 3.5 59.5 87.0 87.0 m = 6 0.0 0.0 0.5 84.0 88.5 m = 7 0.0 0.0 0.0 40.0 85.0 m = 8 0.0 0.0 0.0 4.0 87.0 auto 14.0 14.0 14.0 14.0 14.0 expand 0.5 0.5 0.5 0.5 3.5 Table 4.4: Percentage of runs where Val = 0 after 15, 30, 45, 90, and 180 (timeout) seconds. Our auto is the fastest to find the optimal strategy. With more memory, the probability of finding the target value is higher, but at a significant cost of time. An advantage of our approach is the time in which we can find the optimal strategy. Recall that we had a timeout of 180 seconds on each run. We also save the value of the best strategy found after 15, 30, 45, and 90 seconds. This corresponds to 1/12,1/6,1/4, and 1/2 of the total time. In Table 4.4, we report the percentage of runs with value 0 after given seconds. This demonstrates the problem of adding excess memory. The most probable memory method was uniform m = 6, which found the best strategy in 88.5 % of the runs. However, under 45 seconds, the optimal strategy was found in only one run. More extremely, m = 4 and m = 8 both found the target strategy 87% times. After 90 seconds, the percentages are 87% for m = 4 and 4% for m = 8. That can make a huge difference for online use if time is precious. On the other hand, our auto method finds all 28 instances under 15 seconds. Note that none of the uniforms found the target strategy under 15 seconds. With strategy expansion, one run has optimal value under 15 seconds, and all the other 6 converge only after 90 seconds. This also shows the sudden escape from the local minima, which is very rare in practice. In Figure 4.2, we plot the distribution of values for each of the memory methods, normalized by the value of the best memoryless strategy. Observe that with our methods, most values stay at the value of local minima for m = 3. 4.3.2 Two floors For two floors, the results are more interesting. All uniform memory assignments fail to find the optimal deterministic strategy. This is actually impossible for m < 5 but does not happen for sufficient uniform memory assignments. Our auto method finds the optimal strategy in 7% of the 30 Value (normalized) 0.8 - - - I - - — - 0.6 - 0.4n 9 - 1 W ft*0.6 - 0.4n 9 ft*. • • ,1 *M I 1 0.6 - 0.4n 9 - • 0.0 - _ u u LT 1 1 1 1 1 1 1 1 r 1 2 3 4 5 6 7 8 auto expand Figure 4.2: Value of strategies for 1-floor building on uniform memory assignment (blue) and our automatic memory method (red). The values are normed by the value of the best memoryless strategy found. Red values perform better than m < 4 and reach the optimal value 0. runs (14 total). This is mostly due to the fact that we do specific memory distribution. Depending on the cycle, each corridor needs between 3 and 6 memory values, while 1 suffices for the offices. Uniform memory assignment overshoots the memory in places where it is not needed, increasing the state space and optimization time. On two floors, the minimal values are more interesting since they show that the best values among uniform memory distributions were found for 1 < m < 4; for m more than 4, the values get worse with increasing m. Here, strategy expansion matches the performance of uniform memory dis- tributions. In Figure 4.3, we plot the values of all runs. We can see that the best result for uniforms is m = 3. For higher m, the values get closer to memoryless baselines. For some runs with m = 7 and 8, the normed value is above 1. Our method with expansion has low variance and achieves values similar to m = 3. 4.3.3 Three floors For three floors, the target optimal strategy is simply too complex and big for the current state of the tool. The results for the best strategy found 31 Value (normalized) 0.6 - 0.8 - 1.0 0.4- 0.2 - 0.0 - 1 2 4 5 6 7 8 auto expand Figure 4.3: Value of strategies for 2-floor building on uniform memory assignment (blue) and our automatic memory method (red). The values are normed by the value of the best memoryless strategy found. Our auto method achieves the optimal value 0 as the only memory method. Values of expand are tightly distributed around the minima for m = 3. showcase the robustness of our approach. For m > 5, the tools perform worse than for m = 1. For m = 5, it synthesizes a strategy with equal value as with m = 1. For m < 5, the values are better than the baseline, best for m = 3 with a strategy that makes 19% improvement over m = 1. This is matched by our auto method and outperformed with expansion that finds a strategy making 22% improvement over m = 1. Here, we see the full effect of strategy expansion that can transition smoothly to the new state space. We can see the blow-up of excess memory in Figure 4.4. Observe also the low variance of expand. 4.3.4 Summary The results of these experiments show that uniform assignments are unusable for online use. There is no way to tell for which m the tool will output the best result. This choice heavily depends on the size of the graph and the overall time the user is willing to wait. Our automatic methods achieve consistently good values, while expand achieves particularly stable values. Our methods also show the potential for offline use. The absolutely best value was found by auto for 2-floor and by expand for 3-floor. Moreover, 32 Value (normalized) ~i 1 1 1 1 1 1 1 1 1 — 1 2 3 4 5 6 7 8 auto expand Figure 4.4: Value of strategies for 3-floor building on uniform memory assignment (blue) and our automatic memory method (red). The values are normed by the value of the best memoryless strategy found. Our expand method finds the best strategy and has the smallest variance. Our auto method achieves the same minimum as m = 3. For m > 5, the values are above the memoryless baseline. auto matched the performance of uniforms on the 3-floor, and similarly expand matched uniforms on the 2-floor. 4.4 Patrolling Blinded Offices We continue with the second benchmark on the office building topology, in which the targets are blinded. This setting comes from [15]. The probability of discovering an ongoing attack upon each visit is 0.9. For buildings with n floors, the attack lengths of all targets are equal to lOOn. This is less than what is needed for the deterministic cycle, and the ratio to this length gets smaller with increasing n. The memory assignments are uniform, with m ranging from 1 to 8. We run the benchmark for buildings with one to eight floors. In [15], it is run only for buildings with up to three floors. With more floors and higher m, we got memory issues during the computation. So for all m, we have full data only for buildings with up to 5 floors. 33 Floor Memory 1 2 3 4 5 6 7 8 m = 2 0.80 0.81 0.89 0.90 0.95 0.99 1.02 1.10 m = 3 0.75 0.66 0.86 0.94 1.00 1.05 1.13 1.11 m = 4 0.62 0.59 0.88 1.00 1.08 1.13 1.17 1.19 m = 5 0.73 0.60 0.94 1.04 1.13 1.17 - m = 6 0.65 0.62 1.00 1.10 1.14 1.19 - m = 7 0.73 0.71 1.04 1.13 1.18 - - m = 8 0.73 0.77 1.05 1.16 1.20 - - auto 0.74 0.61 0.80 1.00 1.00 1.00 1.00 0.99 expand 0.74 0.61 0.86 0.99 1.00 1.00 1.00 1.00 Table 4.5: Value of the best strategy found for uniform memory assignments m = 1,..., 8 our auto method, and auto with with strategy expansion expand. The values are reported for a blinded building with 1 to 8 floors. For bigger buildings and higher m, the experiments did not run. Our methods never perform worse than m = 1, achieving good values for smaller buildings. Our auto method found the absolutely best strategy on a 3-floor building. 4.4.1 Results In Table 4.5, we report for each n-floor building and memory method value of the best strategy found. For n < 3, the best result is for m = 4. In these two cases, our method achieves the same minimum with and without strategy expansion. The minimal values are 12 and 2 percentage points worse for the building with 1 and 2 floors. For n = 3, our method without expansion achieves the best value, improving the value of the memoryless strategy by 20%. For 3 < n < 6, the best strategies are found for m = 2, while our method performs the same as m = 1. For n > 6, our values match the memoryless strategies, while every m > 1 performs even worse than m = 1. In Figure 4.5, we show aggregated results of the experiments for building with 1 to 5 floors. With three colors, we distinguish the buildings based on which method found the best strategy. Here, our methods achieve similar results with and without warm-starting. The main difference is that auto found better values for smaller buildings with up to 2 floors. As in the previous, we can observe the robustness and consistency of our approach. For m < 4, the green values (1, 2) do not reach 0.6. For m > 4, the orange values (4) do not reach 0.9. Uniform memory m = 4 achieves poor results with blue values (3, 5) and even worse for n > 6. 34 Value (normalized) 1,2-floor 4-floor 3,5-floor 1 2 3 4 5 6 7 8 auto expand Figure 4.5: Value of strategies on uniform memory assignment and our automatic memory method. The results are aggregated for buildings with one to five floors. The values are normed by the value of the best memoryless strategy found for each building. Our approach works consistently well across the datasets. 4.5 Patrolling Airports We move to evaluating our method on a model with linear targets. This model has so far been studied only in [17], where the authors use the following benchmark. The goal is to patrol gates at an airport. The airport consists of three terminals and n halls. Each hall is connected to two gates, and the airport forms a tree. For completeness, we recall the topology in Figure 4.6. As a baseline, the authors use a strategy that cycles around the graph, visiting each target once on the cycle. The value of such a strategy is then the length of this cycle (3n + 1 for the airport with n halls) multiplied by the maximal value of gates. The authors use the memory of the baseline strategy to run the optimization tool. We denote this memory assignment as degree, as for each location, the memory is its degree in the graph. To demonstrate the need for memory, we also report results with memoryless assignment m = 1. In the setting used by the authors, all gates have the same unit value. In that case, it is experimentally verified that the optimal strategy is actually the deterministic baseline. Following the authors, we generate 10 different 35 Figure 4.6: A patrolling graph for an airport with 3 terminals. All edges have the same unit length. An airport with n halls, has 3n + 1 locations in total. airports, where the number of halls is a sequence 3,4,5,7,9,12,15,19,25,30. We evaluated the methods in two different target settings. One with the uniform values of gates and the second where each value is randomly independently drawn from interval [1,10]. 4.5.1 Uniform values of gates We report aggregated statistics in Table 4.6. By G 15. 4.5.2 Random values of gates For the setting with random values of gates, the results are reported in Table 4.7. The baseline is identical as in the previous section. However, this 36 Memory Median Ql Q3 Avg ± Std G 15 Figure 4.7: Value of strategies for constant assignment (blue) and our automatic methods (red) on the airport benchmark. The results are aggregated into two groups (a) and (b). The values are normalized by the baseline value. Memory is needed, and positional strategies (m = 1) achieve poor results. Our methods outperform constant memory assignments on (a), but performs worse than degree on (b) because of slow convergence on larger graphs. unbounded. We suppose that improving the convergence of the tool would further improve its overall performance when used in conjunction with our methods. 4.6 Patrolling Large Terrains One use of patrolling games is in guarding large terrains (see Related Work). Large terrains can be modeled as connected planar graphs, where each vertex represents a physical position in the terrain, and the length of edges is the time it takes to move between any two positions. We compared the methods on a dataset of randomly generated connected planar graphs. The construction for a graph on n targets is as follows: 1. Generate n points uniformly in a unit 2D-box. 2. Find the Delaunay triangulation D. 38 Value (normalized) Value (normalized) 0.50 -1 1 1 1 1 1 1 1 1 1 m = 1 degree auto expand m = 1 degree auto expand (a) values for n < 15 (b) values for n > 15 Figure 4.8: Value of strategies for constant assignment (blue) and our automatic methods (red) on the airport experiment with random values of gates. The results are aggregated into two groups (a) and (b). The values are normalized by the baseline value. Memory is needed, and positional strategies (m = 1) achieve poor results. The methods with memory achieve similar results in (a), and our automated methods slightly underperform in (b). 3. Find a minimum spanning tree T of D where the length of edges is the Euclidean distance between the endpoints. 4. Add each edge from D to T with probability 1/2. 5. Assign value to each target independently and uniformly from [1,10]. We generated 20 different graph for n ranging from 3 to 41 by steps of 2. For each graph, we ran the two versions of our method, memoryless assignment m = 1, and assignment degree. As with the previous experiments on airports, we choose the strategy that cycles around the graph in the shortest possible time as a baseline. Here, we use an approximate solution to the Traveling salesman problem. For more details on graph generation and the baseline, see the appended code. 39 Memory Median Ql Q3 Avg ± Std G 3. On the other hand, degree is the best performing on airports but here fails for larger graphs. Because of smart memory distribution, our method achieves very good and consistent values in all three experiments with linear targets. 40 Value (normalized) Value (normalized) m = 1 degree auto expand m = 1 degree auto expand (a) values for n < 27 (b) values for n > 27 Figure 4.9: Value of strategies for constant assignment (blue) and our automatic methods (red) on the dataset with planar graphs. The results are aggregated for n < 27 in (a) and for n > 27 in (b). The values are normalized by baseline. In (a), the methods are comparable; m = 1 has some high values because the graph for n = 3 requires memory. In (b), degree achieves bad results because it adds excess memory. 41 Chapter 5 Conclusion In this work, we have introduced a heuristic technique for finding appropriate memory assignments to locations in patrolling games, done in an iterative manner. With our experiments, we have again shown the power of finitememory strategies. However, so far, their practicality has been extremely hindered by the fact that one cannot simply run the tool with excess memory. This blowup in state space causes the tools to find suboptimal strategies with oftentimes poor results. An automatic and robust memory assignment tool was a missing part of up-to-date promising strategy synthesis techniques. Our tool enables the users and experts to fully utilize the power of the synthesis tools. On the one hand, we can push the tool to find complex strategies requiring memory. On the other hand, we keep memory low if it is not needed, enabling the tool to converge to a high-quality strategy. We present our idea in a general way so that it can be applied similarly to other patrolling-type problems with different solution techniques. 42 Bibliography [1] Yevgeniy Vorobeychik, Bo An, and Milind Tambe. "Adversarial patrolling games". In: International Conference on Autonomous Agents and Multiagent Systems, A AM AS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes). Ed. by Wiebe van der Hoek et al. IFAAMAS, 2012, pp. 1307-1308. URL: http://dl.acm.org/citation.cfm?id=2343977. [2] Noa Agmon, Sarit Kraus, and Gal A. Kaminka. "Multi-robot perimeter patrol in adversarial settings". In: 2008 IEEE International Conference on Robotics and Automation, ICRA 2008, May 19-23, 2008, Pasadena, California, USA. IEEE, 2008, pp. 2339-2345. DOl: 10.1109/R0B0T. 2008.4543563. URL: https://doi.org/10.1109/R0B0T.2008.4543563. [3] Noa Agmon et al. "Adversarial Uncertainty in Multi-Robot Patrol". In: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-11, 2009. Ed. by Craig Boutilier. 2009, pp. 1811-1817. URL: http://ijcai.org/Proceedings/09/Papers/301.pdf. [4] Nicola Basilico, Nicola Gatti, and Francesco Amigoni. "Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder". In: Artif. Intell. 184-185 (2012), pp. 78-123. DOl: 10.1016/J.ARTINT.2012.03.003. URL: https://doi.org/10.1016/j.artint.2012.03.003. [5] Nicola Basilico, Nicola Gatti, and Francesco Amigoni. "Leader-follower strategies for robotic patrolling in environments with arbitrary topologies". In: 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, May 10-15, 2009, Volume 1. Ed. by Carles Sierra et al. IFAAMAS, 2009, pp. 57-64. URL: https://dl.acm.org/citation.cfm?id=1558020. [6] Enrique Munoz de Cote et al. "Introducing alarms in adversarial patrolling games: extended abstract". In: International conference on Autonomous Agents and Multi-Agent Systems, AAMAS '13, Saint 43 Paul, MN, USA, May 6-10, 2013. Ed. by Maria L. G ini et al. IFAAMAS, 2013, pp. 1275­1276. URL: http://dl.acm.org/citation.cfm?id=2485180. Efrat Sless, Noa Agmon, and Sarit Kraus. "Multi­robot adversarial patrolling: Handling sequential attacks". In: Artif. Intell. 274 (2019), pp. 1­25. DOl: 10.1016/J.ARTINT.2019.02.004. URL: https://doi.org/10.1016/j.artint.2019.02.004. Hsi­Ming Ho and Joel Ouaknine. "The Cyclic­Routing UAV Problem is PSPACE­Complete". In: Foundations of Software Science and Computation Structures - 18th International Conference, FoSSaCS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, L ondon, UK, April 11-18, 2015. Proceedings. Ed. by Andrew M. Pitts. Vol. 9034. Lecture Notes in Computer Science. Springer, 2015, pp. 328­342. DOI: 10.1007/978­3­662­46678­0\_21. URL: https: //doi. org/10.1007/978­3­662­46678-07,5C_21. David Klaška, Antonín Kučera, and Vojtěch Řehák. "Adversarial Patrolling with Drones". In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand, May 9-13, 2020. Ed. by Amal El Fallah Seghrouchni et al. International Foundation for Autonomous Agents and Multiagent Systems, 2020, pp. 629­637. DOl: 10.5555/3398761.3398837. URL: https://dl.acm.org/doi/10.5555/3398761.3398837. Steve Alpern et al. "Adversarial Patrolling in a Uniform". In: Oper. Res. 70.1 (2022), pp. 129­140. DOl: 10.1287/OPRE.2021.2152. URL: https://doi.org/10.1287/opre.2021.2152. Nicola Basilico, Giuseppe De Nittis, and Nicola G atti. "Adversarial patrolling with spatially uncertain alarm signals". In: Artif. Intell. 246 (2017), pp. 220­257. DOl: 10.1016/J.ARTINT.2017.02.007. URL: https://doi.org/10.1016/j.artint.2017.02.007. Andrew Collins et al. "Optimal patrolling of fragmented boundaries". In: 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada - July 23 - 25, 2013. Ed. by Guy E. Bielloch and Berthold Vöcking. ACM, 2013, pp. 241­250. DOl: 10.1145/2486159.2486176. URL: https://doi.org/10.1145/2486159.2486176. Antonín Kučera and Tomáš Lamser. "Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems". In: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, Singapore, May 9-13, 44 2016. Ed. by Catholijn M. Jonker et al. ACM, 2016, pp. 1171­1179. URL: http://dl.acm.org/citation.cfm?id=2937095. David Klaška and Antonín Kučera and Tomáš Lamser and Vojtěch Řehák. "Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games". In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018. Ed. by Elisabeth André et al. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018, pp. 659­666. URL: http://dl.acm.org/citation.cfm?id=3237481. David Klaška et al. "Regstar: efficient strategy synthesis for adversarial patrolling games". In: Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI 2021, Virtual Event, 27-30 July 2021. Ed. by Cassio P. de Campos, Marloes H. Maathuis, and Erik Quaeghebeur. Vol. 161. Proceedings of Machine Learning Research. AUAI Press, 2021, pp. 471­481. URL: https://proceedings.mlr.press/vl6l/klaska2la.html. Tomáš Brázdil et al. "On­the­fly adaptation of patrolling strategies in changing environments". In: Uncertainty in Artificial Intelligence, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, UAI 2022, 1-5 August 2022, Eindhoven, The Netherlands. Ed. by James Cussens and Kun Zhang. Vol. 180. Proceedings of Machine Learning Research. PMLR, 2022, pp. 244­254. URL: https://proceedings.mlr.press/vl80/brazdil22a.html. David Klaška et al. "Minimizing Expected Intrusion Detection Time in Adversarial Patrolling". In: 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022. Ed. by Piotr Faliszewski et al. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022, pp. 1660­1662. DOI: 10.5555/3535850.3536068. URL: https: //www.ifaamas.org/Proceedings/aamas2022/pdfs/p1660.pdf. Milind Tambe. Security and Game Theory - Algorithms, Deployed Systems, L essons Learned. Cambridge University Press, 2012. ISBN: 978­1­10­709642­4. URL: http://www.Cambridge.org/de/academic/subj ects/computerscience/ communications­information­theory­and­ security/security­and­game­theory­algorithms­deployedsystems­ lessons­ learned?format=AR. 45 Li Huang et al. "A survey of multi-robot regular and adversarial patrolling". In: IEEE CAA J. Autom. Sinica 6.4 (2019), pp. 894-903. DOl: 10.1109/JAS.2019.1911537. URL: https://doi.org/10.1109/JAS.2019.1911537. Alessandro Almeida et al. Recent Advances on Multi-agent Patrolling. Ed. by Ana L. C. Bazzan and Sofiane Labidi. 2004. DOI: 10.1007/978-3-540-28645-5\_48. URL: https: //doi. org/10.1007/978-3-540-28645-50 /„5C_48. David Portugal and Rui P. Rocha. "A Survey on Multi-robot Patrolling Algorithms". In: Technological Innovation for Sustainability - Second IFIP WG 5.5/SOCOLNET Doctoral Conference on Computing, Electrical and Industrial Systems, DoCEIS 2011, Costa de Caparica, Portugal, February 21-23, 2011. Proceedings. Ed. by Luis M. Camarinha-Matos. Vol. 349. IFIP Advances in Information and Communication Technology. Springer, 2011, pp. 139-146. DOl: 10.1007/978-3-642-19170-l\_15. URL: https: //doi. org/10.1007/978-3-642-19170- 1°/„5C_15. Nicola Basilico. "Recent Trends in Robotic Patrolling". In: Current Robotics Reports 3.2 (June 1, 2022), pp. 65-76. ISSN: 2662-4087. U R L : https://doi.org/10.1007/s43154-022-00078-5. Peyman Afshani et al. "Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency". In: Algorithmic Foundations of Robotics XIV, Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics, WAFR 2021, Oulu, Finland, June 21-23, 2021. Ed. by Steven M. LaValle et al. Vol. 17. Springer Proceedings in Advanced Robotics. Springer, 2021, pp. 107-123. DOl: 10.1007/978-3-030-66723-8\_7. URL: https: //doi. org/10.1007/978-3-030-66723-8°/„5C_7. Sai Krishna Kanth Hari et al. "Optimal UAV Route Planning for Persistent Monitoring Missions". In: IEEE Trans. Robotics 37.2 (2021), pp. 550-566. DOl: 10.1109/TRO.2020.3032171. URL: https://doi.org/10.1109/TRO.2020.3032171. Alessandro Farinelli, Luca Iocchi, and Daniele Nardi. "Distributed on-line dynamic task assignment for multi-robot patrolling". In: Autonomous Robots 41.6 (2017), pp. 1321-1345. URL: https://doi.org/10.1007/sl0514-016-9579-8. Zhengyu Yin et al. "Stackelberg vs. Nash in security games: interchangeability, equivalence, and uniqueness". In: 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3. Ed. by Wiebe van der Hoek et al. IFAAMAS, 2010, pp. 1139-1146. URL: https://dl.acm.org/citation.cfm?id=1838360. 46 Arunesh Sinha et al. "Stackelberg Security Games: Looking Beyond a Decade of Success". In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden. Ed. by Jerome Lang. ijcai.org, 2018, pp. 5494-5501. DOl: 10.24963/1JCAI. 2018/775. URL: https://doi.org/10.24963/ij cai.2018/775. Yevgeniy Vorobeychik et al. "Computing Solutions in Infinite-Horizon Discounted Adversarial Patrolling Games". In: Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, ICAPS 2014, Portsmouth, New Hampshire, USA, June 21-26, 2014. Ed. by Steve A. Chien et al. AAAI, 2014. URL: http://www.aaai.org/ocs/index.php/ICAPS/ ICAPS14/paper/view/7783. Yufei Wang et al. "Deep Reinforcement Learning for Green Security Games with Real-Time Information". In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press, 2019, pp. 1401-1408. DOI: 10.1609/AAAI.V33I01.33011401. URL: https://doi.org/10.1609/aaai.v33i01.33011401. Arpita Biswas et al. "Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare". In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021. Ed. by Zhi-Hua Zhou, ijcai.org, 2021, pp. 4039-4046. DOI: 10.24963/1 JCAI. 2021/556. URL: https://doi.org/10.24963/ij cai.2021/556. Lily Xu. "Learning and Planning Under Uncertainty for Green Security". In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021. Ed. by Zhi-Hua Zhou. ijcai.org, 2021, pp. 4927-4928. DOI: 10.24963/1 JCAI. 2021/695. URL: https://doi.org/10.24963/ij cai.2021/695. Jan Karwowski et al. "A Memetic Approach for Sequential Security Games on a Plane with Moving Targets". In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press, 2019, 47 pp. 970-977. DOl: 10.1609/AAAI .V33I01.3301970. URL: https://doi.org/10.1609/aaai.v33i01.3301970. James Pita et al. "Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport". In: 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), Estoril, Portugal, May 12-16, 2008, Industry and Applications Track Proceedings. Ed. by Michael Berger, Bernard Burg, and Satoshi Nishiyama. IFAAMAS, 2008, pp. 125-132. URL: https://dl.acm.org/citation.cfm?id=1402819. Jason Tsai et al. "IRIS - A Tool for Strategic Security Allocation in Transportation Networks". In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2 (Dec. 2011). DOl: 10.1017/CB09780511973031.005. Francesco Maria Delle Fave et al. "Game-Theoretic Patrolling with Dynamic Execution Uncertainty and a Case Study on a Real Transit System". In: J. Artif. Intell. Res. 50 (2014), pp. 321-367. DOI: 10.1613/JAIR.4317. URL: https://doi.org/10.1613/jair.4317. Bo An et al. "PROTECT - A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard". In: AI Mag. 33.4 (2012), pp. 96-110. DOl: 10.1609/AIMAG.V33I4.2401. URL: https://doi.org/10.1609/aimag.v33i4.2401. Benjamin J. Ford et al. "PAWS: adaptive game-theoretic patrolling for wildlife protection". In: International conference on Autonomous Agents and Multi-Agent Systems, AAMAS '14, Paris, Prance, May 5-9, 2014. Ed. by Ana L. C. Bazzan et al. IFAAMAS/ACM, 2014, pp. 1641-1642. URL: http://dl.acm.org/citation.cfm?id=2616103. '18