Emergency Response Optimization using Online Hybrid Planning

1 Application

The emergency response problem has been well studied in the planning and operations research communites in the last five decades. For example see the comprehensive surveys of [Goldberg, 2004; B´elanger et al., 2015; Aringhieri et al., 2016]. The critical goal is to improve the performance of emergency responders, which is typically measured by the time elapsed between the reporting of the emergency and the arrival of responders. This domain has attracted the attention of many cities, e.g., Melbourne [Maxwell et al., 2014] and London [McCormack and Coates, 2015], in order to counteract the effects of urban sprawl (leading to larger service regions) alongside limited budgets and fewer responders. In this work we study a new domain-independent planning approach to the problem of emergency response. Our online planning approach coupled with a parametrized (relational) domain description provides a flexible tool that can easily be applied to different regions.

Prior research in this domain is traditionally categorized into static and dynamic problems. The static problems concern one-shot (time-invariant) decisions, exemplified by ambulance location and coverage problems [Brotcorne et al.,

∗These authors contributed equally to this work

2003; Bjarnason et al., 2009] evaluated against a fixed dispatch policy. On the other hand, dynamic problems take into account the highly random and time-dependent nature of the demand, the state of the roads, weather conditions and realtime traffic information [Azizan et al., 2013]) and output a set of actions (dispatch or relocation of units) for each emergency. The most commonly used policy is to dispatch the nearest responders in terms of travel-time [Jagtenberg et al., 2015, see Table 2]. Previous work has shown that performance of the online planners dominate this greedy baseline [Haghani et al., 2004; Dean, 2008]. However, these approaches have been domain-specific and the viability of a general on-line data-dependent planning approach remained open.

In principle, online action selection offers a scalable alternative both to global dispatch policy optimization and engineering a parametrized policy space. It allows quick and nearoptimal responses for any given emergency taking into account the subsequent emergencies that may arise in the near future. The emergency domain is naturally formulated as a Hybrid State and Action Markov Decision Process (HSAMDP, [Kveton et al., 2006]). The state space consists of both continuous and discrete random variables that encode the status of all responders and details of the current emergency. Unfortunately the hybrid nature of the state space makes algorithms based on dynamic programming to be intractable in general. The second challenge of the online formulation is the factored action space [Raghavan et al., 2012] that is the cross product of assignments to individual responders.

Our contributions are as follows. First, we encode the emergency response domain in the Relational Dynamic Influence Diagram Language (RDDL) [Sanner, 2011]. Second, we present a sampling approach to generate potentially large number of exogenous event sequences from a modest amount of real world data. Third, we evaluate the performance and scalability of a state of the art algorithm based on hindsight optimization (HOP) [Raghavan et al., 2017] and its variants and compare them to a baseline. Our analysis shows that HOP-based algorithms outperform the widely used nearest available vehicle heuristic both in response time and service rate. It also gives useful insights into the problem such as when withholding of some resources for future emergencies improves performance.

2 HSA-MDP Formulation

A discrete-time MDP is a tuple (S, A, T, R) where S is a state set, A is an action set, T : S × A × S → [0, 1] denotes the stochastic transition function for the next time step such that T(s, a, s′ ) = P(s′ |s, a), and R : S × A → R denotes the state-action reward function. In this paper we focus on finite horizon planning for a specified horizon h with the objective of maximizing the expected total reward over h steps.

In Hybrid State and Action MDPs (HSA-MDPs) [Kveton et al., 2006; Sanner et al., 2012] the state space S and action space A are products of finite sets of state variables X = {X1, . . . , Xl} and action variables A = {A1, . . . , Am} respectively, where each variable is either discrete or continuous. The transition function of the MDP is factored over the state variables, ie. P(s′ |s, a) is represented as a product of conditional probability distributions Pi(qi) = P(X′ i |qi) for i = 1, . . . , l, where qi ⊆ {X,A,X′ }, X′ are the next state variables, and the set of dependencies is acyclic.

2.1. RDDL Representation of Reward and Dynamics

Following recent work on HSA-MDPs [Sanner et al., 2012; Vianna et al., 2015], we use the description language RDDL [Sanner, 2011] to specify HSA-MDPs. RDDL allows for relational templates to specify random variables which are instantiated via a set of objects. As a preprocessing step, we ground the templates with a concrete set of objects and expand relational quantifiers over their finite domains to obtain a propositional HSA-MDP as defined above.

The RDDL source code specifies the factored transition and reward functions through a sequence of assignment and sampling statements that define intermediate variables and next state variables, using algebraic expressions in these definitions. Recent work identified a fragment of RDDL that leads to a linear time reduction of finite horizon hybrid planning to Mixed Integer Linear Programs (MILP) [Raghavan et al., 2017]. We use the same definition of stochastic piecewise linear (PWL) syntax for this work.

3 Online Hybrid Planning using HOP

Hindsight Optimization (HOP) [Chang et al., 2000; Chong et al., 2000] is a computationally attractive heuristic for online action selection. HOP approximates the optimal value function by optimally solving different realizations of random trajectories of the MDP called futures and aggregating their values. Despite its provable suboptimality in some cases, previous work has shown that it performs well in many benchmark probabilistic planning problems [Yoon et al., 2008]. Recent work extended HOP-based algorithms by allowing continuous and discrete variables with state-action dependent stochasticity [Raghavan et al., 2017].

Given a fixed policy, the MDP model induces a distribution over length-h trajectories. Viewing the choice of policy, and the random choices of the MDP as separate processes, we can make the random choices in advance, e.g., by fixing the seed for the random number generator. This selection which produces a random trajectory any given policy is known as a random future.

HOP requires sampling random futures and once the random choices are fixed, a future represents a deterministic planning problem. The optimal value of any state in the MDP is V ∗ h (s0 ) = maxπ Ef [∑ht=0 R(stf , πtf )], which is the maximum expected value over random futures f of length h. In contrast, the hindsight value V hop h (s0 ) = Ef [maxa0f ,...,ahf ∑ht=0 R(stf , atf )] is the expected value of the optimal values of each future. Since a future is deterministic, the maximization is over plans instead of a policies.

HSA-HOP [Raghavan et al., 2017] works by first sampling F futures, and then reducing the RDDL definition in linear time to a Mixed Integer Linear Program (MILP) over action variables Af,t j , where j indexes the action factor, f indexes the future and t indexes the time step. The MILP constraints express the transition functions of the next-state variables in the RDDL model. The objective function of the MILP is the h-step accumulated reward averaged over F futures.

3.1. HOP Variants

We employ three different variants of HOP described in [Raghavan et al., 2017]. We evaluate all these variants through rolling horizon planning, i.e., by planning for h steps, executing the first action, and then replanning.

In the first variant called Consensus no other constraints are added to the above MILP, which means that the plan for each future is independent of other futures. An action is selected by majority vote (ties broken randomly) among the Af,0 j across the futures.

In the second variant called HSA-HOP, the MILP solutions for different futures are made dependent by adding an additional set of constraints to the MILP restricting the action variables at t = 0 to be identical across futures:

When the constraints in Equation 1 are added, the MILP implements a one-step lookahead where the solutions are coupled by requiring the first action to be the same.

The third variant is called a straight line plan and is also known as an open loop policy or conformant plan. It commits to a sequence of future actions regardless of the probabilistic outcomes of earlier actions. This is achieved by replacing the constraint in Equation 1 with

The straight line value converges to the optimal value of the best open loop policy as the number of futures increases. Since in this case we are limiting the set of policies considered, the value of the optimal straight line plan is a lower bound on the optimal value of any state. Note that, although this formulation commits to an entire plan, in our evaluation we still use rolling horizon planning.

4 Emergency Domain : RDDL Encoding

In our formulation 1 , each state presents a new emergency and the action consists of the set of responders to dispatch.

1 https://tinyurl.com/yd22wrjo

State Space: The state space consists of (a) the emergency state (x, y, t, code), where the x, y coordinates in miles represent the location, the continuous variable t > 0 is a floating-point representation of time, and the nature code (code) is a discrete random variable that takes up to 15 distinct values, and (b) the responder state (x(r), y(r), tin(r), tout(r), thome(r)) for each responder r, where (x, y) are the coordinates of the responder's last known location, tin is the absolute time of arrival at the scene of the last emergency, and tout and thome are the expected time of completion of its previous assignment and time of return to its home base respectively.

Action Space : In our simplified setup, each responder can fill exactly one of four roles namely Engine, Ambulance, Ladder and Command. Each MDP action is an assignment to boolean action variables of the form dispatch(responder,role).

When a dispatch action is taken, the responder travels from (x(r), y(r)) to (x, y) at a constant speed. Upon arrival, the responder spends a constant amount of time at the scene that is determined by code (denoted by stay(code)). Depending on code, the responder must additionally proceed to one of two special locations (hospital or transfer) before the assignment is considered complete (denoted by destx and desty). After a mandatory waiting period (denoted by wait(code)) at the end point of the assignment, it returns to its appointed (fixed) home base (denoted by homex and homey). We allow a novel type of redeployment than prior work, specifically we allow a responder to be directly dispatched to a new emergency during this waiting period. We assume wait(code) and stay(code) are constants for any given code.

Travel Time : we assume that the travel time of a responder is a deterministic function of the distance between any two points. Following [Leathrum and Niedner, 2012], we use the city block distance (d = |x1 - x2| + |y1 - y2| between any two points (x1, y1), (x2, y2)).

We model the travel speed as a piecewise constant function with 10 pieces, which leads to a PWL model of the travel time as shown in the following equations.

Depending on the nature of the emergency, the function destx(x,code) (desty(y,code)) returns the xcoordinate (y-coordinate, respectively) of the hospital, transfer location or simply returns x (y, respectively). The transition for x(r) and y(r) are analogous.

Response Time : Following [Bjarnason et al., 2009], the performance of responders is evaluated in terms of first response and full response. The first response δ1 is the time elapsed between the reporting of the emergency and the arrival of the first responder. The full response δ2 is defined as the maximum of the time of arrival of all required responders. The requirements are predefined as a mapping from code to the number of required responders of each role and denoted as required. For example, Code-1 Medical emergency needs one ambulance. The specific constants we use are based on the Code3Sim simulator [Leathrum and Niedner, 2012].

We define the intermediate boolean variable overwhelm to check if the requirement of full response is not met. The overwhelm is set to True, if all required responders are not dispatched to the emergency scene and vice-versa. In the event of an overwhelm, the full response time is set to the maximum possible response time ∆ = 20 Min . These can be represented by the following equations.

Constraints : The following constraints enforce the availability of resources and forward flow of time.

The first constraint is an action precondition to ensure that the responder is either at the scene after completion of the previous assignment (tarry) or is idling at the base station. The second constraint ensures that the number of dispatching responders is less than or equal to the required number for the nature code c. The third constraint ensures that each responder is assigned at most one role. Finally, the fourth constraint ensures the validity of the timers for each responder.

5 Dataset & Sampling Futures

The online planning experiments are carried out using emergency data for Corvallis, USA (pop. ≈ 54k). The dataset has historical emergency calls from 2007 to 2011(≈ 1825 days, ≈ 35,222 calls), each call consists of (x, y) :location, t : time, and severity : type of the emergency.

Recall that the HOP variants work by sampling random futures. Importantly, the factored transition of the emergency state is conditionally independent of the transition of the responder's state. For a random future, given an initial emergency state (x, y, t, code) chosen from the data, the corresponding next emergency state (t′ ) is obtained by a two-step process: (1) build a list of next closest emergencies for each day, i.e, the first emergency that occurs after time (t%24) on that day, and (2) sample one emergency uniformly randomly from this list and return it. This sampling approach assumes emergencies to be independent across days, and allows the creation of synthetic data similar to the real world data without excessive modeling effort.

6 Experiments

Baseline: As mentioned earlier, there are no domainindependent MDP algorithms that can scale to hybrid state and action spaces of high dimensions. Our reference baseline will be the dispatch-closest policy that is used extensively in the literature. The policy works as follows : for each code of current emergency call (Engine, Ambulance, Ladder, Command), the Policy dispatches the closest required responder if the responder is available in service; otherwise it dispatches a random responder. The required number is specified by required(code). The closest responders are identified using the travel time.

Setup : The evaluation is done in online replanning mode, i.e., planning is repeated at every world state and one action is output. The average accumulated reward is evaluated by running 30 trails on a fixed test data (240 calls between Jan 1-15, 2010). The data used for generating futures is sampled from 2400 calls between June 1 to Dec 31, 2010 unless otherwise stated. Each evaluation has three experimental parameters: (1) time limit t per decision in seconds, (2) the lookahead depth (h) = the length of sampled futures, and (3) the number of sampled futures (F) per decision.

In practice, the time limit must be small. In the current scenario, the dispatch must be within two minutes of the received call. We found that for small values of h and F, Gurobi (version 7.5) solves the resulting MILPs optimally for many states in under two minutes.

Multiple Objectives: we compare the real world performance for different choices of the reward function. We employ different linear combinations of δ1 and δ2 as reward = (1 - θ)δ1 + θδ2, for 0 ≤ θ ≤ 1. These two objectives oppose each other because they are coupled via resource constraints.

Figure 1 shows the performance (first response, full response) of baseline and the three HOP-based algorithms with 95% confidence interval. We used 5 responders for this experiment, namely a Command, Engine, Ladder and two Ambulances, lookahead h = 4 and F = 5 futures with 120 seconds being the maximum time allowed for optimization.

The left panel shows that the average first response time of three HOP variants are significantly smaller (by about ≈ 1.5 min) for θ = 0 case compared to baseline, whereas the full response time has similar performance to the closest dispatch policy. The right panel shows overwhelm rates, i.e. the fraction of calls left unanswered. The figure denotes complete overwhelms (δ1 = δ2 = ∆) whenever no responder is dispatched in contrast to a partial overhwelm when δ2 = ∆ and the emergency is not fully satisfied. We observe that the complete overwhelm percentage is smaller, from about 5% of calls for the baseline compared to less than 0.2% with HSAHOP, Straight Line and Consensus except for θ = 1. The fraction of partial overwhelms is similar in percentage compared to the baseline.

Scaling with Fleet Size: Figure 2 shows the performance of the three HOP variants and the baseline when the number of responders is increased to 8, consisting of a Command, three Ambulances, two Engines and two Ladders. We observe a larger improvement with respect to the baseline policy for all three HOP-based algorithms. The mean first response time shows (∼ 1.3 min ) an improvement for θ = 0 case and the full response time shows an ∼ 2.1 min improvement. Similarly, the overwhelm rates of MILP algorithms show significant improvements compared to the baseline policy as shown in the right panel of the figure.

Scaling with Futures: In this experiment, we increased the number of futures linearly by fixing lookahead(h) = 4. Table 1 shows the performance of closest dispatch policy and three variants of HOP using 5 and 8 responders. For the case with 5 responders, we did not observe any improvements in baseline policy, whereas, for 8 responders, the HOP algorithms have shown a significant improvement in test reward ((1-θ)δ1 +θδ2)(∼ 1.3 min) for all the future values. On the other hand, the Consensus Policy has shown an improvement in test reward as the futures are increased and shows its best performance at 20 futures. The HSA-HOP policy performs better for lower number of futures, whereas, the Straight Line policy with 8 responders has shown the best performance at 20 futures.

Scaling with Lookahead: Table 2 shows the performance of the three HOP based algorithms with increasing lookahead steps. For Consensus and HSA-HOP policy with 5 responders, we observe a slight improvement in performance with increasing lookahead from 1 to 4. They did not show improvement after 4 lookahead steps. Moreover, the performance of Straight Line policy with 5 responders also shows no improvement. For responders with 8 vehicles, we observe that lookahead does not improve and performs badly in all the three HOP variants. HOP algorithms perform best for myopic planning (i.e lookahead=1), suggesting that deep lookahead is not needed when there are plenty of resources.

Stress analysis by increasing Emergency calls: In this experiment, we increased the number of calls per day by a factor of ∼ 2. This was a reasonable factor to consider given that we observed the maximum number of emergencies to be ≈ 50 in our dataset. The increase in calls is achieved by learning a model from past 5 years of data (35,222 emergency calls). The procedure followed for generating emergency calls (x, y, t, Code) is a three step process: (a) location variables (x, y) of emergency calls (N = 10,000 samples) were sampled using a fitted Gaussian distribution with parameters µx = 1416.138, σx = 2.69, µy = 64.27 and σy = 3.88. (b) For sampling the time of the event, we used a derived random variable called GapTime (absolute time gap between t and t + 1 event) which was sampled from a Weibull distribution (shape (λ) = 0.914, scale (k) = 0.3). (c) We use a multivariate adaptive regression splines for learning the nature code using location and GapTime as independent features for the model. Table 3 shows the performance comparison of the HOP algorithms and the baseline with 8 responders by varying lookahead under stressed emergency calls. We observe that all the three variants of HOP are performing significantly better than the baseline, closest dispatch policy, in terms of test reward (∼ 2.1 min) and fraction of unanswered calls (∼ 20%). We observe that the consensus performance improves with lookahead steps, whereas the other two variants show no sign of improvement.

7 Discussion

We presented an MDP formulation for the emergency response problem consisting of a hybrid state space and a discrete action space. We demonstrated the application of recently developed domain-independent and online planning algorithms for this problem. Our results show that online planners perform significantly better compared to heuristic policy in a significant region of domain and planner parameters. The overall best performance is achieved with 8 responders in terms of test reward (∼ 1.3 min) and the number of overwhelms (∼ 22 % reduction compared to the closest dispatch).

Overall, all the three variants of HOP perform well with 8 responders compared to 5 responders. With 8 responders, the planners can easily send the required vehicles to the emergency spot, thus showing a huge improvement in terms of unanswered calls. The MILP planners with more responders can use the flexibility of sending fewer vehicles and keep some of the vehicles in available state for serving future emergencies, whereas with fewer responders, the planners have less decisive power to choose between future emergencies and the current emergency. Therefore, with 5 responders, the performance is similar to that of the closest dispatch policy.

We found that, Consensus and HSA-HOP policy perform similarly with fewer futures (F=5), whereas the Straight Line policy has poor performance for all futures values. This is not surprising due to its demanding action constraints. We found that HSA-HOP policy does produce a small fraction (∼ 5 %) of infeasible solutions at 20 futures. This is due to the large optimization problem (with 190,000 variables and 400,000 constraints). We also found that Consensus policy with 8 responders shows a strong consensus ratio of ∼ 79% at 5 futures and the ratio drops down to ∼ 70% for 20 futures. The variation of lookahead did not improve performance significantly. This can be attributed to high uncertainty of emergency calls (x, y, t, code). For large lookahead steps, we found that the planners take suboptimal actions for the current emergency by sending high response time vehicles. But, this sacrifice is not always helpful due to the stochastic nature of future emergencies. The experiment with increasing the frequency of emergency calls reinforces the success of using online planners. The planners show a significant increase in performance in terms of test reward (∼ 1.4 min) as well as partial overwhelm rate (∼ 20 %) except for the Straight Line policy at lookahead = 4. The difference in full response time between the HOP variants and the closest dispatch is ∼ 2.2 min, which shows that, unlike the baseline policy, the HOPbased planners are able to save some vehicles for potential future dispatches by not dispatching them to satisfy the current request.

Acknowledgements

This work is supported by NSF under grant nos. IIS-1619433 and CNS-1406049 and by DARPA under grant no. N6600117-2-4030. We thank Carl Niedner of Coele Company of Design and the Corvallis Fire Department for their advice and sharing of data.