SEARCH · Search NASA
Results for “Markov Chain”
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.
Predicting Vertical Concentration Profiles in the Marine Atmospheric Boundary Layer With a Markov Chain Random Walk Model
Explore the source record for details and available documents.
Machine Learning, Markov Chain Monte Carlo, and Optimal Algorithms to Characterize the AdvACT Kilopixel Transition-Edge Sensor Arrays
Explore the source record for details and available documents.
Metrics for Labeled Markov Systems
Partial Labeled Markov Chains are simultaneously generalizations of process algebra and of traditional Markov chains. They provide a foundation for interacting discrete probabilistic systems, the interaction being synchronization on labels as in process algebra. Existing notions of process equivalence are too sensitive to the exact probabilities of various transitions. This paper addresses contextual reasoning principles for reasoning about more robust notions of "approximate" equivalence between concurrent interacting probabilistic systems. The present results indicate that:We develop a family of metrics between partial labeled Markov chains to formalize the notion of distance between processes. We show that processes at distance zero are bisimilar. We describe a decision procedure to compute the distance between two processes. We show that reasoning about approximate equivalence can be done compositionally by showing that process combinators do not increase distance. We introduce an asymptotic metric to capture asymptotic properties of Markov chains; and show that parallel composition does not increase asymptotic distance.
Reliability Models and Demonstration of a Fault-Tolerant Motor Concept for Vertical Takeoff and Landing Vehicles
This report documents the completion of the Revolutionary Vertical Lift Technology Project Annual Performance Indicator 24-3.2.4.1: “Apply and document reliability prediction for high reliability motor concept.” Two modeling tools were completed for calculation of reliability of fault-tolerant (FT) motors, and key FT operations of a modular FT motor were demonstrated experimentally. The two models are complementary tools for the stakeholder and user community. Both models employ Markov chain theory. The first model is a time-homogeneous Markov chain model, and the second is a time-inhomogeneous Markov-Weibull model. This report’s main sections are as follows: 1.0 Introduction, 2.0 Theory, 3.0 Motor Reliability Models, 4.0 Validation of FT Operation by Hardware Demonstration, and 5.0 Concluding Remarks. Novel contributions to the field include development of a modular FT motor concept for electrified vertical takeoff and landing (eVTOL) application, solution methods to solve the reliability calculations, development of figures of merit, and the introduction of “linked chains” to formulate a building-block approach for time-inhomogeneous Markov-Weibull modeling of motor reliability. Example case studies have been completed, and results are provided and discussed herein. A four-module FT motor concept was developed to a preliminary-design level of detail. This eVTOL FT motor concept was designed for galvanic, magnetic, and thermal isolation of stator winding faults. The reliability of the concept motor was calculated using a time-inhomogeneous Markov chain model. Employing average failure rate as a metric, 570 times greater reliability was achieved as compared to a baseline motor without fault tolerance. A demonstrator motor was built and tested. The testing demonstrated the key features of FT operation and validated the essential premises of the FT motor concepts presented herein. The experiments included successful demonstration of the feasibility of the following four key FT features: (1) terminal open-circuit operation, (2) thermal isolation after fault, (3) terminal short-circuit operation, and (4) internal short-circuit operation. These works indicate that FT modular motor drives offer promise for addressing the daunting reliability gap that electric aircraft propulsor drives are facing relative to the best conventional motor drive technology that is available today.
Application of Simulated Annealing and Related Algorithms to TWTA Design
Simulated Annealing (SA) is a stochastic optimization algorithm used to search for global minima in complex design surfaces where exhaustive searches are not computationally feasible. The algorithm is derived by simulating the annealing process, whereby a solid is heated to a liquid state and then cooled slowly to reach thermodynamic equilibrium at each temperature. The idea is that atoms in the solid continually bond and re-bond at various quantum energy levels, and with sufficient cooling time they will rearrange at the minimum energy state to form a perfect crystal. The distribution of energy levels is given by the Boltzmann distribution: as temperature drops, the probability of the presence of high-energy bonds decreases. In searching for an optimal design, local minima and discontinuities are often present in a design surface. SA presents a distinct advantage over other optimization algorithms in its ability to escape from these local minima. Just as high-energy atomic configurations are visited in the actual annealing process in order to eventually reach the minimum energy state, in SA highly non-optimal configurations are visited in order to find otherwise inaccessible global minima. The SA algorithm produces a Markov chain of points in the design space at each temperature, with a monotonically decreasing temperature. A random point is started upon, and the objective function is evaluated at that point. A stochastic perturbation is then made to the parameters of the point to arrive at a proposed new point in the design space, at which the objection function is evaluated as well. If the change in objective function values (Delta)E is negative, the proposed new point is accepted. If (Delta)E is positive, the proposed new point is accepted according to the Metropolis criterion: rho((Delta)f) = exp((-Delta)E/T), where T is the temperature for the current Markov chain. The process then repeats for the remainder of the Markov chain, after which the temperature is decremented and the process repeats. Eventually (and hopefully), a near-globally optimal solution is attained as T approaches zero. Several exciting variants of SA have recently emerged, including Discrete-State Simulated Annealing (DSSA) and Simulated Tempering (ST). The DSSA algorithm takes the thermodynamic analogy one step further by categorizing objective function evaluations into discrete states. In doing so, many of the case-specific problems associated with fine-tuning the SA algorithm can be avoided; for example, theoretical approximations for the initial and final temperature can be derived independently of the case. In this manner, DSSA provides a scheme that is more robust with respect to widely differing design surfaces. ST differs from SA in that the temperature T becomes an additional random variable in the optimization. The system is also kept in equilibrium as the temperature changes, as opposed to the system being driven out of equilibrium as temperature changes in SA. ST is designed to overcome obstacles in design surfaces where numerous local minima are separated by high barriers. These algorithms are incorporated into the optimal design of the traveling-wave tube amplifier (TWTA). The area under scrutiny is the collector, in which it would be ideal to use negative potential to decelerate the spent electron beam to zero kinetic energy just as it reaches the collector surface. In reality this is not plausible due to a number of physical limitations, including repulsion and differing levels of kinetic energy among individual electrons. Instead, the collector is designed with multiple stages depressed below ground potential. The design of this multiple-stage collector is the optimization problem of interest. One remaining problem in SA and DSSA is the difficulty in determining when equilibrium has been reached so that the current Markov chain can be terminated. It has been suggested in recent literature that simulating the thermodynamic properties opecific heat, entropy, and internal energy from the Boltzmann distribution can provide good indicators of having reached equilibrium at a certain temperature. These properties are tested for their efficacy and implemented in SA and DSSA code with respect to TWTA collector optimization.
Analysis and design of a second-order digital phase-locked loop
A specific second-order digital phase-locked loop (DPLL) was modeled as a first-order Markov chain with alternatives. From the matrix of transition probabilities of the Markov chain, the steady-state phase error of the DPLL was determined. In a similar manner the loop's response was calculated for a fading input. Additionally, a hardware DPLL was constructed and tested to provide a comparison to the results obtained from the Markov chain model. In all cases tested, good agreement was found between the theoretical predictions and the experimental data.
Modular techniques for dynamic fault-tree analysis
It is noted that current approaches used to assess the dependability of complex systems such as Space Station Freedom and the Air Traffic Control System are incapable of handling the size and complexity of these highly integrated designs. A novel technique for modeling such systems which is built upon current techniques in Markov theory and combinatorial analysis is described. It enables the development of a hierarchical representation of system behavior which is more flexible than either technique alone. A solution strategy which is based on an object-oriented approach to model representation and evaluation is discussed. The technique is virtually transparent to the user since the fault tree models can be built graphically and the objects defined automatically. The tree modularization procedure allows the two model types, Markov and combinatoric, to coexist and does not require that the entire fault tree be translated to a Markov chain for evaluation. This effectively reduces the size of the Markov chain required and enables solutions with less truncation, making analysis of longer mission times possible. Using the fault-tolerant parallel processor as an example, a model is built and solved for a specific mission scenario and the solution approach is illustrated in detail.
Two-stage chain sampling inspection plans with different sample sizes in the two stages
A further generalization of the family of 'two-stage' chain sampling inspection plans is developed - viz, the use of different sample sizes in the two stages. Evaluation of the operating characteristics is accomplished by the Markov chain approach of the earlier work, modified to account for the different sample sizes. Markov chains for a number of plans are illustrated and several algebraic solutions are developed. Since these plans involve a variable amount of sampling, an evaluation of the average sampling number (ASN) is developed. A number of OC curves and ASN curves are presented. Some comparisons with plans having only one sample size are presented and indicate that improved discrimination is achieved by the two-sample-size plans.
Optimal service allocation among two heterogeneous traffic types with no queueing
Two communication traffic streams with Poisson statistics arrive at a network node. These are to be transmitted across a channel with a total bandwidth capacity of C slots. Messages not accepted at the node are assumed to be lost. Under the assumptions of exponential service time distributions, the problem of dynamic allocation of available channel bandwidth among the two traffic types is studied in order to minimize a weighted sum of blocking probabilities. Modeling the system as a two-dimensional Markov chain is studied to minimize a weighted sum of blocking probabilities. Modeling the system as a two-dimensional Markov chain, it is shown by an application of dynamic programming principles that the optimal policy has the form of a 'switching curve'.
A Markov model for NASA's Ground Communications Facility
A 'natural' way of constructing finite-state Markov chains (FSMC) is presented for those noise burst channels that can be modeled by them. In particular, a five-state Markov chain is given as a model of errors occurring at the Ground Communications Facility (GCF). A maximum likelihood procedure applicable to any FSMC is developed for estimating all the model parameters starting from the data of error runs. A few of the statistics important for estimating the performance of error control strategies on the channel are provided.
Fault trees and imperfect coverage
A new algorithm is presented for solving the fault tree. The algorithm includes the dynamic behavior of the fault/error handling model but obviates the need for the Markov chain solution. As the state space is expanded in a breadth-first search (the same is done in the conversion to a Markov chain), the state's contribution to each future state is calculated exactly. A dynamic state truncation technique is also presented; it produces bounds on the unreliability of the system by considering only part of the state space. Since the model is solved as the state space is generated, the process can be stopped as soon as the desired accuracy is reached.
Maximum likelihood estimation in finite stationary ergodic markaov chains
Maximum likelihood estimation of vector parameter in finite stationary ergodic markov chains
Markov information sources
A regular Markov source is defined as the output of a deterministic, but noisy, channel driven by the state sequence of a regular finite-state Markov chain. The rate of such a source is the per letter uncertainty of its digits. The well-known result that the rate of a unifilar regular Markov source is easily calculable is demonstrated, where unifilarity means that the present state of the Markov chain and the next output of the deterministic channel uniquely determine the next state. At present, there is no known method to calculate the rate of a nonunifilar source. Two tentative approaches to this unsolved problem are given, namely source identical twins and the master-slave source, which appear to shed some light on the question of rate calculation for a nonunifilar source.
Kepler Uniform Modeling of KOIs: MCMC Notes for Data Release 25
This document describes data products related to the reported planetary parameters and uncertainties for the Kepler Objects of Interest (KOIs) based on a Markov-Chain-Monte-Carlo (MCMC) analysis. Reported parameters, uncertainties and data products can be found at the NASA Exoplanet Archive . The codes used for this data analysis are available on the Github website (Rowe 2016). The relevant paper for details of the calculations is Rowe et al. (2015). The main differences between the model fits discussed here and those in the DR24 catalogue are that the DR25 light curves were used in the analysis, our processing of the MAST light curves took into account different data flags, the number of chains calculated was doubled to 200 000, and the parameters which are reported are based on a damped least-squares fit, instead of the median value from the Markov chain or the chain with the lowest 2 as reported in the past.
A graphical language for reliability model generation
A graphical interface capability of the hybrid automated reliability predictor (HARP) is described. The graphics-oriented (GO) module provides the user with a graphical language for modeling system failure modes through the selection of various fault tree gates, including sequence dependency gates, or by a Markov chain. With this graphical input language, a fault tree becomes a convenient notation for describing a system. In accounting for any sequence dependencies, HARP converts the fault-tree notation to a complex stochastic process that is reduced to a Markov chain which it can then solve for system reliability. The graphics capability is available for use on an IBM-compatible PC, a Sun, and a VAX workstation. The GO module is written in the C programming language and uses the Graphical Kernel System (GKS) standard for graphics implementation. The PC, VAX, and Sun versions of the HARP GO module are currently in beta-testing.
Performance and state-space analyses of systems using Petri nets
The goal of any modeling methodology is to develop a mathematical description of a system that is accurate in its representation and also permits analysis of structural and/or performance properties. Inherently, trade-offs exist between the level detail in the model and the ease with which analysis can be performed. Petri nets (PN's), a highly graphical modeling methodology for Discrete Event Dynamic Systems, permit representation of shared resources, finite capacities, conflict, synchronization, concurrency, and timing between state changes. By restricting the state transition time delays to the family of exponential density functions, Markov chain analysis of performance problems is possible. One major drawback of PN's is the tendency for the state-space to grow rapidly (exponential complexity) compared to increases in the PN constructs. It is the state space, or the Markov chain obtained from it, that is needed in the solution of many problems. The theory of state-space size estimation for PN's is introduced. The problem of state-space size estimation is defined, its complexities are examined, and estimation algorithms are developed. Both top-down and bottom-up approaches are pursued, and the advantages and disadvantages of each are described. Additionally, the author's research in non-exponential transition modeling for PN's is discussed. An algorithm for approximating non-exponential transitions is developed. Since only basic PN constructs are used in the approximation, theory already developed for PN's remains applicable. Comparison to results from entropy theory show the transition performance is close to the theoretic optimum. Inclusion of non-exponential transition approximations improves performance results at the expense of increased state-space size. The state-space size estimation theory provides insight and algorithms for evaluating this trade-off.
Graphical workstation capability for reliability modeling
In addition to computational capabilities, software tools for estimating the reliability of fault-tolerant digital computer systems must also provide a means of interfacing with the user. Described here is the new graphical interface capability of the hybrid automated reliability predictor (HARP), a software package that implements advanced reliability modeling techniques. The graphics oriented (GO) module provides the user with a graphical language for modeling system failure modes through the selection of various fault-tree gates, including sequence-dependency gates, or by a Markov chain. By using this graphical input language, a fault tree becomes a convenient notation for describing a system. In accounting for any sequence dependencies, HARP converts the fault-tree notation to a complex stochastic process that is reduced to a Markov chain, which it can then solve for system reliability. The graphics capability is available for use on an IBM-compatible PC, a Sun, and a VAX workstation. The GO module is written in the C programming language and uses the graphical kernal system (GKS) standard for graphics implementation. The PC, VAX, and Sun versions of the HARP GO module are currently in beta-testing stages.