An official website of the United States government
The functioning of interdependent civil infrastructure systems in the aftermath of a disruptive event is critical to the performance and vitality of any modern urban community. Post-event stressors and chaotic circumstances, time limitations, and complexities in the community recovery process highlight the necessity for a comprehensive decision-making framework at the community-level for post-event recovery management. Such a framework must be able to handle large-scale scheduling and decision processes, which involve difficult control problems with large combinatorial decision spaces. This study utilizes approximate dynamic programming algorithms along with heuristics for the identification of optimal community recovery actions following the occurrence of an extreme earthquake event. The proposed approach addresses the curse of dimensionality in its analysis and management of multi-state, large-scale infrastructure systems. Furthermore, the proposed approach can consider the cur-rent recovery policies of responsible public and private entities within the community and shows how their performance might be improved. A testbed community coarsely modeled after Gilroy, California, is utilized as an illustrative example. While the illustration provides optimal policies for the Electrical Power Network serving Gilroy following a severe earthquake, preliminary work shows that the methodology is computationally well suited to other infrastructure systems and hazards.
more »
« less
Solving Markov decision processes for network-level post-hazard recovery via simulation optimization and rollout
Computation of optimal recovery decisions for community resilience assurance post-hazard is a combinatorial decision-making problem under uncertainty. It involves solving a large-scale optimization problem, which is significantly aggravated by the introduction of uncertainty. In this paper, we draw upon established tools from multiple research communities to provide an effective solution to this challenging problem. We provide a stochastic model of damage to the water network (WN) within a testbed community following a severe earthquake and compute near-optimal recovery actions for restoration of the water network. We formulate this stochastic decision-making problem as a Markov Decision Process (MDP), and solve it using a popular class of heuristic algorithms known as rollout. A simulation-based representation of MDPs is utilized in conjunction with rollout and the Optimal Computing Budget Allocation (OCBA) algorithm to address the resulting stochastic simulation optimization problem. Our method employs non-myopic planning with efficient use of simulation budget. We show, through simulation results, that rollout fused with OCBA performs competitively with respect to rollout with total equal allocation (TEA) at a meagre simulation budget of 5-10% of rollout with TEA, which is a crucial step towards addressing large-scale community recovery problems following natural disasters.
more »
« less
- Award ID(s):
- 1638284
- PAR ID:
- 10097438
- Date Published:
- Journal Name:
- 2018 IEEE 14th International Conference on Automation Science and Engineering (CASE)
- Page Range / eLocation ID:
- 906-912
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The functioning of interdependent civil infrastructure systems in the aftermath of a disruptive event is critical to the performance and vitality of any modern urban community. Post-event stressors and chaotic circumstances, time limitations, and complexities in the community recovery process highlight the necessity for a comprehensive decision-making framework at the community-level for post-event recovery management. Such a framework must be able to handle large-scale scheduling and decision processes, which involve difficult control problems with large combinatorial decision spaces. This study utilizes approximate dynamic programming algorithms along with heuristics for the identification of optimal community recovery actions following the occurrence of an extreme earthquake event. The proposed approach addresses the curse of dimensionality in its analysis and management of multi-state, large-scale infrastructure systems. Furthermore, the proposed approach can consider the cur-rent recovery policies of responsible public and private entities within the community and shows how their performance might be improved. A testbed community coarsely modeled after Gilroy, California, is utilized as an illustrative example. While the illustration provides optimal policies for the Electrical Power Network serving Gilroy following a severe earthquake, preliminary work shows that the methodology is computationally well suited to other infrastructure systems and hazards.more » « less
-
Solving Convex Discrete Optimization via Simulation via Stochastic Localization Algorithms Many decision-making problems in operations research and management science require the optimization of large-scale complex stochastic systems. For a number of applications, the objective function exhibits convexity in the discrete decision variables or the problem can be transformed into a convex one. In “Stochastic Localization Methods for Convex Discrete Optimization via Simulation,” Zhang, Zheng, and Lavaei propose provably efficient simulation-optimization algorithms for general large-scale convex discrete optimization via simulation problems. By utilizing the convex structure and the idea of localization and cutting-plane methods, the developed stochastic localization algorithms demonstrate a polynomial dependence on the dimension and scale of the decision space. In addition, the simulation cost is upper bounded by a value that is independent of the objective function. The stochastic localization methods also exhibit a superior numerical performance compared with existing algorithms.more » « less
-
Stochastic SketchRefine: Scaling In-Database Decision-Making under Uncertainty to Millions of TuplesDecision making under uncertainty often requires choosing packages, or bags of tuples, that collectively optimize expected outcomes while limiting risks. Processing Stochastic Package Queries (SPQs) involves solving very large optimization problems on uncertain data. Monte Carlo methods create numerous scenarios, or sample realizations of the stochastic attributes of all the tuples, and generate packages with optimal objective values across these scenarios. The number of scenarios needed for accurate approximation---and hence the size of the optimization problem when using prior methods---increases with variance in the data, and the search space of the optimization problem increases exponentially with the number of tuples in the relation. Existing solvers take hours to process SPQs on large relations containing stochastic attributes with high variance. Besides enriching the SPaQL language to capture a broader class of risk specifications, we make two fundamental contributions toward scalable SPQ processing. First, we propose risk-constraint linearization (RCL), which converts SPQs into Integer Linear Programs (ILPs) whose size is independent of the number of scenarios used. Solving these ILPs gives us feasible and near-optimal packages. Second, we propose Stochastic Sketch Refine, a divide and conquer framework that breaks down a large stochastic optimization problem into subproblems involving smaller subsets of tuples. Our experiments show that, together, RCL and Stochastic Sketch Refine produce high-quality packages in orders of magnitude lower runtime than the state of the art.more » « less
-
Food security can be threatened by extreme natural hazard events for households of all social classes within a community. To address food security issues following a natural disaster, the recovery of several elements of the built environment within a community, including its building portfolio, must be considered. Building portfolio restoration is one of the most challenging elements of recovery owing to the complexity and dimensionality of the problem. This study introduces a stochastic scheduling algorithm for the identification of optimal building portfolio recovery strategies. The proposed approach provides a computationally tractable formulation to manage multi-state, large-scale infrastructure systems. A testbed community modeled after Gilroy, California, is used to illustrate how the proposed approach can be implemented efficiently and accurately to find the near-optimal decisions related to building recovery following a severe earthquake.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
