research-article

Public Access

Hierarchical planning for resource allocation in emergency response systems

Authors:

Geoffrey Pettet,

Ayan Mukhopadhyay,

Mykel J. Kochenderfer,

Abhishek DubeyAuthors Info & Claims

ICCPS '21: Proceedings of the ACM/IEEE 12th International Conference on Cyber-Physical Systems

Pages 155 - 166

https://doi.org/10.1145/3450267.3450543

Published: 19 May 2021 Publication History

Abstract

A classical problem in city-scale cyber-physical systems (CPS) is resource allocation under uncertainty. Typically, such problems are modeled as Markov (or semi-Markov) decision processes. While online, offline, and decentralized approaches have been applied to such problems, they have difficulty scaling to large decision problems. We present a general approach to hierarchical planning that leverages structure in city-level CPS problems for 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 Nashville, Tennessee, a major metropolitan area in the United States, to validate our approach. Our experiments show that the proposed approach out-performs state-of-the-art approaches used in the field of emergency response.

References

[1]

Fouad Baouche, Romain Billot, Rochdi Trigui, and Nour-Eddin El Faouzi. 2014. Efficient allocation of electric vehicles charging stations: Optimization model and application to a dense urban network. IEEE Intelligent Transportation Systems Magazine 6, 3 (2014), 33--43.

[2]

Olfa Chebbi and Jouhaina Chaouachi. 2015. Modeling on-demand transit transportation system using an agent-based approach. In IFIP International Conference on Computer Information Systems and Industrial Management. Springer, 316--326.

Digital Library

[3]

Richard Church and Charles ReVelle. 1974. The maximal covering location problem. In Papers of the Regional Science Association, Vol. 32. Springer-Verlag, 101--118.

[4]

Daniel Claes, Frans Oliehoek, Hendrik Baier, and Karl Tuyls. 2017. Decentralised online planning for multi-robot warehouse commissioning. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 492--500.

[5]

Nashville Fire Department. 2018. Private Communication.

[6]

Erhan Erkut, Armann Ingolfsson, and Güneş Erdoğan. 2008. Ambulance location for maximum survival. 55, 1 (2008), 42--58.

[7]

J-P Forestier and Pravin Varaiya. 1978. Multilayer control of large Markov chains. IEEE Trans. Automat. Control 23, 2 (1978), 298--305.

[8]

Michel Gendreau, Gilbert Laporte, and Frédéric Semet. 1997. Solving an ambulance location model by tabu search. 5, 2 (1997), 75--88.

[9]

Stefan Gössling. 2020. Integrating e-scooters in urban transportation: Problems, policies, and the prospect of system change. Transportation Research Part D: Transport and Environment 79 (2020), 102230.

[10]

Milos Hauskrecht, Nicolas Meuleau, Leslie Pack Kaelbling, Thomas L Dean, and Craig Boutilier. 2013. Hierarchical solution of Markov decision processes using macro-actions. arXiv preprint arXiv:1301.7381 (2013).

[11]

David G Kendall. 1953. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. The Annals of Mathematical Statistics (1953), 338--354.

[12]

Sean K Keneally, Matthew J Robbins, and Brian J Lunday. 2016. A markov decision process model for the optimal dispatch of military medical evacuation assets. Health Care Management Science 19, 2 (2016), 111--129.

[13]

V. A. Knight, P. R. Harper, and L. Smith. 2012. Ambulance allocation for maximal survival with heterogeneous outcome measures. 40, 6 (2012), 918--926.

[14]

Mykel J Kochenderfer. 2015. Decision Making Under Uncertainty: Theory and Application. MIT Press.

Digital Library

[15]

Levente Kocsis and Csaba Szepesvári. 2006. Bandit based monte-carlo planning. In European Conference on Machine Learning (ECML). Springer, 282--293.

Digital Library

[16]

James MacQueen et al. 1967. Some methods for classification and analysis of multivariate observations. In Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1. Oakland, CA, USA, 281--297.

[17]

Jonathan D Mayer. 1979. Emergency medical service: delays, response time and survival. Medical Care (1979), 818--827.

[18]

Ayan Mukhopadhyay, Geoffrey Pettet, Mykel Kochenderfer, and Abhishek Dubey. 2020. Designing Emergency Response Pipelines: Lessons and Challenges. arXiv preprint arXiv:2010.07504 (2020).

[19]

Ayan Mukhopadhyay, Geoffrey Pettet, Chinmaya Samal, Abhishek Dubey, and Yevgeniy Vorobeychik. 2019. An Online Decision-theoretic Pipeline for Responder Dispatch. In International Conference on Cyber-Physical Systems (ICCPS) (Montreal, Quebec, Canada). ACM, 185--196.

Digital Library

[20]

Ayan Mukhopadhyay, Geoffrey Pettet, Sayyed Vazirizade, Yevgeniy Vorobeychik, Mykel Kochenderfer, and Abhishek Dubey. 2020. A Review of Emergency Incident Prediction, Resource Allocation and Dispatch Models. arXiv:2006.04200 [cs.AI]

[21]

Ayan Mukhopadhyay, Yevgeniy Vorobeychik, Abhishek Dubey, and Gautam Biswas. 2017. Prioritized Allocation of Emergency Responders based on a Continuous-Time Incident Prediction Model. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 168--177.

[22]

Ayan Mukhopadhyay, Zilin Wang, and Yevgeniy Vorobeychik. 2018. A Decision Theoretic Framework for Emergency Responder Dispatch. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 588--596.

[23]

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825--2830.

Digital Library

[24]

Geoffrey Pettet, Ayan Mukhopadhyay, Mykel Kochenderfer, Yevgeniy Vorobeychik, and Abhishek Dubey. 2020. On algorithmic decision procedures in emergency response systems in smart and connected communities. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

[25]

Doina Precup and Richard S Sutton. 1998. Multi-time models for temporally abstract planning. In Advances in Neural Information Processing Systems (NIPS). 1050--1056.

[26]

Khashayar Rohanimanesh and Sridhar Mahadevan. 2003. Learning to take concurrent actions. In Advances in Neural Information Processing Systems (NIPS). 1651--1658.

[27]

John F Shortle, James M Thompson, Donald Gross, and Carl M Harris. 2018. Fundamentals of Queueing Theory. Wiley.

[28]

Francisco Silva and Daniel Serra. 2008. Locating emergency services with different priorities: the priority queuing covering location problem. Journal of the Operational Research Society 59, 9 (2008), 1229--1238.

[29]

Richard S Sutton. 1995. TD models: Modeling the world at a mixture of time scales. In International Conference on Machine Learning (ICML). Elsevier, 531--539.

[30]

Constantine Toregas, Ralph Swain, Charles ReVelle, and Lawrence Bergman. 1971. The Location of Emergency Service Facilities. 19 (1971), 1363--1373.

Cited By

Wang SKo RBai GDong NChoi TZhang Y(2024)Evasion Attack and Defense on Machine Learning Models in Cyber-Physical Systems: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2023.334480826:2(930-966)Online publication date: Oct-2025
https://doi.org/10.1109/COMST.2023.3344808
Li JZhang XYao Y(2024)A bi-level robust optimization model for the coupling allocation of post-disaster personnel and materials assistanceJournal of Cleaner Production10.1016/j.jclepro.2024.143099(143099)Online publication date: Jul-2024
https://doi.org/10.1016/j.jclepro.2024.143099
Li MLiu XJiang GLiu W(2024)A novel hierarchical task network planning approach for multi-objective optimizationExpert Systems with Applications10.1016/j.eswa.2024.124058251(124058)Online publication date: Oct-2024
https://doi.org/10.1016/j.eswa.2024.124058
Show More Cited By

Index Terms

Hierarchical planning for resource allocation in emergency response systems

Recommendations

Hierarchical Planning for Dynamic Resource Allocation in Smart and Connected Communities
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 ...
A Dynamic Resource Allocation Approach for Concurrent Emergency Events in Metropolitan Regions
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems

The rescue operations for emergency events usually require multiple emergency departments to cooperate with each other to provide effective and efficient resource allocation plans within a short time limit and dynamically adjust the plans as necessary. ...
A Dynamic Resource Allocation Algorithm for Database-as-a-Service
ICWS '11: Proceedings of the 2011 IEEE International Conference on Web Services

In Database-as-a-Service (DBaaS), a large number of tenants share DBaaS resources (CPU, I/O and Memory). While the DBaaS provider runs DBaaS to "share" resources across the entire tenant population to maximize resource utilization and minimize cost, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCPS '21: Proceedings of the ACM/IEEE 12th International Conference on Cyber-Physical Systems

May 2021

242 pages

ISBN:9781450383530

DOI:10.1145/3450267

General Chairs:
Martina Maggio
Lund University
,
James Weimer
University of Pennsylvania
,
Program Chairs:
Mohammad Al Faruque
University of California at Irvine
,
Meeko Oishi
University of New Mexico

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

In-Cooperation

IEEE-CS\TCRT: TC on Real-Time Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ICCPS '21

Sponsor:

SIGBED

ICCPS '21: ACM/IEEE 12th International Conference on Cyber-Physical Systems

May 19 - 21, 2021

Tennessee, Nashville

Acceptance Rates

Overall Acceptance Rate 25 of 91 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)178
Downloads (Last 6 weeks)21

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang SKo RBai GDong NChoi TZhang Y(2024)Evasion Attack and Defense on Machine Learning Models in Cyber-Physical Systems: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2023.334480826:2(930-966)Online publication date: Oct-2025
https://doi.org/10.1109/COMST.2023.3344808
Li JZhang XYao Y(2024)A bi-level robust optimization model for the coupling allocation of post-disaster personnel and materials assistanceJournal of Cleaner Production10.1016/j.jclepro.2024.143099(143099)Online publication date: Jul-2024
https://doi.org/10.1016/j.jclepro.2024.143099
Li MLiu XJiang GLiu W(2024)A novel hierarchical task network planning approach for multi-objective optimizationExpert Systems with Applications10.1016/j.eswa.2024.124058251(124058)Online publication date: Oct-2024
https://doi.org/10.1016/j.eswa.2024.124058
Zhao YAn ZGao XMukhopadhyay AMa M(2023)Fairguard: Harness Logic-based Fairness Rules in Smart CitiesProceedings of the 8th ACM/IEEE Conference on Internet of Things Design and Implementation10.1145/3576842.3582371(105-116)Online publication date: 9-May-2023
https://dl.acm.org/doi/10.1145/3576842.3582371
Zhao TLi WQin BWang LZomaya A(2023)Pulsed Power Load Coordination in Mission- and Time-critical Cyber-physical SystemsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35731978:1-2(1-27)Online publication date: 7-Mar-2023
https://dl.acm.org/doi/10.1145/3573197
Pettet GMukhopadhyay AKochenderfer MDubey A(2022)Hierarchical Planning for Dynamic Resource Allocation in Smart and Connected CommunitiesACM Transactions on Cyber-Physical Systems10.1145/35028696:4(1-26)Online publication date: 5-Nov-2022
https://dl.acm.org/doi/10.1145/3502869
Pettet GBaxter HVazirizade SPurohit HMa MMukhopadhyay ADubey A(2022)Designing Decision Support Systems for Emergency Response: Challenges and Opportunities2022 Workshop on Cyber Physical Systems for Emergency Response (CPS-ER)10.1109/CPS-ER56134.2022.00012(30-35)Online publication date: May-2022
https://doi.org/10.1109/CPS-ER56134.2022.00012
Mukhopadhyay APettet GVazirizade SLu DJaimes ASaid SBaroud HVorobeychik YKochenderfer MDubey A(2022)A Review of Incident Prediction, Resource Allocation, and Dispatch Models for Emergency ManagementAccident Analysis & Prevention10.1016/j.aap.2021.106501165(106501)Online publication date: Feb-2022
https://doi.org/10.1016/j.aap.2021.106501

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents