SEARCH · Engineering Papers

Results for “Markov models”

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.

SourceResearch connectionFrom yearThrough year

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

At least 91 records · Page 5

All sources NASA NTRS DOE OSTI

NASA NTRS1989

Markov reliability models for digital flight control systems

The reliability of digital flight control systems can often be accurately predicted using Markov chain models. The cost of numerical solution depends on a model's size and stiffness. Acyclic Markov models, a useful special case, are particularly amenable to efficient numerical solution. Even in the general case, instantaneous coverage approximation allows the reduction of some cyclic models to more readily solvable acyclic models. After considering the solution of single-phase models, the discussion is extended to phased-mission models. Phased-mission reliability models are classified based on the state restoration behavior that occurs between mission phases. As an economical approach for the solution of such models, the mean failure rate solution method is introduced. A numerical example is used to show the influence of fault-model parameters and interphase behavior on system unreliability.

Mcgough, John↗

NASA NTRS1991

Model reduction by trimming for a class of semi-Markov reliability models and the corresponding error bound

Semi-Markov processes have proved to be an effective and convenient tool to construct models of systems that achieve reliability by redundancy and reconfiguration. These models are able to depict complex system architectures and to capture the dynamics of fault arrival and system recovery. A disadvantage of this approach is that the models can be extremely large, which poses both a model and a computational problem. Techniques are needed to reduce the model size. Because these systems are used in critical applications where failure can be expensive, there must be an analytically derived bound for the error produced by the model reduction technique. A model reduction technique called trimming is presented that can be applied to a popular class of systems. Automatic model generation programs were written to help the reliability analyst produce models of complex systems. This method, trimming, is easy to implement and the error bound easy to compute. Hence, the method lends itself to inclusion in an automatic model generator.

White, Allan L.↗

NASA NTRS1995

Reduction Of Sizes Of Semi-Markov Reliability Models

Trimming technique reduces computational effort by order of magnitude while introducing negligible error. Error bound depends on only three parameters from semi-Markov model: maximum sum of rates for failure transitions leaving any state, maximum average holding time for recovery-mode state, and operating time for system. Error bound computed before any model generated, enabling modeler to decide immediately whether or not model can be trimmed. Trimming procedure specified by precise and easy description, making it easy to include trimming procedure in program generating mathematical models for use in assessing reliability. Typical application of technique in design of digital control systems required to be extremely reliable. In addition to aerospace applications, fault-tolerant design has growing importance in wide range of industrial applications.

White, Allan L.↗

NASA NTRS1990

Closed-form solution of decomposable stochastic models

Markov and semi-Markov processes are increasingly being used in the modeling of complex reconfigurable systems (fault tolerant computers). The estimation of the reliability (or some measure of performance) of the system reduces to solving the process for its state probabilities. Such a model may exhibit numerous states and complicated transition distributions, contributing to an expensive and numerically delicate solution procedure. Thus, when a system exhibits a decomposition property, either structurally (autonomous subsystems), or behaviorally (component failure versus reconfiguration), it is desirable to exploit this decomposition in the reliability calculation. In interesting cases there can be failure states which arise from non-failure states of the subsystems. Equations are presented which allow the computation of failure probabilities of the total (combined) model without requiring a complete solution of the combined model. This material is presented within the context of closed-form functional representation of probabilities as utilized in the Symbolic Hierarchical Automated Reliability and Performance Evaluator (SHARPE) tool. The techniques adopted enable one to compute such probability functions for a much wider class of systems at a reduced computational cost. Several examples show how the method is used, especially in enhancing the versatility of the SHARPE tool.

Sjogren, Jon A.↗

DOE OSTI2020

On the advantages of exploiting memory in Markov state models for biomolecular dynamics

Biomolecular dynamics play an important role in numerous biological processes. Markov State Models (MSMs) provide a powerful approach to study these dynamic processes by predicting long time scale dynamics based on many short molecular dynamics (MD) simulations. In an MSM, protein dynamics are modeled as a kinetic process consisting of a series of Markovian transitions between different conformational states at discrete time intervals (called “lag time”). To achieve this, a master equation must be constructed with a sufficiently long lag time to allow interstate transitions to become truly Markovian. This imposes a major challenge for MSM studies of proteins since the lag time is bound by the length of relatively short MD simulations available to estimate the frequency of transitions. Here, we show how one can employ the generalized master equation formalism to obtain an exact description of protein conformational dynamics both at short and long time scales without the time resolution restrictions imposed by the MSM lag time. Using a simple kinetic model, alanine dipeptide, and WW domain, we demonstrate that it is possible to construct these quasi-Markov State Models (qMSMs) using MD simulations that are 5–10 times shorter than those required by MSMs. These qMSMs only contain a handful of metastable states and, thus, can greatly facilitate the interpretation of mechanisms associated with protein dynamics. A qMSM opens the door to the study of conformational changes of complex biomolecules where a Markovian model with a few states is often difficult to construct due to the limited length of available MD simulations.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

NASA NTRS1989

Projection methods for the numerical solution of Markov chain models

Projection methods for computing stationary probability distributions for Markov chain models are presented. A general projection method is a method which seeks an approximation from a subspace of small dimension to the original problem. Thus, the original matrix problem of size N is approximated by one of dimension m, typically much smaller than N. A particularly successful class of methods based on this principle is that of Krylov subspace methods which utilize subspaces of the form span(v,av,...,A(exp m-1)v). These methods are effective in solving linear systems and eigenvalue problems (Lanczos, Arnoldi,...) as well as nonlinear equations. They can be combined with more traditional iterative methods such as successive overrelaxation, symmetric successive overrelaxation, or with incomplete factorization methods to enhance convergence.

Saad, Youcef↗

NASA NTRS1984

Upper and lower bounds for semi-Markov reliability models of reconfigurable systems

This paper determines the information required about system recovery to compute the reliability of a class of reconfigurable systems. Upper and lower bounds are derived for these systems. The class consists of those systems that satisfy five assumptions: the components fail independently at a low constant rate, fault occurrence and system reconfiguration are independent processes, the reliability model is semi-Markov, the recovery functions which describe system configuration have small means and variances, and the system is well designed. The bounds are easy to compute, and examples are included.

White, A. L.↗

NASA NTRS1983

Reliability with imperfect diagnostics

A reliability estimation method for systems that continually accumulate faults because of imperfect diagnostics is developed and an application for redundant digital avionics is presented. The present method assumes that if a fault does not appear in a short period of time, it will remain hidden until a majority of components are faulty and the system fails. A certain proportion of a component's faults are detected in a short period of time, and a description of their detection is included in the reliability model. A Markov model of failure during flight for a nonreconfigurable five-plex is presented for a sequence of one-hour flights followed by maintenance.

White, A. L.↗

NASA NTRS1990

The cost of unreliability in the avionics suite of a launch vehicle

The main objective of the Advanced Launch System (ALS) program is to realize a substantial reduction in recurring launch costs over present launch systems. A methodology is presented for assessing the impact of the reliability of the avionics suite on the recurring launch cost of the ALS. The methodology is illustrated by focusing on two architectures. The first is a distillation of a typical architecture for this type of application. The second is a simplified implementation of the Advanced Information Processing System (AIPS) technology developed at the Charles Stark Draper Laboratory, Inc. Both architectures utilize redundancy of hardware to tolerate faults. the key contributors to the cost of unreliability are identified and modeled utilizing Markov modeling techniques for each of the two architectures. The results are presented along with the more traditional costs for these avionics suites.

Rosch, Gene↗

NASA NTRS1987

Validation of the SURE Program, phase 1

Presented are the results of the first phase in the validation of the SURE (Semi-Markov Unreliability Range Evaluator) program. The SURE program gives lower and upper bounds on the death-state probabilities of a semi-Markov model. With these bounds, the reliability of a semi-Markov model of a fault-tolerant computer system can be analyzed. For the first phase in the validation, fifteen semi-Markov models were solved analytically for the exact death-state probabilities and these solutions compared to the corresponding bounds given by SURE. In every case, the SURE bounds covered the exact solution. The bounds, however, had a tendency to separate in cases where the recovery rate was slow or the fault arrival rate was fast.

Dotson, Kelly J.↗

DOE OSTI2025

Unfolding of the Villin Headpiece Domain: Revealing Structural Heterogeneity with Time‐Resolved X‐Ray Solution Scattering and Markov State Modeling

Understanding protein folding pathways is crucial to deciphering the principles of protein structure and function. Here, the unfolding dynamics of the 35‐residue villin headpiece (HP35) and a norleucine‐substituted variant (2F4K) using a combination of experimental and computational techniques is investigated. Time‐resolved X‐ray solution scattering coupled with equilibrium molecular dynamics simulations and Markov state modeling reveals distinct unfolding mechanisms between the two variants: HP35 and 2F4K. Specifically, HP35 exhibits a two‐state unfolding process, whereas an intermediate state is identified for the 2F4K mutant. A Markov state model constructed from simulations is used to map atomic‐level transitions to experimental observations, providing insights into the role of sequence variations in modulating folding pathways. The findings underscore the importance of integrating experimental and computational approaches to unravel protein unfolding mechanisms between heterogenous structural ensembles.

Nijhawan, Adam K. [Department of Chemistry Northwe↗

NASA NTRS1986

The SURE Reliability Analysis Program

The SURE program is a new reliability analysis tool for ultrareliable computer system architectures. The program is based on computational methods recently developed for the NASA Langley Research Center. These methods provide an efficient means for computing accurate upper and lower bounds for the death state probabilities of a large class of semi-Markov models. Once a semi-Markov model is described using a simple input language, the SURE program automatically computes the upper and lower bounds on the probability of system failure. A parameter of the model can be specified as a variable over a range of values directing the SURE program to perform a sensitivity analysis automatically. This feature, along with the speed of the program, makes it especially useful as a design tool.

Butler, R. W.↗

NASA NTRS1986

The SURE reliability analysis program

The SURE program is a new reliability tool for ultrareliable computer system architectures. The program is based on computational methods recently developed for the NASA Langley Research Center. These methods provide an efficient means for computing accurate upper and lower bounds for the death state probabilities of a large class of semi-Markov models. Once a semi-Markov model is described using a simple input language, the SURE program automatically computes the upper and lower bounds on the probability of system failure. A parameter of the model can be specified as a variable over a range of values directing the SURE program to perform a sensitivity analysis automatically. This feature, along with the speed of the program, makes it especially useful as a design tool.

Butler, R. W.↗

NASA NTRS1988

SURE reliability analysis: Program and mathematics

The SURE program is a new reliability analysis tool for ultrareliable computer system architectures. The computational methods on which the program is based provide an efficient means for computing accurate upper and lower bounds for the death state probabilities of a large class of semi-Markov models. Once a semi-Markov model is described using a simple input language, the SURE program automatically computes the upper and lower bounds on the probability of system failure. A parameter of the model can be specified as a variable over a range of values directing the SURE program to perform a sensitivity analysis automatically. This feature, along with the speed of the program, makes it especially useful as a design tool.

Butler, Ricky W.↗

NASA NTRS1993

Automatic specification of reliability models for fault-tolerant computers

The calculation of reliability measures using Markov models is required for life-critical processor-memory-switch structures that have standby redundancy or that are subject to transient or intermittent faults or repair. The task of specifying these models is tedious and prone to human error because of the large number of states and transitions required in any reasonable system. Therefore, model specification is a major analysis bottleneck, and model verification is a major validation problem. The general unfamiliarity of computer architects with Markov modeling techniques further increases the necessity of automating the model specification. Automation requires a general system description language (SDL). For practicality, this SDL should also provide a high level of abstraction and be easy to learn and use. The first attempt to define and implement an SDL with those characteristics is presented. A program named Automated Reliability Modeling (ARM) was constructed as a research vehicle. The ARM program uses a graphical interface as its SDL, and it outputs a Markov reliability model specification formulated for direct use by programs that generate and evaluate the model.

Liceaga, Carlos A.↗

NASA NTRS1995

KRESKA: A compression system for small and very large images

An effective lossless compression system for grayscale images is presented using finite context variable order Markov models. A new method to accurately estimate the probability of the escape symbol is proposed. The choice of the best model order and rules for selecting context pixels are discussed. Two context precision and two symbol precision techniques to handle noisy image data with Markov models are introduced. Results indicate that finite context variable order Markov models lead to effective lossless compression systems for small and very large images. The system achieves higher compression ratios than some of the better known image compression techniques such as lossless JPEG, JBIG, or FELICS.

Ohnesorge, Krystyna W.↗

NASA NTRS1986

A hierarchical approach to reliability modeling of fault-tolerant systems

A methodology for performing fault tolerant system reliability analysis is presented. The method decomposes a system into its subsystems, evaluates vent rates derived from the subsystem's conditional state probability vector and incorporates those results into a hierarchical Markov model of the system. This is done in a manner that addresses failure sequence dependence associated with the system's redundancy management strategy. The method is derived for application to a specific system definition. Results are presented that compare the hierarchical model's unreliability prediction to that of a more complicated tandard Markov model of the system. The results for the example given indicate that the hierarchical method predicts system unreliability to a desirable level of accuracy while achieving significant computational savings relative to component level Markov model of the system.

Gossman, W. E.↗

NASA NTRS1989

Numerical methods in Markov chain modeling

Several methods for computing stationary probability distributions of Markov chains are described and compared. The main linear algebra problem consists of computing an eigenvector of a sparse, usually nonsymmetric, matrix associated with a known eigenvalue. It can also be cast as a problem of solving a homogeneous singular linear system. Several methods based on combinations of Krylov subspace techniques are presented. The performance of these methods on some realistic problems are compared.

Philippe, Bernard↗