Efficiently Solving Joint Activity Based Security Games

1 Introduction

Stackelberg Security Games (SSGs) have been widely applied to real-world security domains with these applications depending on significant advances in fast algorithms for SSGs [Jain et al., 2010; Tambe, 2011]. Yet, scale-up remains a significant issue in advancing the scope of SSGs.

A major drawback of the current algorithms [Conitzer and Sandholm, 2006; Jain et al., 2010; Paruchuri et al., 2008; Vanek et al., 2011] is their failure to scale-up in solving games that include joint coordinated activities, which require coordination in time and/or space, and provide the defender additional benefits. Yet such coordination is an important aspect of real-world security systems. For example, the PROTECT application for the US Coast Guard computes patrol routes for protecting ports in the US [Shieh et al., 2012]; but this application only focuses on one-boat patrols. Yet there are benefits that may accrue from coordination across multiple boats, e.g., if a target is visited by a single patrol boat, it may only be 50% effective in detecting (and hence stopping) a potential attack. The arrival of a second boat may increase the effectiveness to 80% (as the attacker may be forced to react to a second boat). Yet no SSG algorithm today can scaleup to handle US Coast Guard coordinated patrols for small or large-scale ports.

To remedy the challenge of scale-up, this paper makes the following contributions. First, it presents SMART, Security games with Multiple coordinated Activities and Resources that are Time-dependent, a model extending the framework of security games to explicitly represent jointly coordinated activities. Second, the paper puts forward an optimal algorithm, SMARTO, that computes optimal defender strategies for SMART problems. Third, the paper discusses a heuristic iterative procedure, SMARTH, that achieves further speed-up over SMARTO. Both algorithms use a branch-and-price algorithm [Barnhart et al., 1994] to deal with the large strategy space of the domain. Furthermore, these algorithms are able to exploit the structure of the joint activity coordination problem to gain speed up based on the following key ideas: (i) use of insights from the Traveling Salesman Problem to order the search space, especially in SMARTH, while maintaining coordination, (ii) efficient greedy computation of patrols per resource via iterative reward shaping to generate a joint patrol, and (iii) generation of tight upper-bounds exploiting scheduling constraints to allow pruning of the search space based on the submodular property of joint activities.

2 SMART

A SMART problem instance is defined on a graph Gr = (T,Er), where the vertices T are the targets and the edges Er represent connectivity between the targets for resource r. This allows for heterogeneous resources, e.g., boats or helicopters, which have the same targets but the connectivity between nodes can be different. For each e ∈ Er, τ(e) represents the time it takes one defender resource to traverse the edge e. As usual with SSGs [Yin et al., 2010], for each target t ∈ T, there is an associated reward U c d (t) and penalty U u d (t) to the defender if t was protected with an effectiveness of 100% and 0% respectively. Similarly, payoffs U c a (t) and U u a (t) are defined for the attacker, with U u d (t) < U c d (t) and U c a (t) < U u a (t). The defender has a set of R resources, and each resource can choose an activity from the set A = {α1, α2, . . . αK}. The notation used in SMART is described in Table 1.

The attacker's pure strategy space is the set of all targets, T. Each pure strategy of the defender is a route for each resource, such that the route starts and ends at a pre-defined home base tb ∈ T, and the total route length of each individual patrol is upper bounded by Γr. The pure strategy Xi of one defender resource is a patrol route, which is represented as an ordered list of 3-tuples Xi = [X1 i , . . . ,Xj i , . . .]. Here, each 3-tuple Xj i = (t, α, γ) represents that this defender resource conducts and completes activity α at target t at time γ, where different activities require different amounts of time and effectiveness. Each pure strategy is restricted to begin and end at the home base, i.e. X1 i .t = tb and X|Xi| i .t = tb. Each route length is upper bounded by Γr, as follows:

X r is defined as the set of pure strategies for resource r and the set of joint pure strategies P is given by the cross-product of pure strategies for each resource, i.e., ∏Rr=1 {X r }.

SMART is unique in that it explicitly models joint activities, or activities coordinated in space and time between multiple defender resources. The defender is said to conduct a joint activity 〈αi, αj〉 in its pure strategy if there exists at least two tuples (ti, αi, γi) and (tj , αj , γj) in the defender's pure strategy such that ti = tj and |γi -γj | ≤ W, where W is the time window for two activities on the same target.

For each activity αi, eff(αi) represents the effectiveness of the activity αi. This effectiveness ranges from 0% to 100%, and measures the probability of the defender successfully preventing an attack on target t if the attack on t happened when the defender was conducting activity αi at t. This is similar to what was done in PROTECT [Shieh et al., 2012]. We define the effectiveness of the joint activity 〈αi, αj〉 as eff(αi, αj). We assume that a joint activity composed of two resources receives the maximum effectiveness and any additional resource visiting target t in the time window will have no additional benefit 1 . eff(S) represents the maximum effectiveness of an individual or a joint activity over a set S of activities performed at a target. eff() is submodular if for all S1 ⊆ S2:

1 This formulation be extended to handle n-ary combinations of defender resources

This means that each additional activity performed has diminishing gains in effectiveness. As we will see later in the paper, when this property holds we are able to prove nice theoretical properties of our algorithms.

The expected utility Ud(Pi, t) of the defender when the defender is conducting pure strategy Pi, which is a single pure strategy for multiple defender resources, and the attacker attacks target t is given as follows:

Here ωt(Pi) defined in Equation (3) represents the effective coverage of the defender on target t when executing pure strategy Pi. This is computed by taking the maximum effectiveness of either a single or joint activity performed at target t. For the purposes of this paper we assume that the time it takes to attack is longer than the time required to patrol, thus the attacker only cares about the maximum effective activity or joint activity. Once the effectiveness ωt(Pi) is computed from the pure strategy Pi, the defender and attacker expected utilities Ud(Pi, t) and Ua(Pi, t) are calculated as defined in Equation (4) and (5).

Problem Statement: The objective of the defender is to maximize her expected utility in the SMART problem by computing the optimal mixed strategy given that the attacker will best respond to the defender's strategy.

3 SMARTO: Optimal Branch-and-Price Solver

SMARTO computes an optimal solution of the SMART problem by building upon work that has leveraged the branchand-price framework [Jain et al., 2010]. The two major novelties of SMARTO over previous work are the formulation of the slave component to handle joint activities (in Section 3.1) and a better bounding component (in Section 3.2).

3.1 Pricing component

The branch-and-price framework constructs a branch-andbound tree, where for each leaf of the tree, the attacker's target is fixed to a different t′ . The objective of the pricing component is to find the best defender mixed strategy x at that leaf, such that the best response of the attacker to x is to attack target t′ . Due to the exponential number of defender pure strategies, the best defender mixed strategy is determined using column generation, which is composed of a master and slave procedure, where the slave iteratively adds a new column (defender strategy) to the master.

Master: The master LP given in Equations (6) to (10) solves for the optimal defender mixed strategy x over a given set of pure strategies J, given that the pure strategy of the attacker is set to t′ (determined by the leaf node). This is similar in formulation to the ERASER algorithm [Kiekintveld et al., 2009]. Ud(t, c) and Ua(t, c) are the utilities of the defender and the attacker respectively when the defender's effective marginal coverage is c and the attacker attacks t. For each pure strategy Pj , ωt(Pj) is the effectiveness on t.

Slave: Once the master LP is solved to optimality, the slave problem receives the values of the duals of the master LP. The reduced cost cj associated with column Pj is defined to be

where z is the dual variable of Equation (9) and {yt} are the duals of Equation family (8). The reduced cost of a column gives the potential change in the master's objective function when a candidate pure strategy is added to J.

The objective for the slave problem is to find the column Pj with the least reduced cost, to add to the current set of columns. The best column is identified using a mixed-integer linear program (MILP) formulation over the transition graph as defined below, which captures all the spatio-temporal constraints of the problem in handling joint activities and avoids having to enumerate all pure strategies.

The transition graph Gr = (N ′r ,E′r ) contains nodes u = (t, γ) for each target t and time instant γ ∈ [0, Γr] if it is possible for the defender to be at target t at time instant γ (the time interval is discretized). The transition graph can have up to |T| ×Γr nodes. Each edge in E′r is associated with an activity α. An edge e(u,v,α) from node u to node v maps to a defender patrol that starts from target tu at time γu, goes to target tv and conducts activity α at target tv. Therefore, γv = γu+τ (tu, tv)+τ (α) where τ (tu, tv) is the time required to traverse from target tu to tv and τ(α) is the time required to conduct activity α. The graph contains a virtual source and sink node that contain edges to/from the base target tb to ensure that patrols start and end at tb.

Example: Figure 1 shows a sample transition graph. Here, tb = t1 and the source has three edges, one for each activity α1 - α3. Looking at node u = (t1, 0), target t1 is adjacent to t2 and t5, so for each of these targets, three edges are added to represent the travel and corresponding activity at that target. For example, if activity α2 is then performed at target t2, then the new vertex would be at time γ = 0 + τ(α2) + τ12 = 0+1+2 = 3, where τ12 = 2, and node v = (t2, 3) as shown in Figure 1.

Slave Problem MILP: This novel MILP component of SMARTO solves for joint activities and generates the optimal defender pure strategy as given in Equation (12) to (16).

This MILP uses one copy of the transition graph for each defender resource, where f(er) represents the flow on edge e for resource r, and gt and ht represent the effectiveness of the defender's individual and joint activities on target t. It only considers the maximum effective activity at target t (Equations (12), (14), and (15)) in accordance with our assumption of the attacker's decision making.

Here, the set IA(d) represents the set of edges in the transition graph such that they represent one resource performing an activity α on target d, and can be represented as:

where in(ur) represents all edges with the target node ur. Similarly, the set JA(ri, rj , d) contains pairs of edges 〈ei, ej〉 such that both edges lead to the same target d and are separated by a time window no larger than W, corresponding to when resources i and j perform a joint activity on target d. Formally, JA(ri, rj , d) =

The result from the slave MILP is a set of 0-1 integer flows for each defender resource r. From the flows, the defender pure strategy Pj is computed, and the effective coverage ω(Pj) is then calculated and returned to the master.

3.2 Branch-and-bound component

The objective of the branch and bound component is (i) to compute upper bounds for each internal node of the tree such that leaf nodes can be pruned thereby requiring less computation, and (ii) to determine an efficient ordering of leaves. To compute tight upper bounds, we present ORIGAMIP, a novel modification of ORIGAMI [Kiekintveld et al., 2009] specifically designed to generate tighter upper bounds for SMART problem instances by exploiting the structure of the domain.

ORIGAMIP uses the transition graph defined in the slave formulation (Section 3.1). Equations (17)-(18) minimize the attacker's maximum expected utility, with Ua(t, c) representing the attacker's utility given the defender's effective marginal coverage is c and the attacker attacks t, and qt representing the attacker's strategy. Equations (19)-(20) define the flows of the edges and enforce the flow conservation property. Equation (21) limits the coverage of the defender based on the amount of flow and the respective activity.

ORIGAMIP estimates the effectiveness of a defender patrol on a target as being the sum of the effectiveness of all individual activities on a target. This is an over-estimate of the effectiveness (thereby providing an upper bound on defender utility) if the effectiveness function eff is sub-additive, i.e., eff(αi) + eff(αj ) ≥ eff(αi, αj ), which follows from the submodularity property in (2).

Proposition 1. ORIGAMIP computes valid upper bounds if eff() is submodular.

ORIGAMIP is an LP and therefore solvable in polynomial time. Once the ORIGAMIP solution has been obtained, the defender's expected utility Ud(t, c) is computed for each target t. The targets are then ordered in decreasing order of Ud(t, c). This ordering and computation of upper bounds is then exploited to prune the nodes in the branch-and-price tree.

4 SMARTH: Further scaling up SMART

SMARTO fails to scale beyond 4 targets in our computational experiments; thus we present SMARTH, a heuristic approach for SMART that achieves further scale-up. It uses the previously discussed branch-and-price framework, but the slave is now solved using a novel heuristic formulation, which is built on two intuitions related to coordination: (i) Joint patrols can be computed by considering individual patrols iteratively, by shaping the reward function between iterations to reflect the additive benefit of joint activities. (ii) Each defender resource would like to visit as many targets as possible, and visiting targets in accordance with an ordering based on a solution of the Traveling Salesman Problem is likely to extract maximal benefit out of the resource while still accounting for the spatio-temporal constraints needed for coordination. As a result, the SMARTH slave only needs to solve a set of linear programs (as opposed to solving a MILP in SMARTO's slave).

4.1 Reward Shaping

The slave in SMARTH computes the joint patrol Pj of the defender by iteratively and greedily building up individual patrols Xr for each defender resource r. The additional benefit of joint activities is considered by appropriately shaping the rewards for each resource based on the patrols of other resources. Reward shaping has been used in other reinforcement learning contexts [Sutton and Barto, 1998]; here we leverage this idea for coordination among multiple resources.

SMARTH uses a greedy algorithm, as outlined in Algorithm 1. This algorithm takes the coefficients yt (refer Equation (11)) as input and builds Pj iteratively in Lines 3-5. Line 4 computes the best individual patrol Xr for the defender resource r (described in Section 4.2). Xr is then merged with the rest of the defender's pure strategy Pj (in Line 5). Line 6 computes μ, the potential effectiveness contribution from one resource to another given the current pure strategy Pj. This is computed over each edge e(u,v,α) in the transition graph, and measures the added benefit to the defender if the defender resource was to travel from u.t to v.t at time u.γ performing activity e.α at target v.t. These values of μ are used in the next iteration when computing an individual patrol for the next defender resource.

How close to optimal is the solution of the greedy algorithm? [Nemhauser et al., 1978] states that greedy maximization of a non-negative submodular function achieves a constant-factor approximation. Recall that the objective of the slave problem is to find a pure strategy Pj that minimizes the reduced cost cj. This is equivalent to maximizing:

The duals y from the master are always negative in this formulation making F(Pj) non-negative. ωt(Pj) is the effectiveness of pure strategy Pj at target t as defined in (3).

If F(Pj) is submodular, and if P∗ is the optimal defender pure strategy, then the solution Pj of the greedy algorithm satisfies

For the relaxed constraint where the time window, W, is greater than or equal to the maximum patrol time, Γ, 2 we show that F(Pj) is submodular. F(Pj) is submodular if P1 and P2 are two pure strategies where P1 ⊆ P2 and F (P1 ∪ {X}) - F (P1) ≥ F (P2 ∪ {X}) - F (P2). We show F(Pj) is submodular by showing that ωt(Pj) is submodular since F(Pj) is defined by a non-negative linear combination of ωt(Pj).

2W ≥ Γ implies that two resources present at the same target at anytime during the patrol are considered to conduct a joint activity.

Theorem 1. F(Pj) is submodular in Pj if W ≥ Γ and eff() is submodular.

Proof Sketch. Because W ≥ Γ, ωt(Pj) = eff(SPj ), where SPj is the set of activities of Pj on target t. Together with (2), this directly implies that ωt(P1 ∪ X) - ωt(P1) ≥ ωt(P2 ∪ X) - ωt(P2), P1 ⊆ P2.

In real life situations, W may be less than Γ. We show that even in this situation, F(Pj) is submodular for 2 resources.

Theorem 2. F(Pj) is submodular in Pj for two resources if eff() is submodular.

Proof Sketch. We prove that F(P1∪{X})-F(P1) ≥ F(P2∪ {X}) - F(P2) where P1 = {∅} and P2 contains a single patrol {X2}. For each target t, we show that ωt({X}) ≥ ωt({X2, X}) - ωt({X2}) based on the submodularity property of eff() in (2).

Qualifying this result for W < Γ for 2 resources is important since this setup is used most frequently in the realworld, e.g., US Coast Guard. For three or more resources, we can artificially construct counter-examples that break submodularity. However, given actual domain geometries, time windows and operational rules, submodularity may hold even for larger number of resources - e.g., Theorem 1 shows that relaxing the time window may lead to such submodularity. Characterizing these spaces is a topic left for future work.

4.2 TSP Ordering with Transition Graph

To achieve the approximation bound (24), we need to optimally compute an individual patrol Xr for the defender resource r in Line 4 of Algorithm 1. This can be solved by an MILP of similar form to the slave MILP (Equations (12)- (16)), but for a single patrol. The resulting MILP for a single patrol has less variables than the MILP for all patrols, however this still fails to scale up beyond 6 targets (Section 5).

Instead, we present a heuristic approach that achieves better scale-up by exploiting the spatial structure of the domain, and is provably optimal in certain cases. Our approach is based on the following restricted version of the problem: we define an ordering of the targets and restrict the patrols' sequence of target visits to be increasing in this order. We construct the ordered transition graph in the same way as described in Section 3.1; however, now, an edge from node u to v is added only if target u.t appears before target v.t in the ordering. If there does not exist a direct edge from u to v, an edge is added between these nodes where the distance is that of the shortest path. Traversing along this edge does not impact the effectiveness of the intermediate targets. Instead of computing the maximum effectiveness of the multiple edges per target, each target is only visited once per patrol in the ordered transition graph. The resulting problem is equivalent to a min-cost flow, which has integer extreme points that allow us to drop the integrality constraint (16), since a feasible solution of the resulting LP is guaranteed to be an integer flow.

These LPs are easier to solve than the above MILPs, both in theory as well as in our experiments.

Fixing an ordering will exclude certain patrols. Therefore, we would like an ordering such that the resulting patrol, which corresponds to a subsequence of the ordering, will still be a sensible way to visit targets compared to patrols with alternative orderings. To that end, SMARTH uses an ordering based on the solution of the traveling salesman problem (TSP) for the input graph with all targets G = (T,E). We show that under certain conditions, using the TSP ordering results in an optimal solution of the single-patrol problem. We look at a tree structure because various domains in the real-world, e.g., ports, contain an graph similar to a tree.

Theorem 3. Suppose the input graph G is a tree, and the time window for joint effectiveness is greater than or equal to the maximum patrol time. Then SMARTH computes a patrol for a single unit that optimizes the slave objective.

Proof Sketch. SMARTH outputs a patrol P on a subset of targets TP , corresponding to a subsequence of the TSP ordering. We define GP to be the subgraph of G containing the targets TP . It can be shown that P is a TSP tour of GP given that GP is a tree; we omit the details for brevity. Consider a patrol P ′ on TP that does not follow the TSP ordering. Since P is a TSP tour of GP , if P ′ finishes within the time limit then P also does. Since the time window is large, joint activities in P ′ will also be joint activities in P, and thus P achieves the same slave objective as P ′ . Therefore we never lose optimality by considering only patrols that follow the TSP order.

When the graph is a tree but the time window is smaller than the patrol time limit, the algorithm is not guaranteed to be optimal. However, as we show in our experiments, SMARTH generates optimal or near-optimal solutions for SMART problem instances.

5 Experimental Results

We cannot compare with previous algorithms [Conitzer and Sandholm, 2006; Jain et al., 2010; Paruchuri et al., 2008; Vanek et al., 2011] due to the inability of these algorithms to scale-up to the combinatorics unleashed by joint activities. This problem is so complex that even human schedulers are unable to generate schedules. Therefore, we are limited to comparing different versions of SMARTH and SMARTO.

The experiments were run on 100 game instances generated with random payoffs in the range [-10,10] and two defender resources unless otherwise noted. All experiments were run on graphs resembling ports: the graphs were constructed beginning with a tree that spans the targets and then adding 10 random edges between nodes. The time window was 30 minutes with 3 possible activities for the defender, taking 0, 5, or 15 minutes. The time discretization was 5 minutes, with the exception of the tests comparing SMARTO to SMARTH, where the time discretization was 15 minutes. All experiments were run on a machine with a Dual core 2.0 GHz processor and 4 GB of RAM.

Figure 2(a) shows the runtime of SMARTH versus SMARTO. The x-axis is the number of targets and the y-axis is the runtime. SMARTO was only able to run for 4 or less targets. For 20 targets, SMARTH takes less than a minute to run. This shows the difficulty of solving SMART instances and the importance of finding efficient solution techniques.

Table 2 shows the solution quality, or defender expected utility, of SMARTH versus SMARTO. For 3 targets, SMARTH provided the same exact solution quality as SMARTO for all game instances. For 4 targets, the average solution quality for SMARTH was 0.0205 lower than SMARTO with there being only one game instance where SMARTH computed a lower defender expected utility than SMARTO (difference of 0.679). This shows that on average SMARTH computes a final result that is very close to SMARTO. However, SMARTO is unable to run on bigger game instances.

Figure 2(b) shows that as we increase the importance of the coordinated joint activity, as measured by the ratio of effectiveness of joint activities, the defender

achieves a higher expected reward. The y-axis shows the solution quality and the x-axis denotes the maximum patrol time. This ratio is computed as shown with αmax equivalent to the highest quality activity: eff(αmax,αmax)-eff(αmax) eff(αmax) . As the patrol time is increased, a simple strategy with no defender coordination (no benefit to joint activities) provides very little benefit to the solution quality while the improvement due to the coordination of multiple defender resources can almost double the solution quality.

Figure 2(c) shows that SMARTH can handle heterogeneous defender resources (a boat and an aerial type) for 10 targets. The aerial resource is different than the boat in the following ways: (1) shorter transit times; (2) shorter patrol time; (3) lower effectiveness values. The x-axis is the maximum patrol time for a boat resource and the y-axis is the solution quality. In this experiment, the aerial resource has a patrol time and effectiveness value that is 25% of the boat resource's time/value. SMARTH was able to run these instances.

The SMARTH algorithm can handle in general n-ary combinations of resources efficiently by simply modifying the underlying utility function. SMARTH's reward shaping then efficiently computes μ based on this new utility function based on the n-ary interaction (line 5 of Algorithm 1). Figure 3 demonstrates the ability of SMARTH to handle coordination among multiple defender resources. In this figure, the x-axis is the number of defender resources and arity of joint actions (e.g., 3 resources with ternary interactions) and the y-axis is the runtime, where we assumed an additive joint action function. This also shows that SMARTH can efficiently handle n-ary interactions: runtime grows linearly with the number of resources and arity of interactions.

For a comparison of the impact of the different components of SMARTH, please refer to [Shieh et al., 2013].

6 Conclusion and RelatedWork

Addressing joint coordinated activities is the next frontier of the SSG research area. Such coordination is critical for realworld applications, and yet beyond the capabilities of both today's best algorithms to solve SSGs and human schedulers. To address this challenge, this paper presented two novel algorithms, SMARTO and SMARTH, that leveraged the properties and structure of joint activities to provide significant speed-ups to solve SMART problem instances.

In terms of related work within SSGs, we have discussed limitations of related algorithms throughout this paper. Studies on multiagent patrols beyond SSGs have focused on frequency-based patrols and adversarial environments [Agmon et al., 2008; Machado et al., 2003; Vanek et al., 2010], including patrols in marine environments that take into account uncertain environmental conditions [Agmon et al., 2011]. These studies aim to minimize the time lag between visits and do not consider targets of varying importance nor the impact of joint activities.

Acknowledgments: We thank the USCG officers for their exceptional collaboration. This research is supported by US Coast Guard grant HSHQDC-10-D-00019 and MURI grant W911NF-11-1-0332.