dc.description.abstract | Technological advancements in sensors, data collection, and embedded computers have enabled research in societal scale cyber-physical systems (SCPS), also known as Smart Cities. The problem category of interest to this dissertation is the acquisition, allocation, and deployment of spatio-temporal resources across geographical regions. Many problems fall in this area, including emergency response and public transit. In each of these systems, there are resources (ambulances, buses, taxies, etc.) which are dispatched to respond to demand that is distributed over both space and time throughout the city (traffic incidents, ridership requests, etc.). Effective management of such systems is important -- for some systems such as public transit, inefficient deployments can result in increased costs and unhappy users. For others it is safety critical, such as emergency response management. However, traditionally resource management strategies have been limited to reactive algorithms that seek to optimize utility based on the current environment and system state, leading to myopic allocations that are not optimized for future uncertainty.
This dissertation emphasizes the formulation and design of computational procedures necessary to implement proactive management policies. The primary observation is that we need to model how the environment is likely to evolve and account for the impact current decisions will have in the future. Towards this goal the dissertation makes following contributions: (a) Defining an integrated decision support framework for SCPS, (b) creating a clustering-based spatial-temporal forecasting framework to model SCPS environments, (c) creating a decentralized planning approach that is scalable and robust to communication failures, (d) creating a hierarchical planning approach that is scalable while maintaining agent coordination, and (e) creating a hybrid decision-making approach that combines reinforcement learning with online planning. However, this is extremely non-trivial because forecasting models require high spatial-temporal resolution to be useful. This results in extremely sparse and imbalanced data. Further, the spatial regions in which resource allocation systems operate are dynamic and non-stationary. Forecasting and decision models must be able to adapt to a constantly changing real world environment. The approach is principally decision theoretic and makes use of a semi-Markov decision formulation of the problem where generative models trained on highly sparse real-world data are used to estimate future demand.
We demonstrate the effectiveness of the proposed approach with three important resource allocation applications. First, we use emergency response management (ERM) as a case study. In ERM, responders must promptly attend to emergency incidents dispersed across space and time using limited resources. Emergency incident distributions are particularly sparse, and dispatching decisions must be made under heavy time constraints. We use real-world data from the Nashville Fire Department and the Tennessee Department of Transportation to validate our proactive resource allocation and dispatching framework. Second, we apply the approach to the problem of grid-aware electric bus charge scheduling, where we seek to minimize the transit system’s operational costs associated with charging and power grid disruptions while maintaining schedule adherence. Finally, we apply the approach to the Dynamic Vehicle Routing Problem (DVRP) with stochastic trip requests, and validate the approach using data from Chattanooga’s paratransit service. | |