Optimal Escape Interdiction on Transportation Networks

1 Introduction

Preventing crimes or terrorist attacks in urban areas is challenging, since the number of potential targets in cities and large towns is huge. For example, the large number of bank branches, especially those offering many escape routes, could be highly profitable targets for bank robbers. In case of such an event, e.g., bank robbery or terrorist attack on buildings, it is critical for police officers to respond quickly and catch the attacker on his escape route. In this paper, we aim to help law enforcement agencies (defender) with efficiently scheduling security resources to interdict the escaping attacker.

It is a significant challenge to develop an effective response plan given the limited security resources and the attacker's strategic actions. Given the initial locations of the security resources, the defender needs to consider trafficdependent travel time in planning the schedules. In addition, one defender resource may capture the attacker at different intersections on his possible escape routes. Therefore, to make the best use of her limited resources, the defender needs to dynamically relocate them among potential intersections during the event. Moreover, the attacker may strategically choose his escape path and dynamically change his driving speed on different roads along the path to avoid being captured, which makes the attacker's strategy space continuous. This type of problems is typically referred to as pursuit-evasion games (PEGs) within the game theory literature, where the evader tries to minimize the probability of encountering the pursuer but the pursuer wants to thwart the evader's plans by capturing him [Adler et al., 2002; Nowakowski and Winkler, 1983]. However, PEGs do not consider realistic traffic dynamics, where the travel time is influenced by the traffic flow. Furthermore, the evader in PEGs cannot escape to the external world, thus the goal of the pursuer is to minimize the number of rounds needed to catch the evader. In contrast, our domain consists of a defender who aims to maximize the probability of capturing the attacker before he escapes. While there has been a variety of research work on applying game theoretic approaches to security domains [Tambe, 2011; Shieh et al., 2012; Letchford and Conitzer, 2013; Blum et al., 2014; Vorobeychik et al., 2014; Yin et al., 2014; 2015; Zhao et al., 2016; Guo et al., 2016], most of these unrealistically assume that at most one player takes paths [Basilico et al., 2009; Fang et al., 2016], and the time dynamics are irrelevant [Tsai et al., 2010; Jain et al., 2013]. As such, these models are not suitable for our problem. In particular, the attacker can exploit the fact that traffic is slower in some places, and then can choose a path, which could have been covered by the police in current models with no time dynamics, but not in our setting.

To fill this gap, we introduce a novel Escape Interdiction Game (EIG) to model time-dependent strategies for both players, where the defender chooses a sequence of intersections for each police officer to protect, while the attacker chooses an escape path and his travel time on different edges along the path. However, due to these extensions, both the defender strategy space and the continuous attacker strategy space suffer an exponential growth. These lead to major challenges in the computation of the optimal solution, as we will prove this problem is NP-hard. In particular, state-of-the-art security game solutions, such as the current double oracle type algorithms [Jain et al., 2013;

Wang et al., 2016], can only be applied to our problem at very small scales. To overcome this computational challenge, we first propose our solution, EIGS, which incorporates the following key components: 1) a new double oracle structure to avoid calling the hard oracle, i.e., the best response attacker oracle, frequently; 2) novel mixed-integer linear programming (MILP) formulations to compute the best response strategies for both players; and 3) a greedy algorithm and an efficient modified Dijkstra algorithm to efficiently generate improving strategies. To further improve the scalability to solve largescale scenarios with hundreds of intersections, we introduce a novel defender algorithm RedAD that reduces the strategy space by deploying each defender resource to protect only one node, assuming that the attacker travels with maximum speed, and using a novel algorithm to contract the graph before using the MILP to compute the attacker response strategy. We conduct extensive experiments showing that EIGS can efficiently obtain a robust solution significantly outperforming existing approaches in problems of related small scales and RedAD can scale up to realistic-sized transportation networks of hundreds of intersections with good solution quality.

2 Modelling Traffic Network

In this section, we introduce a realistic macroscopic traffic model to illustrate how the traffic flow influences the travel time in a transportation network [Daganzo, 1994; 1995; Skabardonis and Dowling, 1997; Coogan and Arcak, 2015]. Network Structure: The urban road network is modeled as a directed graph G = (V,E) consisting of a set of directed links E to represent the roads, and a set of nodes V to represent the intersections. For each link e = (σe, τe), the traffic flows from its start node σe to its end node τe. An extra node v∞ ∈ V represents the external world, which is both the source of the flow entering the network and the sink of flow exiting it. In particular, the sets of entry and exit links are denoted by Eentry = {e|σe = v∞} and Eexit = {e|τe = v∞}, respectively. Accordingly, the remaining subset of the links is the set of internal links Einter = {e|σe, τe ∈ V \ {v∞}}. It assumes that there are no self-loops, i.e., σe ̸= τe for each link e ∈ E. For each link e ∈ E, Te is the minimal travel time when the road is empty, Ce is the link capacity, and the sets of upstream links and downstream links are denoted by Ee = {e′ |τe′ = σe} and E+ e = {e′ |σe′ = τe}, respectively. Traffic Flow: Each entry link e ∈ Eentry is associated with a constant traffic demand de ≥ 0 modelling the rate of vehicles entering the node τe from the external world 1 . Traffic flows among consecutive links according to a static turning preference matrix R ∈ RE×E + whose entry Ree′ represents the fraction of vehicles flowing out of link e that are routed to link e′ . These turning ratios model the route choice behavior of drivers, justified by empirical observations [Lebacque, 2005]. Conservation of mass implies that ∑e′∈E+ e Ree′ = 1 for all e ∈ E. Moreover, the natural topological constraints imply that Ree′ = 0 if τe ̸= σe′ . To avoid trivial cases, we assume that for every node v, there exists at least one directed path from v to the node v∞, so that every vehicle will eventually exit. The rate of vehicles passing link e is denoted by traffic flow fe. According to [Coogan and Arcak, 2015], there exists a unique equilibrium flow f = {fe, e ∈ E} such that:

1 This rate is possibly time-varying. For simplicity we consider it as constant during the relatively short time period of interest.

For any given demand vector d and turning preference matrix R, the induced equilibrium flow f is used to calculate the minimal travel time te on link e. This solution can be easily extended to handle more complex traffic models [Aboudolas et al., 2009; Daganzo, 1994; 1995].

Travel Time: te on a link e, strictly increasing with fe, is defined by the commonly used Bureau of Public Roads (BPR) function [Manual, 1964; Skabardonis and Dowling, 1997]:

3 The Escape Interdiction Game

The EIG is played between the escapee (attacker), and the police officers (defender). The attacker tries to escape to the external world v∞ via any exit node d ∈ D ⊂ {v|∃e = (v, v∞) ∈ E} after conducting some criminal activity at node va 0 ∈ V . There are m defender resources (police officers/teams), initially located at intersections v1 0 , . . . , vm 0 ∈ V . To only consider nontrivial problems, we assume that va 0 ̸= vr 0 , for all r ∈ R = {1, . . . ,m}. W.l.o.g., we assume that the event starts at time 0 and ends at time tmax > 0. The traffic flow on each edge e is likely to affect the corresponding travel time te of players, which is measured by Eq.(3). The traffic network, the initial positions of the bank and the police officers are common knowledge, but both players cannot see each other until the attacker gets caught.

Strategies: A pure attacker strategy is a sequence of states A = 〈a1 = (va 0 , 0), . . . , aj = (vj, taj ), . . . , ak-1 = (d ∈ D, tak-1 ), ak = (v∞, tak ≤ tmax)〉, where each state aj = (vj, taj ) represents the situation that the attacker arrives at node vj at time taj . For every two consecutive states aj = (vj, taj ) and aj+1 = (vj+1, taj+1 ) in an attacker strategy A, it is satisfied that vj+1 ∈ N(vj), where N(vj) = {u ∈ V |(vj, u) ∈ E}, and taj+1 ≥ taj + t(vj,vj+1). This means the attacker can spend any time longer or equal to the minimal travel time t(vj,vj+1) and makes the attacker's strategy space A continuous. A mixed attacker strategy is denoted by y = 〈yA〉, with yA representing the probability that A is played.

A state of defender resource dr is a tuple sr = (vr , tr,in , tr,out ), representing the situation that dr is protecting node vr during [tr,in , tr,out ]. We assume that dr can only stay at a node for a multiple of a constant time interval δ (e.g., 10 seconds), i.e., tr,out -tr,in = κδ, where κ is a nonnegative integer. To simplify our analysis, we assume that dr captures the attacker at a node. Thus, for every two consecutive states sri = (vr i , tr,in i , tr,out i ) and sri+1 = (vr i+1 , tr,in i+1 , tr,out i+1 ), tr,in i+1 - tr,out i = dist(vr i , vr i+1 ), which is the minimal travel time between vr i and vr i+1 . This can easily be computed using Dijkstra's shortest path algorithm.

A pure strategy for the defender is a set of m schedules, i.e., S = {Sr : r ∈ R}. The schedule for dr is a sequence of states Sr = 〈sr1 , . . . , sri , . . . , srk 〉, where sr1 = (vr 0 , 0, tr,out 1 ) and srk = (vrk , tr,in k , tmax). Moreover, dr cannot drive to the external world v∞ to capture the attacker, i.e., vr i ∈ V \{v∞}, ∀sri ∈ Sr . The defender's pure strategy space is denoted by S. A defender's mixed strategy is x = 〈xS〉, with xS representing the probability that S is played.

Utility: We are only concerned with whether the attacker can be captured or not, so we assume a zero-sum game. For aj = (vj , taj ) and sri = (vr i , tr,in i , tr,out i ), we say the attacker is captured by dr at node vr i if vr i = vj and tr,in i ≤ taj ≤ tr,out i . In such a case, zsri ,aj = 1, otherwise zsri ,aj = 0. If an attacker successfully escapes to the external world, he gains a utility of 1 and the defender gets -1; otherwise both players get a utility of 0. Formally, the defender utility is given by:

Given x and A, the expected utility of the defender is Ud(x, A) = ∑S∈S Ud(S, A)xS. Accordingly, we can define Ud(x, y) = ∑A∈A yAUd(x, A). Note that Ua = -Ud.

Equilibrium: We use Nash equilibrium (NE) as the solution concept of this game as both players decide their strategies simultaneously. The NE is the same as the maxmin equilibrium given the zero-sum assumption. Thus, the optimal mixed strategy x of the defender can be computed by solving the following linear program (LP).

4 Solution Approach

Solving the LP in Eqs.(5)-(7) under the exponentially large S and the continuous A is challenging. To handle this challenge, we develop a novel double oracle algorithm EIGS (EIG Solver). Now, we first show that solving EIG is NP-hard.

Proposition 1. Computing the NE of EIG is NP-hard.

Proof. We reduce 3-SAT to the computation of NE of EIG. 3-SAT asks if there exists an assignment of values to a set of boolean variables that satisfies a given boolean formula in 3CNF (i.e., a conjunctive normal form where each clause is limited to at most three literals). Let the variables of the 3SAT be x1, . . . , xn, and the clauses be C1 ∧ C2 ∧ · · · ∧ Ck. We construct an EIG on a road network shown in Figure 1, such that, as we will show later, the 3CNF is satisfiable if and only if (denoted as ⇔1 ) there exists a defender pure strategy intercepting all attacker pure strategies if and only if (denoted as ⇔2 ) the attacker gets caught with probability 1 in NE (under the mixed strategy setting). Particularly, we will focus the proof on "⇔1 " as "⇔2 " is trivial. If there exists such a defender pure strategy, then the defender can simply play a mixed strategy incorporating only this pure strategy regardless of which strategy the attacker plays. Otherwise, for any defender strategy, the attacker can always find a pure strategy not being intercepted by at least one pure strategy in the support of the defender strategy, which gives the attacker a non-zero probability of escaping successfully.

In this graph, the ⊙ on the top represents the source node va 0 where the attacker begins to escape; each of the ⊗'s on the bottom and in the red boxes represent an exit node through which the attacker can escape to the external world; each diamond represents a police station, where one police car is available.

For each variable xi of the 3-SAT problem, we create a gadget shown in the blue box, in which there is a police station with two outbound roads. The police car from this station can choose either to move left or right, corresponding to xi = true or false, respectively. The choice of directions of all the police cars in these blue boxes corresponds to an assignment of values to x1, . . . , xn in the 3-SAT problem.

For each clause Cj , we create a gadget consisting of a road, call it the clause road, from va 0 to an exit node and three components each corresponding to a literal of the clause. In each of the red boxes, there is a police station with two outbound roads. The one to the right links to the road of the clause, so that choosing this direction, the police car can intercept attacker pure strategies passing through the clause road. The one to the left leads to an exit node, and joints in the middle with another road coming from one of the blue boxes and corresponding to: xi = true if the literal is ¬xi; and xi = false if the literal is xi. Namely, for example, if in the blue box xi is chosen to be true, the false direction is left open for the attacker to pass through, so that to the police cars in the red boxes corresponding to ¬xi have to move left to intercept the attacker. In such a way, attacker pure strategies passing through a clause road can be intercepted (without missing any attack pure strategy exiting from the red boxes) only when one of its literals is made true by choices of directions in the blue boxes.

We show that: the 3CNF is satisfiable ⇔ there exists a defender pure strategy intercepting all attacker pure strategies.

1. The "⇒" direction. Suppose there exists a satisfying assignment for the 3-SAT problem. What the defender can do

Algorithm 1: EIGS

1 Initialize S ′ , A′ . 2 repeat 3 (x, y) ← CoreLP (S ′ , A′ ); 4 S ∗ ← {betterDO(y)}; 5 if S ∗ = ∅ then S ∗ ← {bestDO(y)}; 6 S ′ ←S ′ ∪S ∗ ; 7 A∗ ← {betterAO(x)}; 8 if A∗ = ∅ ∧ S ∗ = ∅ then A∗ ← {bestAO(x)}; 9 A′ ←A′ ∪A∗ ; 10 until convergence; 11 return (x, y).

is let the police car in each blue box move to the direction that is the same as the value of xi in the satisfying assignment and stay at the first intersection. The other direction in each blue box is left open, but the roads passing through it eventually lead to the red boxes and can be intercepted by moving police cars in the red boxes to the left. Finally, since each clause contains at least one literal which is made true, the police cars in the corresponding red box do not need to move left to intercept the attacker as the attacker is already intercepted in the blue boxes; therefore, letting these police cars move to the clause road, all attacker pure strategies passing through the clause roads get intercepted as well.

2. The "⇐" direction. If there is not a satisfying assignment, then no matter how the defender moves the resources, there exists at least one clause such that the police cars in the red boxes of its literals all have to move left to intercept the incoming attacker. The clause road is left open. Then the attacker strategy passing through the clause road reaches the exit node successfully.

4.1 ANovel Double Oracle Framework

Now we develop EIGS, which first computes the equilibrium strategy for a significantly smaller restricted game, then iteratively computes improving strategies for both players, and finally converges to a global equilibrium.

EIGS is sketched in Algorithm 1. Line 1 initializes S ′ and A′ , which are small sets of pure strategies for both players. Then, CoreLP computes the maximin strategies x and y for the restricted game 〈S ′ ,A′ 〉 (Line 3) by solving the LP in Eqs.(5)-(7). To improve both players' utilities, the defender oracle (DO) (Lines 4-6) and the attacker oracle (AO) (Lines 7-9) are repeatedly used to find other strategies out of 〈S ′ ,A′ 〉 until no improving strategy can be found (Line 10). DO first calls efficient betterDO (better response DO) trying to find an improving strategy that may be suboptimal. If betterDO fails, it proceeds to bestDO (best response DO) that is optimal. Similarly, AO first calls efficient betterAO (better response AO), and if betterAO and DO both fail, it proceeds to bestAO (best response AO). This structure at Line 8 is different from the classic double oracle employed in security games [Jain et al., 2013; Wang et al., 2016], where the best oracle will be called if the corresponding better oracle fails. However, it is not efficient if one runs much slower than the other between best oracles.

Algorithm 2: betterDO (y)

19 return {Sr , r ∈ R}.

4.2 Defender Oracle

The defender needs to find an improving path with a stop time such that it can intercept as many attacker paths as possible, i.e., increase the probability of catching the attacker. Formally, given (x, y) provided by CoreLP, S is added to S ′ if Ud(S, y) > Ud(x, y). This can be formulated as an MILP, i.e., bestDO. It first constructs a path attaching travel time and stop time, and then checks if it can intercept the given attacker path, i.e., both players meet at the same time and the same node. If there are more attacker paths being intercepted by this new defender path, the defender will get a higher utility. This procedure is represented by the following MILP:

Algorithm 3: betterAO (x)

14 A ← 〈(v0, 0), (v1, ta [v1]), . . . , (vη, ta [vη])〉 such that

0 , vη = v∞, and vi = prev[vi+1] ∀ i = 0, . . . , η - 1;

v0 = va

15 return A.

Here, sri,v = 1 indicates that dr arrives at v by the i-th state of Sr . Eq.(9) indicates that dr starts at vr 0 and stays on only one node in any state of Sr . In Eqs.(10) and (11), the 0/1 variable ωr,i,(v,u) encodes whether there is a path v-u between the i-th state and (i + 1)-th state of Sr . Eq.(12) forces the strategy to start at time 0 and end at tmax, where Lmax is a sufficiently large number to estimate the maximum length allowed of the defender strategy sequence, and the time that dr stays on the i-th state is κr,iδ. Eq.(13) ensures that dr travels one stop to another through the shortest path. With Eqs.(14)-(18), zA determines whether the attacker using A is caught. Specifically, (vA j , tAj ) represents the attacker's j-th state in A; γA,j r,i indicates whether the attacker using A, meets dr at his j-th state's position while dr is at her i-th stop; αA,j r,i (respectively, βA,j r,i ) indicates whether the attacker arrives at his j-th state's position after dr arrives (respectively, before dr leaves); and M is a very large number.

To speed up the above MILP, we propose a faster oracle betterDO as shown in Algorithm 2. It is a greedy algorithm, i.e., at each step, the defender goes to the nodes with the highest marginal value. This marginal value on each node is the probability of intercepting the remaining attacker paths if the defender moves to that node. As shown in Algorithm 2, A stores the attacker's paths that are not caught by any Sr . Initially, dr is at her initial position vr 0 (Line 1). Lines 2-18 are the main loop, where we repeatedly allocate police officers to interdict the attacker's paths with the highest marginal value. Specifically, Lines 3-9 enumerate all the combinations 〈r, v〉 ∈ R × V , and check how much value dr can obtain if she moves to v and stays there as long as possible (therefore, in Lines 6-8, all attacker paths in which the attacker arrives at v later than t[r][v] are intercepted, and the corresponding values are added to ∆y[r][u]). dr∗ who can obtain the highest value among defender resources is chosen (Line 10). The remaining part is to update the finalized movement (Lines 1315), where the attacker paths caught by the movement are removed from A, and tr∗ ,out Lr∗ is updated to the time that this movement can intercept as many attacker paths as possible. dr∗ stays at a node for κδ (Line 16) and then updates her new state to the strategy sequence (Line 17).

4.3 Attacker Oracle

The attacker needs to find an improving path with a travel time such that it can minimize the probability of being caught. Formally, given (x, y) provided by CoreLP, A is added to A′ if Ua(x, A) > Ua(x, y). This can be formulated as an MILP, i.e., bestAO. It first constructs a path attaching travel time, and then checks if it is intercepted by the given defender path, i.e., both players meet at the same time and the same node. If there are more defender paths intercepting this new attacker path, the attacker will get a lower utility. This procedure is represented by the following MILP:

Here Aj,v indicates whether the attacker arrives at v in the j-th state. Eq.(22) ensures that the attacker starts at va 0 , terminates at v∞, and only arrives at one node in each state. Eqs.(23)-(24) fix the attacker at the sink node v∞ in the following states after he reaches v∞ and ensure that the attacker's strategy is a path; namely, the attacker can visit some node u in state j + 1 only if it is a neighbour of the node v in state j recorded by ωj,(v,u) in Eqs.(25)-(26). Eqs.(27)-(28) initialize the time and update it at the following states. Finally, with Eqs.(29)-(31), zS captures whether the attacker is caught by S.

Now we propose betterAO to efficiently achieve a better response. This algorithm is similar to Dijkstra's algorithm (see Algorithm 3). Let's say the length of an attacker path is the probability of being caught by the given x. Variable ∆x[v] maintains, for all v ∈ V , the shortest so-far-known acyclic path from va 0 to v. In the main loop, the node with minimum ∆x is extracted from Q (Line 4). Then in Lines 7-13, ∆x of each neighbor of v is updated with ∆x[v], where in Line 8 a best time point t is calculated such that reaching u at t minimizes the probability of attacker being caught (φu(S, t) = 1 if in S at least one defender resource stays at u at time t, and 0 otherwise). prev[u] maintains the previous node of u in the so-far-known shortest path, with which an attacker path is constructed in the end (Line 14).

5 Improving the Scalability

EIGS has improved its scalability by deploying efficient better oracles. However, it it cannot efficiently solve the best oracle of large scale games due to the large strategy spaces. In this section, we further improve scalability without significantly sacrificing the defender's utility much. Our approach is motivated by the intuition that the attacker wants to escape as soon as possible and, correspondingly, each police officer goes to one certain node with maximum speed and then waits for the attacker.

5.1 AReduced Game of EIG

A is reduced to A, which satisfies the condition that for every two consecutive states aj = (vj , taj ) and aj+1 = (vj+1, taj+1 ) of each attacker strategy A ∈ A, taj+1 = taj + t(vj,vj+1). That is, the attacker travels with the maximum speed. S is reduced to S, which satisfies the condition that for each defender strategy S ∈ S, the schedule Sr has the following form: Sr = 〈(vr 0 , 0, 0), (vr 1 , dist(vr 0 , vr 1 ), tmax)〉, where vr 1 ∈ V \ {v∞}. That is, the defender goes to some node with maximum speed and waits there. Obviously, A ⊆ A and S ⊆ S. Now we have the following property about the relation of A and S.

Proposition 2. Given a defender strategy x with its support set Sx ⊆ S, there is an attacker optimal strategy A∗ ∈ A.

Proof. Suppose that there is not an optimal strategy A∗ ∈ A. This means that if A is an optimal strategy, then A ∈ A \ A and Ua(x, A∗ ) < Ua(x, A).

In any strategy S ∈ S, the schedule Sr has the following form: Sr = 〈(vr 0 , 0, 0), (vr , tr,in , tmax)〉, where 0 ≤ tr,in = dist(vr 0 , vr 1 ) ≤ tmax. Suppose the optimal strategy A = 〈a1 = (va 0 , ta0 = 0), . . . , aj = (vj, taj ), . . . , ak-1 = (vk-1, tak-1 ), ak = (v∞, tak )〉. Keeping the nodes' sequence order of A , we can obtain A's strategy A∗ = 〈a∗1 = (va 0 , ta∗ 0 = 0), . . . , a∗j = (vj, ta∗ j ), . . . , a∗k-1 = (vk-1, ta∗ k-1 ), a∗k = (v∞, ta∗ k )〉, where ta∗ j = t(vj-1,vj) + ta∗ j-1 (j > 0). Then ta∗ j ≤ taj (∀a∗j ∈ A∗ , aj ∈ A) as taj ≥ t(vj-1,vj) + taj-1 (j > 0).

Moreover, we define z∗Sr ,a∗j ∈ {0, 1} and zSr ,aj ∈ {0, 1} (a∗j ∈ A∗ , aj ∈ A) as: z∗Sr ,a∗j = 1 if vr = vj, tr,in ≤ ta∗ j , otherwise z∗Sr ,a∗j = 0; and zSr ,aj = 1 if vr = vj, tr,in ≤ taj , otherwise zSr ,aj = 0. Then, z∗Sr ,a∗j ≤ zSr ,aj as ta∗ j ≤ taj (∀a∗j ∈ A∗ , aj ∈ A).

Furthermore, we define z∗S ∈ {0, 1} and zS ∈ {0, 1} (S ∈ Sx) as: z∗S = 1 if ∃z∗Sr ,a∗j = 1(r ∈ R, a∗j ∈ A∗ ), otherwise z∗S = 0; and zS = 1 if ∃zSr ,aj = 1(r ∈ R, aj ∈ A), otherwise zS = 0. Then, z∗S ≤ zS as z∗Sr ,a∗j ≤ zSr ,aj (∀a∗j ∈ A∗ , aj ∈ A).

Algorithm 4: advancedAO(x)

14 return A∗ .

Therefore, the utility obtained from the optimal defender strategy of the reduced game (S,A) is the same as the one in the semi-reduced game (S, A) by Proposition 2. This means that bestAO cannot find an improving strategy for the attacker if the defender strategy is an equilibrium of (S,A).

5.2 An Approximate Algorithm of EIG

Based on the reduced game (S,A), we can redesign the oracles in Algorithm 1. Here the new best DO, RedbestDO, has the same objective function as bestDO and it has the follow-

srv = 1 indicates that resource r is deployed to node v. Eq.(33) ensures that each resource will be assigned to one node, which is protected by at most one resource (Eq.(34)). zA indicates whether the attacker's path is intercepted by the defender. zA = 1 only when there is one node on the path where there is one resource reaching there before the attacker (reflected by dist(vr 0 , vA j ) ≤ tAj ) enforced by Eq.(35).

The new better DO, RedbetterDO, is similar to betterDO, except that RedbetterDO only deploys each resource to one node. The new best AO, RedbestAO, is obtained from bestAO by changing the method for updating time in Eq.(28) to taj+1 = taj + ∑(v,u)∈E t(v,u)ωj,(v,u) to reflect the fact that the attacker will travel with maximum speed. Similarly, the new better AO, RedbetterAO, is obtained from betterAO by modifying Line 8 in Algorithm 3 to: if ∃Sr s.t.zsr2 ,(u,ta [v]+tv,u) = 1, ∀S ∈ Sv, then Φ(t) ←Φ(t) +xS.

In the above new oracles, RedbestAO still has to add |V | variables (i.e., Aj,v) for each state in A, which will dramatically slow it down. To speed it up, we further reduce the attacker strategy space by graph contraction.

advancedAO: The advanced AO is based on the following intuition: for the nodes where no defender will appear, the at- Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

tacker can travel freely through them without being caught at any time; but, for the node where the defender will appear, he has to find an optimal strategy, e.g., the optimal time, to travel through these nodes to avoid being caught. For example, as shown in Figure 2, to reach the external world, the attacker needs to travel through the circle and triangle nodes. The attacker knows that he will not be caught at the circle nodes but will probably be caught at the triangle nodes. So he can freely take any strategy (path) to travel through the circle nodes but wants to take an optimal strategy (path) to travel through the triangle nodes. To reflect these facts in a simplified network, the circle nodes and their adjacent edges can be deleted. Then four new edges from the square node to each blue triangle node and from each red triangle node to the hexagon node will be added with the travel time of the corresponding special shortest path 2 in the original network.

This contraction procedure is shown in Algorithm 4. Vx stores nodes in the support set of x (Line 1). Vf , a set of nodes that can be reached from va 0 without traversing the nodes in Vx, is given by DFS(G, Vx, va 0 ) (Line 2), where DFS(G, Vx, va 0 ) is obtained from the classic Depth First Search algorithm by ending each path at the nodes in Vx. That is, a node v is pushed into the stack only if v is unvisited and v /∈ Vx. If v∞ ∈ Vf , then P(dist(Vf ,Vx,f)(va 0 , v∞)) is an optimal strategy that will not be intercepted by the defender (Line 3). Here P(dist(Vf ,Vx,f)(va 0 , v∞)) is the shortest path from va 0 to v∞ on the network (Vf , {(u, v) | (u, v) ∈ E, u ∈ Vf \ Vx,f , v ∈ Vf}) with corresponding travel time dist(Vf ,Vx,f) (va 0 , v∞). Otherwise, the network G is contracted (Lines 5-11) and RedbestAO(x) is called for the contracted network (Line 12). Vb stores nodes reached from v∞ in the backward network of G (Line 5). After that, new edges are added (Line 7) with corresponding travel time (Lines 8 and 9), and then, the contracted network (Vc,Ec) is generated in Lines 10 and 11. Finally, Line 13 maps the generated strategy (Line 12) to the original network.

Now we can obtain RedAD, an efficient algorithm based on the reduced game of EIG, from Algorithm 1 by replacing bestDO, betterDO, bestAO, and betterAO with RedbestDO, RedbetterDO, advancedAO 3 , and RedbetterAO, respectively.

2 They are not necessary the shortest paths in the network because they do not contain the triangle nodes, except for the start or end node.

3 advancedAO can be applied to the full game (S,A) by replacing RedbestAO with bestAO in Line 12 of Algorithm 4. Actually, we also propose a two-stage approach for the full game (S,A) which

6 Experimental Evaluation

We evaluate our model and algorithms with numerical experiments. All LPs and MILPs are solved with CPLEX (version 12.6). All computations are performed on a machine with a 3.20GHz quad core CPU and 16.00GB memory. All points in the figures are averaged over 30 samples. We use the Grid model with Random Edges (GRE) to generate urban road network topologies [Peng et al., 2014]. GRE is a planar connected graph made of a L ×W square grid of nodes, where horizontal/vertical edges between neighbors are controlled by probability p, and diagonal ones by q. The values of p spread in [0.3, 0.9] and q in [0.1, 0.7] to best match realistic road networks. We add a node v∞ that is connected to all the nodes at the border of the area to generate the entry and exit links.

In the traffic model, Ce = 6, and Te is randomly chosen in [1,10]. The traffic demand of each entry link is randomly chosen in [0,6], and the turning preference matrix R is uniformly generated. In EIG, va 0 is fixed to the center node of the area, and all the m defender resources are initially uniformly distributed on the network. The exit nodes D are randomly chosen from the nodes at the border of the area. The defender travels faster than the attacker because the police can circumvent traffic constraints unless otherwise specified. Central parameter values are chosen as L×W = 8×8 nodes, (p, q) = (0.4, 0.2), |D| = 10 exit nodes and m = 4 resources unless otherwise specified.

6.1 Solution Quality

We compare the solution quality of our approaches with two baselines. The first baseline is Rugged [Jain et al., 2011], where the defender resources are deployed to intercept the attacker's path without considering the travel time on paths. Rugged is a representative solution in the urban network security domain for the following reasons: 1) it is an extension of the min-cut method that the defender resources are uniformly distributed on the va 0 -v∞ min-cut [Washburn and Wood, 1995] without the travel time constraint; 2) it has the same solution quality as its variation of Snares [Jain et al., 2013] because Snares deploys Rugged's best response oracles, i.e., Snares is just an improvement of Rugged in scalability; 3) its performance in solution quality is better than MiCANS [Iwashita et al., 2016], which is an approximate algorithm for urban network security based on multiple cuts. The second baseline is the approximate algorithm bettAD where EIGS does not call the best response oracles. Comparing bettAD with RedAD in solution quality will further show the importance of developing RedAD. The solution quality of strategy x in Rugged, RedAD, and bettAD is assessed in terms of Ua(x, A), where A is obtained by using bestAO. A lower attacker utility indicates a higher defender utility given the zero-sum assumption.

Figures 3(a)-3(d) compare the solution quality obtained from our approaches with those obtained from baselines varying: the number of intersections, denoted by L × W, with

uses RedAD to initialize (S ′ , A′ ) in Line 1 of Algorithm 1 to obtain algorithm EIGS-TS, and then obtain a heuristic algorithm EIGS-TSH where bestAO is replaced by advancedAO. However, they cannot improve much in solution quality and scalability.

|D| = L in Figure 3(a); edge probabilities in Figure 3(b); the number of exit nodes in Figure 3(c); and the number of resources in Figure 3(d). Results show that Rugged performs the worst in all cases because it is designed without considering players' travel time on roads. Meanwhile, EIGS performs the best. bettAD performs significantly worse than EIGS. However, RedAD achieves good solution quality, which has similar performance to EIGS and significantly outperforms bettAD in most cases.

In terms of robustness, the defender may face execution uncertainty caused by the unpredictable delays associated with congestion, traffic signals, etc. To analyze the performance of EIGS in the presence of uncertainty, we add noise θ to the travel time. So the actual travel time ˆ te = te × (1 + θ). Figure 3(e) shows the attacker utility of EIGS under different degrees of uncertainty. Here we can see that while the performance of EIGS decreases as θ is increased, it still outperforms Rugged.

6.2 Scalability

We compare the scalability of EIGS with a baseline, EIGS-O, which runs EIGS under the double oracle framework adopted by [Jain et al., 2013; Wang et al., 2016]. This shows the effectiveness of our new double oracle framework. In addition, we evaluate the efficiency of RedAD with another baseline, Reduce, where RedAD calls RedbestAO instead of advancedAO. 4

Figures 3(f)-3(h) present the runtime in seconds varying different variables similar to the setting of solution quality. From Figure 3(f), we can see that EIGS-O does not scale up to the network with 8 × 8 intersections, so we do not show the result of EIGS-O in Figures 3(g) and 3(h). Results show that: 1) Our new double oracle framework outperforms the old one by comparing EIGS with EIGS-O; 2) RedAD outperforms EIGS and Reduce significantly; 3) The running time generally increases with the size of the network and the edge probabilities, but it reflects the easy-hard-easy pattern in security games [Jain et al., 2012]; 4) RedAD can scale up to realistic-sized problems, i.e., an urban road network with 324 intersections. Note that in real world examples, police forces typically focus on patrolling their own wards, which typically have the size of up to hundreds of intersections 5 . Thus, our algorithm can scale up to problems with realistic size.

4 We do not show the running time of Snares because it has the same solution quality as Rugged, which performs significantly worse than our algorithm in solution quality.

7 Conclusions

We present a novel game-theoretic model for interdicting the escaping attacker on urban traffic networks. We show finding NE is NP-hard. Therefore, we propose an efficient double oracle framework, EIGS, based on novel MILPs for best response oracles and heuristic algorithms for better response oracles. To solve large-scale problems, we develop RedAD to significantly reduce the strategy space for both players. Experimental results show that our algorithms obtain a robust solution that significantly outperforms baselines and can scale up to realistic-sized problems.

Acknowledgments

This research is supported by NRF2015 NCR-NCR003004. Long Tran-Thanh was supported by the EPSRC funded project EP/N02026X/1, Zhen Wang was supported by the NSFC funded project 61403059, and Jiarui Gan was funded by EPSRC International Doctoral Scholars Grant EP/N509711/1 and his department.

5 E.g., Singapore Police Force has six divisions, and each division has up to dozens of neighbourhood police posts or police centers distributed in the city.