- Design, Operation and Optimization of Smart Cyber-Physical Systems
Dr. Ayan Mukhopadhyay is a Research Scientist in the Department of Electrical Engineering and Computer Science at Vanderbilt University, USA. Prior to this, he was a Post-Doctoral Research Fellow at the Stanford Intelligent Systems Lab at Stanford University, USA. He was awarded the 2019 CARS post-doctoral fellowship by the Center of Automotive Research at Stanford (CARS). Before joining Stanford, he completed his Ph.D. at Vanderbilt University’s Computational Economics Research Lab, and his doctoral thesis was nominated for the Victor Lesser Distinguished Dissertation Award 2020. His research interests include multi-agent systems, robust machine learning, and decision-making under uncertainty applied to the intersection of CPS and smart cities. His work has been published in several top-tier AI and CPS conferences like AAMAS, UAI, and ICCPS. His work on creating proactive emergency response pipelines has been covered in the government technology magazine, won the best paper award at ICLR’s AI for Social Good Workshop, and covered in multiple smart city symposiums.
Dr. Ayan Mukhopadhyay Publications with ScopeLab
S. Pavia, J. C. M. Mori, A. Sharma, P. Pugliese, A. Dubey, S. Samaranayake, and A. Mukhopadhyay, Designing Equitable Transit Networks. arXiv, 2022.
@misc{sophiefairtransit2022arxiv,
doi = {10.48550/ARXIV.2212.12007},
url = {https://arxiv.org/abs/2212.12007},
author = {Pavia, Sophie and Mori, J. Carlos Martinez and Sharma, Aryaman and Pugliese, Philip and Dubey, Abhishek and Samaranayake, Samitha and Mukhopadhyay, Ayan},
keywords = {Computers and Society (cs.CY), FOS: Computer and information sciences, FOS: Computer and information sciences},
title = {Designing Equitable Transit Networks},
publisher = {arXiv},
year = {2022},
preprint = {https://arxiv.org/abs/2212.12007},
copyright = {arXiv.org perpetual, non-exclusive license}
}
Public transit is an essential infrastructure enabling access to employment, healthcare, education, and recreational facilities. While accessibility to transit is important in general, some sections of the population depend critically on transit. However, existing public transit is often not designed equitably, and often, equity is only considered as an additional objective post hoc, which hampers systemic changes. We present a formulation for transit network design that considers different notions of equity and welfare explicitly. We study the interaction between network design and various concepts of equity and present trade-offs and results based on real-world data from a large metropolitan area in the United States of America.
J. P. Talusan, A. Mukhopadhyay, D. Freudberg, and A. Dubey, On Designing Day Ahead and Same Day Ridership Level Prediction Models for City-Scale Transit Networks Using Noisy APC Data, in 2022 IEEE International Conference on Big Data (Big Data), Los Alamitos, CA, USA, 2022, pp. 5598–5606.
@inproceedings{talusan2022apc,
author = {Talusan, Jose Paolo and Mukhopadhyay, Ayan and Freudberg, Dan and Dubey, Abhishek},
booktitle = {2022 IEEE International Conference on Big Data (Big Data)},
title = {On Designing Day Ahead and Same Day Ridership Level Prediction Models for City-Scale Transit Networks Using Noisy APC Data},
year = {2022},
volume = {},
issn = {},
pages = {5598-5606},
keywords = {training;schedules;statistical analysis;stochastic processes;predictive models;big data;data models},
doi = {10.1109/BigData55660.2022.10020390},
url = {https://doi.ieeecomputersociety.org/10.1109/BigData55660.2022.10020390},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
month = dec
}
The ability to accurately predict public transit ridership demand benefits passengers and transit agencies. Agencies will be able to reallocate buses to handle under or over-utilized bus routes, improving resource utilization, and passengers will be able to adjust and plan their schedules to avoid overcrowded buses and maintain a certain level of comfort. However, accurately predicting occupancy is a non-trivial task. Various reasons such as heterogeneity, evolving ridership patterns, exogenous events like weather, and other stochastic variables, make the task much more challenging. With the progress of big data, transit authorities now have access to real-time passenger occupancy information for their vehicles. The amount of data generated is staggering. While there is no shortage in data, it must still be cleaned, processed, augmented, and merged before any useful information can be generated. In this paper, we propose the use and fusion of data from multiple sources, cleaned, processed, and merged together, for use in training machine learning models to predict transit ridership. We use data that spans a 2-year period (2020-2022) incorporating transit, weather, traffic, and calendar data. The resulting data, which equates to 17 million observations, is used to train separate models for the trip and stop level prediction. We evaluate our approach on real-world transit data provided by the public transit agency of Nashville, TN. We demonstrate that the trip level model based on Xgboost and the stop level model based on LSTM outperform the baseline statistical model across the entire transit service day.
G. Pettet, H. Baxter, S. Vazirizade, H. Purohit, M. Ma, A. Mukhopadhyay, and A. Dubey, Designing Decision Support Systems for Emergency Response: Challenges and Opportunities, in 2022 Workshop on Cyber Physical Systems for Emergency Response (CPS-ER), Los Alamitos, CA, USA, 2022, pp. 30–35.
@inproceedings{pettet2022designing,
author = {Pettet, G. and Baxter, H. and Vazirizade, S. and Purohit, H. and Ma, M. and Mukhopadhyay, A. and Dubey, A.},
booktitle = {2022 Workshop on Cyber Physical Systems for Emergency Response (CPS-ER)},
title = {Designing Decision Support Systems for Emergency Response: Challenges and Opportunities},
year = {2022},
volume = {},
issn = {},
pages = {30-35},
keywords = {decision support systems;road accidents;uncertainty;decision making;medical services;emergency services;hazards},
doi = {10.1109/CPS-ER56134.2022.00012},
url = {https://doi.ieeecomputersociety.org/10.1109/CPS-ER56134.2022.00012},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
month = may
}
Designing effective emergency response management (ERM) systems to respond to incidents such as road accidents is a major problem faced by communities. In addition to responding to frequent incidents each day (about 240 million emergency medical services calls and over 5 million road accidents in the US each year), these systems also support response during natural hazards. Recently, there has been a consistent interest in building decision support and optimization tools that can help emergency responders provide more efficient and effective response. This includes a number of principled subsystems that implement early incident detection, incident likelihood forecasting and strategic resource allocation and dispatch policies. In this paper, we highlight the key challenges and provide an overview of the approach developed by our team in collaboration with our community partners.
S. Eisele, M. Wilbur, T. Eghtesad, K. Silvergold, F. Eisele, A. Mukhopadhyay, A. Laszka, and A. Dubey, Decentralized Computation Market for Stream Processing Applications, in 2022 IEEE International Conference on Cloud Engineering (IC2E), Pacific Grove, CA, USA, 2022.
@inproceedings{eisele2022Decentralized,
author = {Eisele, Scott and Wilbur, Michael and Eghtesad, Taha and Silvergold, Kevin and Eisele, Fred and Mukhopadhyay, Ayan and Laszka, Aron and Dubey, Abhishek},
booktitle = {2022 IEEE International Conference on Cloud Engineering (IC2E)},
title = {Decentralized Computation Market for Stream Processing Applications},
year = {2022},
volume = {},
issn = {},
pages = {},
doi = {},
publisher = {IEEE Computer Society},
address = {Pacific Grove, CA, USA},
month = oct
}
While cloud computing is the current standard for outsourcing computation, it can be prohibitively expensive for cities and infrastructure operators to deploy services. At the same time, there are underutilized computing resources within cities and local edge-computing deployments. Using these slack resources may enable significantly lower pricing than comparable cloud computing; such resources would incur minimal marginal expenditure since their deployment and operation are mostly sunk costs. However, there are challenges associated with using these resources. First, they are not effectively aggregated or provisioned. Second, there is a lack of trust between customers and suppliers of computing resources, given that they are distinct stakeholders and behave according to their own interests. Third, delays in processing inputs may diminish the value of the applications. To resolve these challenges, we introduce an architecture combining a distributed trusted computing mechanism, such as a blockchain, with an efficient messaging system like Apache Pulsar. Using this architecture, we design a decentralized computation market where customers and suppliers make offers to deploy and host applications. The proposed architecture can be realized using any trusted computing mechanism that supports smart contracts, and any messaging framework with the necessary features. This combination ensures that the market is robust without incurring the input processing delays that limit other blockchain based solutions. We evaluate the market protocol using game-theoretic analysis to show that deviation from the protocol is discouraged. Finally, we assess the performance of a prototype implementation based on experiments with a streaming computer-vision application.
Z. Kang, A. Mukhopadhyay, A. Gokhale, S. Wen, and A. Dubey, Traffic Anomaly Detection Via Conditional Normalizing Flow, in 2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC), 2022, pp. 2563–2570.
@inproceedings{kang2022generative,
author = {Kang, Zhuangwei and Mukhopadhyay, Ayan and Gokhale, Aniruddha and Wen, Shijie and Dubey, Abhishek},
booktitle = {2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC)},
title = {Traffic Anomaly Detection Via Conditional Normalizing Flow},
year = {2022},
volume = {},
number = {},
pages = {2563-2570},
doi = {10.1109/ITSC55140.2022.9922061}
}
Traffic congestion anomaly detection is of paramount importance in intelligent traffic systems. The goals of transportation agencies are two-fold: to monitor the general traffic conditions in the area of interest and to locate road segments under abnormal congestion states. Modeling congestion patterns can achieve these goals for citywide roadways, which amounts to learning the distribution of multivariate time series (MTS). However, existing works are either not scalable or unable to capture the spatial-temporal information in MTS simultaneously. To this end, we propose a principled and comprehensive framework consisting of a data-driven generative approach that can perform tractable density estimation for detecting traffic anomalies. Our approach first clusters segments in the feature space and then uses conditional normalizing flow to identify anomalous temporal snapshots at the cluster level in an unsupervised setting. Then, we identify anomalies at the segment level by using a kernel density estimator on the anomalous cluster. Extensive experiments on synthetic datasets show that our approach significantly outperforms several state-of-the-art congestion anomaly detection and diagnosis methods in terms of Recall and F1-Score. We also use the generative model to sample labeled data, which can train classifiers in a supervised setting, alleviating the lack of labeled data for anomaly detection in sparse settings.
V. Nair, K. Prakash, M. Wilbur, A. Taneja, C. Namblard, O. Adeyemo, A. Dubey, A. Adereni, M. Tambe, and A. Mukhopadhyay, ADVISER: AI-Driven Vaccination Intervention Optimiser for Increasing Vaccine Uptake in Nigeria, in 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.
@inproceedings{ijcai22Ayan,
title = {ADVISER: AI-Driven Vaccination Intervention Optimiser for Increasing Vaccine Uptake in Nigeria},
author = {Nair, Vineet and Prakash, Kritika and Wilbur, Michael and Taneja, Aparna and Namblard, Corinne and Adeyemo, Oyindamola and Dubey, Abhishek and Adereni, Abiodun and Tambe, Milind and Mukhopadhyay, Ayan},
doi = {https://doi.org/10.48550/ARXIV.2204.13663},
url = {https://arxiv.org/abs/2204.13663},
booktitle = {31st International Joint Conference on Artificial Intelligence (IJCAI)},
year = {2022},
month = jul
}
More than 5 million children under five years die from largely preventable or treatable medical conditions every year, with an overwhelmingly large proportion of deaths occurring in under-developed countries with low vaccination uptake. One of the United Nations’ sustainable development goals (SDG 3) aims to end preventable deaths of newborns and children under five years of age. We focus on Nigeria, where the rate of infant mortality is appalling. We collaborate with HelpMum, a large non-profit organization in Nigeria to design and optimize the allocation of heterogeneous health interventions under uncertainty to increase vaccination uptake, the first such collaboration in Nigeria. Our framework, ADVISER: AI-Driven Vaccination Intervention Optimiser, is based on an integer linear program that seeks to maximize the cumulative probability of successful vaccination. Our optimization formulation is intractable in practice. We present a heuristic approach that enables us to solve the problem for real-world use-cases. We also present theoretical bounds for the heuristic method. Finally, we show that the proposed approach outperforms baseline methods in terms of vaccination uptake through experimental evaluation. HelpMum is currently planning a pilot program based on our approach to be deployed in the largest city of Nigeria, which would be the first deployment of an AIdriven vaccination uptake program in the country and hopefully, pave the way for other data-driven programs to improve health outcomes in Nigeria.
A. Sivagnanam, S. U. Kadir, A. Mukhopadhyay, P. Pugliese, A. Dubey, S. Samaranayake, and A. Laszka, Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit, in 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.
@inproceedings{sivagnanam2022offline,
title = {Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit},
preprint = {https://arxiv.org/abs/2204.11992},
author = {Sivagnanam, Amutheezan and Kadir, Salah Uddin and Mukhopadhyay, Ayan and Pugliese, Philip and Dubey, Abhishek and Samaranayake, Samitha and Laszka, Aron},
booktitle = {31st International Joint Conference on Artificial Intelligence (IJCAI)},
year = {2022},
month = jul
}
Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider requests as they arrive in real-time. Based on discussions with public transit agencies, we identify a real-world problem that is not addressed by existing formulations: booking trips with flexible pickup windows (e.g., 3 hours) in advance (e.g., the day before) and confirming tight pickup windows (e.g., 30 minutes) at the time of booking. Such a service model is often required in paratransit service settings, where passengers typically book trips for the next day over the phone. To address this gap between offline and online problems, we introduce a novel formulation, the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests—similar to offline VRPs—but must abide by strict constraints on running time—similar to online VRPs. To solve this problem, we propose a novel computational approach, which combines an anytime algorithm with a learning-based policy for real-time decisions. Based on a paratransit dataset obtained from our partner transit agency, we demonstrate that our novel formulation and computational approach lead to significantly better outcomes in this service setting than existing algorithms.
G. Pettet, A. Mukhopadhyay, and A. Dubey, Decision Making in Non-Stationary Environments with Policy-Augmented Monte Carlo Tree Search. 2022.
@misc{pettet2022decision,
title = {Decision Making in Non-Stationary Environments with Policy-Augmented Monte Carlo Tree Search},
author = {Pettet, Geoffrey and Mukhopadhyay, Ayan and Dubey, Abhishek},
year = {2022},
eprint = {2202.13003},
preprint = {https://arxiv.org/abs/2202.13003},
archiveprefix = {arXiv},
primaryclass = {cs.AI}
}
Decision-making under uncertainty (DMU) is present in many important problems. An open challenge is DMU in non-stationary environments, where the dynamics of the environment can change over time. Reinforcement Learning (RL), a popular approach for DMU problems, learns a policy by interacting with a model of the environment offline. Unfortunately, if the environment changes the policy can become stale and take sub-optimal actions, and relearning the policy for the updated environment takes time and computational effort. An alternative is online planning approaches such as Monte Carlo Tree Search (MCTS), which perform their computation at decision time. Given the current environment, MCTS plans using high-fidelity models to determine promising action trajectories. These models can be updated as soon as environmental changes are detected to immediately incorporate them into decision making. However, MCTS’s convergence can be slow for domains with large state-action spaces. In this paper, we present a novel hybrid decision-making approach that combines the strengths of RL and planning while mitigating their weaknesses. Our approach, called Policy Augmented MCTS (PA-MCTS), integrates a policy’s actin-value estimates into MCTS, using the estimates to seed the action trajectories favored by the search. We hypothesize that PA-MCTS will converge more quickly than standard MCTS while making better decisions than the policy can make on its own when faced with nonstationary environments. We test our hypothesis by comparing PA-MCTS with pure MCTS and an RL agent applied to the classical CartPole environment. We find that PC-MCTS can achieve higher cumulative rewards than the policy in isolation under several environmental shifts while converging in significantly fewer iterations than pure MCTS.
M. Wilbur, S. Kadir, Y. Kim, G. Pettet, A. Mukhopadhyay, P. Pugliese, S. Samaranayake, A. Laszka, and A. Dubey, An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services, in ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS), 2022.
@inproceedings{wilbur2022,
title = {An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services},
booktitle = {ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS)},
publisher = {IEEE},
author = {Wilbur, Michael and Kadir, Salah and Kim, Youngseo and Pettet, Geoffrey and Mukhopadhyay, Ayan and Pugliese, Philip and Samaranayake, Samitha and Laszka, Aron and Dubey, Abhishek},
year = {2022},
month = apr
}
Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse—our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to compute near-optimal actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.
G. Pettet, A. Mukhopadhyay, M. J. Kochenderfer, and A. Dubey, Hierarchical Planning for Dynamic Resource Allocation in Smart and Connected Communities, ACM Trans. Cyber-Phys. Syst., vol. 6, no. 4, Nov. 2022.
@article{pettet2021hierarchical,
author = {Pettet, Geoffrey and Mukhopadhyay, Ayan and Kochenderfer, Mykel J. and Dubey, Abhishek},
title = {Hierarchical Planning for Dynamic Resource Allocation in Smart and Connected Communities},
year = {2022},
issue_date = {October 2022},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {6},
number = {4},
issn = {2378-962X},
url = {https://doi-org.proxy.library.vanderbilt.edu/10.1145/3502869},
doi = {10.1145/3502869},
journal = {ACM Trans. Cyber-Phys. Syst.},
month = nov,
articleno = {32},
numpages = {26},
preprint = {https://arxiv.org/abs/2107.01292},
keywords = {planning under uncertainty, semi-Markov decision process, large-scale CPS, hierarchical planning, Dynamic resource allocation}
}
Resource allocation under uncertainty is a classic problem in city-scale cyber-physical systems. Consider emergency response, where urban planners and first responders optimize the location of ambulances to minimize expected response times to incidents such as road accidents. Typically, such problems involve sequential decision making under uncertainty and can be modeled as Markov (or semi-Markov) decision processes. The goal of the decision maker is to learn a mapping from states to actions that can maximize expected rewards. While online, offline, and decentralized approaches have been proposed to tackle such problems, scalability remains a challenge for real world use cases. We present a general approach to hierarchical planning that leverages structure in city level CPS problems for resource allocation. We use emergency response as a case study and show how a large resource allocation problem can be split into smaller problems. We then use Monte Carlo planning for solving the smaller problems and managing the interaction between them. Finally, we use data from Nashville, Tennessee, a major metropolitan area in the United States, to validate our approach. Our experiments show that the proposed approach outperforms state-of-the-art approaches used in the field of emergency response.
A. Mukhopadhyay, G. Pettet, S. M. Vazirizade, D. Lu, A. Jaimes, S. E. Said, H. Baroud, Y. Vorobeychik, M. Kochenderfer, and A. Dubey, A Review of Incident Prediction, Resource Allocation, and Dispatch Models for Emergency Management, Accident Analysis & Prevention, vol. 165, p. 106501, 2022.
@article{mukhopadhyay2021review,
title = {A Review of Incident Prediction, Resource Allocation, and Dispatch Models for Emergency Management},
journal = {Accident Analysis & Prevention},
volume = {165},
pages = {106501},
year = {2022},
issn = {0001-4575},
doi = {https://doi.org/10.1016/j.aap.2021.106501},
url = {https://www.sciencedirect.com/science/article/pii/S0001457521005327},
author = {Mukhopadhyay, Ayan and Pettet, Geoffrey and Vazirizade, Sayyed Mohsen and Lu, Di and Jaimes, Alejandro and Said, Said El and Baroud, Hiba and Vorobeychik, Yevgeniy and Kochenderfer, Mykel and Dubey, Abhishek},
keywords = {Resource allocation for smart cities, Incident prediction, Computer aided dispatch, Decision making under uncertainty, Accident analysis, Emergency response},
preprint = {https://arxiv.org/abs/2006.04200}
}
In the last fifty years, researchers have developed statistical, data-driven, analytical, and algorithmic approaches for designing and improving emergency response management (ERM) systems. The problem has been noted as inherently difficult and constitutes spatio-temporal decision making under uncertainty, which has been addressed in the literature with varying assumptions and approaches. This survey provides a detailed review of these approaches, focusing on the key challenges and issues regarding four sub-processes: (a) incident prediction, (b) incident detection, (c) resource allocation, and (c) computer-aided dispatch for emergency response. We highlight the strengths and weaknesses of prior work in this domain and explore the similarities and differences between different modeling paradigms. We conclude by illustrating open challenges and opportunities for future research in this complex domain.
Y. Senarath, A. Mukhopadhyay, S. Vazirizade, hemant Purohit, S. Nannapaneni, and A. Dubey, Practitioner-Centric Approach for Early Incident Detection Using Crowdsourced Data for Emergency Services, in 21st IEEE International Conference on Data Mining (ICDM 2021), 2021.
@inproceedings{ICDM_2021,
author = {Senarath, Yasas and Mukhopadhyay, Ayan and Vazirizade, Sayyed and hemant Purohit and Nannapaneni, Saideep and Dubey, Abhishek},
booktitle = {21st IEEE International Conference on Data Mining (ICDM 2021)},
tag = {ai4cps,incident},
title = {Practitioner-Centric Approach for Early Incident Detection Using Crowdsourced Data for Emergency Services},
year = {2021}
}
Emergency response is highly dependent on the time of incident reporting. Unfortunately, the traditional approach to receiving incident reports (e.g., calling 911 in the USA) has time delays. Crowdsourcing platforms such as Waze provide an opportunity for early identification of incidents. However, detecting incidents from crowdsourced data streams is difficult due to the challenges of noise and uncertainty associated with such data. Further, simply optimizing over detection accuracy can compromise spatial-temporal localization of the inference, thereby making such approaches infeasible for real-world deployment. This paper presents a novel problem formulation and solution approach for practitioner-centered incident detection using crowdsourced data by using emergency response management as a case-study. The proposed approach CROME (Crowdsourced Multi-objective Event Detection) quantifies the relationship between the performance metrics of incident classification (e.g., F1 score) and the requirements of model practitioners (e.g., 1 km. radius for incident detection). First, we show how crowdsourced reports, ground-truth historical data, and other relevant determinants such as traffic and weather can be used together in a Convolutional Neural Network (CNN) architecture for early detection of emergency incidents. Then, we use a Pareto optimization-based approach to optimize the output of the CNN in tandem with practitioner-centric parameters to balance detection accuracy and spatial-temporal localization. Finally, we demonstrate the applicability of this approach using crowdsourced data from Waze and traffic accident reports from Nashville, TN, USA. Our experiments demonstrate that the proposed approach outperforms existing approaches in incident detection while simultaneously optimizing the needs for realworld deployment and usability.
M. Wilbur, A. Mukhopadhyay, S. Vazirizade, P. Pugliese, A. Laszka, and A. Dubey, Energy and Emission Prediction for Mixed-Vehicle Transit Fleets Using Multi-Task and Inductive Transfer Learning, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2021.
@inproceedings{ecml2021,
author = {Wilbur, Michael and Mukhopadhyay, Ayan and Vazirizade, Sayyed and Pugliese, Philip and Laszka, Aron and Dubey, Abhishek},
title = {Energy and Emission Prediction for Mixed-Vehicle Transit Fleets Using Multi-Task and Inductive Transfer Learning},
booktitle = {Joint European Conference on Machine Learning and Knowledge Discovery in Databases},
year = {2021},
tag = {ai4cps,transit}
}
Public transit agencies are focused on making their fixed-line bus systems more energy efficient by introducing electric (EV) and hybrid (HV) vehicles to their
eets. However, because of the high upfront cost of these vehicles, most agencies are tasked with managing a mixed-fleet of internal combustion vehicles (ICEVs), EVs, and HVs. In managing mixed-fleets, agencies require accurate predictions of energy use for optimizing the assignment of vehicles to transit routes, scheduling charging, and ensuring that emission standards are met. The current state-of-the-art is to develop separate neural network models to predict energy consumption for each vehicle class. Although different vehicle classes’ energy consumption depends on a varied set of covariates, we hypothesize that there are broader generalizable patterns that govern energy consumption and emissions. In this paper, we seek to extract these patterns to aid learning to address two problems faced by transit agencies. First, in the case of a transit agency which operates many ICEVs, HVs, and EVs, we use multi-task learning (MTL) to improve accuracy of forecasting energy consumption. Second, in the case where there is a significant variation in vehicles in each category, we use inductive transfer learning (ITL) to improve predictive accuracy for vehicle class models with insufficient data. As this work is to be deployed by our partner agency, we also provide an online pipeline for joining the various sensor streams for xed-line transit energy prediction. We find that our approach outperforms vehicle-specific baselines in both the MTL and ITL settings.
S. Singla, A. Mukhopadhyay, M. Wilbur, T. Diao, V. Gajjewar, A. Eldawy, M. Kochenderfer, R. Shachter, and A. Dubey, WildfireDB: An Open-Source Dataset ConnectingWildfire Spread with Relevant Determinants, in 35th Conference on Neural Information Processing Systems (NeurIPS 2021) Track on Datasets and Benchmarks, 2021.
@inproceedings{wildfiredb2021,
author = {Singla, Samriddhi and Mukhopadhyay, Ayan and Wilbur, Michael and Diao, Tina and Gajjewar, Vinayak and Eldawy, Ahmed and Kochenderfer, Mykel and Shachter, Ross and Dubey, Abhishek},
booktitle = {35th Conference on Neural Information Processing Systems (NeurIPS 2021) Track on Datasets and Benchmarks},
title = {WildfireDB: An Open-Source Dataset ConnectingWildfire Spread with Relevant Determinants},
tag = {ai4cps,incident},
year = {2021}
}
Modeling fire spread is critical in fire risk management. Creating data-driven models to forecast spread remains challenging due to the lack of comprehensive data sources that relate fires with relevant covariates. We present the first comprehensive and open-source dataset that relates historical fire data with relevant covariates such as weather, vegetation, and topography. Our dataset, named \textitWildfireDB, contains over 17 million data points that capture how fires spread in the continental USA in the last decade. In this paper, we describe the algorithmic approach used to create and integrate the data, describe the dataset, and present benchmark results regarding data-driven models that can be learned to forecast the spread of wildfires.
S. M. Vazirizade, A. Mukhopadhyay, G. Pettet, S. E. Said, H. Baroud, and A. Dubey, Learning Incident Prediction Models Over Large Geographical Areas for Emergency Response Systems, 2021.
@inproceedings{vazirizade2021learning,
title = {Learning Incident Prediction Models Over Large Geographical Areas for Emergency Response Systems},
author = {Vazirizade, Sayyed Mohsen and Mukhopadhyay, Ayan and Pettet, Geoffrey and Said, Said El and Baroud, Hiba and Dubey, Abhishek},
year = {2021},
eprint = {2106.08307},
archiveprefix = {arXiv},
tag = {ai4cps,incident},
preprint = {https://arxiv.org/abs/2106.08307},
primaryclass = {cs.LG}
}
Principled decision making in emergency response management necessitates the use of statistical models that predict the spatial-temporal likelihood of incident occurrence. These statistical models are then used for proactive stationing which allocates first responders across the spatial area in order to reduce overall response time. Traditional methods that simply aggregate past incidents over space and time fail to make useful short-term predictions when the spatial region is large and focused on fine-grained spatial entities like interstate highway networks. This is partially due to the sparsity of incidents with respect to the area in consideration. Further, accidents are affected by several covariates, and collecting, cleaning, and managing multiple streams of data from various sources is challenging for large spatial areas. In this paper, we highlight how this problem is being solved for the state of Tennessee, a state in the USA with a total area of over 100,000 sq. km. Our pipeline, based on a combination of synthetic resampling, non-spatial clustering, and learning from data can efficiently forecast the spatial and temporal dynamics of accident occurrence, even under sparse conditions. In the paper, we describe our pipeline that uses data related to roadway geometry, weather, historical accidents, and real-time traffic congestion to aid accident forecasting. To understand how our forecasting model can affect allocation and dispatch, we improve upon a classical resource allocation approach. Experimental results show that our approach can significantly reduce response times in the field in comparison with current approaches followed by first responders.
G. Pettet, A. Mukhopadhyay, M. Kochenderfer, and A. Dubey, Hierarchical Planning for Resource Allocation in Emergency Response Systems, in Proceedings of the 12th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2021, Nashville, TN, USA, 2021.
@inproceedings{iccps2021,
author = {Pettet, Geoffrey and Mukhopadhyay, Ayan and Kochenderfer, Mykel and Dubey, Abhishek},
title = {Hierarchical Planning for Resource Allocation in Emergency Response Systems},
booktitle = {Proceedings of the 12th {ACM/IEEE} International Conference on Cyber-Physical Systems, {ICCPS} 2021, Nashville, TN, USA},
year = {2021},
tag = {ai4cps,decentralization,incident},
keywords = {emergency},
project = {smart-cities,smart-emergency-response}
}
A classical problem in city-scale cyber-physical systems (CPS) is resource allocation under uncertainty. Spatial-temporal allocation of resources is optimized to allocate electric scooters across urban areas, place charging stations for vehicles, and design efficient on-demand transit. Typically, such problems are modeled as Markov (or semi-Markov) decision processes. While online, offline, and decentralized methodologies have been used to tackle such problems, none of the approaches scale well for large-scale decision problems. We create a general approach to hierarchical planning that leverages structure in city-level CPS problems to tackle resource allocation under uncertainty. We use emergency response as a case study and show how a large resource allocation problem can be split into smaller problems. We then create a principled framework for solving the smaller problems and tackling the interaction between them. Finally, we use real-world data from a major metropolitan area in the United States to validate our approach. Our experiments show that the proposed approach outperforms state-of-the-art approaches used in the field of emergency response.
J. Martinez, A. M. A. Ayman, M. Wilbur, P. Pugliese, D. Freudberg, A. Laszka, and A. Dubey, Predicting Public Transportation Load to Estimate the Probability of Social Distancing Violations, in Proceedings of the Workshop on AI for Urban Mobility at the 35th AAAI Conference on Artificial Intelligence (AAAI-21), 2021.
@inproceedings{juan21,
title = {Predicting Public Transportation Load to Estimate the Probability of Social Distancing Violations},
author = {Martinez, Juan and Ayman, Ayan Mukhopadhyay Afiya and Wilbur, Michael and Pugliese, Philip and Freudberg, Dan and Laszka, Aron and Dubey, Abhishek},
booktitle = {Proceedings of the Workshop on AI for Urban Mobility at the 35th AAAI Conference on Artificial Intelligence (AAAI-21)},
year = {2021},
tag = {transit}
}
Public transit agencies struggle to maintain transit accessibility with reduced resources, unreliable ridership data, reduced vehicle capacities due to social distancing, and reduced services due to driver unavailability. In collaboration with transit agencies from two large metropolitan areas in the USA, we are designing novel approaches for addressing the afore-mentioned challenges by collecting accurate real-time ridership data, providing guidance to commuters, and performing operational optimization for public transit. We estimate rider-ship data using historical automated passenger counting data, conditional on a set of relevant determinants. Accurate ridership forecasting is essential to optimize the public transit schedule, which is necessary to improve current fixed lines with on-demand transit. Also, passenger crowding has been a problem for public transportation since it deteriorates passengers’ wellbeing and satisfaction. During the COVID-19 pandemic, passenger crowding has gained importance since it represents a risk for social distancing violations. Therefore, we are creating optimization models to ensure that social distancing norms can be adequately followed while ensuring that the total demand for transit is met. We will then use accurate forecasts for operational optimization that includes \textit(a) proactive fixed-line schedule optimization based on predicted demand, \textit(b) dispatch of on-demand micro-transit, prioritizing at-risk populations, and \textit(c) allocation of vehicles to transit and cargo trips, considering exigent vehicle maintenance requirements (\textiti.e., disinfection). Finally, this paper presents some initial results from our project regarding the estimation of ridership in public transit.
G. Pettet, A. Mukhopadhyay, M. Kochenderfer, Y. Vorobeychik, and A. Dubey, On Algorithmic Decision Procedures in Emergency Response Systems in Smart and Connected Communities, in Proceedings of the 19th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2020, Auckland, New Zealand, 2020.
@inproceedings{Pettet2020,
author = {Pettet, Geoffrey and Mukhopadhyay, Ayan and Kochenderfer, Mykel and Vorobeychik, Yevgeniy and Dubey, Abhishek},
title = {On Algorithmic Decision Procedures in Emergency Response Systems in Smart and Connected Communities},
booktitle = {Proceedings of the 19th Conference on Autonomous Agents and MultiAgent Systems, {AAMAS} 2020, Auckland, New Zealand},
year = {2020},
tag = {ai4cps, decentralization,incident},
category = {selectiveconference},
keywords = {emergency, performance},
project = {smart-emergency-response,smart-cities},
timestamp = {Wed, 17 Jan 2020 07:24:00 +0200}
}
Emergency Response Management (ERM) is a critical problem faced by communities across the globe. Despite its importance, it is common for ERM systems to follow myopic and straight-forward decision policies in the real world. Principled approaches to aid decision-making under uncertainty have been explored in this context but have failed to be accepted into real systems. We identify a key issue impeding their adoption — algorithmic approaches to emergency response focus on reactive, post-incident dispatching actions, i.e. optimally dispatching a responder after incidents occur. However, the critical nature of emergency response dictates that when an incident occurs, first responders always dispatch the closest available responder to the incident. We argue that the crucial period of planning for ERM systems is not post-incident, but between incidents. However, this is not a trivial planning problem - a major challenge with dynamically balancing the spatial distribution of responders is the complexity of the problem. An orthogonal problem in ERM systems is to plan under limited communication, which is particularly important in disaster scenarios that affect communication networks. We address both the problems by proposing two partially decentralized multi-agent planning algorithms that utilize heuristics and the structure of the dispatch problem. We evaluate our proposed approach using real-world data, and find that in several contexts, dynamic re-balancing the spatial distribution of emergency responders reduces both the average response time as well as its variance.
A. Mukhopadhyay, G. Pettet, C. Samal, A. Dubey, and Y. Vorobeychik, An online decision-theoretic pipeline for responder dispatch, in Proceedings of the 10th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2019, Montreal, QC, Canada, 2019, pp. 185–196.
@inproceedings{Mukhopadhyay2019,
author = {Mukhopadhyay, Ayan and Pettet, Geoffrey and Samal, Chinmaya and Dubey, Abhishek and Vorobeychik, Yevgeniy},
title = {An online decision-theoretic pipeline for responder dispatch},
booktitle = {Proceedings of the 10th {ACM/IEEE} International Conference on Cyber-Physical Systems, {ICCPS} 2019, Montreal, QC, Canada},
year = {2019},
tag = {ai4cps,incident},
pages = {185--196},
bibsource = {dblp computer science bibliography, https://dblp.org},
biburl = {https://dblp.org/rec/bib/conf/iccps/MukhopadhyayPSD19},
category = {selectiveconference},
doi = {10.1145/3302509.3311055},
file = {:Mukhopadhyay2019-An_Online_Decision_Theoretic_Pipeline_for_Responder_Dispatch.pdf:PDF},
keywords = {emergency},
project = {smart-cities,smart-emergency-response},
timestamp = {Sun, 07 Apr 2019 16:25:36 +0200},
url = {https://doi.org/10.1145/3302509.3311055}
}
The problem of dispatching emergency responders to service traffic accidents, fire, distress calls and crimes plagues urban areas across the globe. While such problems have been extensively looked at, most approaches are offline. Such methodologies fail to capture the dynamically changing environments under which critical emergency response occurs, and therefore, fail to be implemented in practice. Any holistic approach towards creating a pipeline for effective emergency response must also look at other challenges that it subsumes - predicting when and where incidents happen and understanding the changing environmental dynamics. We describe a system that collectively deals with all these problems in an online manner, meaning that the models get updated with streaming data sources. We highlight why such an approach is crucial to the effectiveness of emergency response, and present an algorithmic framework that can compute promising actions for a given decision-theoretic model for responder dispatch. We argue that carefully crafted heuristic measures can balance the trade-off between computational time and the quality of solutions achieved and highlight why such an approach is more scalable and tractable than traditional approaches. We also present an online mechanism for incident prediction, as well as an approach based on recurrent neural networks for learning and predicting environmental features that affect responder dispatch. We compare our methodology with prior state-of-the-art and existing dispatch strategies in the field, which show that our approach results in a reduction in response time with a drastic reduction in computational time.
G. Pettet, A. Mukhopadhyay, C. Samal, A. Dubey, and Y. Vorobeychik, Incident management and analysis dashboard for fire departments: ICCPS demo, in Proceedings of the 10th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2019, Montreal, QC, Canada, 2019, pp. 336–337.
@inproceedings{Pettet2019,
author = {Pettet, Geoffrey and Mukhopadhyay, Ayan and Samal, Chinmaya and Dubey, Abhishek and Vorobeychik, Yevgeniy},
title = {Incident management and analysis dashboard for fire departments: {ICCPS} demo},
booktitle = {Proceedings of the 10th {ACM/IEEE} International Conference on Cyber-Physical Systems, {ICCPS} 2019, Montreal, QC, Canada},
year = {2019},
pages = {336--337},
tag = {incident},
bibsource = {dblp computer science bibliography, https://dblp.org},
biburl = {https://dblp.org/rec/bib/conf/iccps/PettetMSDV19},
category = {poster},
doi = {10.1145/3302509.3313329},
file = {:Pettet2019-Incident_management_and_analysis_dashboard_for_fire_departments_ICCPS_demo.pdf:PDF},
keywords = {emergency},
project = {smart-cities,smart-emergency-response},
timestamp = {Sun, 07 Apr 2019 16:25:36 +0200},
url = {https://doi.org/10.1145/3302509.3313329}
}
This work presents a dashboard tool that helps emergency responders analyze and manage spatial-temporal incidents like crime and traffic accidents. It uses state-of-the-art statistical models to learn incident probabilities based on factors such as prior incidents, time and weather. The dashboard can then present historic and predicted incident distributions. It also allows responders to analyze how moving or adding depots (stations for emergency responders) affects average response times, and can make dispatching recommendations based on heuristics. Broadly, it is a one-stop tool that helps responders visualize historical data as well as plan for and respond to incidents.
A. Mukhopadhyay, Y. Vorobeychik, A. Dubey, and G. Biswas, Prioritized Allocation of Emergency Responders based on a Continuous-Time Incident Prediction Model, in Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, 2017, pp. 168–177.
@inproceedings{Mukhopadhyay2017,
author = {Mukhopadhyay, Ayan and Vorobeychik, Yevgeniy and Dubey, Abhishek and Biswas, Gautam},
title = {Prioritized Allocation of Emergency Responders based on a Continuous-Time Incident Prediction Model},
booktitle = {Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, {AAMAS} 2017, S{\~{a}}o Paulo, Brazil, May 8-12, 2017},
year = {2017},
pages = {168--177},
tag = {ai4cps,incident},
bibsource = {dblp computer science bibliography, https://dblp.org},
biburl = {https://dblp.org/rec/bib/conf/atal/MukhopadhyayVDB17},
category = {selectiveconference},
file = {:Mukhopadhyay2017-Prioritized_Allocation_of_Emergency_Responders_based_on_a_Continuous-Time_Incident_Prediction_Model.pdf:PDF},
keywords = {emergency},
project = {smart-emergency-response,smart-cities},
timestamp = {Wed, 27 Sep 2017 07:24:00 +0200},
url = {http://dl.acm.org/citation.cfm?id=3091154}
}
Efficient emergency response is a major concern in densely populated urban areas. Numerous techniques have been proposed to allocate emergency responders to optimize response times, coverage, and incident prevention. Effective response depends, in turn, on effective prediction of incidents occurring in space and time, a problem which has also received considerable prior attention. We formulate a non-linear mathematical program maximizing expected incident coverage, and propose a novel algorithmic framework for solving this problem. In order to aid the optimization problem, we propose a novel incident prediction mechanism. Prior art in incident prediction does not generally consider incident priorities which are crucial in optimal dispatch, and spatial modeling either considers each discretized area independently, or learns a homogeneous model. We bridge these gaps by learning a joint distribution of both incident arrival time and severity, with spatial heterogeneity captured using a hierarchical clustering approach. Moreover, our decomposition of the joint arrival and severity distributions allows us to independently learn the continuous-time arrival model, and subsequently use a multinomial logistic regression to capture severity, conditional on incident time. We use real traffic accident and response data from the urban
area around Nashville, USA, to evaluate the proposed approach, showing that it significantly outperforms prior art as well as the real dispatch method currently in use.
