Problems on decision making under uncertainty
Date
2019
Authors
Sarkale, Yugandhar, author
Chong, Edwin K. P., advisor
Young, Peter, committee member
Luo, J. Rockey, committee member
Zhou, Yongcheng, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
Humans and machines must often make rational choices in the face of uncertainty. Determining decisions, actions, choices, or alternatives that optimize objectives for real-world problems is computationally difficult. This dissertation proposes novel solutions to such optimization problems for both deterministic and stochastic cases; the proposed methods maintain near-optimal solution quality. Even though the applicability of the techniques developed in our work cannot be limited to a few examples, the applications addressed in our work include post-hazard large-scale real-world community recovery management, path planning of UAVs by incorporating feedback from intelligence assets, and closed-loop, urban target tracking in challenging environments. As an illustration of the properties shared by the solutions developed in this dissertation, we will describe the example of community recovery in depth. In the work associated with community recovery, we handle both deterministic and stochastic recovery decisions. For the deterministic problems (outcome of recovery actions is deterministic but we handle the uncertainty in the underlying models), we develop a sequential discrete-time decision-making framework and compute the near-optimal decisions for a community modeled after Gilroy, California. We have designed stochastic models to calculate the damage to the infrastructures systems within the community after an occurrence of an earthquake. Our optimization framework to compute the recovery decisions, which is hazard agnostic (the hazard could be a nuclear explosion or a disruptive social event), is based on an approximate dynamic programming paradigm of rollout; we have modeled the recovery decisions as string of actions. We design several base heuristics pertaining to the problem of community recovery to be used as a base heuristic in our framework; in addition, we also explore the performance of random heuristics. In addition to modeling the interdependence between several networks and the cascading effect of a single recovery action on these networks, we also fuse the traditional optimization approaches, such as simulated annealing, to compute efficient decisions, which mitigates the simultaneous spatial and temporal evolution of the recovery problem. For the stochastic problems, in addition to the previous complexities, the outcome of the decisions is stochastic. Inclusion of this single complexity in the problem statement necessitates an entirely novel way of developing solutions. We formulate the recovery problem in the powerful framework of Markov Decision Processes (MDPs). In contrast to the conventional matrix-based representation, we have formulated our problem as a simulation-based MDP. Classical solutions to solve an MDP are inadequate; therefore, approximation to compute the Q-values (based on Bellman's equation) is necessary. In our framework, we have employed Approximate Policy Improvement to circumvent the limitation with the classical techniques. We have also addressed the risk-attitudes of the policymakers and the decision-makers, who are a key stakeholder in the recovery process. Despite the use of a state-of-the-art computational platform, additional optimization must be made to the resultant stochastic simulation optimization problem owing to the massive size of the recovery problem. Our solutions are calculated using one of the best performing simulation optimization method of Optimal Computing Budget Allocation. Further, in the stochastic setting, scheduling of decisions for the building portfolio recovery is even more computationally difficult than some of the other coarsely-modeled networks like Electric Power Networks (EPN). Our work proposes a stochastic non-preemptive scheduling framework to address this challenging problem at scale. For the stochastic problems, one of the major highlights of this dissertation is the decision-automation framework for EPN recovery. The novel decision-making-under-uncertainty algorithms developed to plan sequential decisions for EPN recovery demonstrate a state-of-the-art performance; our algorithms should be of interest to practitioners in several fields—those that deal with real-world large-scale problem of selecting a single choice given a massive number of alternatives. The quality of recovery decisions calculated using the decision-automation framework does not deteriorate despite a massive increase in the size of the recovery problem. Even though the focus of this dissertation is primarily on application to recovery of communities affected by hazards, our algorithms contributes to the general problem of MDPs with massive action spaces. The primary objective of our work in the community recovery problem is to address the issue of food security. Particularly, we address the objective of making the community food secure to the pre-hazard levels in minimum amount of time or schedule the recovery actions so that maximum number of people are food secure after a sequence of decisions. In essence, our framework accommodates the stochastic hazard models, handles the stochastic nature of outcome of human or machine repair actions, has lookahead, does not suffer from decision fatigue, and incorporates the current policies of the decision makers. The decisions calculated using our framework have been aided by the free availability of a powerful supercomputer.
Description
Rights Access
Subject
decision making under uncertainty
optimization
tracking
MDPs
control
POMDPs