--- title: "Optimal Cruiser-Drone Traffic Enforcement Under Energy Limitation" authors: - "Ariel Rosenfeld" - "Oleg Maksimov" - "Sarit Kraus" doi: "10.24963/ijcai.2018/535" url: "https://ijcai.org/proceedings/2018/535" pdf: "https://ijcai.org/proceedings/2018/0535.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "3848-3855" track: "Main track" keywords: - "Multidisciplinary Topics and Applications: Security and Privacy" - "Multidisciplinary Topics and Applications: Multidisciplinary Topics and Applications" --- # Optimal Cruiser-Drone Traffic Enforcement Under Energy Limitation Ariel Rosenfeld, Oleg Maksimov, Sarit Kraus *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 3848-3855. DOI: [10.24963/ijcai.2018/535](https://doi.org/10.24963/ijcai.2018/535) ## Abstract Drones can assist in mitigating traffic accidents by deterring reckless drivers, leveraging their flexible mobility. In the real world, drones are fundamentally limited by their battery/fuel capacity and have to be replenished during long operations. In this paper, we propose a novel approach where police cruisers act as mobile replenishment providers in addition to their traffic enforcement duties. We propose a binary integer linear program for determining the optimal rendezvous cruiser-drone enforcement policy which guarantees that all drones are replenished on time and minimizes the likelihood of accidents. In an extensive empirical evaluation, we first show that human drivers are expected to react to traffic enforcement drones in a similar fashion to how they react to police cruisers using a first-of-its-kind human study in realistic simulated driving. Then, we show that our proposed approach significantly outperforms the common practice of constructing stationary replenishment installations using both synthetic and real world road networks. ## Full text ## 1 Introduction Efficient traffic enforcement is an essential yet complex component in mitigating traffic accidents [World Health Organization, 2016; European Transport Safety Council, 2016]. Recently, worldwide preliminary testing has been done on the use of traffic enforcement drones for mitigating traffic accidents (e.g., in Canada [Smith, 2017], India [Malhotra, 2016], Russia [NTV, 2017] and China [News163, 2016] to name a few of the countries involved). The major advantage of drones compared to the traditional traffic enforcement resources such as speed cameras and police cruisers is their ability to provide both a "bird's eye view" on reckless drivers as well as their flexible mobility, which is not bound to road network structure and traffic congestion. The use of drones for mitigating various types of securityrelated challenges such as illegal poaching [Xu et al., 2018] has been investigated. Two assumptions are commonly made in this realm: First, drones cannot directly interdict attacks or violations, only ground resources can. Second, the drones' battery/fuel limitation does not pose a significant concern. While the first assumption is true for many security domains, drones in traffic enforcement settings can actively enforce traffic by both deterring drivers from committing traffic violations as well as recording violations and producing citations to be sent at a later time (similar to stationary speed cameras). As for the second assumption, in the real world, special attention has to be invested in ensuring that drones do not run out of energy before they reach their destination as they may be damaged, destroyed or stolen if left unattended. To address the limited battery/fuel capacity of drones we investigate two possible approaches: 1) constructing stationary replenishment installations at a relative high setup and operation cost; and 2) allowing traffic police cruisers to perform the replenishment in the field, acting as mobile replenishment service providers, in addition to their traffic enforcement duties. The use of the latter approach encompasses significant potential benefits such as allowing the traffic police to relatively quickly integrate drones within its existing cruiserbased enforcement scheme, compared to the costly and time consuming process of building stationary replenishment installations. Furthermore, the latter approach allows for malleability in adjusting the traffic police practices and policies in the future given changes in the environment (e.g., new roads, changes in manpower). However, mobile replenishment cannot be implemented without a cost: First, cruiser enforcement activities are constrained by their need to rendezvous with the drones. Second, if the traffic police seeks to avoid the very expensive processes of converting their current cruisers to allow automated replenishment, a manual "in-the-field" replenishment should be performed during which the police officer cannot actively engage in traffic enforcement. Regardless of the adopted approach, the cruiser-drone routing and the placement and scheduling of replenishment services (be they stationary or mobile) are strongly coupled problems and obtaining optimal solutions to either is computationally difficult. In this work we provide the following contributions: First, we formulate two optimization problems corresponding to the two replenishment approaches (stationary and mobile) and prove that both are computationally complex. Second, we provide two Binary Integer linear Programs (BIPs) aimed at solving the two problems. Then, using a first-of-its-kind extensive human study with 72 human drivers, we investigate drivers' reactions to the presence of traffic drones. The results of this experiment allow us to utilize an efficient optimization technique. Lastly, we provide an extensive empirical evaluation, using both synthetic and real world road networks, demonstrating the potential benefits of the mobile replenishment approach. ## 2 RelatedWork and Background We review three research threads related to our task. ## 2.1 Drones For Security It is common to model the interaction between security agencies and potential offenders as a Security Game (SG) [Tambe, 2011]. The generic SG framework consists of a defender (e.g., traffic police) who has a limited number of resources (police cruiser and drones) to protect a large set of targets (road segments) from an adversary (reckless drivers) [Paruchuri et al., 2008]. Recently, several works in this realm have considered the combination of drones and ground resources for security purposes. For example, Park et al. [2015] considered a coupled approach in which (some of the) human patrollers are coupled with drones, thus extending the latter's monitoring capabilities in mitigating illegal poaching. A different approach was taken by Xu et al. [2018] who allow for a loosely-coupled approach where drones can deter potential attackers as well as alert any close-by ground resource about a potential attack or violation. In this work, we differ from previous works in this realm in two ways: (1) Both drones and police cruisers can actively enforce the law; and (2) Drones have a (very) limited battery/fuel capacity which has to be explicitly addressed. ## 2.2 Drone Scheduling Drones are fundamentally limited by their batteries or fuel capacity. Commonly, this problem is addressed by setting stationary replenishment installations for the drones to use during their tasks (e.g., [Derenick et al., 2011; Sundar et al., 2016]). More recently, the advantages of mobile replenishment have been leveraged by different researchers [Mathew et al., 2015; Yu et al., 2017]. The latter approach is usually built on the assumption that a special team of ground "charging robots" is used to provide the mobile replenishment. In this work we examine and compare the use of stationary replenishment installations to the use of mobile replenishment provided by existing traffic police cruisers, whose primary objective is to enforce traffic laws and mitigate traffic accidents. The potential benefits of the mobile replenishment approach were only recently demonstrated in a preliminary field test by the United Parcel Service (UPS) [McFarland, 2017]. In the UPS proposed system, a delivery man would park the truck in a neighborhood, load a package into a mobile replenishment service provider and then continue on his way to make another delivery at a different address. The drone would find its way back to the truck and pick up another package. Once its flying time was up, the drone would recharge its batteries while docked on the truck. To the best of our knowledge, due to its preliminary nature, this experiment did not consider the strategic coordination between the drone and the truck and only accounted for a single truck and a single drone coupling. To the best of our knowledge, the investigation of mobile ground resources as mobile replenishment service providers in addition to their primary task is unique to this work. ## 2.3 Location-Allocation-Routing Problems Location-Allocation problems are very prominent in operational research literature [Cooper, 1963]. In its basic formulation, a mathematical program is stated as to determine the optimal location(s) for one or more facilities (e.g., hospitals, warehouses) to which the allocation of expected service demands (e.g., patients, costumers) is optimally performed. The task often involves optimal routing (e.g., transporting goods fromwarehouses to customers), resulting in the three components of the Location-Allocation-Routing (LAR) problem. Despite the possible resemblance to our task, LAR-based methods seem unsuitable for traffic enforcement since our goal is to minimize the expected number of traffic accidents while meeting the drones' energy constraints. Specifically, there is no explicit demand to allocate or fulfill. Nonetheless, in this work we adopt the common practice of modeling LAR problems in terms of Mixed Integer Linear Programs (MILPs) or BIPs, which are solved either optimally or heuristically [Wu et al., 2002]. ## 3 Cruiser-Drone Traffic Enforcement Allocation Setup. Consider a 2D physical space (e.g., a precinct) in which a road network resides. The police has k homogeneous ground resources (police cruisers pc1,. . . ,pck) and m homogeneous aerial ![Image](https://ijcai.org/proceedings/2018/fulltext/535/image_000000_7052b665456bae7f359434e47ac33da9f6e4d1b248ab1da7b0b4fec6d3e30a0f.png) resources (drones d1, . . . , dm) at its disposal for enforcing the traffic laws. We model the interaction between drivers and police as a repeated game over T(< ∞) rounds where drivers and police cruisers operate on the given road network, represented as a graph Groad = 〈V, E〉 where V = {v} is the set of intersections and E = {e = (u, v)} is the set of road segments, and drones move freely over the given physical space under energy limitation - namely a battery/fuel restriction. Specifically, drones are free to move across the physical space (and not necessarily over the road segments to which ground resources are bound) yet they are limited to Γ consecutive rounds of operation before they have to recharge. Following the common practice in drone routing and search problems, we assume that the physical terrain is represented as a grid C, covering the entire space where the size of grid cells c ∈ C is determined by a drone sensor's footprint on the physical space. Namely, the effective space which can be viewed by the drone stationed at the center of the cell [Nigam, 2014]. The grid induces a graph Gcells = 〈C,EC〉 where the vertices are the set of grid cells C, and edges are defined per the drones' mobility restrictions (e.g., EC connects every two adjacent cells but does not allow access to cells in the vicinity of the airport). If (ci, cj) ∈ EC we call ci and cj neighbors and denote cj ∈ δ(ci). Each grid cell c ∈ C is associated with a set of road segments that intersect with the cell, denoted R(c) = {e ∈ E|e intersects with c}. Specifically, a drone in grid cell c may enforce the law on all roads in R(c). Note that R(c) may be the empty set or a set with more than one element. Table 1: Summary of key notations. | notation | meaning | |-----------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | t ≤ T et ct R(c) π(c) m φ Ht[et] Ht[cd,t] Γ risk(et) eff(et,Ht) | Game round index. Road segment e at round t. A grid cell c at round t. The set of road segments which intersect with c. Indicator whether c contains a replenishment installation. Number of deployed drones. Replenishment time. Indicator whether a cruiser is present at et. Indicator whether drone d is present at ct. Drone battery capacity. Likelihood of a car accident occurring at et in the absence of police enforcement. The effectiveness of police enforcement on et. | We assume no accidents occur off-road, and therefore E is the set of enforcement targets in this framework (intersection v is considered part of the road segments that share v, thus there is no need to consider v as a different target). We further assume that k +m << |E| as police resources are limited. W.l.o.g. we assume that the time it takes for a drone to travel between two neighboring grid cells and the time it takes for a police car to travel through a road segment is 1 time unit. This assumption can be readily relaxed by dividing the road segments into smaller ones as needed (e.g., to account for traffic jams). We further assume that the police never place more than one resource to enforce the same target at the same time (otherwise, reallocating one resource to any unenforced target would be more efficient) as recently suggested in similar settings [Xu et al., 2018; Rosenfeld and Kraus, ]. Police Perspective. At each round t, the police places ground resources on a subset of roads sized k, denoted Gt, and places aerial resources on a subset of grid cells sized m, denoted At. The allocation must respect the graph's connectivity constraints (police cruisers can only move on roads), the grid connectivity (drones can only move according to EC) and the battery/fuel restrictions. We presume that G1 may assume any subset of size k from E (G1 ∈ {G|G ⊆ E ∧ |G| = k}), and A1 can assume any subset of size m from C (A1 ∈ {A|A ⊆ C ∧ |A| = m}). We denote the police allocation history at round t as Ht = 〈G1,A1, . . . ,Gt,At〉. We denote Ht[et] as an indicator of whether some police cruiser (pci) is allocated to road segment e at time t according to the allocation history Ht. We further denote Ht[cd,t] as an indicator of whether the drone d is allocated to grid cell c at time t according to the allocation history Ht. At round t, each police resource can either stay in its current place (enforcing for a longer period of time) or move to a neighboring edge (cell) given Gt-1 (At-1), yet drones must recharge (at least) every Γ rounds (the battery/fuel capacity). Replenishment. We investigate two replenishment approaches: First, the construction of stationary replenishment installations. For this option, the police select a subset of grid cells π ⊆ C where replenishment installations will be constructed. We denote π(c) as an indicator which assumes the value of 1 if a stationary replenishment installation is constructed at c. The construction and maintenance cost of stationary replenishment installations can be expressed in terms of drone cost (the alternative investment of funds). Specifically, given a fixed budget, the police have to choose how many drones to deploy (d1, . . . , dm), and the number and placement of stationary replenishment installations (via π), thus trading off between several bundles (e.g., 2 drones and 2 replenishment installations vs. 3 drones and a single replenishment installation). Second, a police cruiser can replace drones' batteries in the field, acting as a mobile replenishment service provider. To that end, a drone and a police cruiser must meet at a road segment. Formally, the drone needs to be stationed at c ∈ C such that there exists a police cruiser in e ∈ R(c) for a period of φ rounds (i.e., replenishment time). Note however that since police officers perform the replenishment manually, during the replenishment period no enforcement takes place. 1 We assume that both cruisers and stationary replenishment installations can provide sufficient battery replacements indefinitely yet can only serve a single drone at a time. Drivers' Perspective. Our recently proposed Traffic Enforcement Allocation Problem (TEAP) [Rosenfeld and Kraus, ] adopted the opportunistic crimes approach to traffic enforcement, modeling the drivers, and thereby accidents, as reactive to police allocations in the current and past rounds. Following the TEAP's formulation, we denoted the risk of accidents occurring at et as risk(et). The risk function measures the likelihood that a severe traffic accident will occur at et in the absence of police enforcement (in the [0,1] range). The effectiveness of enforcement is denoted eff(Ht, et). eff measures the effect that the police allocation history has on the risk of accidents occurring at et. A close examination of traffic enforcement literature (e.g., [Elvik et al., 2009]) as well as the original instantiation of the problem reveals that in fact drivers are assumed to have a fixed memory length µ and that drivers' actions at et depend only on police actions at the specific place of enforcement or in adjutant road segments. As a result, drivers' actions at et depend on police actions at et and adjutant road segments between round max{t - µ, 0} and round t (including t) alone. Road networks are usually sparse and the maximal rank of a vertex in a road network graph can be bound by a constant 2 . As a result, it is reasonable to assume that both risk and eff can be enumerated in polynomial space and time in the road network and grid size. Objective. Using the stationary replenishment installations approach, given a model of drivers' behavior (risk, eff and µ) and a fixed budget, the police seek to determine how many replenishment installations and drones to deploy such that the expected number of accidents is minimized and all constraints are met. Similarly, using the mobile replenishment approach, the police seek to minimize the expected number of accidents while exhausting its drone budget only on drones. Formally, the police seek to minimize the following objective using both approaches (π is applicable only for the stationary replenishment setting): 1 The proposed model can also handle the case where the officer can both things at the same time. 2 In Israel the rank of any vertex is bounded by 4. under the budget, travel and battery/fuel constraints discussed above. Although eff may be enumerated in polynomial time and space, both problems are computationally complex. Theorem 1. Optimal cruiser-drone traffic enforcement, with either stationary or mobile replenishment, cannot be optimally determined in polynomial time, unless P = NP . Theorem 1 is due to a simple reduction from the multiagent pathfinding problem [Yu and LaValle, 2013]. ## 4 Binary Integer Programs for Cruiser-Drone Traffic Enforcement We first define a BIP to solve the cruiser-drone traffic enforcement allocation problem with stationary replenishment: s.t ∑ Ht[(v′t-1 , vt)t-1]- We start with standard flow constraints: Constraint 3 is a standard flow constraint for the police cruisers and Constraints 4 and 5 ensure that each drone is only at a single place at a time and executes a valid route. We now turn to address the replenishment constraints. Constraint 6 introduces a set of auxiliary variables γd,t indicating that drone d finished a replenishment process at time t. 3 We assume that all drones start with a full battery/fuel tank as guaranteed by Constraint 7. Finally, Constraint 8 ensures that each drone finishes a replenishment process at least once every Γ + φ time steps. Next, Constraint 9 makes sure that no more than a single drone is at the same cell at the same time. Constraint 10 is a straightforward budget constraint, the next two constraints are standard binary constraints and the last one makes sure that exactly m drones are deployed. In words, the optimizer seeks to minimize the expected number of accidents through setting HT (the set of indicators specifying where and when cruisers/drones are deployed), Π (the set of indicators specifying where stationary replenishment installations are set) and m (the number of drones to deploy) appropriately given the above constraints. Note however that m is an integer, thusł given a fixed budget, the optimizer can iteratively solve the BIPs induced by each of the Pareto-efficient combinations of replenishment installations and drones which do not exceed the budget constraint. Namely, all "non-wasteful" combinations of replenishment installations and drones which do not exceed the budget constraint can be checked by the BIP solver iteratively to find the optimal one. For the mobile replenishment we need to perform two minor modifications: 1. We modify Constraint 6 to the following: naturally changing the auxiliary variables definition such that γd,t assumes the value of 1 only if drone d meets with some cruiser for φ time framesł ending at t. 2. We change Constraint 10 to the following: ## 5 Understanding eff of Drones Recall that risk measures the likelihood that a severe traffic accident will occur at any et, and can be estimated from past data (e.g., [Weisburd, 2016]). As for eff, which measures the effectiveness of enforcement on any et for any Ht, it has been argued that the eff is submodular in Ht (e.g., [Rosenfeld and Kraus, ; Elvik et al., 2009]). However, to the best of our knowledge, this submodularity has only been demonstrated for cruiser-based traffic enforcement since traffic enforcement drones are still uncommon today. To better understand the effectiveness of drone-enhanced traffic enforcement, we conduct a first-of-its-kind human study, with 72 human drivers 4 ranging in age from 20 to 30 (42 males, 30 females) recruited from a major university in Israel. All participants have a valid driver's license. 3 Linearization is possible since all variables are binary. ## 5.1 Driving Simulator In order to simulate driving conditions, we adopted the popular open-source CARLA driving simulator [Dosovitskiy et al., 2017]. Using a randomly selected map from CARLA's dataset, we designed a driving course starting at an urban street (explained to participants as their home) from which they need to exit to reach an interurban road. The interurban road consisted of 3 symmetrical but non-identical parts connected by sharp turns which force drivers to reduce their speed significantly. At the end of the third interurban part, drivers enter a different city to reach a designated parking spot (explained to participants as their workplace). All three interurban parts are marked with 60Km/h speed signs while urban roads are marked with 40Km/h speed signs. We introduced two police enforcement resources to CARLA: a police drone, and a police cruiser with an officer holding a speed laser gun at the side of the road (see Figure 1 for an illustration). Figure 1: Newly added traffic enforcement drone (left) and cruiser (right) in CARLA. ![Image](https://ijcai.org/proceedings/2018/fulltext/535/image_000001_34b2cd072fe7d233c494668be73504f70868832db7ddab8c6a9d534dee1a716a.png) ## 5.2 Experimental Design Participants first viewed a PowerPoint presentation (available at http://www.biu-ai.com/trafficPolice/ ) explaining the task. Each participant was then presented with the CARLA simulator and asked to drive along the designed route without any enforcement present. Participants were assisted by an experienced tutor (who did not co-author this paper) who assisted them in getting acquainted with the simulator and the route. Then, each participant was asked to drive through the route 4 times, each time facing one of the following scenarios in a random order: Scenario (1): no police presence (as was the case in the preliminary step); scenario (2): a single drone stationed at the first part of the inter-urban road; scenario (3) a single police cruiser stationed at the third part of the inter-urban road; and scenario (4): a single police cruiser stationed at the first part of the inter-urban road while a drone is present at the third part of the inter-urban road. Participants were counter-balanced such that each possible ordering of the 4 scenarios was encountered by exactly 3 participants. 4 The experiment was authorized by the corresponding institutional review board. The driving speed was logged every second as an indicator of driving safety, as justified by [Elvik, 2013]. We want participants to reach their destination as quickly and safely as possible, while avoiding traffic citations. To this end, for each drive we pay each participant 5 New Israeli Shekels (approximately $1.5, denoted NIS) if she completes the route successfully within the top 15% of the participant population, 3 NIS if she is ranked between the 15th percentile and the 85th percentile, and 1 NIS otherwise. However, if she is involved in an accident she will lose the reward. In addition, if a participant receives a traffic citation, she loses 3 NIS (all rewards are bounded by 0). Namely, if one expects most drivers to drive according to the designated speed-limit (which most drivers do in reality and in our simulation), one would trade-off the chance of completing the route faster than most drivers (thus getting an additional 2 NIS) with the risk of losing the entire reward in a traffic accident or risking losing 3 NIS due to a traffic citation. Once each drive was completed, the participant was informed whether or not a ticket was issued. A ticket was issued if the participant exceeded the speed limit (by at least 5%) along the segment where police enforcement is visible (either a drone or a cruiser). ## 5.3 Results First, we notice a slight "learning curve" in drivers' skills during the course of the experiment, possibly attributed to their gained familiarity with the CARLA simulator. Therefore, we would first need to eliminate this trend. Given the eff model proposed in [Rosenfeld and Kraus, ], we seek to estimate the following two key factors: 1) Given that a road segment is enforced by a drone (DR = 1 if true, 0 otherwise) or a cruiser (CR = 1 if true, 0 otherwise), on average, how will the driving speed change on the segment? and 2) Given that a road segment was enforced at drive t-1 by a drone (DRt-1 = 1 if true, 0 otherwise) or cruiser (CRt-1 = 1 if true, 0 otherwise), how would the driving speed change at drive t? Using regression analysis [Draper and Smith, 2014], with driving speed as the dependent variable and the turn number T, DR, CR, DRt-1 and CRt-1 as independent variables, we seek to understand the effect of these independent variables on driving speeds. For completeness, we further introduce indicator variables differing between the 3 road segments denoted A,B and C. We evaluate the following model: First, we notice that the intercept is close to the speed limit ( ˆ α0 = 55.9, p < 0.05). Also, as expected, drivers do increase their speed as a function of drive number ( ˆ α1 = 1.5, p < 0.05), while decreasing their speed when police presence is encountered ( ˆ α2 = -12.9, ˆ α3 = -8.4, p < 0.05 for both). Although police presence at the previous road segment has a negative influence on driving speed ( ˆ α4 = -5.1, ˆ α5 = -2.0), it is not statistically significant. It turns out that participants drive slower on road segment B, which is not enforced ( ˆ α7 = -26.7, p < 0.05). This is due to a traffic light being present at segment B which is not present in segments A Figure 2: Average marginal improvement (Y-Axis) due to the introduction of drones from budget 1 (leftmost) to budget 4 (rightmost) as a function of the number of grid cells (X-Axis). The higher the better. ![Image](https://ijcai.org/proceedings/2018/fulltext/535/image_000002_15452c7ff1d82b76230b85cd9c18285228e507c2664fbe22eeea3deea7e0bea4.png) or C. No significant difference was found between segments A and C, indicating that they are in fact similar. ## 5.4 Discussion With the results of Section 5.3 in mind, one can justify the submodularity assumption for the use of drones as well as cruisers (which were already investigated in the literature). Therefore, for the following evaluation of the two replenishment approaches, we adjust the eff to reflect the possible difference between the two enforcement resources as observed in the experiment while accounting for the submodularity of eff. Specifically, we adopt the eff function of [Rosenfeld and Kraus, ] and extend it by setting the parameters associated with drone enforcement according to their effect as observed in the experiment above. This allows us to use the Relaxed Optimization Solver Enhancer (ROSE) technique, as proposed and evaluated in the original paper, for our BIPs as well. Note that our experiment was carried out in a laboratory setting and, as such, in order to translate the results to real world deployment, additional experimentation in real world settings are needed. Future work will seek to provide a more thorough understanding of why drivers seem to react (slightly) differently to cruisers and drones. A first step towards that end was recently taken in [Rosenfeld, 2018], investigating and comparing drivers' beliefs and perceptions relating to traffic enforcement drones not only across different jurisdictions (i.e., urban and interurban) but also compared to other traffic law enforcement resources (e.g., police cruisers and speed cameras). ## 6 Evaluation We evaluate the two replenishment approaches, Stationary and Mobile, using both synthetic and real world road networks varying in topology. To quantify the marginal improvement from the adoption of drone technology and a specific replenishment approach, the performance of both approaches is measured as the percentage of accidents which are expected to be avoided compared to the use of cruisers alone. According to a drone expert with whom we consulted, the cost associated with constructing a stationary replenishment installation is significantly higher than the cost associated with purchasing a traffic enforcement drone. Nevertheless, to better demonstrate the potential benefits of the mobile replenishment approach over constructing stationary replenishment installations, we assume that the police budget can support up to K "units", be they drones, charging stations or any combination thereof. According to a traffic enforcement expert from the Israeli Traffic Police, setting K up to 4 and the number of police cruisers around 10 is reasonable for a precinct or district. We use these guidelines in the following evaluation. 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]. ## 6.1 Synthetic Road Networks We generated a series of synthetic road networks as follows: each road network consists of between 20 and 80 nodes in intervals of 20, where the connectivity between nodes (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. The number of cells was set to 52 , 102 or 152 . Each road segment was uniformly randomized as to which grid cells it intersects with (i.e., each road segment intersects with one cell, but a cell may intersect with several road segments). Connectivity between cells was randomized as well such that each two grid cells are neighbors with 0.9 probability. risk uniformly samples a value in the [0, 1] interval for each road segment and time. eff is borrowed from [Rosenfeld and Kraus, ], naturally extended in light of the results observed in Section 5. The number of cruisers is set to either 5, 10 or 15, Γ was set to 4, φ was set to 1 and T was set to 24. Overall, 108 settings were evaluated. The instantiation of variables for evaluation was chosen in consultation with a drone and traffic enforcement experts. Surprisingly, for all tested settings and budgets, the mobile replenishment approach yields better marginal improvement compared to the stationary approach. By varying the number of grid-cells and budget levels, Figure 2 demonstrates the statistically significant benefit from performing mobile replenishment compared to stationary replenishment (p < 0.05). For example, on average, with a budget of 2 "units" the mobile replenishment approach brings about a marginal improvement 86% higher than that of a stationary approach. ## 6.2 Real World Road Network We evaluate the two replenishment approaches using the "Shfela" district from the Israeli road network and the risk prediction model available from [Rosenfeld et al., 2017], allowing for reproducibility of the results. The road network is larger than the synthetic networks analyzed previously, consisting of approximately 100 road segments with a very low density (on average, each intersection connects between 3 and 4 road segments). The number of cruisers is set to 10, Γ was set to 4, φ was set to 1 and T was set to 24, aligned with expert expectations. Furthermore, the number of grid-cells required to cover the district can vary between 100 and 400 cells, depending on drone technology. We next evaluate both extremes. Varying the number of available "units", Figure 2 illustrates the significant benefit of the mobile replenishment approach. Consider the use of a single drone under the mobile setting compared to the use of a single drone and a single charging station under the stationary setting with 400 gridcells. The former brings about a marginal improvement of 2%, while the latter brings about a marginal improvement of 2.33%, as no police cruiser is diverted from its traffic enforcement duties. However, if the stationary installation were to be replaced with an additional drone in the mobile setting, a significant gain could be observed with 4.2% marginal improvement. Similar results were observed for 100 grid-cells. Figure 3: Marginal improvement (Y-Axis) due to the introduction of drones as a function of available budget (X-Axis) and the replenishment approach (the higher the better). ![Image](https://ijcai.org/proceedings/2018/fulltext/535/image_000003_9652fffa008bb7d5362ad2b16a4595abbf07133e8769570b69234be1b2921865.png) ## 6.3 Discussion The results for both the synthetic and real world networks indicate that the use of mobile replenishment encompasses significant benefits compared to the stationary approach. However, the results further demonstrate an interesting trade-off between solution quality and runtime. While the mobile replenishment approach allows for better enforcement, the runtime of the solver given a fixed budget increases substantially. For example, for the Israeli network, given a budget of 2 "units", the mobile approach (i.e., 2 drones) will take about 18 minutes compared to the stationary approach (a single installation and a single drone) which takes only 8 minutes. The difference becomes insignificant when considering the use of 2 drones and a single stationary replenishment installation under the stationary approach (about 17 minutes), possibly suggesting that, similar to the analysis of performance carried out above, the most prominent factor here is the number of drones and not the budget constraint. We plan to focus on this issue in future work. It is important to note that once an unexpected event occurs (e.g., road block, technical problem) a police cruiser or drone may not arrive at the assigned location on time. An efficient way to resolve this issue is for central command to allocate the police cruisers and drones, assuming perfect execution. Only after a non-default transition occurs does the central command resolve the appropriate BIP from the current state [Delle Fave et al., 2014]. We plan to investigate more efficient methods of adapting the schedule given unexpected events in future work. ## 7 Conclusions Drones could provide an economical solution for improving traffic enforcement quality. In this paper, we investigate the challenge of designing optimal cruiser-drone traffic enforcement, focusing on the limited energy of drones. By modeling the interaction between police cruisers, drones and drivers, we investigate two possible approaches for mitigating drone energy limitations: 1) constructing stationary replenishment installations; and 2) having police cruisers act as mobile replenishment providers in addition to their traffic enforcement duties. Then, in order to better understand drivers' reactions to drone-enhanced traffic enforcement, we conducted a firstof-its-kind human study, with 72 drivers demonstrating that drivers are expected to react to police drones similar to how they react to police cruisers. Finally, in an extensive empirical evaluation, with real and synthetic road networks, we demonstrate the significant benefits of our rendezvous replenishment approach compared to standard practices. All collected data, code and simulations are available at http://www.biu-ai.com/trafficPolice/. ## Acknowledgments The research has been supported in part by the Ministry of Science and Technology, Israel and the Japan Science and Technology Agency (JST), Japan. ## References 1. [Cooper, 1963] Leon Cooper. Location-allocation problems. Operations research, 11(3):331-343, 1963. 2. [Delle Fave et al., 2014] Francesco Maria Delle Fave, Al- bert Xin Jiang, Zhengyu Yin, Chao Zhang, Milind Tambe, Sarit Kraus, and John P Sullivan. Game-theoretic pa- trolling with dynamic execution uncertainty and a case study on a real transit system. Journal of Artificial Intelli- gence Research, 50:321-367, 2014. 3. [Derenick et al., 2011] Jason Derenick, Nathan Michael, and Vijay Kumar. Energy-aware coverage control with dock- ing for robot teams. In Proceedings of the Intelligent Robots and Systems (IROS) Conference, pages 3667- 3672. IEEE, 2011. 4. [Dosovitskiy et al., 2017] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. CARLA: An open urban driving simulator. In Proceed- ings of the Annual Conference on Robot Learning, pages 1-16, 2017. 5. [Draper and Smith, 2014] Norman R Draper and Harry Smith. Applied regression analysis. John Wiley & Sons, 2014. 6. [Elvik et al., 2009] Rune Elvik, Truls Vaa, Alena Erke, and Michael Sorensen. The handbook of road safety measures. Emerald Group Publishing, 2009. 7. [Elvik, 2013] Rune Elvik. A re-parameterisation of the power model of the relationship between the speed of traf- fic and the number of accidents and accident victims. Ac- cident Analysis & Prevention, 50:854-860, 2013. 8. [European Transport Safety Council, 2016] European Transport Safety Council. How traffic law enforce- ment can contribute to safer roads: Pin flash report 31. Technical report, June 2016. http://etsc.eu. Gurobi Optimization, 2016] Inc. Gurobi Optimization. Gurobi optimizer manual, 2016. http://www.gurobi.com. 9. [Malhotra, 2016] Abhinav Malhotra. Drone to monitor Kan- pur traffic. The Times of India, 2016. 10. [Mathew et al., 2015] Neil Mathew, Stephen L Smith, and Steven L Waslander. Multirobot rendezvous planning for recharging in persistent tasks. IEEE Transactions on Robotics, 31(1):128-142, 2015. 11. [McFarland, 2017] Matt McFarland. UPS drivers may tag team deliveries with drones. Technical report, CNN, February 2017. 12. [News163, 2016] News163. Traffic police using unmanned aerial high-speed UAV. more than 30 people were arrested, 2016. http://news.163.com/photoview/00AP0001/2198301.html. 13. [Nigam, 2014] Nikhil Nigam. The multiple unmanned air vehicle persistent surveillance problem: A review. Ma- chines, 2(1):13-72, 2014. 14. [NTV, 2017] NTV. UAV began to catch vi- olators on the roads of chuvashia, 2017. http://www.ntv.ru/novosti/1924648/. 15. [Park et al., 2015] Noseong Park, Edoardo Serra, Tom Snitch, and VS Subrahmanian. APE: A data-driven, be- havioral model-based anti-poaching engine. IEEE Trans- actions on Computational Social Systems, 2(2):15-37, 2015. 16. [Paruchuri et al., 2008] Praveen Paruchuri, Jonathan P Pearce, Janusz Marecki, Milind Tambe, Fernando Or- donez, and Sarit Kraus. Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games. In International Conference on Autonomous Agents and Multiagent Systems, pages 895-902, 2008. 17. Rosenfeld and Kraus, ] Ariel Rosenfeld and Sarit Kraus. When security games hit traffic: Optimal traffic enforce- ment under one sided uncertainty. In Proceedings of the In- ternational Conference on Artificial Intelligence (IJCAI), pages 3814-3822. 18. [Rosenfeld et al., 2017] Ariel Rosenfeld, Oleg Maksimov, and Sarit Kraus. Optimizing traffic enforcement: From the lab to the roads. In International Conference on Deci- sion and Game Theory for Security, pages 3-20. Springer, 2017. 19. [Rosenfeld, 2018] Ariel Rosenfeld. Are drivers ready for traffic enforcement drones? 2018. (under review). [Smith, 2017] 20. Ainsley Smith. Ontario high- ways will soon be monitored by drones, 2017. http://dailyhive.com/toronto/sky-guys-drones-ontario- highways-2017. 21. [Sundar et al., 2016] Kaarthik Sundar, Saravanan Venkat- achalam, and Sivakumar Rathinam. Formulations and al- gorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem. In American Control Conference, pages 6489-6494. IEEE, 2016. 22. [Tambe, 2011] Milind Tambe. Security and game theory: al- gorithms, deployed systems, lessons learned. Cambridge University Press, 2011. 23. [Weisburd, 2016] Sarit Weisburd. Does police presence re- duce car accidents? Technical report, Auguest 2016. 24. [World Health Organization, 2016] World Health Organization. Road traffic injuries fact sheet. Technical report, November 2016. http://www.who.int/mediacentre/factsheets/fs358/en/. 25. [Wu et al., 2002] Tai-Hsi Wu, Chinyao Low, and Jiunn- Wei Bai. Heuristic solutions to multi-depot location- routing problems. Computers & Operations Research, 29(10):1393-1415, 2002. 26. [Xu et al., 2018] Haifeng Xu, Kai Wang, Phebe Vayanos, and Milind Tambe. Strategic coordination of human pa- trollers and mobile sensors with signaling for security games. In AAAI Conference on Artificial Intelligence, pages 1290-1297, 2018. 27. [Yu and LaValle, 2013] Jingjin Yu and Steven M LaValle. Structure and intractability of optimal multi-robot path planning on graphs. In AAAI Conference on Artificial In- telligence, pages 1443-1449, 2013. 28. [Yu et al., 2017] Kevin Yu, Ashish Kumar Budhiraja, and Pratap Tokekar. Algorithms for routing of unmanned aerial vehicles with mobile recharging stations and for package delivery. arXiv preprint arXiv:1704.00079, 2017.