Multi-Agent Reinforcement Learning for Joint Police Patrol and Dispatch
Matthew Repasky He Wang Yao Xie










H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology


Multi-Agent Reinforcement Learning for 
Joint Police Patrol and Dispatch
    Yao Xie
    

========================================================================



§ ABSTRACT 
Police patrol units need to split their time between performing preventive patrol and being dispatched to serve emergency incidents. In the existing literature, patrol and dispatch decisions are often studied separately. We consider joint optimization of these two decisions to improve police operations efficiency and reduce response time to emergency calls.
Methodology/results: We propose a novel method for jointly optimizing multi-agent patrol and dispatch to learn policies yielding rapid response times. Our method treats each patroller as an independent Q-learner (agent) with a shared deep Q-network that represents the state-action values. The dispatching decisions are chosen using mixed-integer programming and value function approximation from combinatorial action spaces. We demonstrate that this heterogeneous multi-agent reinforcement learning approach is capable of learning joint policies that outperform those optimized for patrol or dispatch alone. 
Managerial Implications: Policies jointly optimized for patrol and dispatch can lead to more effective service while targeting demonstrably flexible objectives, such as those encouraging efficiency and equity in response.




Multi-Agent Reinforcement Learning for 
Joint Police Patrol and Dispatch
    Yao Xie
    

========================================================================







§ INTRODUCTION

The timeliness of police response to emergency calls plays a critical role in maintaining public safety and preventing crimes. 
However, recent data showed that police response times in major U.S. cities are getting longer, partly due to staffing shortages <cit.>. In this paper, we study how to improve police patrol operations and reduce emergency call response times by multi-agent reinforcement learning, where each patrol unit (e.g., a police patrol car) is treated as an agent.

Coordinating the patrol of multiple agents in a shared environment has been a task of interest in operations research and machine learning for many years. Approaches ranging from extensions of the traveling salesman problem <cit.> to deep reinforcement learning (RL) for multi-agent robot patrol <cit.> have been applied. Many challenges are associated with multi-agent patrol, including large action spaces that grow exponentially with the number of patrollers, coordination/cooperation of agents, and state representation.
Some prior works evaluate patrol policies using criteria that capture “coverage,” such that all locations are visited frequently <cit.>. Instead, in this work, we evaluate patrol policies with respect to a separate but related task: multi-agent dispatch.




The police dispatching problem has traditionally been considered using multi-server priority queues <cit.>. The task of a dispatcher is to select a patroller to dispatch to the scene of an incident. Recent efforts have considered the effects of dispatch policies given positioning and/or routing of patrollers in some space (e.g., a grid or a graph) <cit.>. Oftentimes, the response times to incidents must meet some key performance indicators <cit.>, which has also been considered in the context of dispatch <cit.>.

The positioning of patrollers is key to effective dispatch, yet most dispatch works consider heuristic patrol policies. Early works considering multi-agent patrol (without dispatch) coordinated individual agent patrol decisions using heuristics such as neighboring node idleness <cit.>. Others considered extensions of the single-patroller traveling salesman problem to multiple agents <cit.>. Multi-agent reinforcement learning (MARL) for multi-agent patrolling has also been considered for many years <cit.>; e.g., node idleness can be minimized by independent learners with cooperative rewards. Early RL approaches considered individual patrollers who only had information about their local environment but could communicate with others about intended actions. More recently, multi-agent patrol policies have been learned using Bayesian learning <cit.> and deep RL <cit.>. A common theme is distributed policy optimization with varying degrees of communication between agents, where the goal is to optimize with respect to idleness or frequency of visits to each location.

In addition to a growing need for efficient police operations in light of staffing shortages and limited resources in recent years <cit.>, fairness and equity in operations such as patrol and dispatch is an area of increased interest, and the benefits of such considerations are plentiful. For instance, <cit.> shows that police officers who are perceived to be fair are more likely to observe respect and legitimacy with their community. Moreover, opinions within the US justice system echo the sentiment that fairness in law enforcement is crucial for public cooperation and support <cit.>. The importance of this issue is highlighted by many police departments across the US, often posting statements and procedures regarding fairness in their operations <cit.>. Algorithmic considerations of fairness in police operations typically focus on providing equity in service to multiple groups <cit.>.

To our knowledge, ours is the first work to optimize policies for patrol and dispatch jointly. Our contributions are as follows.

    
    
  * Jointly-optimized policies for patrol and dispatch: Prior dispatch optimization strategies typically assume heuristic patrol policies. Similarly, prior multi-agent patrolling works do not jointly optimize separate decision tasks such as dispatch. We outline a procedure to optimize policies for patrol and dispatch jointly, outperforming benchmark policies optimized for patrol or dispatch alone in addition to heuristic policies such as priority queue dispatch. We demonstrate that the superior performance of our method is robust to a range of simulated environments of varying sizes and dynamics and with different objectives.

    
  * Novel optimization approach: We use distributed MARL with parameter sharing to exploit similarities between patrollers while jointly optimizing a dispatcher agent whose action space has combinatorial cardinality. We extend recent works in combinatorial RL to systems with stochastic transitions. We incorporate them into our MARL framework via a coordinate-descent-style alternating optimization of patrol and dispatch policies.

    
  * Fairness and real service systems: We demonstrate that our approach is flexible to various reward definitions, such as those that encourage equitable policies. Policies that explicitly encode equity in the reward definition yield more balanced responses to groups of different sizes. We also apply our approach to scenarios based on real calls-for-service data.









 §.§ Related works

RL is a machine learning approach for training an agent to make sequential decisions in a stochastic environment <cit.>. Deep RL uses neural networks, such as deep Q networks (DQNs), to learn policies <cit.>. Making decisions for multiple agents is a central issue in MARL, as the number of possible actions is exponential in the number of agents. Independent Q-learning (IQL) <cit.> addresses this by decomposing the problem into multiple single-agent RL problems. Each agent operates in the same environment, but there are no guarantees regarding cooperation and interference; nonetheless, the naive extension of DQNs to the IQL framework has been successful in some cases <cit.>. To address cooperation and efficiency in distributed MARL, parameter sharing in deep RL has been employed <cit.>. Greater degrees of parameter sharing are often most effective between agents with similar value spaces and reward functions.

Multi-agent patrol has been investigated from the perspective of operations research <cit.>, Bayesian learning <cit.>, and (deep) MARL <cit.>. Many of these works pose the problem as a discrete-time, discrete-location graph traversal <cit.>. Past works recognize the inherent complexity of making a centralized decision to patrol many agents and decompose the problem via distributed optimization <cit.>. Similarly, our approach to learning multi-agent patrol policies is distributed while addressing issues arising from the decentralized decision-making for multiple cooperative agents. Additionally, we consider this problem in conjunction with a separate but connected dispatch task, which is not thoroughly addressed in prior work.

Dispatch of multiple patrollers and resources is typically considered from the queueing or ranking systems perspective. <cit.> investigate such a setting using static and dynamic priority queues, connecting to the queuing literature in developing dispatch policies and indicating the static queues yield better performance. For instance, <cit.> construct a ranking system based on quantitative incident characteristics, such as arrival time, priority, and distance to the nearest patroller. Similarly, <cit.> formulates the dispatch decision process by constructing multiple queues, considering incident categories and severity, amongst other factors such as routing of units. Crucially, prior works regarding dispatch in service systems neglect to optimize multi-agent patrol policies, typically assuming basic heuristics.

A typical notion of fairness in machine learning applications suggests that the outcome of an algorithm should be independent of the group to which it is applied <cit.>. In the context of service operations such as police patrol and dispatch, such groups can be defined by socioeconomic or racial status. For example, fairness has been studied in the police districting problem to improve efficiency while mitigating racial disparity in defining patrol districts <cit.>. Parallel works have worked to alleviate disproportionate minority contact that can arise due to hot spot policing <cit.>. Such works find that simply neglecting to take sensitive features (e.g., race or location) into account is ineffective at achieving fairnesss <cit.>. Therefore, these attributes are taken into account in decision-making problems to encode fairness explicitly, often leading to a minimal tradeoff in efficiency.




§ BACKGROUND


This section provides the necessary background information regarding reinforcement learning (RL) and multi-agent reinforcement learning (MARL) as applied to service systems such as police patrol and dispatch.



 §.§ Single-Agent Reinforcement Learning


An infinite-horizon discounted Markov Decision Process (MDP) can be represented by a tuple ⟨𝒮, 𝒜, ℙ, R, γ⟩ with state space 𝒮, action space 𝒜, transition dynamics ℙ:𝒮×𝒜→Δ(𝒮), reward function R:𝒮×𝒜×𝒮→ℝ, and discount γ∈[0,1). The goal of RL <cit.> is to learn a policy π:𝒮→𝒜 maximizing cumulative discounted reward, captured by the value function V^π:𝒮→ℝ:

    V^π(s_0) = 𝔼[∑_t≥0γ^t R(s_t, π(s_t), s_t+1) ],

beginning in state s_0 and following a_t ∼π(s_t), where s_t is the state in period t. A policy that maximizes the value function V^π(s_0) above is called an optimal policy and is denoted by π^⋆. Let V^⋆ be the optimal value function.

It is often more convenient to consider the state-action value (Q-value) in RL:

    Q^π(s_0, a_0) = 𝔼[ R(s_0, a_0, s_1) + ∑_t≥1γ^t R(s_t, π(s_t), s_t+1) ].

The state value V^π(s) and the state-action value Q^π(s, a) are connected by V^π(s) = Q^π(s,π(s)). Let Q^⋆ be the optimal Q-value. 
The optimal policy π^⋆ takes greedy actions with respect to Q^⋆: π^⋆(s) = max_a ∈𝒜Q^⋆(s, a).
Since V^⋆=max_a Q^⋆(s,a), the Bellman optimality equation reveals:

    Q^⋆(s, a) = 𝔼[ R(s, a, s') +  γ V^⋆(s') ].




  §.§.§ Deep Q-Learning.

Q-learning is a model-free RL technique to learn the optimal state-action value function by exploiting the Bellman optimality condition <cit.>. Q^π, approximated by a function parameterized by θ, can be learned given transitions (s_t, a_t, s_t+1, r_t)∈𝒟, where r_t := R(s_t, a_t, s_t+1) and 𝒟 sampled from the MDP. Parameter θ can then be learned by minimizing the least-squares value iteration (LSVI) objective <cit.>:

    θ̂ = θ argmin( ∑_(s_t, a_t, s_t+1, r_t)∈𝒟_ℓ⊂𝒟( r_t + γ a max Q^θ̃(s_t+1, a) - Q^θ(s_t, a_t) )^2 ),

A deep Q-network (DQN) <cit.> Q^θ: ℝ^d →ℝ^|𝒜| is often used as the approximator, taking s∈𝒮⊂ℝ^d and outputting Q^θ(s,a) values for each action. Target networks parameterized by θ̃, a copy of θ cloned every L updates, are often used to stabilize optimization.




  §.§.§ Value Function Approximation.

One might instead want to approximate V^π(s) given policy π. Assume tuples (s_t,r̃_t)∈ℰ are observed, where r̃_t := ∑_t'≥ tγ^t'-t R(s_t',π(s_t'), s_t'+1) is the discounted sum of reward following state s_t under policy π. Value V^π(s) can be approximated by a function V^ϕ parameterized by ϕ to minimize the following objective:

    ϕ̂ = ϕ argmin( ∑_(s_t, r̃_t)∈ℰ(  V^ϕ(s_t) - r̃_t )^2 ).






  §.§.§ Reinforcement Learning with Combinatorial Action Space

If |𝒜| is too large to enumerate (e.g., selection amongst combinatorially-many sets of pairings), Q-learning is not applicable since it must enumerate all action values. Let x_ij=1 if i is paired to j, with x_ij=0 otherwise. Define d_ij the reward for this pairing. Since the optimal action maximizes the current reward plus the next state value <cit.>:

    π(s) = {x_ij} argmax ∑_i
        ∑_j d_ijx_ij + V^π(s'),

subject to problem-specific constraints. If s' can be computed given the action and V^π is approximated as in Section <ref>, actions are selected by solving a mixed-integer program (MIP).





 §.§ Multi-Agent Reinforcement Learning


Given agents i=1,…,N, centralized MARL formulates decision-making as an MDP <cit.>; one agent learns a policy π mapping states to a joint action in 𝒜_1×⋯×𝒜_N. IQL addresses the exponential growth of this joint action space by learning N functions Q^θ_i <cit.>. Agent i operates within the single-agent MDP represented by the tuple ⟨𝒮, 𝒜_i, ℙ_i, R_i, γ_i ⟩. When the agents are similar, parameter sharing can accelerate learning, acting as an intermediate between centralized MARL and IQL <cit.>.

MARL can also be described using a Markov game (MG) <cit.> formulation, defined by a tuple ⟨ N, 𝒮, {𝒮_i}_i=1^N, {𝒜_i}_i=1^N, ℙ, {R_i}_i=1^N, γ⟩, including a universal state space 𝒮, “perspectives" {𝒮_i}_i=1^N, joint action space 𝒜 = 𝒜_1×⋯×𝒜_N, transition dynamics ℙ:𝒮×𝒜→Δ(𝒮), reward functions R_i:𝒮×𝒜×𝒮→ℝ, and discount γ. The goal is to maximize the expected discounted sum of future reward for each agent Ṽ^π_i(s_0) = 𝔼[ ∑_t≥0γ^t R_i(s_t,π(s_t), s_t+1) ], where s_0∈𝒮 is an initial universal state and π=(π_1,…,π_N) is a joint policy. Similarly:

    Q̃^π_i(s_0, a_0) = 𝔼[ R_i(s_0, a_0, s_1) + ∑_t≥1γ^t R_i(s_t, π(s_t), s_t+1) ].

Each Ṽ^π_i is meant to be maximized with respect to all other policies, such that

    π_i=π_i' argmax Ṽ^π'_i  where π'=(π_1, …, π_i',…, π_N).

IQL can be employed to optimize each π_i. Moreover, if {𝒮_i}_i=1^N, {𝒜_i}_i=1^N, and {R_i}_i=1^N are similar among all agents, parameter sharing can be employed to learn the policies.




 §.§ Police Operations

Police jurisdictions are typically hierarchically divided. For example, the Atlanta Police Department (APD) divides the city of Atlanta into six zones, each of which is divided into beats <cit.>. One patroller is usually assigned to each beat. When calls-for-service arrive at the dispatcher, an officer in the same zone as the incident is dispatched to the scene; a patroller can be dispatched to a call outside their assigned beat. This joint problem of beat-based patrol and dispatch is further discussed and formalized in Section <ref>.





§ PROBLEM FORMULATION

Consider patrollers i=1,…,N making decisions in time t=1,2,…. Joint patrol and dispatch is formalized as an MDP with a central agent and then is decomposed into an MG of N+1 agents.







 §.§ The Patrol Problem

Patrollers navigate a connected, undirected graph G=(V,E) <cit.> with nodes/locations V connected by edges E which are traversed in a single iteration; each v∈ V is connected to itself. Each patroller i is assigned to a node subset (beat) V_i, an example is visualized in Figure <ref>. The patrol problem involves travel decisions for each patroller. For patrollers not busy responding to incidents (Sections <ref> and <ref>), a patrol policy directs each patroller to a neighboring node in V_i.





 §.§ The Dispatch Problem

Incidents of categories k=1,…,K arrive with rates λ_k following distributions q_k(v) supported on V, requiring t_ scene∼ Exp(β_k) on-scene time to manage. The dispatch problem involves matching free patrollers (not currently dispatched) to idle incidents (not yet been assigned). A dispatch policy selects among all possible groups of pairings, including leaving incidents idle or patrollers free. A dispatched patroller travels along the shortest path towards the incident, whose number of edges is equivalent to the travel time t_ travel in iterations. If a patroller arrives at iteration t, it is finished managing the incident starting at iteration t+t_ scene.





 §.§ Joint Patrol & Dispatch

The service time for patroller i to manage incident j is t_ service(i,j) = t_ idle(j) + t_ travel(i, j) + t_ scene(j), where t_ idle(j) is the time spent in the queue before dispatch. When patroller i is dispatched, it must travel toward the incident or remain at the scene. When outside its beat, it must return once free. Define the response time, reflecting the time incident j waited before patroller i arrived:

    t_ response(i,j) = t_ idle(j) + t_ travel(i, j).

Joint patrol and dispatch can be formulated as an MDP to learn joint policy π.




  §.§.§ Joint State Space.

Given patroller positions v_1,…,v_N∈ V and busy statuses u_1,…,u_N∈ℕ (travel and on-scene time), define v := [(v_1,u_1),…,(v_N,u_N)]. At dispatch, patrollers observe the random on-scene service time. Given locations of M idle incidents w_1,…,w_M∈ V and idle times p_1,…,p_M∈ℕ, define w := [(w_1,p_1),…,(w_M,p_M)]. The queue has a fixed idle-incident capacity M; when full and a new incident arrives, the longest-waiting incident is replaced. The joint state space is 𝒮 = {s = [ v⊕ w]^T}, where ⊕ refers to vector concatenation.




  §.§.§ Joint Action Space.

For a free patroller, patrol action set 𝒜^( patrol)_i(v_i,t, u_i,t) contains movements to neighboring vertices in V_i. A busy patroller moves towards an incident or stays at the scene, moving back towards its beats afterward. After patrol actions, a dispatch action is selected from the dispatch action set 𝒜^( dispatch)( v'_t,  w'_t). Note, v'_t and w'_t refer to the updated v_t and w_t according to the patrol actions and the incident arrivals. The joint action space is

    𝒜( v_t,  w_t) = 𝒜^ (patrol)_1(v_1,t,u_1,t)×⋯×𝒜^ (patrol)_N(v_N,t,u_N,t)×𝒜^( dispatch)( v'_t,  w'_t).

The patrol action space has exponential cardinality in N, and the dispatch action space has combinatorial cardinality.




  §.§.§ Response-Based Reward & Objective.

The reward function is the negative sum of response times and a penalty for incidents removed from a capacitated queue:

    R(t) = - ( ∑_j  dispatched in iteration  t t_ response(i, j) + ∑_j  removed in iteration  tα· t_ idle(j)  ).

Penalty weight α is a hyper-parameter (α=2 in this work). Given s_0∈,

    π^⋆ (s_0) = π∈Π argmax 𝔼[ ∑_t≥0γ^t R(t)  |  s_t ∼ℙ(s_t-1,π(s_t-1)) ∀ t>0 ].


 


  §.§.§ Markov Game Decomposition.

Patrol and dispatch can be decomposed into an MG with N+1 agents defined by tuple:

    ⟨ N+1,  𝒮,  {𝒮^(patrol)_i}_i=1^N∪𝒮^(dispatch),  {𝒜^(patrol)_i}_i=1^N∪𝒜^(dispatch),  ℙ,  R,  γ⟩.

Patrol agent i corresponds to 𝒜^(patrol)_i(v_i,t,u_i,t) and the dispatch agent corresponds to 𝒜^( dispatch)( v'_t,  w'_t). Similar but distinct state spaces {𝒮^(patrol)_i}_i=1^N are defined so that each patrol agent observes its own perspective, swapping the location and busy status to the first index: v^(i):= [(v_i,u_i),…,(v_i-1,u_i-1),(v_1,u_1),(v_i+1,u_i+1),…,(v_N,u_N)]. This yields 𝒮^(patrol)_i = {s = [ v^(i)⊕ w]^T}. The dispatch agent observes joint state space 𝒮^(dispatch) = 𝒮. Reward R(t) (<ref>) is shared. The goal is to learn patrol policies π^(patrol)_i and dispatch policy π^(dispatch) to minimize the response time while avoiding incidents being removed from the queue.









§ METHODOLOGY

Parameter sharing in deep Q-learning is applied to learn patrol policies for each patroller (Section <ref>), and incidents are assigned to patrollers using a MIP and value function approximation (Section <ref>). These are combined to learn joint policies for patrol and dispatch (Section <ref>).




 §.§ MARL with Parameter Sharing for Patrolling

The MG patrol policies (Section <ref>) are learned using MARL. Recall, in Section <ref>, the state spaces {𝒮^(patrol)_i}_i=1^N are defined to contain the positions and statuses of all patrollers and incidents on the graph, while the action spaces {𝒜^(patrol)_i}_i=1^N contain movements along the graph edges. Furthermore, all patrol agents share a reward R. Based upon prior MARL works indicating that similar agents benefit from parameter sharing <cit.>, this similarity in the state spaces, action spaces, and shared reward suggests that parameter sharing can be applied.

Moreover, since the state spaces and action spaces are nearly identical, we employ an extreme version of parameter sharing in learning the patrol policies. That is, a single neural network Q^θ (parameterized by θ) learns a state-action value function for all agents. Our assumption is that the universal approximation power of a “large enough” neural network has the capacity to jointly learn all patrol policies, which is validated by the performance of the learned patrol policies in the experiments of Section <ref>. We find that DQNs of relatively few layers can learn these policies. Patrol policies thus select actions according to π_i^θ(s_i) = a argmax  Q^θ(s_i,a). Mini-batches of transitions (s_i,t, a_i,t, r_t, s_i,t+1) from each agent's perspective are collected via ϵ-greedy simulation to update Q^θ using LSVI updates.




 §.§ Policy Iteration for Dispatching

A variation of the MIP action selection strategy outlined in Section <ref> is employed for dispatch. Let x_ij=1 if patroller i is assigned to incident j, otherwise let x_ij=0. The first term of reward (<ref>) can be computed given x_ij: ∑_i,j t_ response(i,j)· x_ij. Unlike <cit.>, we cannot directly compute the entire reward, nor can we obtain the transition state deterministically due to incident queue “overflow” resulting from stochastic call arrival dynamics. This factor, and the difference in patroller positions due to the patrol policy, affects the state transition.

Given V^(dispatch) (or an approximation V^ϕ), the next-state value can be approximated. Define the value delta for patroller i as

    δ V^(dispatch)_i(s) := 𝔼[ V^(dispatch)(patroller  i  assigned) - V^(dispatch)(patroller  i  not assigned) ]

and for incident j as

    δ V^(dispatch)_j(s) := 𝔼[ V^(dispatch)(incident  j  assigned) - V^(dispatch)(incident  j  not assigned) ],

where the expectation is taken under the transition dynamics ℙ conditioned upon the policies for patrol and dispatch. These represent beginning in state s and considering the expected change in value for assigning patroller i to some idle incident, with no other assignments made. Given approximators δ V^ϕ_1_i for δ V^(dispatch)_i and δ V^ϕ_2_j for δ V^(dispatch)_j, dispatch is formulated as the MIP:

    π^ϕ(s) =     xargmin     ∑_i=1^N ∑_j=1^M t_ response(i,j)·(x_ij - δ V^ϕ_1_i(s) - δ V^ϕ_2_j(s))
          s.t.     ∑_j=1^M x_ij≤𝕀_{patroller  i  is free}  ∀ i∈{1,…,N}
             ∑_i=1^N x_ij≤𝕀_{incident  j  is idle}  ∀ j∈{1,…,M}
              x_ij∈{0,1}  ∀ i∈{1,…,N},j∈{1,…,M},

where 𝕀_{event} is an indicator for {event}. Notably, given δ V^ϕ_1_i and δ V^ϕ_2_j, this can be computed deterministically given x_ij and the initial state s.

δ V^ϕ_1_i and δ V^ϕ_2_j can be learned by first approximating V^(dispatch) using V^ϕ (Section <ref>). Using V^ϕ, mappings are generated from states to expectations (<ref>)-(<ref>). Approximators δ V^ϕ_1_i and δ V^ϕ_2_j are trained to map states to value deltas. We utilize a policy iteration scheme as in <cit.>; we iterate between updating V^ϕ and updating δ V^ϕ_1_i and δ V^ϕ_2_j using V^ϕ. In practice, one network is learned for patrollers, δ V^ϕ_1, and one network for incidents, δ V^ϕ_2, which have output dimension equal to the number of patrollers and the size of the incident queue, respectively.




 §.§ Joint Patrol & Dispatch Policy 

The joint policy for patrol and dispatch combines the separate patrol and dispatch policies by optimizing their parameters alternatively. As described in Section <ref>, the parameters of the patrol policies are frozen when learning those of the dispatch policy, and vice versa. This alternating procedure is empirically found to converge to effective policies that outperform those optimized for patrol or dispatch alone (see Figure <ref> and Section <ref>).

Given jointly-optimized policies for patrol and dispatch, the policy is deployed as follows: patroller i observes a state and moves according to π_i^θ. Incidents are sampled, and the dispatch agent matches patrollers to incidents according to π^ϕ. R(t) and joint state s_t+1 are finally computed. The dispatcher observes the state as influenced by the patrol policy in the first phase, with reward and subsequent state observed by the patrollers being influenced by the dispatch policy. The assumption that the coordination of the patrollers and the dispatcher is enhanced by a joint optimization is validated by the improved performance of the jointly-optimized policies in our experiments.










  §.§.§ Joint Policy Optimization

We alternatively optimize the parameters defining the patrol and dispatch policies. One phase involves Q-learning of the shared patroller Q^θ, while the other phase involves updates to the incident value networks V^ϕ, δ V_i^ϕ_1, and δ V_j^ϕ_2, repeating to convergence. For outer loop iterations, a number of inner loop updates are made to the dispatcher, followed by a number of inner loop updates to the patrollers. The steps of the n_ inner,ϕ inner loop updates to the dispatcher are: 

    
  (1) collect transitions from on-policy simulation,
    
  (2) conduct n_ epoch,ϕ epochs of training for V^ϕ,
    
  (3) generate “delta transitions” for each delta network using V^ϕ, and 
    
  (4) conduct n_ epoch,ϕ_1=n_ epoch,ϕ_2 epochs of training on each network δ V^ϕ_1 and δ V^ϕ_2.

The steps of the n_ inner,θ inner loop updates to the patrollers are:

    
  (1) collect transitions from ϵ-greedy on-policy simulation and 
    
  (2) conduct n_ epoch,θ epochs of training for Q^θ.

This is repeated for n_ outer outer loop iterations. We find that performance gains from learning dispatch policies are greater than patrol policies, so we begin optimization with a “warm-start” to the dispatch policy consisting of n_ warm dispatch inner loop iterations. For the experiments of Section <ref>, all networks are multi-layer perceptrons (MLPs) using rectified linear unit (ReLU) activation. Dispatch inner loops train using n_ dispatch number of transitions (per inner loop iteration), while patrol inner loops train using n_ patrol transitions. All transitions are split into an 80%/20% train/validation split. The discount factor γ=0.9 in all settings.






§ EXPERIMENTS

The experiments compare joint optimization of patrol and dispatch to policies optimized for patrolling or dispatch alone. In Section <ref>, the goal is to minimize the reward as defined in (<ref>). Then, in Section <ref>, the reward is altered to demonstrate learning of more equitable policies. Finally, a real data example is outlined in Section <ref> based on a region in the City of Atlanta. See Appendix <ref> for a discussion of model selection in each experiment.



  
Baselines & Comparison. 
The three baselines include patrol-only optimization, dispatch-only optimization, and a fully heuristic policy. For policies without optimized patrol, patrollers move randomly in their assigned regions. For policies without optimized dispatch, dispatch follows a first come, first serve priority queue whereby incident class 2 precedes incident class 1, and the closest free patroller is sent to the scene. To compare policies, we evaluate incident response over n_ episode episodes, each consisting of 5,000 iterations of on-policy simulation. The characteristics of the response time distributions are compared in addition to the number of incident queue overflows per episode.











 §.§ Efficient Response Experiments




  
Simulated Settings.
Consider two simulated settings on the same graph consisting of two 7×7 beats adjacent on one edge. Two categories of incident arrive with rates λ_1 and λ_2, uniform distributions q_1 and q_2, and average service times β_1=1 and β_2=3. The incident queue size is 3. In the High Call Volume setting, λ_1=0.15 and λ_2=0.075. In the Low Call Volume setting, λ_1=0.075 and λ_2=0.05.




  
Modeling & Optimization.
Joint optimization is conducted using n_ outer=4 with n_ inner,ϕ=5 and n_ inner,θ=5 and beginning with n_ warm=20. Each dispatch inner loop trains for n_ epochs,ϕ=n_ epochs,ϕ_1=n_ epochs,ϕ_2=25 epochs each for V^ϕ, δ V^ϕ_1, and δ V^ϕ_2. This is conducted over n_ dispatch=1,000 simulated transitions per iteration with batch size 100 and learning rate 10^-3. Each patrol inner loop fixes ϵ=1 (fully random patrol) and trains for n_ epochs,θ=1 epochs for Q^θ, which is conducted over n_ patrol=1.25 million simulated transitions with batch size 50 and learning rate 10^-5. V^ϕ, δ V^ϕ_1, and δ V^ϕ_2 are MLPs of 1 hidden layer with 128 nodes, while Q^θ is an MLP of 2 hidden layers with 512 nodes each. Validation loss is visualized in Figure <ref> for the high call volume setting. The dispatch dynamic is very noisy but still leads to an effective policy. The patrol-only optimization uses n_ inner,θ=20 updates to a patrol Q^θ network. The dispatch-only optimization uses n_ inner,ϕ=50 updates to dispatch networks. All other patrol- and dispatch-only optimization parameters are identical to those of the joint optimization.




  
Results.
Response time distributions are generated using n_ episodes=100. The high call volume experiment results are visualized in Table <ref> and Figure <ref>. The jointly-optimized policy has the fastest response and loses few incidents. This and the dispatch-only optimized policy have similar response distributions. Response times are visualized by category in Figure <ref>(b)-(c); the jointly-optimized policy is best in category 1 with diminished performance in category 2. This could indicate that dispatch optimization yields policies that prefer incidents that take less time to manage (since β_1<β_2), resulting in lower average response times. Table <ref> and Figure <ref> show the low call volume results. The jointly-optimized policy responds more quickly, and all policies lose a similarly small number of calls except for the dispatch-only optimized policy. In this case, the jointly-optimized policy has a similar response time to both categories.













 §.§ Equity-based Reward




  
Simulated Setting.
Figure <ref>(a) visualizes a graph of 119 nodes divided into two beats of 58 and 61 nodes. One incident category arrives with rate λ=0.2 and has average service time β=3. In Figure <ref>(b) and (c), it is revealed that the non-uniform incident distribution induces two groups. The smaller of these groups, Group 1, consists of 20 nodes and has incident probability ten times that of the larger group, Group 2, which consists of 99 nodes.




  
Fairness.
An equity-based reward can be constructed to yield different penalties for each group:

    R̃(t) = - ( ∑_j  dispatched in iteration  tρ_j t_ response(i, j) + ∑_j  removed in iteration  tρ_jα· t_ idle(j)  ),

where ρ_j is the weight of the penalty incurred for the group in which j occurred. Additional metrics can be introduced to quantify fairness. The distribution of response times can be compared between the two groups; connecting to the independent notion of fairness <cit.>, response efficiency should be independent of the group. Similarly, a fair policy could be expected to cover each group for a fraction of iterations equal to the portion of the graph the group represents.




  
Modeling & Optimization.
The networks V^ϕ, δ V^ϕ_1, δ V^ϕ_2, and Q^θ are structured and optimized exactly as in Section <ref>. Jointly-optimized policies trained using equitable reward (<ref>) with different weights are compared. Specifically, the weight of the small group is fixed at ρ_ small=1, and the weight of the large group is ρ_ large∈{0.5, 1.0} representing weighted and unweighted policies, respectively.





  
Results.
Response characteristics are compared using n_ episodes=100. The results are visualized in Table <ref> and Figure <ref>. A discrepancy in average response time between the two groups is observed in all settings, but this is particularly pronounced in the “unfair” optimized setting (ρ_ large=1.0). This discrepancy is about an iteration smaller for the “fair” (ρ_ large=0.5), which is also an improvement over the heuristic. Moreover, the fair policy improves upon the overall response time of the heuristic policy while achieving a better balance in response. Coverage is compared using n_ episodes=25 simulations, and the results are compared in the final column of Table <ref>. The unfair and heuristic policies do a poor job of balancing coverage, while the fair policy does much better to cover the larger group. Appendix <ref> outlines model selection for this section; Figure <ref> reveals that the unfair (ρ_ large=1.0) policy has a large discrepancy in average response throughout training, which is not the case for the fair policy. Both policies can experience similar coverage ratios, but this can come at a cost to a balanced or effective response.
















 §.§ Southwest Atlanta Beats




  
Environment Setting.
The graph environment in this experiment is based upon a 3-beat region in Southwest Atlanta, which is discretized into 154 rectangular partitions representing nodes on the spatial graph. See Figure <ref>(a); the patches are selected based on APD patroller trajectory data discretized into 1-minute intervals. The patches are constructed such that observed trajectories take approximately 1 iteration (i.e., 1 minute) to travel between adjacent patches. In Figure <ref>(b), the resultant graph is shown, which is divided into three beats with one patroller per beat. Finally, as shown in Figure <ref>(c), incidents are spatially distributed according to a distribution estimated given the ∼90k APD calls-for-service from January 1, 2009 to January 8, 2012. The temporal intensity λ=0.25 per iteration and service time β=5 iterations.



  
Real Policy.
An additional baseline is developed for this setting based on limited APD patroller trajectory data. That is, divided into 1-minute time intervals, APD patroller trajectories over a 2-day interval are tracked along the graph structure. Transitions to adjacent nodes are counted, and the resultant policy ranks potential actions according to the frequency with which each edge was traversed in the real trajectory data. This is denoted the “Real Policy,” and can reflect some information about how the police patrol in practice. This policy also uses a first come, first serve queue for dispatch.



  
Modeling & Optimization.
Joint optimization is conducted using n_ outer=8 with n_ inner,ϕ=10 and n_ inner,θ=5 with 0 warm-start iterations. The dispatch networks are trained using n_ dispatch=10,000 simulated transitions per inner loop iteration, while all other optimization parameters for patrol and dispatch are identical to those described in Section <ref>. For comparison, patrol-only optimization uses n_ inner, θ=40 and dispatch-only optimization uses n_ inner,ϕ=80. As before, the patrol- and dispatch-only optimization parameters are identical to those of the joint optimization.



  
Results.
In Figure <ref> and Table <ref>, the response time distributions for each policy are represented over n_ episodes=100 episodes. While the jointly-optimized policy has the fastest response on average, the overall response time distribution characteristics are similar to those of the dispatch-only optimized policy. However, as shown in Figure <ref>(b), the jointly-optimized policy loses substantially fewer incidents per episode than the other policies, indicating that it is the most effective overall policy. Moreover, the jointly-optimized policy leads to faster response and fewer incidents lost than the realistic policy. This suggests that (joint) policy optimization can lead to substantial improvements when applied to real-world environments.






§ CONCLUSION

We have outlined a novel procedure for the joint optimization policies for patrol and dispatch using MARL. The patrol policies are learned using deep Q-learning with parameter sharing, and the dispatch policies are learned using a policy iteration scheme based on MIP action selection. These policies are combined in a joint optimization procedure that follows a coordinate-descent-style scheme, iteratively updating patrol policies given fixed dispatch policy and vice versa. Within this framework, we extend previous works addressing combinatorial action selection in RL via an MIP approach, where our novel procedure facilitates action selection in settings with stochastic state transitions. We comprehensively demonstrate that policies learned using this joint optimization approach outperform those optimized for patrol or dispatch alone, in addition to heuristics such as random patrol and priority-queue-based dispatch.

The experiments of Section <ref> reveal that the joint optimization procedure is robust to settings with a range of incident arrival dynamics. In the high call volume setting, the jointly-optimized policy performs similarly to the dispatch-only optimized policy. In the low call volume setting, the jointly-optimized policy performs similarly to the patrol-only optimized policy. The jointly-optimized policy is the only policy to perform effectively in both settings. In Section <ref>, a modified reward is used to obtain more fair policies than those trained “greedily”. The results reveal that our procedure is flexible to the reward definition and can generate policies that yield more balanced responses and coverage across groups. While there is still much room for improvement according to the equity-based metrics, this represents a promising direction for further research within the framework of joint policy optimization. Finally, Section <ref> suggests that the outlined method applies to real-world scenarios by applying joint policy optimization to a setting based on Southwest Atlanta. A comparison to a realistic policy based on real patroller trajectory data reveals significant improvements in response time distribution characteristics due to policy optimization; particularly, jointly-optimized policies for patrol and dispatch are most effective.

Future work can incorporate additional incident-level information in the decision-making process. For instance, the experiment of Section <ref> indicates that the encoding of group attributes in the reward can lead to a more equitable response. As with prior works considering fairness in police patrol and dispatch, incidents can also include information regarding socioeconomic and racial status, going beyond the geographic location-based fairness demonstrated in this work. Algorithmically, future research can also focus on the incorporation of fairness into the learning procedure itself, drawing inspiration from prior work on fairness in learning for contextual bandits <cit.> and RL <cit.>. Such studies require that certain equity constraints are satisfied throughout the learning process, which could be relevant to online learning of policies for patrol and dispatch.







§ ACKNOWLEDGEMENT


This work is partially supported by an NSF CAREER CCF-1650913, NSF DMS-2134037, CMMI-2015787, CMMI-2112533, DMS-1938106, DMS-1830210, and the Coca-Cola Foundation.

msom/informs2014


















§ MODEL SELECTION




 §.§ Model Selection in Section <ref>

In the experiments of Section <ref>, the desired policy is that which responds to incidents most efficiently. As such, the average response time is tracked over n_ episodes=100 of on-policy validation simulation over the course of optimization for each of the three optimized policies in each setting. This is depicted for the high call volume setting in Figure <ref>(a), which demonstrates that the policies corresponding to the minimum average response time are the jointly-optimized policy after iteration 22, the patrol-only optimized policy after iteration 15, and the dispatch-only optimized policy after iteration 9. Similarly, in the low call volume setting depicted in Figure <ref>(b), the selected policies are the jointly-optimized policy after iteration 35, the patrol-only optimized policy after iteration 19, and the dispatch-only optimized policy after iteration 7.



 §.§ Model Selection in Section <ref>

In the experiment of Section <ref>, the goal is to find a policy that minimizes the difference in average response time between the two groups while balancing coverage. The characteristics of the “unfair” (ρ_ large=1.0) policy over the course of training are depicted in Figure <ref>(a), where coverage is computed using n_ episodes=25 on-policy validation simulations in each iteration, and response time characteristics are computed over n_ episodes=100 simulations (the same is true of the “fair" policy in Figure <ref>(b)). With the goal of this section in mind, the unfairly selected policy corresponds to iteration 66, which has a minimal average difference in response time and comparable coverage to the heuristic policy. The fair policy is chosen similarly - the goal is to balance fair response and fair coverage while still yielding an “effective policy”. With this in mind, while iteration 23 corresponds to the most balanced average response in the top panel of Figure <ref>(b), the policy is not “effective” since there is a very large number of incident queue overflows (bottom panel). Therefore, the fair (ρ_ large=0.5) policy used in Section <ref> corresponds to the optimized policy after iteration 36, which improves upon the balancing of average response time (second panel) while maintaining few overflows of the incident queue (bottom panel) and yielding a better coverage ratio (top panel).



 §.§ Model Selection in Section <ref>

Just as in Section <ref> and Appendix <ref>, in the experiment of Section <ref>, the policy is selected to minimize the average response time. Therefore, this metric is tracked over n_ episodes=100 on-policy simulated episodes throughout the optimization of each policy. This is visualized in Figure <ref>, indicating that the optimal policies are those after iteration 110 for the jointly-optimized policy, after iteration 33 for the patrol-only optimized policy, and after iteration 77 for the dispatch-only optimized policy.















