Decentralized Decision Making for the Restoration of Interdependent Networks
Publication: ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 6, Issue 2
Abstract
This study introduces tractable algorithms to model the decentralized decision-making process for postdisaster restoration of interdependent networks. Restoration strategies are devised by a host of agents, who control different layers of interdependent networks. Because of interdependencies, each agent’s decisions are impacted by other agents’ decisions. However, agents communicate poorly in real-world settings—particularly after contingencies—and therefore, they cannot access all the information that is necessary in order to make a decision; instead, they compensate with their expert judgment. We propose the notion of Judgment Call to model this practical human contrivance. We explore several types of judgment, including pure random judgment, optimistic judgment, and judgments guided by importance measures. The performance of the method is compared to optimal solutions applied to a database of ideal networks that contains different configurations of random, scale-free, and grid networks. In addition, we apply the method to the interdependent infrastructure network of Shelby County, Tennessee, as a realistic case study. The results show that the method performs best when there is no randomness in the decentralized judgment process, which highlights the need to improve communication, monitoring, and modeling of distributed systems in order to reduce uncertainties. Moreover, the results show that interdependency density and resource availability influence the performance of the Judgment Call method the most. These insights are key for decision support in the practice of postdisaster recovery and community resilience.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code generated or used during the study are available from the authors by request.
Acknowledgments
The authors gratefully acknowledge the support of the US Department of Defense (Grant No. W911NF-13-1-0340) and the US National Science Foundation (Grant No. CMMI-1541033).
References
Adachi, T., and B. R. Ellingwood. 2009. “Serviceability assessment of a municipal water system under spatially correlated seismic intensities.” Comput. Aided Civ. Infrastruct. Eng. 24 (4): 237–248. https://doi.org/10.1111/j.1467-8667.2008.00583.x.
Alemzadeh, S., and M. Mesbahi. 2018. “Influence models on layered uncertain networks: A guaranteed-cost design perspective.” Preprint, submitted July 17, 2018. https://arxiv.org/abs/1807.06612.
Amaral, L. A. N., and J. M. Ottino. 2004. “Complex networks.” Eur. Phys. J. B Condens. Matter 38 (2): 147–162. https://doi.org/10.1140/epjb/e2004-00110-5.
Åström, K. J. 1965. “Optimal control of Markov processes with incomplete state information.” J. Math. Anal. Appl. 10 (1): 174–205. https://doi.org/10.1016/0022-247X(65)90154-X.
Barbosa, R. D. P., A. Ene, H. L. Nguyen, and J. Ward. 2015. “The power of randomization: Distributed submodular maximization on massive datasets.” Preprint, submitted on February 9, 2015. https://arxiv.org/abs/1502.02606.
Bellman, R. 1957. “A Markovian decision process.” J. Math. Mech. 6 (5): 679–684.
Bernstein, D. S., R. Givan, N. Immerman, and S. Zilberstein. 2002. “The complexity of decentralized control of Markov decision processes.” Math. Oper. Res. 27 (4): 819–840. https://doi.org/10.1287/moor.27.4.819.297.
Bollobás, B., C. Borgs, J. Chayes, and O. Riordan. 2003. “Directed scale-free graphs.” In Proc., 14th Annual ACMSIAM Symp. on Discrete Algorithms, 132–139. Philadelphia: Society for Industrial and Applied Mathematics.
Box, G. E. P., and G. C. Tiao. 1973. Bayesian inference in statistical analysis. Boston, MA: Addison-Wesley.
Boyd, S. 2010. “Distributed optimization and statistical learning via the alternating direction method of multipliers.” Found. Trends Mach. Learn. 3 (1): 1–122. https://doi.org/10.1561/2200000016.
Bruneau, M., S. E. Chang, R. T. Eguchi, G. C. Lee, T. D. O’Rourke, A. M. Reinhorn, M. Shinozuka, K. Tierney, W. A. Wallace, and D. Von Winterfeldt. 2003. “A framework to quantitatively assess and enhance the seismic resilience of communities.” Earthquake Spectra 19 (4): 733–752. https://doi.org/10.1193/1.1623497.
Buldyrev, S. V., R. Parshani, G. Paul, H. E. Stanley, and S. Havlin. 2010. “Catastrophic cascade of failures in interdependent networks.” Nature 464 (7291): 1025–1028. https://doi.org/10.1038/nature08932.
Cavdaroglu, B., E. Hammel, J. E. Mitchell, T. C. Sharkey, and W. A. Wallace. 2013. “Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems.” Ann. Oper. Res. 203 (1): 279–294. https://doi.org/10.1007/s10479-011-0959-3.
Chang, S., H. Seligson, and R. Eguchi. 1996. Estimation of the economic impact of multiple lifeline disruption: Memphis light, gas and water division case study. Buffalo, NY: Multidisciplinary Center for Earthquake Engineering Research.
Cressie, N., and C. K. Wikle. 2015. Statistics for spatio-temporal data. New York: Wiley.
Dantzig, G. B., and P. Wolfe. 1960. “Decomposition principle for linear programs.” Oper. Res. 8 (1): 101. https://doi.org/10.1287/opre.8.1.101.
Dueñas-Osorio, L., J. I. Craig, B. J. Goodno, and A. Bostrom. 2007. “Interdependent response of networked systems.” J. Infrastruct. Syst. 13 (3): 185–194. https://doi.org/10.1061/(ASCE)1076-0342(2007)13:3(185).
Efron, B., and R. Tibshirani. 1986. “Bootstrap methods for standard errors, confidence intervals, and other methods of statistical accuracy.” Stat. Sci. 1 (1): 54–75. https://doi.org/10.1214/ss/1177013815.
Erdös, P., and A. Rényi. 1959. “On random graphs.” Publicationes Mathematicae 6 (6): 290–297.
Farahani, R. Z., E. Miandoabchi, W. Szeto, and H. Rashidi. 2013. “A review of urban transportation network design problems.” Eur. J. Oper. Res. 229 (2): 281–302. https://doi.org/10.1016/j.ejor.2013.01.001.
Feizollahi, M. J. 2015. “Large-scale unit commitment: Decentralized mixed integer programming approaches.” Ph.D. dissertation, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology.
Gelman, A., J. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and D. B. Rubin. 1995. Bayesian data analysis. London: Chapman and Hall/CRC.
Gelman, A., and D. B. Rubin. 1992. “Inference from iterative simulation using multiple sequences.” Stat. Sci. 7 (4): 457–472. https://doi.org/10.1214/ss/1177011136.
González, A. D., A. Chapman, L. Dueñas-Osorio, M. Mesbahi, and R. M. D’Souza. 2017. “Efficient infrastructure restoration strategies using the recovery operator.” Comput. Aided Civ. Infrastruct. Eng. 32 (12): 991–1006. https://doi.org/10.1111/mice.12314.
González, A. D., L. Dueñas-Osorio, A. L. Medaglia, and M. Sánchez-Silva. 2016a. “The time-dependent interdependent network design problem (td-INDP) and the evaluation of multi-system recovery strategies in polynomial time.” In Proc., 6th Asian-Pacific Symp. on Structural Reliability and Its Applications, 544–550. Shanghai, China: Tongji Univ.
González, A. D., L. Dueñas-Osorio, M. Sánchez-Silva, and A. L. Medaglia. 2016b. “The interdependent network design problem for optimal infrastructure system restoration.” Comput. Aided Civ. Infrastruct. Eng. 31 (5): 334–350. https://doi.org/10.1111/mice.12171.
Hernandez-Fajardo, I., and L. Dueñas-Osorio. 2011. “Sequential propagation of seismic fragility across interdependent lifeline systems.” Earthquake Spectra 27 (1): 23–43. https://doi.org/10.1193/1.3544052.
Hoffman, M. D., and A. Gelman. 2011. “The no-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo.” Preprint, submitted November 18, 2011. https://arxiv.org/abs/1111.4246.
Johnson, D. S., J. K. Lenstra, and A. H. G. R. Kan. 1978. “The complexity of the network design problem.” Networks 8 (4): 279–285. https://doi.org/10.1002/net.3230080402.
Karabulut, E. 2017. “Distributed integer programming.” Ph.D. dissertation, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology.
Lee, E. E., II, J. E. Mitchell, W. A. Wallace, E. E. Lee, J. E. Mitchell, and W. A. Wallace. 2007. “Restoration of services in interdependent infrastructure systems: A network flows approach.” IEEE Trans. Syst. Man Cybernetics, Part C (Appl. Rev.) 37 (6): 1303–1317. https://doi.org/10.1109/TSMCC.2007.905859.
Ling, Q., W. Shi, G. Wu, and A. Ribeiro. 2015. “DLM: Decentralized linearized alternating direction method of multipliers.” IEEE Trans. Signal Process. 63 (15): 4051–4064. https://doi.org/10.1109/TSP.2015.2436358.
Metropolis, N., A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. 1953. “Equation state calculations by fast computing machines.” J. Chem. Phys. 21 (6): 1087–1092. https://doi.org/10.1063/1.1699114.
Miller, M., and J. Baker. 2015. “Ground-motion intensity and damage map selection for probabilistic infrastructure network risk assessment using optimization.” Earthquake Eng. Struct. Dyn. 44 (7): 1139–1156. https://doi.org/10.1002/eqe.2506.
Mirzasoleiman, B., R. Sarkar, A. Karbasi, and A. Krause. 2013. “Distributed submodular maximization: Identifying representative elements in massive data.” Adv. Neural Inf. Process. Syst. 26: 2049–2057.
Nasrazadani, H., M. Mahsuli, H. Talebiyan, and H. Kashani. 2017. “Probabilistic modeling framework for prediction of seismic retrofit cost of buildings.” J. Constr. Eng. Manage. 143 (8): 04017055. https://doi.org/10.1061/(ASCE)CO.1943-7862.0001354.
National Academies of Sciences, Engineering, and Medicine. 2017. “Enhancing the resilience of the nation’s electricity system.” Washington, DC: National Academies Press.
Nedic, A., and D. P. Bertsekas. 2001. “Incremental subgradient methods for nondifferentiable optimization.” SIAM J. Optim. 12 (1): 109–138. https://doi.org/10.1137/S1052623499362111.
Nedic, A., and A. Ozdaglar. 2009. “Distributed subgradient methods for multi-agent optimization.” IEEE Trans. Autom. Control 54 (1): 48–61. https://doi.org/10.1109/TAC.2008.2009515.
Nemhauser, G. L., L. A. Wolsey, and M. L. Fisher. 1978. “An analysis of approximations for maximizing submodular set functions-I.” Math. Program. 14 (1): 265–294. https://doi.org/10.1007/BF01588971.
Ouyang, M. 2014. “Review on modeling and simulation of interdependent critical infrastructure systems.” Reliab. Eng. Syst. Saf. 121 (Jan): 43–60. https://doi.org/10.1016/j.ress.2013.06.040.
Polson, N. G., and J. G. Scott. 2012. “On the half-Cauchy prior for a global scale parameter.” Bayesian Anal. 7 (4): 887–902. https://doi.org/10.1214/12-BA730.
Poss, M. 2012. “Models and algorithms for network design problems.” 4OR 10 (2): 215–216. https://doi.org/10.1007/s10288-011-0174-8.
Rabbat, M., and R. Nowak. 2004. “Distributed optimization in sensor networks.” In Proc., 3rd Int. Symp. on Information Processing in Sensor Networks—IPSN’04, 20. New York: ACM Press.
Rinaldi, S. M., J. P. Peerenboom, and T. K. Kelly. 2001. “Identifying, understanding, and analyzing critical infrastructure interdependencies.” IEEE Control Syst. Mag. 21 (6): 11–25. https://doi.org/10.1109/37.969131.
Rosenblatt, M. 1956. “Remarks on some nonparametric estimates of a density function.” Ann. Math. Statistics 27 (3): 832–837. https://doi.org/10.1214/aoms/1177728190.
Scott, D. W. 1979. “On optimal and data-based histograms.” Biometrika 66 (3): 605–610. https://doi.org/10.1093/biomet/66.3.605.
Seuken, S., and S. Zilberstein. 2008. “Formal models and algorithms for decentralized decision making under uncertainty.” Auton. Agents Multi-Agent Syst. 17 (2): 190–250. https://doi.org/10.1007/s10458-007-9026-5.
Sharkey, T. C., B. Cavdaroglu, H. Nguyen, J. Holman, J. E. Mitchell, and W. A. Wallace. 2015. “Interdependent network restoration: On the value of information-sharing.” Eur. J. Oper. Res. 244 (1): 309–321. https://doi.org/10.1016/j.ejor.2014.12.051.
Shi, W., Q. Ling, G. Wu, and W. Yin. 2015. “EXTRA: An exact first-order algorithm for decentralized consensus optimization.” SIAM J. Optim. 25 (2): 944–966. https://doi.org/10.1137/14096668X.
Singh, G., and C. M. O’Keefe. 2016. “Decentralised scheduling with confidentiality protection.” Oper. Res. Lett. 44 (4): 514–519. https://doi.org/10.1016/j.orl.2016.05.004.
Song, J., and S. Y. Ok. 2010. “Multi-scale system reliability analysis of lifeline networks under earthquake hazards.” Earthquake Eng. Struct. Dyn. 39 (3): 259–279. https://doi.org/10.1002/eqe.938.
Talebiyan, H., and L. Duenas-Osorio. 2019. “Probabilistic assessment of decentralized decision-making for interdependent network restoration.” In Proc., 13th Int. Conf. on Applications of Statistics and Probability in Civil Engineering (ICASP13). Seoul: Seoul National Univ.
Tsitsiklis, J. N. 1984. “Problems in decentralized decision making and computation.” Ph.D. dissertation, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.
Tsitsiklis, J. N., D. Bertsekas, and M. Athans. 1986. “Distributed asynchronous deterministic and stochastic gradient optimization algorithms.” IEEE Trans. Autom. Control 31 (9): 803–812. https://doi.org/10.1109/TAC.1986.1104412.
Viswanath, K., and S. Peeta. 2003. “Multicommodity maximal covering network design problem for planning critical routes for earthquake response.” Transp. Res. Rec. 1857 (1): 1–10. https://doi.org/10.3141/1857-01.
Waslander, S. L., G. Inalhan, and C. J. Tomlin. 2004. “Decentralized optimization via Nash bargaining.” In Vol. 4 of Theory and algorithms for cooperative systems, 565–585. Singapore: World Scientific.
Wong, R. T. 1978. A survey of network design problems. Boston: Operations Research Center.
Wu, J. 2017. “End-to-end seismic risk analysis framework for the identification of infrastructure network retrofits.” Ph.D. dissertation, Dept. of Civil and Environmental Engineering, Stanford Univ.
Xiao, L., and S. Boyd. 2004. “Fast linear iterations for distributed averaging.” Syst. Control Lett. 53 (1): 65–78. https://doi.org/10.1016/j.sysconle.2004.02.022.
Zhang, Z., and M.-Y. Chow. 2012. “Convergence analysis of the incremental cost consensus algorithm under different communication network topologies in a smart grid.” IEEE Trans. Power Syst. 27 (4): 1761–1768. https://doi.org/10.1109/TPWRS.2012.2188912.
Information & Authors
Information
Published In
ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 6 • Issue 2 • June 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Dec 15, 2018
Accepted: Jun 12, 2019
Published online: Feb 11, 2020
Published in print: Jun 1, 2020
Discussion open until: Jul 11, 2020
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.