Search NASA⌕ Search

SEARCH · Search NASA

Results for “Markov modeling”

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
All sourcesNASA NTRSDOE OSTI
NASA NTRS1991

A Markov model reduction technique for fault tolerant processor reliability analysis

A fault tolerant processor (FTP) plays a key role in many high performance, safety-critical control system applications. Realistic modeling of an FTP is crucial to gaining a high degree of confidence in the reliability and safety analysis of such a system. While fidelity is clearly a major consideration, a practical model must also be kept to a moderate size to allow its incorporation into the overall system model. This paper presents a systematic reduction technique that starts from a complex, detailed model of a triple, redundant FTP and produces a low order approximation of very high accuracy. The existence of two distinct time scales represents the key to the success of the technique. No eigenvalue solution or coordinate transformation are needed. The reduced model captures all the important features of the detailed model, is amenable to an analytical solution and provides insight into the reconfiguration behavior of an FTP.

Schor, Andrei L.↗
NASA NTRS1998

An Introduction to Markov Modeling: Concepts and Uses

Kharkov modeling is a modeling technique that is widely useful for dependability analysis of complex fault tolerant systems. It is very flexible in the type of systems and system behavior it can model. It is not, however, the most appropriate modeling technique for every modeling situation. The first task in obtaining a reliability or availability estimate for a system is selecting which modeling technique is most appropriate to the situation at hand. A person performing a dependability analysis must confront the question: is Kharkov modeling most appropriate to the system under consideration, or should another technique be used instead? The need to answer this gives rise to other more basic questions regarding Kharkov modeling: what are the capabilities and limitations of Kharkov modeling as a modeling technique? How does it relate to other modeling techniques? What kind of system behavior can it model? What kinds of software tools are available for performing dependability analyses with Kharkov modeling techniques? These questions and others will be addressed in this tutorial.

Boyd, Mark A.↗
NASA NTRS2002

Protein Kinase Classification with 2866 Hidden Markov Models and One Support Vector Machine

The main application considered in this paper is predicting true kinases from randomly permuted kinases that share the same length and amino acid distributions as the true kinases. Numerous methods already exist for this classification task, such as HMMs, motif-matchers, and sequence comparison algorithms. We build on some of these efforts by creating a vector from the output of thousands of structurally based HMMs, created offline with Pfam-A seed alignments using SAM-T99, which then must be combined into an overall classification for the protein. Then we use a Support Vector Machine for classifying this large ensemble Pfam-Vector, with a polynomial and chisquared kernel. In particular, the chi-squared kernel SVM performs better than the HMMs and better than the BLAST pairwise comparisons, when predicting true from false kinases in some respects, but no one algorithm is best for all purposes or in all instances so we consider the particular strengths and weaknesses of each.

Weber, Ryan↗
NASA NTRS1986

Towards automatic Markov reliability modeling of computer architectures

The analysis and evaluation of reliability measures using time-varying Markov models is required for Processor-Memory-Switch (PMS) structures that have competing processes such as standby redundancy and repair, or renewal processes such as transient or intermittent faults. The task of generating these models is tedious and prone to human error due to the large number of states and transitions involved in any reasonable system. Therefore model formulation 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 formulation. This paper presents an overview of the Automated Reliability Modeling (ARM) program, under development at NASA Langley Research Center. ARM will accept as input a description of the PMS interconnection graph, the behavior of the PMS components, the fault-tolerant strategies, and the operational requirements. The output of ARM will be the reliability of availability Markov model formulated for direct use by evaluation programs. The advantages of such an approach are (a) utility to a large class of users, not necessarily expert in reliability analysis, and (b) a lower probability of human error in the computation.

Liceaga, C. A.↗
NASA NTRS1990

State reduction for semi-Markov reliability models

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 construction 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. Automatic model generation programs have been written to help the reliability analyst produce models of complex systems. Because of the importance of these programs, the model reduction technique needs to be precise and easily implemented. This paper presents a model reduction technique called trimming that can be applied to a popular class of systems. An error bound for the trimming procedure is derived that uses readily available system parameters. The trimming procedure is precisely described and appears easy to implement in a model generation program.

Reduced order systems↗
NASA NTRS1996

Probabilistic Independence Networks for Hidden Markov Probability Models

In this paper we explore hidden Markov models(HMMs) and related structures within the general framework of probabilistic independence networks (PINs). The paper contains a self-contained review of the basic principles of PINs. It is shown that the well-known forward-backward (F-B) and Viterbi algorithms for HMMs are special cases of more general enference algorithms for arbitrary PINs.

random variables pattern recognition signal proces↗
NASA NTRS1987

Automated model generation for reliability analysis programs

Semi-Markov models (a generalization of Markov models) can be used to calculate the reliability of virtually any fault-tolerant system. However, the process of delineating all of the states and transitions in the model of a complex system can be devastatingly tedious and error-prone. The ASSIST program allows the user to describe the semi-Markov model in a high-level language. Instead of specifying the individual states of the model, the user specifies the rules governing the behavior of the system, and these are used by ASSIST to automatically generate the model. A small number of statements in the abstract language can be used to describe a very large, complex model. Because no assumptions are made about the system being modeled, the ASSIST program can be used to generate models describing the behavior of any type of system. The ASSIST program and its input language are described and illustrated by examples.

Johnson, Sally C.↗
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.↗