Robust Incident Prediction, Resource Allocation and Dynamic Dispatch
A constant threat that plagues urban areas today are incidents like crimes, fires and traffic accidents. These concerns are further escalated by a rather alarming rise in population density, making these incidents one of the major concerns for governments across the globe. Typically, such incidents are characterized by loss of life, damage to properties and injuries, and are collectively called “emergencies” since they threaten public safety, health, and welfare. This makes it imperative that we create principled methods to tackle such incidents. The domain of emergency response has many sub-problems that each present their own technical challenges. We decomposed the overall problem into three crucial atomic sub-problems - forecasting, resource allocation and dispatch. Through the course of this thesis, we study each of the sub-problems independently, and also look at how they can work together to form a pipeline for emergency response. We start by looking at spatial-temporal incident forecasting approaches that can model incident occurrence in continuous-time. While this problem has been looked at extensively in the literature, there is a lack of principled data-driven and scalable approaches that can accommodate arbitrary risk covariates. We bridge this gap systematically by using Survival Modeling and Multinomial Logistic Regression to learn distributions over incident arrival and severity. We also describe a novel way in which the spatial granularity of such forecasting algorithms can directly be learned from data. A potential issue in forecasting incidents like crimes is that criminals can gain knowledge about policing strategies and alter their behavior. In order to tackle this, we design models of incident prediction that are robust to manipulation in criminal behavior. We describe how such models can capture manipulations made by criminals and present novel algorithmic approaches to solve the formulation. Armed with a model for forecasting incidents, we look at the problem of resource allocation. We present a two-stage optimization problem to allocate police in response to crimes, and describe an iterative algorithmic approach based on Bender's decomposition to solve the problem. To allocate responders to time-critical emergencies, we describe a formulation that maximizes the coverage area of first responders with restrictions on waiting times for accidents. We describe how such formulations are non-trivial to solve and craft specifically designed heuristics that exploit the structure of the problem. Finally, to tackle the problem of dispatching responders as incidents occur, we look at how such problems manifest themselves in semi-Markovian environments, and design algorithmic approaches to solve such problems. In order to balance efficacy of an emergency response pipeline with computational time needed to make decisions, we also describe an online approach for solving the dispatch problem. An important yardstick of judging our work is to evaluate its impact in the field. To this effect, we created a web-based tool to aid emergency responders in the field, and we briefly describe the components of our tool. All our work is evaluated with real emergency response data from Nashville, TN.