When Security Games Hit Traffic: Optimal Traffic Enforcement Under One Sided Uncertainty

1 Introduction

About 1.25 million people die worldwide each year as a result of road accidents and many more are injured [World Health Organization, 2016]. An essential component in mitigating serious traffic accidents (accidents that cause death or injury) is efficient traffic enforcement, which is based on giving drivers the feeling that they are likely to be caught and sanctioned when breaking the law [Elvik et al., 2009]. Unfortunately, traffic police cannot cover the entire road network given its limited number of police cars and officers [DeAngelo and Hansen, 2014].

Within the Security Games (SG) field, optimal police allocation mechanisms for mitigating various types of crimes have been developed. The generic SG framework consists of a defender (traffic police) who has a limited number of resources (police cars) to protect a large set of targets (road segments) from an adversary (reckless drivers) [Paruchuri et al., 2008; Tambe, 2011]. To the best of our knowledge, [Brown et al., 2014] is the only work in the scope of SG which addresses traffic enforcement. The authors model the problem as a Stackelberg Security Game (SSG) where traffic police seek to apprehend reckless drivers who in turn seek to avoid apprehension. In a SSG, the traffic police commit to a mixed strategy where drivers can first observe and then respond as best as possible. In practice, traffic enforcement seeks to reduce traffic accidents (and not necessarily to apprehend reckless drivers) [European Transport Safety Council, 2016]. Furthermore, due to the dynamic environment factors which influence driving behavior (weather, traffic jams, etc.), drivers have been shown to act in a less strategical manner, responding to changes in their environment, including the observed police presence in current and past rounds [Elliott et al., 2005]. Therefore, SSGs seem unsuitable to the task of preventing serious road accidents.

Non-strategical adversaries in SG settings have recently been modeled as opportunistic criminals which choose where and when to commit a crime in real-time based on police presence and the attractiveness of the potential targets [Zhang et al., 2016]. Opportunistic criminals are reactive to police actions and do not consider their behaviors' effect on future police actions. We adopt this approach here, modeling the drivers, and thereby accidents, as reactive to police allocations. However, unlike [Zhang et al., 2016], drivers may react to both present and past police enforcement allocations, making the authors' Markovian assumption unsuitable. For example, it has been shown that drivers continue to react to police presence long after the enforcement operation has ceased [Elliott et al., 2005]. Basilico et al. [2009] have investigated non-Markovian strategies for robotic patrols. However, the authors assume that the attacker is strategic, and therefore the approach is inapplicable. To our knowledge, no work has efficiently addressed the non-Markovian property in SG.

Most allocation mechanisms in SG simplify the computational task by assuming that planning for each police unit separately will bring about a (near-)optimum solution [Delle Fave et al., 2014]. However, this is not the case in traffic enforcement. For example, experts from the Israeli Traffic Police (ITP) claim that if police cars are stationed at the same place and time, their effectiveness in reducing traffic accidents cannot be assumed to be greater than the effectiveness of a single police car at the same point and time, a fact we leverage in this work. Furthermore, significant benefits may accrue from coordination across multiple police units, e.g., allocating two police cars in adjacent road segments could have a stronger impact than allocating a single police car. This notion relates to the coordinated actions notion in [Delle Fave et al., 2015] which captures the combined effects of multiple defenders guarding the same target simultaneously. As a result, the computational task of deriving optimal traffic enforcement allocation in order to prevent serious road accidents is both coupled and non-Markovian, which makes it computationally intractable. Namely, the optimal allocation of traffic enforcement at time t could depend on the trajectories of all police cars (i.e., coupled) up to time t (i.e., nonMarkovian).

In order to address these shortcomings, we first formulate the TRAFFIC ENFORCEMENT ALLOCATION PROBLEM (TEAP). We prove that deriving or approximating the optimal solution to a TEAP is hard, and remedy this hardness by introducing an optimal novel algorithm called the RELAXED OPTIMIZATION SOLVER ENHANCER, or ROSE for short. ROSE uses a master/slave optimization approach, aimed at reducing the computational burden of directly solving the TEAP, and leverages common characteristics of TEAPs that have not been investigated in previous works. In an extensive empirical evaluation, we show that ROSE favorably compares to several baseline approaches, achieving a significant speed-up, using both synthetic and real-world road networks.

The TEAP formulation is based on the prediction of the risk of an accident at different road segments and different times, as well as the effectiveness of varying police enforcement allocations. We model the former using a newly developed state-of-the-art accident prediction model, based on a large set of features (110) and 11 years of collected accident reports. Our model achieves an Area Under the Curve (AUC) of 0.87. Both models are available at http: //www.biu-ai.com/trafficPolice in order to encourage other researchers to tackle the important and challenging task of preventing serious traffic accidents.

Our proposed solution, based on the ROSE algorithm and our prediction model, is currently being implemented by the Israeli Traffic Police (ITP) in field trials.

2 Traffic Enforcement Allocation

We model the interaction between drivers and police as a repeated game over T(< ∞) rounds, which takes place on a road network, represented as a graph G = 〈V,E〉 where V = {v} is the set of intersections and E = {e = (u, v)} is the set of road segments. We assume no accidents occur offroad, and therefore E is the set of enforcement targets in this work (intersection v is considered part of the road segments that share v, thus there is no need to consider v as a different target). Without losing generality, we assume that the time it takes to travel through each road segment is 1 round; this assumption can be relaxed by including dummy vertices.

The traffic police has k(<< |E|) police cars at its disposal. At each round t, the police places enforcement on a subset of size k from E, which we refer to as the allocation at round t denoted at, such that the allocation respects the graph's connectivity constraints and no more than a single police car is assigned to any edge. Namely, at round t, each police car can either stay in its current road segment (enforcing for a longer period of time) or move to an adjacent edge given at-1. a1 can assume any subset of size k of E. We denote the traffic police allocation history at round t as Ht = 〈a1, . . . , at〉. We use the notation H[et] as an indicator of whether a police car is assigned to road e at round t, et for short. Simultaneously, drivers choose whether to obey the law (drive safely) or not at each road segment e ∈ E.

We assume that drivers' actions at round t are visible to the police. For example, the ITP, as with many other police departments, uses anonymous cellular reports provided by commercial companies to evaluate the distribution of speeds on each road in real-time. Other technological aids such as speed cameras are also in use. Note that while the police does not consider the behavior of each driver individually, they do obtain aggregated statistics on traffic behavior for the entire road network. On the other hand, drivers are only exposed to a noisy signal regarding the police allocation. For example, common applications such as WAZE and other technological instruments such as police scanners allow drivers to have an indicator of police presence at et. However, these indicators are not completely accurate (police presence in a road segment is not always reported in WAZE, an indicator of police presence may not be up-to-date, a police car may be covert, etc.). As a result, the game is conducted under one-sided uncertainty. Due to this uncertainty, the drivers base their actions at et according to at (although not completely visible) and the police's past allocations (Ht-1), which together constitute Ht.

Following recent advancements in predictive policing, including the prediction model constructed in the course of this study, and in the same spirit as done in previous works such as [Shieh et al., 2012], we define the risk of accidents occurring at et as risk(et). The risk function measures the likelihood that a serious traffic accident will occur at et in the absence of police enforcement (in the [0,1] range). We further define the effectiveness of enforcement as eff(Ht, et). eff measures the effect that the police allocation history has on the risk of accidents occurring at et.

The traffic police is interested in minimizing the total expected number of accidents occurring throughout the game. Formally, it seeks to minimize the following objective of the optimization problem we denote as the TRAFFIC ENFORCEMENT ALLOCATION PROBLEM (TEAP):

risk(et) cannot be influenced by police enforcement but rather through modification of the road's characteristics (e.g., number of lanes), traffic (e.g., reducing speed-limit), etc. On the other hand, eff heavily depends on police enforcement, Ht. We assume both risk(et) and eff(et, Ht) are known to the police and can be computed in polynomial time.

A summary of the notations used in this paper is available in Table 1.

The solution to Eq. (1) prescribes a pure strategy for the traffic police. The police could optimize over all rounds simultaneously, however this approach is computationally expensive; it needs to solve a possibly non-convex optimization problem as the police must consider drivers' responses (modeled within eff). Unfortunately, approximating the optimal solution to a TEAP, within any constant factor, is hard even for a single driver and a single police car.

Theorem 1. TEAP cannot be approximated within any factor of c ≥ 1 in polynomial time, unless P = NP .

A proof is available in the appendix.

Two key computational challenges arise from the TEAP formulation. First, the arbitrary risk and eff, which can take any polynomial time computable form and depend on an unbounded history of police actions (eff), pose a significant optimization challenge. Second, the space of possible police strategies (joint schedules for all police cars) grows exponentially in the number of resources and the number of time steps which make the computation even more challenging.

3 Optimizing Police Strategy

In this work we derive an optimal pure strategy for traffic enforcement for T steps. Our goal is to find the pure strategy that would minimize the total expected number of serious accidents. In our framing, any randomized mixedstrategy, which is the combination of pure strategies, results in a greater number of accidents than the optimal pure strategy, as in [Zhang et al., 2016].

Given Theorem 1, we resort to remedying the hardness of solving the TEAP by introducing an optimal novel algorithm called the RELAXED OPTIMIZATION SOLVER ENHANCER, or ROSE for short. ROSE uses a master/slave optimization approach, aimed at reducing the computational burden of directly solving the TEAP. It exploits the fact that no two police cars are allowed to enforce the same road segment at the same time. ROSE is guaranteed to return an optimal solution, hence, in the worst case, ROSE will run in exponential time. Nevertheless, experimental results (see Section 4) on road networks of varying characteristics show that ROSE is able to derive an optimal solution significantly faster than competing approaches.

Before introducing ROSE, we first cast the TEAP as a binary graph flow problem and present an exponential sized Binary Integer Program (BIP) for solving it.

3.1 TEAP as Graph Flow

We model the TEAP using a transition graph [Yin et al., 2012]. The transition graph is a compact representation which captures the spatio-temporal structure of the road network and allows us to handle the exponential strategy space by avoiding the enumeration of all pure strategies. Technically, given a road network G, we transform it into a T timeexpanded graph GT such that each vertex v (edge e) is replicated T times, one for each round, denoted vt (et).

Each vt in the transition graph is associated with the number of police cars that start their trajectories in it minus the number of police cars that end their trajectory in it, denoted bvt . bvt is assumed to be known in advance and cannot be changed by the police. 1 The resulting flow problem can be formulated as the following mathematical program:

Constraints (3) and (4) are standard binary flow constraints. Let Sol = {et|HT [et] = 1} denote the set of ets that were assigned a unit of flow (a police car) in the optimal assignment.

We transform the above mathematical program into a 01 integer linear program (or Binary Integer Problem, BIP for short) of exponential size, using the following procedure: risk(et) and eff(et,Ht) are enumerable; for every et and possible HT (which is bounded in size by 2|V ||E||T| ) one can conceptually calculate the value of risk(et) · (1 - eff(et, Ht)) offline and store it in a table. For every entry i in the table, which assumes a possible allocation history Hi t , we denote V isitedi = {et|Hi t [et] = 1} as the set of ets that assumed the value of 1 under Hi t . Let V aluei denote the value of risk(et) · (1 - eff(et,Ht)) for entry i. For every entry i we create a new binary variable pi which takes the value of 1 if Sol ∩ V isitedi = V isitedi. To that end, we add the constraint:

Equation (5) might seem non-linear at first. However, it is rather easy to linearize it using a fix-sized set of linear constraints that will force the indicator pi to assume the correct value (a short explanation of the procedure is available at http://www.leandro-coelho.com/ linearization-product-variables/).

Let Pow(i) be the set of all strict (proper) subsets of V isitedi. We then modify the optimization objective (2) using the inclusion-exclusion principle:

Intuitively, for a given et and i, we shall refer to the summed term as penalty if the summed term is positive, and reward otherwise.

Clearly, the result is a BIP. Furthermore, the resulting BIP is not sensitive to the number of police cars. The correctness of the above procedure follows that of the inclusion-exclusion principle. In order to understand the procedure better, consider the following example:

1 This formulation allows police cars to start and finish their paths at different times and locations.

3.2 Linear Optimization Using ROSE

The resulting BIP of the procedure above cannot scale up due to the exponential number of variables and constraints (see evaluation in Section 4). To overcome this limitation we introduce a novel master/slave-based optimization algorithm, ROSE. The Master program consists of two levels: At the high level the Master program maintains a subset of penalty terms, denoted P. At the low level a BIP solver is used to solve a relaxed BIP in which only a subset of penalty terms are introduced along with their associated binary variables, pi. At the beginning of the execution, P contains all penalty terms of Eq. (6) and the low level solver generates a solution, Sol, while contemplating only pi variables associated with reward terms. Given Sol, the Slave program is executed to examine whether any penalty term p ∈ P is triggered, that is, the Slave program checks whether any binary variable pi associated with a penalty term in P should assume the value of 1 given Sol. If no penalty terms from P are triggered, the Slave returns an empty set, indicating that an optimal solution has been found and ROSE terminates; otherwise, a set of penalty terms P ′ ⊆ P is returned. The returned P ′ is injected into the relaxed BIP and removed from P by the Master.

The Slave program can return any subset P ′ ⊆ P as long as it obeys the following two rules: 1) P ′ = ∅ if no penalty terms from P are triggered under Sol; and 2) P ′ contains at least one penalty term (if such exists). We use an elementary implementation of the Slave program, returning all triggered penalty terms from P. The investigation of more elaborate Slave programs which predict which penalty terms are most beneficial to introduce, in terms of minimizing ROSE 's runtime, is left for future work.

Proposition 2. ROSE always terminates and returns an optimal solution.

A proof is available in the appendix.

Algorithm 1 ROSE

Require: Time-expanded graph GT , BIP Solver Solver. 1: function MASTER 2: BIP ← Initialize BIP with reward terms 3: P ← Penalty terms 4: Sol ← ∅ 5: repeat 6: Sol ← Solver(BIP ) 7: P ′ ← Slave(Sol, P ) 8: if P ′ = ∅ then 9: return Sol 10: P = P \ P ′ 11: Introduce P ′ into BIP 12: function SLAVE(Sol,P) 13: P ′ = {p|p ∈ P ∧ p is triggered by Sol} 14: return P ′

BIP solvers are sensitive to the number of constraints. Therefore, ROSE's computational performance depends on the number of penalty terms in P which can be avoided in the iterative penalty generation process. Namely, the choice of Slave function has a significant effect on computation time. Similar to other iterative methods such as cutting plane and column generation [Chen et al., 2011], it is hard to guarantee the computational benefit of the approach in the general case. While ROSE may be inefficient in some cases (e.g., no penalty term can be avoided regardless of Slave implementation), in several settings, including realistic and realworld traffic enforcement settings, it can bring about a significant improvement in runtime. For example, as discussed in [Delle Fave et al., 2015], eff is submodular in many security settings. Namely,

Definition 3. eff is submodular if for every et, e′t and Ht ⊆ H′ t , eff(et, Ht ∪{e′t })-eff(et, Ht) ≥ eff(et, H′ t ∪{e′t })- eff(et, H′ t )

A submodular eff means that performing an additional enforcement activity (allocating a police car at e′t ) has diminishing gains in effectiveness. In Section 4 we show the significant runtime benefits that can be generated by ROSE when this property holds.

4 Evaluation

For reproducibility purposes and to allow future research on traffic enforcement, we establish a realistic simulation environment which we name SECURE. SECURE consists of 3 components: 1) Several real-world road networks; 2) A stateof-the-art prediction model for modeling risk; and 3) A submodular eff function. risk and eff, which are described below, are derived from 11 years of accident data, extensive literature review on accident prevention and analysis and human expert knowledge from the ITP. Further details are provided in the appendix and complete source code is available at http://www.biu-ai.com/trafficPolice.

We evaluate ROSE on synthetic road networks and the Israeli road network, which are available on SECURE.

ROSE is compared with 4 baseline solutions: First, a Na¨ıve solver which solves the entire BIP (Eq. (6)) in its general form. Second, a Random solver which for each police unit selects an action at random at each time step, resolving conflicts locally. Third, a Greedy solver, which computes a greedy path for each individual police car iteratively, capturing a (wrongly) assumed additivity in individual police car gains. Greedy considers a simplified version of eff which only accounts for the marginal gains that an enforcement in a road segment will generate given the current allocation of other police cars. Given the calculated path, Greedy updates the simplified eff given the visited road segments and continues to the next police car. Finally, we compare ROSE with Domain Expert allocations from the ITP. We could not evaluate Cartesian product solutions, which capture the joint effects of all police units, such as the ones presented in [Yang et al., 2013; Zhang et al., 2016], due to their lack of scalability in the number of road segments (we were unable to solve road networks larger than 5 road segments, which are unrealistic).

The resulting allocations are evaluated on the basis of two criteria: 1) Quality, the reduction in the objective value (Eq. (6)) between the no-police enforcement condition and the provided solution; 2) Runtime and Scalability of the deployed algorithm with respect to the number of police cars, road segments and the density of the road network [Black, 2005].

The evaluation was done on a personal computer with 16 GB RAM and a CPU with 4 cores each operating at 4 GHz. The BIP solver was GUROBI [Gurobi Optimization, 2016].

4.1 Synthetic Road Networks

We evaluate ROSE, Na¨ıve, Random and Greedy on a series of synthetic road networks. We used 2 sets of synthetic road networks: Small networks (each consists of between 40 and 100 road segments in intervals of 10) and realistic networks (each consists of between 200 and 400 road segments in intervals of 100). Connectivity between road segments (i.e., the network density) is randomized such that each two road segments are connected by an intersection with a probability ranging between 0.05 and 0.15 (in intervals of 0.05), allowing for different topologies. risk uniformly samples a value in the [0, 1] interval for each road segment and round and eff is defined as in the SECURE simulation. The number of police cars is set to either 5, 10 or 15 and T is set for either 8, 16 or 24. Overall, 270 networks were evaluated. A 30 minute timeout was set for all conditions and networks.

Quality

As expected, ROSE and Na¨ıve return optimal allocations. On average, they reduce 22.7% and 5.3% of the no-enforcement objective value in small and realistic networks, respectively. On the other hand, on average, Random and Greedy reduce 1% of the no-enforcement objective value in both small and realistic networks. In realistic networks Greedy exceeded the timeout for all networks of size 300 and 400 and thus its quality cannot be evaluated properly. In our trials, Random and Greedy did not come up with an optimal allocation in any of the cases. Figures 1a and 1e present the results.

Runtime and Scalability

We begin by analyzing the non-optimal algorithms, aimed at reducing runtime. Random takes negligible time under all settings (< 3 seconds). Greedy is linear in the number of police cars (it iteratively solves the problem for each police car separately) but exponential in the size of the network. For example, for a network of size 100 with density of 0.1, 10 police cars and T = 16, ROSE takes exactly 1 second to derive an optimal solution while Greedy takes 289 seconds, and produces a suboptimal solution. Greedy reached the timeout for all realistic networks.

Analyzing the Na¨ıve and ROSE conditions head-to-head provides interesting insights. First, in all tested networks, ROSE performed faster than Na¨ıve. On average, for small networks, ROSE requires only 19% of the runtime needed by Na¨ıve. We were able to manually engineer circumstances in which Na¨ıve outperforms ROSE, mainly in very small networks (size < 40) or in networks with a high number of police cars (> 25). The runtime difference increases significantly depending on the network's size and density but slightly decreases in the number of police cars and network's density. Similar to Greedy, Na¨ıve was unable to solve most networks of size 200 and all networks of size 300 (and above) in 30 minutes time. See Figures 1b,1c, 1d, 1f, 1g and 1h.

4.2 Real-World Road Network

We evaluate ROSE using the Israeli road network. Unlike for synthetic networks, for the Israeli road network we used the risk prediction model available at SECURE. T was set to 8, 16 and 24 and the number of police cars varied between 5 and 30 (in intervals of 5) per the Israeli police's abilities (18 settings in total). We also evaluate a Domain Expert condition in which we asked an experienced ITP superintendent who specialized in traffic enforcement to provide an allocation.

The Israeli road network is much larger than the synthetic networks analyzed previously, consisting of 715 road segments, but with a very low density (on average, each intersection connects between 3 and 4 road segments). Therefore, the results display slightly different patterns. The results show that both in terms of quality and runtime ROSE outperforms the Na¨ıve, Greedy and Domain Expert conditions by a large margin. Na¨ıve achieves the same solution quality as ROSE (5.5%) but requires up to 6 times longer for runtime. For example, under T = 16 and 10 police cars, ROSE requires only 45 seconds compared to almost 4 minutes required by Na¨ıve. Greedy and Random produced extremely poor solutions across the conditions, averaging less then 0.5%. Greedy required a significantly longer runtime than ROSE and reached our timeout of 30 minutes in most cases. As expected, Random required negligible runtime under all settings (< 2 seconds). See Table 2 for the results.

The Domain Expert produced allocations where police cars were allocated permanently at the most risky road segments. The quality of the proposed allocation was about 0.5%.

5 Discussion

When presenting a new formulation, such as the TEAP, and new solutions such as ROSE, it is worth discussing limitations. ROSE allows us to optimally solve large TEAPs with significant runtime improvement compared to baseline approaches. This improvement is most significant for large, dense networks. However, ROSE's runtime is slightly impaired with the increase in the number of police units. The reason is simple: with the increase in the number of police cars, penalty terms are more likely to be triggered by feasible solutions. Therefore, in a "congested" TEAP (i.e., small network with many police cars), ROSE could be counterproductive. In our experiments, such road networks are solved very quickly by both ROSE and Na¨ıve. According to ITP experts, traffic police worldwide use a network size - police car ratio similar to the one deployed in Israel. Therefore, in real-world deployment in other countries, one is most likely to encounter large networks with a relatively low number of police resources, like the settings investigated in this paper.

The TEAP solution is a pure strategy for the police, which makes predictability an issue. Unlike various other security models such as adversarial robotic patrolling (e.g., [Agmon et al., 2011; Sless et al., 2014; Agmon et al., 2009]), in this paper, TEAP assumes that the drivers are reactive to police presence and essentially do not learn the police's actual policy. This assumption may lead to repetitive police allocations which drivers may (eventually) understand and anticipate. A practical solution to this concern is to (periodically) define additional allocation constraints that impose or restrict the enforcement of a specific road segment, similar to the entropybased approach suggested in [Brown et al., 2014]. Today, police forces occasionally define road segments that must or must not be visited during a shift due to special enforcement needs (e.g., road work). The injection of these constraints in the TEAP formulation is straightforward. An automatic process may randomly select which road segments must/mustnot be enforced in a given allocation such that every road segment has at least a user-defined ϵ probability of being enforced at every time step.

A common challenge to many human-centered problems, such as the TEAP, is the efficient adaption to human-driven changes in the environment. For example, adapting to a human's changing preferences or abilities (e.g., [Rosenfeld and Kraus, 2016; Rosenfeld et al., 2016; Rosenfeld et al., 2015]). In traffic enforcement, this challenge may manifest itself as a police car being delayed, which might make the calculated allocation undesirable or infeasible. An efficient way to resolve this issue is for central command to allocate the police cars, assuming perfect execution. Only after a non-default transition occurs does the central command resolve the TEAP starting from the current state [Delle Fave et al., 2014]. Given the positive runtime results of ROSE, such reallocation should not pose a significant computational concern.

6 Related Notions in Traffic Enforcement

It has been established that a significant reduction in the occurrence of serious traffic accidents can be achieved by efficient traffic police allocation [Elvik et al., 2009]. Specifically, efficient traffic enforcement has been shown to reduce a wide range of high-risk, illegal driving behaviors, including driving while under the influence of drugs/alcohol, speeding, lack of seat belt use and red-light running, and thus reduces traffic accidents (e.g., [Bates et al., 2012; Simandl et al., 2016]). Therefore, recently, traffic police forces have begun implementing the predictive policing paradigm [Perry, 2013] through which police officers can identify people and locations at increased risk. From a methodological standpoint, the effort of predicting traffic accidents has mainly focused on aggregative analysis, specifically on the prediction of the annual number of serious accidents per road segment using statistical methods such as Poisson or negative binomial regression models [Chang, 2005]. Such aggregation is limited in its use to police forces as the allocation of traffic police enforcement requires a prediction on a much more finely-grained level. To the best of our knowledge, the state-of-the-art prediction models provide prediction for three hour time-frames. Overall, despite its promise and successful implementation, predictive policing does not provide police officers with a means to derive optimal enforcement allocations. In this study, we were able to construct a prediction model that provides beneficial predictions for one hour time-frames by using a unique set of features and 11 years of collected data.

The Gambler's Fallacy is the phenomenon where people tend to put ample weight on previous events, believing that they influence future outcomes. This phenomenon manifests itself in the context of traffic patrol in the form of halo effects. For over 4 decades traffic halo effects have been validated repeatedly, showing that enforcement effects are not restricted to the specific time and space in which the enforcement is performed. Two such effects are called time-halo and distancehalo [Elliott et al., 2005]. To our knowledge, this is the first work to formulate and integrate halo effects in enforcement optimization. Existing works on modeling human behavior in SG settings such as [Lin et al., 2011; Kar et al., 2015; Fang et al., 2015] consider the adaptive nature of human behavior to successes and failures in past rounds. However, the integration of halo effects in such models is not straightforward.

7 Conclusions

This paper introduces a novel framework for designing traffic police allocation in realistic settings. First, we model the interaction between drivers and traffic police as a Traffic Allocation Enforcement Problem (TEAP) and prove that accurately solving or approximating the optimal solution of a TEAP is hard. Next, we cast the TEAP as a binary graph flow problem, which in turn is translated into a unique binary optimization problem, and we show how to solve it efficiently and optimally by a new algorithm called the RELAXED OPTIMIZATION SOLVER ENHANCER, ROSE. Extensive empirical evaluation, with real and synthetic road networks, demonstrates the benefits of our approach.

We hope that this study will encourage other researchers to tackle the important and challenging task of preventing serious traffic accidents. To assist others with this challenge, we also provide a realistic simulation environment, which we name SECURE, that includes a state-of-the-art accident prediction model along with useful road networks and data.

Acknowledgment

This work was supported in part by the LAW-TRAIN project that has received funding from the European Union Horizon 2020 research and innovation program under grant agreement 653587 and in part by by a grant from the Ministry of Science & Technology, Israel & the Japan Science and Technology Agency (jst), Japan.

Appendix

Theorem 1. TEAP cannot be approximated within any constant factor of c ≥ 1 in polynomial time, unless P = NP .

Proof. To prove the theorem, we give a reduction from SAT to TEAP with one driver and one police car: On input Φ(x1, . . . , xn), construct n + 1 nodes V = {vi}, i = 1, . . . , n + 1. Then connect node i with node i + 1 (i = 1, . . . , n) using 2 directed edges, one for xi = True and one for xi = False, and a single directed edge from vn+1 to v1 representing Satisfiable (S). Consider the resulting graph G = (V, E) as the road network for a TEAP with T = n + 1. A single police car starts at v0. Let risk assume 0 for all edges in all rounds except for edge S at round t +1, which assumes the value of 1. Let eff assume 0 for all edges, rounds and allocation histories except for eff(S,Ht), which assumes the value of 1 if the police trajectory (Ht) corresponds to a satisfying assignment for Φ(x1, . . . , xn) and 0 otherwise. Clearly, the driver's action (causing an accident at edge S or not) can be decided in polynomial time.

The above construction takes polynomial time. Assume to the contrary that such an approximation polynomial time algorithm App(G) exists. If there is no satisfying assignment to Φ, then every trajectory the police car may take will bring about an objective value of 1, thus App(G) ≥ c. If there is a satisfying assignment, then the defender can take the respective trajectory and receive a value of 0, hence App(G) = 0.

Proposition 1 ROSE always terminates and returns an optimal solution.

Proof. The Slave program introduces at least one penalty term to the relaxed BIP at each non-terminal iteration. Due to the finite number of penalty terms, ROSE terminates after a finite number of steps. At each iteration, the value of each feasible solution cannot decrease as ROSE only introduces penalty terms to the objective function. When ROSE terminates, all penalty terms triggered by Sol have been injected into the relaxed BIP, therefore the relaxed BIP's objective value under Sol is the optimal value under both the relaxed BIP and the original BIP, and its objective value would not change if any additional penalties from P were to be added to the objective function.

SECURE

SECURE consists of 3 components: 1) Several real-world road networks; 2) A state-of-the-art prediction model for modeling risk; and 3) A submodular eff function. risk and eff are derived from 11 years of accident data, extensive literature review on accident prevention and analysis and human expert knowledge from the ITP. We will describe the main components of SECURE. For complete details, source code and data see http://www.biu-ai. com/trafficPolice.

risk

We obtained a record of 11 years of accident reports from the Israeli Central Bureau of Statistics (2005-2015). By cross-referencing these reports with additional sources such as the Israeli GIS database and weather reports, we were able to characterize each accident using 110 features, including infrastructure characteristics (e.g., number of lanes), date and time characteristics (e.g., weekend/weekday), weather (e.g., precipitation), traffic (e.g., average speed), etc. To the best of our knowledge, this is the largest set of features ever to be used to predict serious car accidents. For comparison, the Indiana traffic police use an intelligent accident prediction tool https://www.in.gov/isp/ ispCrashApp/main.html which is based on approximately 90 features which we also use here. Experts in traffic enforcement claim that only the Indiana and Tennessee State traffic police use accident prediction tools but we were only able to obtain the latter's features. Using more than 30,000 accident records and under sampling the "non-accident" class (see [Chawla, 2005]), we trained a deep neural network model that, given 110 features representing et, returns a value in the [0,1] range, acting as a proxy to the likelihood of an accident occurring at et. 2 We compared our prediction model to several baseline prediction models such as logistic regression, SVM and XGBoost (which is currently in use by the Indiana traffic police). Our model achieves an AUC of 0.87, outperforming logistic regression, SVM and XGBoost which recorded 0.78, 0.77 and 0.82, respectively.

eff

We base eff on [Weisburd, 2016], which used a unique database to track the exact location of the Dallas Police Department's patrol cars throughout 2009 and cross-referenced it with the car accidents of that year. To the best of our knowledge, this is the most recent investigation of the topic. The author found that if et is enforced, eff should assume a value of 36%. However, enforcement effects are not restricted to the specific time and space in which the enforcement is performed. For example, Time halo is the time and the intensity to which the effects of enforcement on drivers' behavior continue after the enforcement operations have been concluded. It has been recorded that longer enforcement efforts cause more intense time halo effects that can last for hours and influence the next day(s) or even week(s) during the same time of day as the enforcement. Distance halo is defined as the distance over which the effects of an enforcement operation last after a driver passes the enforcement site. The most frequent distance halo effects are in the range of 1.5 - 3.5 kilometers from the enforcement site (see [Elliott et al., 2005] for a review). In accordance with the ITP's estimations, we define time halo effects in the exponential diminishing form 36 2k % where k ≥ 0 is the time-steps that have passed from the enforcement effort. To avoid negligible effects, we prune the effect at k = 3. The Distance halo effect is defined to be 5%, given that the two road segments are adjutant. Given the police allocation, eff assumes a simple submodular form where eff takes the largest applicable effect and adds half of each of the smaller appropriate effects to it. For example, if both et are et+1 are enforced (and no other time or distance halo effects are appropriate), eff assumes 45% (= 36% + 18 2 %).

2 Note that serious accidents are sporadic events in both time and space. Therefore, directly estimating the probability of accidents occurring at et is extremely challenging.

We are currently investigating a more data-driven approach for modeling eff in Israel.