Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Markov process”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3

Mean-Variance Problems for Finite Horizon Semi-Markov Decision Processes

This paper deals with a mean-variance problem for finite horizon semi-Markov decision processes. The state and action spaces are Borel spaces, while the reward function may be unbounded. The goal is to seek an optimal policy with minimal finite horizon reward variance over the set of policies with a given mean. Using the theory of N-step contraction, we give a characterization of policies with a given mean and convert the second order moment of the finite horizon reward to a mean of an infinite horizon reward/cost generated by a discrete-time Markov decision processes (MDP) with a two dimension state space and a new one-step reward/cost under suitable conditions. We then establish the optimality equation and the existence of mean-variance optimal policies by employing the existing results of discrete-time MDPs. We also provide a value iteration and a policy improvement algorithms for computing the value function and mean-variance optimal policies, respectively. In addition, a linear program and the dual program are developed for solving the mean-variance problem.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Performability analysis using semi-Markov reward processes

Beaudry (1978) proposed a simple method of computing the distribution of performability in a Markov reward process. Two extensions of Beaudry's approach are presented. The method is generalized to a semi-Markov reward process by removing the restriction requiring the association of zero reward to absorbing states only. The algorithm proceeds by replacing zero-reward nonabsorbing states by a probabilistic switch; it is therefore related to the elimination of vanishing states from the reachability graph of a generalized stochastic Petri net and to the elimination of fast transient states in a decomposition approach to stiff Markov chains. The use of the approach is illustrated with three applications.

Ciardo, Gianfranco↗

Markov Decision Process based Trajectory Planning for UAVs under Uncertain Wind Conditions

In this paper we propose a Markov Decision Process (MDP) algorithm for path-planning of Unmanned Aviation Vehicles (UAVs) under varying wind conditions. Solutions to path-planning for UAVs are becoming increasingly necessary as autonomous UAVs continue to enter commercial and government spaces. Path-planning is inherently challenging, as UAVs needs to account for dynamically changing flying conditions such as weather, obstacle or no-fly zones, degraded vehicle health and off-nominal battery power consumption. Machine learning methods such as Markov Decision Process (MDPs) have the potential to revolutionize how vehicles navigate in such uncertain environments. Previous papers have demonstrated the use of MDPs to optimize UAV path-planning for energy consumption under time-varying wind distribution. In this study, UAV trajectories from a pre-determined waypoint to target cell, will be computed on a 7X7 grid environment by optimizing parameters for mission assurance and safety limits in addition to the energy consumption, and operation time. The UAV navigates the grid by taking actions to move in either of the eight cardinal and intercardinal directions, under constant thrust profile. The next state of the UAV is calculated by considering its action, transition probability, obstacle cells and the wind speed magnitude and direction. Both constant and stochastic wind will be considered in this paper, the parameters being extracted from real wind measurements in proximity to an experimental UAV flight. One of the studies to be demonstrated in this paper is that as the unmanned airspace gets more complex with multiple vehicles and environmental uncertainties, trade-offs between energy consumption, operation time, risk tolerance, and mission assurance needs to be made. Further, MDPs are capable of fast computation of UAV trajectories under varying wind, hence making them suitable for in-flight path planners.

decision-making↗

Impulsive Control for Continuous-Time Markov Decision Processes: A Linear Programming Approach

In this paper, we investigate an optimization problem for continuous-time Markov decision processes with both impulsive and continuous controls. We consider the so-called constrained problem where the objective of the controller is to minimize a total expected discounted optimality criterion associated with a cost rate function while keeping other performance criteria of the same form, but associated with different cost rate functions, below some given bounds. Our model allows multiple impulses at the same time moment. The main objective of this work is to study the associated linear program defined on a space of measures including the occupation measures of the controlled process and to provide sufficient conditions to ensure the existence of an optimal control.

97 MATHEMATICS AND COMPUTING↗

The Discounted Method and Equivalence of Average Criteria for Risk-Sensitive Markov Decision Processes on Borel Spaces

This note concerns discrete-time controlled Markov chains with Borel state and action spaces. Given a nonnegative cost function, the performance of a control policy is measured by the superior limit risk-sensitive average criterion associated with a constant and positive risk sensitivity coefficient. Within such a framework, the discounted approach is used (a) to establish the existence of solutions for the corresponding optimality inequality, and (b) to show that, under mild conditions on the cost function, the optimal value functions corresponding to the superior and inferior limit average criteria coincide on a certain subset of the state space. The approach of the paper relies on standard dynamic programming ideas and on a simple analytical derivation of a Tauberian relation.

97 MATHEMATICS AND COMPUTING↗

Random field optimization

Herein we present a new modeling paradigm for optimization that we call random field optimization. Random fields are a powerful modeling abstraction that aims to capture the behavior of random variables that live on infinite-dimensional spaces (e.g., space and time) such as stochastic processes (e.g., time series, Gaussian processes, and Markov processes), random matrices, and random spatial fields. This paradigm involves sophisticated mathematical objects (e.g., stochastic differential equations and space-time kernel functions) and has been widely used in neuroscience, geoscience, physics, civil engineering, and computer graphics. Despite of this, however, random fields have seen limited use in optimization; specifically, existing optimization paradigms that involve uncertainty (e.g., stochastic programming and robust optimization) mostly focus on the use of finite random variables. This trend is rapidly changing with the advent of statistical optimization (e.g., Bayesian optimization) and multi-scale optimization (e.g., integration of molecular sciences and process engineering). Our work extends a recently-proposed abstraction for infinite-dimensional optimization problems by capturing more general uncertainty representations. Moreover, we discuss solution paradigms for this new class of problems based on finite transformations and sampling, and identify open questions and challenges.

97 MATHEMATICS AND COMPUTING↗

Symbolic Heuristic Search for Factored Markov Decision Processes

We describe a planning algorithm that integrates two approaches to solving Markov decision processes with large state spaces. State abstraction is used to avoid evaluating states individually. Forward search from a start state, guided by an admissible heuristic, is used to avoid evaluating all states. We combine these two approaches in a novel way that exploits symbolic model-checking techniques and demonstrates their usefulness for decision-theoretic planning.

Morris, Robert↗

Distributionally Robust Partially Observable Markov Decision Process with Moment-Based Ambiguity

In this paper, we consider a distributionally robust partially observable Markov decision process (DR-POMDP), where the distribution of the transition-observation probabilities is unknown at the beginning of each decision period, but their realizations can be inferred using side information at the end of each period after an action being taken. We build an ambiguity set of the joint distribution using bounded moments via conic constraints and seek an optimal policy to maximize the worst-case (minimum) reward for any distribution in the set. We show that the value function of DR-POMDP is piecewise linear convex with respect to the belief state and propose a heuristic search value iteration method for obtaining lower and upper bounds of the value function. We conduct numerical studies and demonstrate the computational performance of our approach via testing instances of a dynamic epidemic control problem. Our results show that DR-POMDP can produce more robust policies under misspecified distributions of transition-observation probabilities as compared to POMDP but has less costly solutions than robust POMDP. The DR-POMDP policies are also insensitive to varying parameter in the ambiguity set and to noise added to the true transition-observation probability values obtained at the end of each decision period.

97 MATHEMATICS AND COMPUTING↗

Decision-making based on Markov decision process in integrated artificial reasoning framework—Part I: Theory

This paper presents a decision-making framework based on an integrated artificial reasoning framework and Markov decision process (MDP). The integrated artificial reasoning framework provides a physics-based approach that converts system information into state transition models, and the analysis result will be represented by the transition probabilities that can be used with an MDP to find a traceable and explainable optimal pathway. A dynamic Bayesian network (DBN) is well suited for representing the structure of an MDP. The causality information among process variables (or among subsystems) is mathematically represented in a DBN by the conditional probabilities of the node’s states provided different probabilities of the parent node’s states. To define node states in a physically understandable manner, we used multilevel flow modeling (MFM). An MFM follows the fundamental energy and mass conservation laws and supports the selection of process variables that represent the system of interest so that causal relations among process variables are properly captured. An MFM-based DBN supports developing state transition models in an MDP to capture the effect of process variables of system having physical relations. The operators of the target system can capture stochastic system dynamics as multiple subsystem state transitions based on their physical relations and uncertainties coming from component degradation or random failures. We analyzed a simplified exemplary system to illustrate an optimal operational policy using the suggested approach.

Markov decision process↗

Transition-Independent Decentralized Markov Decision Processes

There has been substantial progress with formal models for sequential decision making by individual agents using the Markov decision process (MDP). However, similar treatment of multi-agent systems is lacking. A recent complexity result, showing that solving decentralized MDPs is NEXP-hard, provides a partial explanation. To overcome this complexity barrier, we identify a general class of transition-independent decentralized MDPs that is widely applicable. The class consists of independent collaborating agents that are tied up by a global reward function that depends on both of their histories. We present a novel algorithm for solving this class of problems and examine its properties. The result is the first effective technique to solve optimally a class of decentralized MDPs. This lays the foundation for further work in this area on both exact and approximate solutions.

Becker, Raphen↗

Semi-Markov Control Processes with Unknown Holding Times Distribution Under an Average Cost Criterion

This paper deals with a class of semi-Markov control models with Borel state and control spaces, possibly unbounded costs, and unknown holding times distribution F. Assuming that F does not depend on state-action pairs, we combine suitable methods of statistical estimation of the mean holding time with control procedures to construct an average cost optimal Markovian policy {pi}-hat={l_brace}f{sub n}{r_brace}, and an optimal stationary policy {l_brace}f{sub {infinity}}{r_brace}, where f{sub n} converges to f{sub {infinity}} in the sense of Schael.

97 MATHEMATICS AND COMPUTING↗

Relaxation process of quantum system: Stochastic Liouville equation and initial correlation

Time evolution of a quantum system which is influenced by a stochastically fluctuating environment is studied by means of the stochastic Liouville equation. The two different types of the stochastic Liouville equation and their relation are discussed. The stochastic Liouville equation is shown to be derived from the quantum master equation of the Lindblad under certain conditions. Relaxation processes of single and bipartite quantum systems which are initially correlated with a stochastic environment are investigated. It is shown the possibility that the stochastic fluctuation can create coherence and entanglement of a quantum system with the assistance of the initial correlation. The results are examined in the pure dephasing processes of qubits, which are caused by the nonstationary Gauss-Markov process and two-state jump Markov process.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Measurement-based reliability/performability models

Measurement-based models based on real error-data collected on a multiprocessor system are described. Model development from the raw error-data to the estimation of cumulative reward is also described. A workload/reliability model is developed based on low-level error and resource usage data collected on an IBM 3081 system during its normal operation in order to evaluate the resource usage/error/recovery process in a large mainframe system. Thus, both normal and erroneous behavior of the system are modeled. The results provide an understanding of the different types of errors and recovery processes. The measured data show that the holding times in key operational and error states are not simple exponentials and that a semi-Markov process is necessary to model the system behavior. A sensitivity analysis is performed to investigate the significance of using a semi-Markov process, as opposed to a Markov process, to model the measured system.

Hsueh, Mei-Chen↗

Quantum logic gate synthesis as a Markov decision process

Reinforcement learning has witnessed recent applications to a variety of tasks in quantum programming. The underlying assumption is that those tasks could be modeled as Markov decision processes (MDPs). Here, we investigate the feasibility of this assumption by exploring its consequences for single-qubit quantum state preparation and gate compilation. By forming discrete MDPs, we solve for the optimal policy exactly through policy iteration. We find optimal paths that correspond to the shortest possible sequence of gates to prepare a state or compile a gate, up to some target accuracy. Our method works in both the absence and presence of noise and compares favorably to other quantum compilation methods, such as the Ross–Selinger algorithm. This work provides theoretical insight into why reinforcement learning may be successfully used to find optimally short gate sequences in quantum programming.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Markov Modeling of Component Fault Growth over a Derived Domain of Feasible Output Control Effort Modifications

This paper introduces a novel Markov process formulation of stochastic fault growth modeling, in order to facilitate the development and analysis of prognostics-based control adaptation. A metric representing the relative deviation between the nominal output of a system and the net output that is actually enacted by an implemented prognostics-based control routine, will be used to define the action space of the formulated Markov process. The state space of the Markov process will be defined in terms of an abstracted metric representing the relative health remaining in each of the system s components. The proposed formulation of component fault dynamics will conveniently relate feasible system output performance modifications to predictions of future component health deterioration.

Bole, Brian↗

Markov Decision Processes for Intelligent, Risk-Informed Asset-Management Decision-Making

Advanced nuclear reactors are a promising option for aiding the world in achieving its net-zero carbon emission goals, however, there are significant challenges to attaining and maintaining economic competitiveness with other sources of electricity. To improve the economic competitiveness of advanced reactor designs, a project was initiated to explore the use of Markov Decision Processes (MDPs) to guide asset-management decision-making during advanced reactor operation. MDPs are a powerful tool for optimizing decision-making in complex environments and their application to advanced reactors can aid in planning maintenance and repair activities to minimize downtime and maximize generation. The described approach expands on previous work regarding the use of MDPs for operational decision-making through the direct incorporation of real-time plant information. The integral MDP analysis includes information from online component diagnostic tools and the plant’s real-time generation risk assessment (GRA) and probabilistic risk assessment (PRA), which evaluate plant risk from both an economic and safety perspective. The result is an asset-management optimization framework that is based on real-time data regarding plant component status and the current best-estimate of plant risk. The paper presents an overview of the theoretical framework to incorporate the different information pathways into an integral MDP analysis, along with example analyses.

Grabaskas, David↗

Arbitrarily accurate, nonparametric coarse graining with Markov renewal processes and the Mori–Zwanzig formulation

Stochastic dynamics, such as molecular dynamics, are important in many scientific applications. However, summarizing and analyzing the results of such simulations is often challenging due to the high dimension in which simulations are carried out and, consequently, due to the very large amount of data that are typically generated. Coarse graining is a popular technique for addressing this problem by providing compact and expressive representations. Coarse graining, however, potentially comes at the cost of accuracy, as dynamical information is, in general, lost when projecting the problem in a lower-dimensional space. This article shows how to eliminate coarse-graining error using two key ideas. First, we represent coarse-grained dynamics as a Markov renewal process. Second, we outline a data-driven, non-parametric Mori–Zwanzig approach for computing jump times of the renewal process. Numerical tests on a small protein illustrate the method.

36 MATERIALS SCIENCE↗

A Markov Decision Process Framework for Optimal Airport Reconfiguration

The airport runway configuration is defined as a combination set of runways for arrivals and departures used at a point during operation of the airport. An optimal configuration of these runways depends on a number of factors, including traffic demand, wind magnitude and direction, other adverse weather conditions, and noise restrictions, among others. Based on the current state of these factors and predictions of traffic demand and weather conditions, runway configuration changes are made and coordinated between tower controller, other air traffic control facilities, pilots, and ground personnel. Reconfigurations can be quite disruptive to airport operations; minimizing their frequency and scheduling them well in advance is essential for mitigating some of the added workload for controllers and pilots. Unfortunately, deciding on an appropriate time to change is challenging for human decision makers. Not only do multiple factors need to be evaluated, but the uncertainty in their forecasts must also be considered. Previous optimization methods, such as mixed linear integer programming, have been proposed. Although these methods can reason over a large set of variables, they do not systematically handle the uncertainty associated with weather movement, traffic demands, and other variables. In this work, we introduce a Markov Decision Process (MDP)-based decision making framework which can reason effectively over the inherent uncertainties and make optimal decisions on if/when to change the airport configuration. In a prototype implementation, we present a single runway with three aircraft and utilize knowledge of the forecasted wind speed and direction to determine whether to keep or change the current runway configuration. Our aim through this work is to present a framework for airport reconfiguration which can be scalable to additional aircraft, multiple runways, and various input parameters. This technique will optimize the airport reconfiguration procedure by providing a proactive approach, optimizing not just at the next optimal opportunity for a reconfiguration based on varying atmospheric and traffic conditions in the terminal airspace, but also anticipating future necessary reconfigurations. This will eliminate the inefficiencies of frequent changes currently associated with runway reconfiguration procedures.

runway reconfiguration↗