Staying Ahead of the Game: Adaptive Robust Optimization for Dynamic Allocation of Threat Screening Resources

1 Introduction

Screening for threats is an important security challenge, be it inspecting cargo at ports, passengers at airports, or fans entering a stadium. Given a strategic adversary capable of exploiting gaps in security measures, along with a large number of screenees, it becomes critical to optimize the allocation of limited screening resources. Indeed, to improve airport screening efficiency and effectiveness, the US Transportation Security Administration (TSA) recently launched the Dynamic Aviation Risk Management Solution (DARMS) initiative [AAAE, 2014] to incorporate adaptive screening.

Threat Screening Games (TSGs) [Brown et al., 2016; Schlenker et al., 2016] have been previously introduced to model screening domains as bayesian Stackelberg games. These games model situations, wherein a strategic attacker attempts to penetrate a secure area, while the screener has the opportunity to screen for threats using limited resources. Optimizing the defender (mixed) strategy by means of the TSG captures the strategic behavior of attackers and thus yields more effective screening strategies. TSGs are inspired by previous research in security games [Tambe, 2011; Korzhyk et al., 2010; Yin et al., 2015; Balcan et al., 2015; Basilico et al., 2009], where a defender protects a set of targets from a strategic adversary. However, TSGs differ significantly because they (i) do not have an explicitly modeled set of targets; (ii) include a large number of non-player screenees that must be screened while a single adversary attempts to pass through undetected; and (iii) encompass screening resources with differing efficacies and capacities that are combined to work in teams. These key differences make TSGs more appropriate for screening settings.

Despite promising results, previous work in TSG fails in its mission to realistically model real-world settings. Its fundamental limitation is its assumption of perfect fore-knowledge of screenee arrival times (e.g., arrival times of passengers at airports). However, in the real-world there is significant uncertainty in arrival times. Addressing this challenge is difficult, as it requires reasoning about all the possible realizations of the uncertainty and coming up with an optimal plan for each of those scenarios. When dealing with a large number of screenees, this result in millions of possible scenarios, making the planning problem extremely difficult.

To address this shortcoming, our first contribution is a new model Robust Threat Screening Games (RTSG), which expresses the required uncertainty in screenee arrival times. In RTSG, we model the problem faced by a screener as a robust multistage optimization problem. We present a tractable solution approach with three key novelties that contribute to its efficiency: (i) compact linear decision rules; (ii) robust reformulation; and (iii) constraint randomization. We present extensive empirical results that show that our approach outperforms the original TSG methods that ignore uncertainty, and the exact solution methods that account for uncertainty.

2 ProblemFormulation

2.1 The Case when Screenee Arrivals are Known

We consider a finite planning horizon consisting of W time windows (periods) W := {1, . . . ,W}. During each period, a known number of screenees arrive, each from a known category κ := (ρ, φ), ρ ∈ P := {1, . . . , P}, φ ∈ F := {1, . . . , F}. The first (second) component of their category,

ρ (φ), represents the uncontrollable (resp. controllable) part of the screenee's category. Thus, each screenee can decide the controllable part of their category, however, they cannot decide the uncontrollable part of their category, which stems from their inherent characteristics. For notational convenience, we let K := P ×F. We assume that each screenee knows their own category. As an example, in the context of passenger screening at airports, ρ can represent the risk category of the passenger (e.g., normal boarding versus TSA precheck), while φ can represent a flight type (e.g., international with given departure time) - note that both these components are known to the passenger. We let N w κ denote the number of screenees in category κ to arrive in time window w. Since the category and arrival time of each screenee is known, the quantities N w κ are perfectly known. Without loss of generality, we assume that N w κ > 0 for all w and κ.

One of the screenees is planning on conducting an attack using an attack method m of his choosing from the set M. For this reason, the screener is operating a checkpoint comprised of T teams indexed by t ∈ T and can decide which team should screen each screenee based on their category. Each of these teams consists of various resource types. The set of all available resource types is denoted by R. The subset of resources composing team t is denoted by R(t) ⊆ R. If a screenee is assigned to team t, then he must be screened by all resource types allocated to that team. Unfortunately, not all screenees can be screened by the most effective resources as each resource has a capacity Cr on the number of screenees that it can process in each time window. The attack will be averted if the attack method is identified by any one of the resources screening the attacker. We let Et,m denote the effectiveness (ie. probability of interception) of team t at detecting attack method m, determined by the effectiveness of each resource, see Example 1.

Example 1. Assuming independence of the effectiveness of the resources that make up each team and letting Err,m denote the probability of detecting an attack of type m using resource r, we have Et,m = 1 - ∏r∈R(t) (1 - Err,m).

Following the (by now standard) approach in the literature, we formalize this problem as a Threat Screening Game, i.e., a Stackelberg game in which the screener, as the leader, commits to mixed strategies, and the attacker acts as the follower [Brown et al., 2016; Schlenker et al., 2016]. The rationale is that the screener acts first by selecting a (randomized) screening strategy, i.e., a feasible assignment of screenees to teams. In response to the choice of screening strategy, the attacker (after observing the screenee allocation) selects: a) his attack method m, b) his attack window w, and c) the components of his category that he can control in κ, so as to cause maximum harm. We refer to such a choice as an attack (m,w, κ). If the attack is caught, the screener receives a utility U + κ , which depends on the category of the adversary. Accordingly, if the screener is unsuccessful at preventing the attack, he receives the (negative) utility U - κ . The attacker's utilities are assumed to be negative of the screener's utilities, so that the game is zero-sum. We assume that the defender knows the probability that the attacker's uncontrollable category is ρ, denoted by Pρ and we have ∑ρ∈P Pρ = 1.The objective of the screener is then to select the best randomized allocation (i.e., mixed strategy), in anticipation of the attacker's best response.

We are now ready to provide a mathematical formulation of the problem in the spirit of [Brown et al., 2016].

Defender Pure Strategy Set. An assignment of screenees to teams occurs at the beginning of each period w ∈ W, and corresponds to a decision on the number of screenees from each category κ to allocate to each team t out of the N w κ screenees that arrive in that time window. Letting ν w κ,t denote this assignment, the defender pure strategy set is given by

The first constraint in the set stipulates that the number of screenees must be a non-negative integer. The second ensures that all the screenees are allocated to a team. The third guarantees that resource capacities are not exceeded. Note that S has finite cardinality, i.e., there are finitely many pure strategies available to the screener. The probability of detecting an attack (m, w, κ) given defender strategy s is given by

where ν w,s κ,t denotes the number of screenees in category κ screened by team t in window w according to pure strategy s. DefenderMixed Strategies. Amixed strategy corresponds to a distribution over pure strategies, i.e., to a choice

The probability of detecting an attack (m,w, κ) is given by ∑s∈S qsDw,s κ,m.

Robust Linear Programming Formulation. Since the attacker can select his attack (m,w, κ), but cannot select the uncontrollable aspect of his category, the problem faced by the screener is expressible as the following robust optimization problem in variables z and q

We have omitted the sets of the variables κ, m, w and φ to minimize notational overhead. The variable zw κ,m is the probability of detecting an attack (m, w, κ). Accordingly, the objective function corresponds to the worst-case expected utility of the screener. The expectation is taken with respect to the uncontrollable component of the attacker's category. The minimum is taken across all choices available to the attacker.

The cardinality of the strategy set S (and accordingly the number of decision variables in Problem (1)) is exponential in the number of time windows and Problem (1) is NPhard [Brown et al., 2016]. We thus consider a relaxation to Problem (1) obtained by performing the change of variables πw κ,t := ∑s∈S qsnw,s κ,t /N w κ . The variable πw κ,t can be interpreted as the (marginal) probability of allocating a screenee in category κ to team t in window w. We obtain the following robust linear problem in variables z and π whose size is polynomial in the number of time windows

The first constraint is a direct consequence of the first constraint in Problem (1) combined with the change of variables, and

denotes the set of all marginal strategies. We note that Problem (2) is equivalent to a moderately sized linear program obtained by linearizing the piecewise linear concave objective function using the standard epigraph reformulation approach.

2.2 The Case of Uncertain Screenee Arrivals

Insofar, we have assumed that screenee arrival times are perfectly known. Unfortunately, this assumption fails to hold in most threat screening problems. Moreover, ignoring uncertainty in the screenee arrivals during optimization may yield severely suboptimal or even infeasible allocations, see Section 4. We thus develop a novel modeling and solution framework for threat screening that is robust to uncertainty in screenee arrival times. Our framework builds upon formulation (2) which enjoys better tractability properties than Problem (1).

Model of Uncertainty. We model the number of screenees from each category to arrive in each time window as random variables that are defined on the probability space (Ξ, F, P), which consists of the sample space Ξ, the Borel σ-algebra F and the probability measure P. The elements of the sample space are denoted by ξ := (ξ0, ξ1, . . . , ξW) where the subvector ξw := (ξw,κ)κ∈K is observed at the end of period w and ξw,κ represents the number of people from category κ that arrive in window w. We also let ξw := (ξ0, . . . , ξw) denote the portion of ξ that has been observed by the end of time window w. We assume that Ξ is a bounded set expressible as

for some matrix V ∈ Rℓ×WK and vector h ∈ Rℓ , where ℓ corresponds to the number of constraints in the uncertainty set. Thus Ξ corresponds to the intersection of the set of all non-negative integers with a polyhedral set. Without loss of generality, we assume that Ξ ⊂ {ξ : ξ0 = 1} (since w = 0 is not a valid time period, we let ξ0 be a constant, so that affine functions of (ξw)w∈W can be represented compactly as linear functions of ξ). We assume that Ξ is bounded. In the spirit of robust optimization, we refer to Ξ as the uncertainty set. We note that polyhedral uncertainty sets allow for a lot of modeling flexibility and enable us to capture a wide variety of constraints of practical relevance such as in the airport screening domain.

Example 2 (Airport Screening). In the context of security screening at airports, the total number of people to travel in category κ on a given day, denoted by Nκ is known from the flight manifests. At the same time, passenger arrival times are conditioned by the time of their flight category φ. It is thus natural to assume that all passengers in category κ will arrive in some window w ∈ ∆κ ⊆ W (covering e.g., a couple of hours before their flight time). A suitable choice of uncertainty set is then given by

which we denote by AS for Airport Screening.

In this paper, we take the view of a risk-averse screener that wishes to be immunized against all possible realizations of ξ ∈ Ξ. This view point is very natural for the set of applications under consideration that fall under the realm of security. This implies that the attacker can in some sense "strategize with nature" to devise a maximally harmful attack. Equivalently, it can be interpreted as the desire to be immunized against an attacker who would, by his own fortune, select the maximally harmful attack relative to uncertainty in arrivals.

Adaptive Screening. As information about screenee arrivals is revealed sequentially over time, the screener has the opportunity to adjust his screening policy in an adaptive fashion, at the beginning of each time window, in response to these observations. In particular, at the beginning of time window w, the screenee has observed the sequence of past arrivals ξw-1 and can use that information to reason about uncertainty in remaining time windows and adjust his screening strategy accordingly. Mathematically, the screening decisions made at the beginning of time window w (i.e., πw) in Problem (2) must be modeled as functions of the history of screenee arrivals ξw-1 . Given a realization ˜ ξw-1 of ξw-1 , the screener will allocate πw κ,t ( ˜ ξw-1 ) percent of screenees of category κ to team t in window w. Accordingly, the probability of intercepting an attacker from category κ using attack method m in time window w (i.e., zw κ,m) also depends on the realization of ξw-1 and must be modeled as a function of the history of observations, i.e., we have zw κ,m(ξw-1 ).

Resource Overflow. When arrivals are uncertain, the resource capacity constraint in (2) reads

It requires that for all possible realizations of screenee arrivals, the allocation must be such that all screenees be screened by available resources in the window in which they arrive. This may lead to highly conservative strategies that allocate most (if not all) screenees to the team with the highest capacity. To mitigate such over-conservatism, we propose to allow each resource r ∈ R to overflow from one time window to the next at a cost Fr per screenee that is delayed. Thus, each screenee is allocated to a team in the window in which they arrive. However, screening by some (or all) of the resources in that team may take place in a future time window if that resource is over-capacity. The higher the overflow fine Fr, the least likely that resource r will be overcapacity. We note that similarly to the screening policy, the number of screenees to overflow in each resource from time window w to time window w + 1, denoted ow+1 r , must be modeled as functions of the history of screenee arrivals, ξw . Under these considerations, the resource capacity constraint becomes

and is enforced for all r ∈ R, w ∈ W, and ξ ∈ Ξ.

Adaptive Robust Optimization Formulation. We now formulate the screener's problem as a multi-stage robust optimization problem. We note that if the attacker chooses category κ and time window w for his attack, at least one screenee in category κ (corresponding to the attacker) must arrive in that time window, i.e., it must hold that ξw,κ > 0. The screener's problem may be formulated in epigraph form as

The decision variables of Problem (P) are θ ∈ R, uρ(ξ), owr (ξw-1 ), zw κ,m(ξw-1 ), πw κ,t (ξw-1 ) ∈ R, and

.

We omit the dependence on ξ to minimize notational overheard. The variables uρ(ξ) express the utility of the screener in scenario ξ when the uncontrollable category of the screener is ρ. The remaining variables admit the same interpretation as in Section 2.1. In the present setting they are however adaptive. The first set of constraints is used to linearize the piecewise linear concave objective function. The second set of constraints determines the worst-case value of uρ(ξ) for each scenario ξ. For any given choice of (κ, w, m) by the attacker, this constraint is only enforced over those ξ ∈ Ξ for which ξw,κ > 0 since at least one screenee must arrive in the attacker's chosen category and attack window. The following Proposition establishes correctness of the above formulation by showing equivalence of Problem (P) and an appropriately constructed robust dynamic program.

Proposition 1. The multi-stage robust optimization problem (P) computes the optimal defender screening strategy, which maximizes his worst-case expected utility when screenee arrivals are uncertain. It is always feasible.

Complexity. Since Ξ is discrete and bounded, Problem (P) is equivalent to a deterministic linear program obtained by enumerating all possible realizations of ξ ∈ Ξ and imposing appropriate non-anticipativity constraints, in the spirit of scenario-based stochastic programming [Birge and Louveaux, 1997]. While the numbers of decision variables and constraints in that problem is linear in the number of scenarios, the number of scenarios (cardinality of Ξ) can grow very large, as illustrated by the following example.

Example 3 (Airport Screening). Consider the uncertainty set ΞAS from Example 2. For any fixed screenee category κ, the number of possible ways in which these screenees may arrive is

For fixed |∆κ| this quantity is O(N |∆κ| κ ); and for fixed Nκ, it is O(|∆κ|Nκ ). Since passenger arrivals are independent across different categories, the cardinality of ΞAS is given by g|K| and is thus exponential in the number of categories. In the context airport screening, the number of scenarios is thus exponential in the number of flight categories. In addition, both the number of flight categories and corresponding number of passengers are generally linear in the number of time windows. This implies that the size of the corresponding scenario problem is exponential in the number of time windows.

3 Proposed Solution Approach

Problem (P) can become computationally expensive to solve for realistic size instances where the cardinality of Ξ is exponential in the number of time windows, see Example 3. We thus propose a solution approach that results in a tractable problem even when Ξ has exponentially many scenarios. In what follows, we describe our approach and main results. The proofs can be found in the Appendix. 1

3.1 Linear Decision Rule Approximation

Information Aggregation. In Problem (P), the decision variables πw are modeled as functions of the entire vector of past arrival realizations ξw-1 . As a first step to obtain a tractable problem we propose to reduce information available to the screener and only allow his screening policy to adapt to the aggregate number of screenees that have arrived in past windows. Thus, we model the screening policy πw for time window w as a function of the aggregate information

1 http://teamcore.usc.edu/papers/2017/smc17.Appendix.pdf

ζw-1 := {ζw-1,κ}κ∈K, where ζw,κ := ∑ww′=1 ξw′ ,κ. The following proposition shows that this results in a conservative approximation to the optimal screening policy, since the restricted policy lies within the space of feasible policies.

Proposition 2. Restricting the adaptive decision variables πw and zw for each time window w ∈ W to be functions of the aggregate information vector ζw-1 provides a lower bound on the optimal objective value of Problem (P).

However, even when restricting π to be functions of the aggregate arrival ζ, ow and uρ are still functions of the full passenger arrival ξw-1 . The overflow in time window w is a function of not only ξw but all ξi ∀i ≤ w since ow ≥ ∑wi=1 (πiκ,t ξi,κ - Cr). Additionally, uρ depends on ζw for all w, which is equivalent to knowing the actual passenger arrival ξ. Since restricting ow and uρ to be functions of ζ w-1 would result in further loss of optimality we avoid it here.

Linear Decision Rule. In Problem (P), the decision variables of the problem are arbitrary (bounded) functions of the uncertain parameter realizations. As a second step to obtain a tractable problem, we propose to restrict the space of feasible adaptive decisions to those that exhibit affine dependence on the data in the spirit of [Ben-Tal et al., 2004]. Thus, we let

where the vectors πw κ,t , zw κ,m ∈ RK , owr ∈ RK(w-1) and uρ ∈ RKW represent the new decision variables of the problem. Following the decision rule approximation, the number of decision variables of the problem is polynomial in the number of time windows, categories, resources, and teams. Also, it is independent of the number of scenarios. Since the linear functions lie in the space of all feasible functions the decision rule results in a conservative approximation. We denote the resulting conservative approximation by (Pl).

Proposition 3. Problem (Pl) provides a lower bound on the optimal objective value of problem (P).

3.2 Robust Counterpart

Problem (Pl) exhibits only a moderate number of decision variables but still a very large number of constraints. In what follows, we propose to mitigate the number of constraints by using techniques inspired from modern robust optimization [Ben-Tal et al., 2004]. The key observation is that under the linear decision rule approximation, all constraints in the problem (except from (4)) are linear in ξ, thus being expressible in the form a(x)⊤ξ ≤ 0 ∀ξ ∈ Ξ, for some linear function a that maps the collection of all decision rule coefficients (denoted by x) to coefficients of ξ. The following proposition enables us to reformulate these constraints in a compact fashion.

Proposition 4. For any y ∈ Rk , define:

Then ii) implies i).

To represent these constraints efficiently, we apply the above result to each constraint in Problem (Pl) (except from (4)) and denote the resulting problem by (Pl-rc). For general uncertainty sets, we obtain a conservative approximation to Problem (Pl) . The following Proposition establishes that with uncertainty set ΞAS, as defined as in Example 2, the reformulation of these constraints is exact.

Proposition 5. Suppose that we have the uncertainty set ΞAS as defined in Example 2. Then, statements i) and ii) in Proposition 4 are equivalent and Problems (Pl) and (Pl-rc) are equivalent.

3.3 Constraint Randomization

Problem (Pl-rc) still involves constraint (4) enforced over a set Ξ of potentially very large cardinality. We obtain a tractable approximation to (Pl-rc) by replacing Ξ with subsets ΞN ⊂ Ξ of cardinality N. We denote the resulting problem by (PN l-rc ). The following theorem shows that a randomly sampled subset ΞN of moderate cardinality N will lead a good approximation.

Theorem 1 ([Campi and Garatti, 2008]). Suppose that (Pl-rc) is feasible and accommodates n decision variables. For a prespecified violation probability ϵ ∈ (0, 1) and confidence β ∈ (0, 1), define

Then, the probability mass of all ξ ∈ Ξ whose associated constraints are violated by an optimal solution of (Pl-rc), for N ≥ N(ϵ, β), does not exceed ϵ with confidence 1 - β.

The parameter ϵ describes the probability that an optimal solution to (Pl-rc) violates the overflow constraint. A violation of the overflow constraint implies that the overflows are calculated incorrectly for some samples so that the part of the objective associated with overflow is calculated incorrectly. The theorem states that such miscalculations are rare. Moreover, the size of the resulting sampled problem is polynomial in the number of time windows, categories, resources, and teams, see [Vayanos et al., 2012]. In order to solve the resulting problem more efficiently we employ a cutting plane method, in the spirit of [Fischetti and Monaci, 2012].

4 Evaluation

We evaluate our framework on airport passenger screening problems with uncertainty set ΞAS.

4.1 Solution Quality

The optimal objective of our solution gives us the performance on the training set of samples we use. We evaluate the solution quality out of sample (both on average and in the worst case) by generating a large test set. We also use the test set to compute an experimental violation probability. We assume that the arrival of passengers is normally distributed in the range ∆κ. Each data point is averaged over 30 trials, each with randomized parameter settings, with error bars giving the 90% confidence intervals. For each of these trials we generate 10,000 samples from the distribution of passenger arrivals, and evaluate the computed strategy on each sample so that each data point corresponds to 300,000 evaluations.

Uncertainty model vs Averaged Model. We compare our solution method to the TSG model for problems with increasing numbers of flights with W = 10. The TSG model optimizes against only the average ξ, so there will be many scenarios where the strategy becomes infeasible. We consider two heuristics to adjust an infeasible strategy: (1) Overflow Heuristic: add excess passengers to the existing overflow queue, or (2) Open-Team Heuristic: send excess passengers to any team with available capacity. Figure 1 summarizes our results. Against both heuristics, we outperform the TSG in worst case (average) by more than 100% (50%). The average violation probability was 98 ± 2% for the averaged sample solutions and 0.5±0.02% for the solution to (PN l-rc ).

Uncertainty Model vs UniformRandom. We compare to a baseline where passengers are assigned to teams uniformly at random. Figure 1 shows our results. In both the average and worst cases, the solution quality of random screening can be arbitrarily bad- we reach around 200% improvement.

Full Stochastic Program. We also compare the quality of the solution of (PN l-rc ) to that of the optimal solution to the full stochastic program associated with (P). Because the full program is exponential in the number of categories, we can only solve for very small problem instances. We fix the number of time windows, with an arrival period of 2 time windows for any flight, and show runtime and solution quality for a small range of categories. The results are shown in Table 2 where near-optimal performance is exhibited.

4.2 Scalability

Figure 2 shows total solve and wall times for problems with increasing number of flight categories. We are able to efficiently solve for a very large number of flight categories, with polynomial growth with respect to flight categories. Table 1 summarizes our findings. We see that even for very large problems, where the cardinality of ΞAS is very large, the computed strategies have very low violation probability.

Deployment to Saturation Ratio. In Figure 3 we explore the space in which the decision problem becomes difficult by comparing the linear decision rule to a constant decision rule, where we make the same decisions regardless of the past arrival of passengers. It is a known phenomenon in security games, that the problem difficulty increases as the deployment to saturation ratio (ratio of defender resources to targets) approaches 0.5 [Jain et al., 2012].

Deployment Saturation Ratio

Figure 3: Utility improvement using adaptive decision rules.

% Improvement We measure the ratio by comparing the number of passengers to the capacity, for a single flight, so that the maximum number of passengers which can be screened in any time window is clearly defined. Figure 3 shows that as the problem difficulty increases, the gap in solution quality becomes large and the adaptive screening greatly outperforms the constant strategy.

5 Conclusion

We address a significant limitation in this area of work, where the previous unrealistic assumption of complete certainty in screenee arrival times, renders its solution unusable in realworld settings by proposing a scalable framework that provides good solution quality and works for generalized models of uncertainty.

Acknowledgements

This research was supported by MURI Grant W911NF-11-10332.