Search NASA⌕ Search

SEARCH · Search NASA

Results for “Markov”

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 163 records · Page 9
All sourcesNASA NTRSDOE OSTI
NASA NTRS2026

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.

Electric Motor↗
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.↗
NASA NTRS1990

Three real-time architectures - A study using reward models

Numerous applications in the area of computer system analysis can be effectively studied with Markov reward models. These models describe the evolutionary behavior of the computer system by a continuous-time Markov chain, and a reward rate is associated with each state. In reliability/availability models, upstates have reward rate 1, and down states have reward rate zero associated with them. In a combined model of performance and reliability, the reward rate of a state may be the computational capacity, or a related performance measure. Steady-state expected reward rate and expected instantaneous reward rate are clearly useful measures which can be extracted from the Markov reward model. The diversity of areas where Markov reward models may be used is illustrated with a comparative study of three examples of interest to the fault tolerant computing community.

Sjogren, J. A.↗
NASA NTRS1992

Linear system identification via backward-time observer models

Presented here is an algorithm to compute the Markov parameters of a backward-time observer for a backward-time model from experimental input and output data. The backward-time observer Markov parameters are decomposed to obtain the backward-time system Markov parameters (backward-time pulse response samples) for the backward-time system identification. The identified backward-time system Markov parameters are used in the Eigensystem Realization Algorithm to identify a backward-time state-space model, which can be easily converted to the usual forward-time representation. If one reverses time in the model to be identified, what were damped true system modes become modes with negative damping, growing as the reversed time increases. On the other hand, the noise modes in the identification still maintain the property that they are stable. The shift from positive damping to negative damping of the true system modes allows one to distinguish these modes from noise modes. Experimental results are given to illustrate when and to what extent this concept works.

Juang, Jer-Nan↗
NASA NTRS1992

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.

Patterson-Hine, F. A.↗
NASA NTRS2004

A Decision-Theoretic Approach to Autonomous Planetary Rover Control

The report discusses the: Decentralized Control of Markov Decision Processes. Study the complexity of decentralized control of Markov decision processes, and develop algorithms for finding optimal control policies. Scheduling Contract Algorithms. Develop an optimal method for scheduling runs of a contract anytime algorithm (one that takes the deadline as input) in situations where the deadline is unknown, multiple problem instances must be solved, and a multi-processor machine is available. Planetary Rover Control as a Markov Decision Process.Use the Markov decision process framework to formalize and solve problems in planetary rover control. Adaptive Peer Selection. Use reinforcement learning to maximize the expected down-load speed for a client in a peer-to-peer file sharing system.

Zilberstein, Shlomo↗
NASA NTRS2004

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.

Radke, Eric M.↗
NASA NTRS1979

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.

Blasche, P. R.↗
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 NTRS1987

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↗
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 NTRS1988

Automated generation of reliability models

The abstract semi-Markov specification interface to the SURE (Semi-Markov Range Evaluator) tool (ASSIST) program allows the user to describe the Markov model in a high-level language. Instead of listing the individual states of the model, the user specifies the rules governing the behavior of the system, and these are used to automatically generate the model. A small number of statements in the abstract language can describe a large, complex model. Becuase no assumptions are made about the system being modeled, ASSIST can be used to generate models describing the behavior of any type of system. The abstract model definition and the automatic model generation strategy are described. Analysis of an example fault-tolerant architecture, a triad of processor with cold spare processors, shows how the behavior of a system can be captured by a few general rules. The syntax of the ASSIST input language is then described and demonstrated by creating a model to describe the fault behavior of the example architecture. The flexibility of the abstract language is demonstrated by expanding the example to model multiple triads of processors sharing a pool of cold spare processors.

Johnson, Sally C.↗
NASA NTRS1989

Coverage modeling for dependability analysis of fault-tolerant systems

Several different models for predicting coverage in a fault-tolerant system, including models for permanent, intermittent, and transient errors, are discussed. Markov, semi-Markov, nonhomogeneous Markov, and extended stochastic Petri net models for computing coverage are developed. Two types of events that interfere with recovery are examined; and methods for modeling such events, whether they are deterministic or random, are given. The sensitivity of system reliability/availability to the coverage parameter and the sensitivity of the coverage parameter to various error-handling strategies are investigated. It is found that a policy of attempting transient recovery upon detection of an error can actually increase the unreliability of the system. This result is true if the error detectability is not nearly perfect, so that the risk of producing an undetectable error is greater than the benefit gained by not discarding the component.

Dugan, Joanne Bechta↗
NASA NTRS1991

Comparison of several system identification methods for flexible structures

In the last few years various methods of identifying structural dynamics models from modal testing data have appeared. A comparison is presented of four of these algorithms: the Eigensystem Realization Algorithm (ERA), the modified version ERA/DC where DC indicated that it makes use of data correlation, the Q-Markov Cover algorithm, and an algorithm due to Moonen, DeMoor, Vandenberghe, and Vandewalle. The comparison is made using a five mode computer module of the 20 meter Mini-Mast truss structure at NASA Langley Research Center, and various noise levels are superimposed to produced simulated data. The results show that for the example considered ERA/DC generally gives the best results; that ERA/DC is always at least as good as ERA which is shown to be a special case of ERA/DC; that Q-Markov requires the use of significantly more data than ERA/DC to produce comparable results; and that is some situations Q-Markov cannot produce comparable results.

Lew, J.-S.↗
NASA NTRS1991

Comparison of several system identification methods for flexible structures

In the last few years various methods of identifying structural dynamics models from modal testing data have appeared. This paper presents a comparison of four of these algorithms: the Eigensystem Realization Algorithm (ERA), the modified version ERA/DC where DC indicates that it makes use of data correlations, the Q-Markov Cover algorithm, and an algorithm due to Moonen, DeMoor, Vandenberghe and Vandewalle. The comparison is made using a five mode computer model of the 20 meter Mini-Mast truss structure at NASA Langley Research Center, and various noise levels are superimposed to produce simulated data. The results show that for the example considered ERA/DC generally gives the best results; that ERA/DC is always at least as good as ERA which is shown to be a special case of ERA/DC; that Q-Markov requires the use of significantly more data than ERA/DC to produce comparable results; and that in some situations Q-Markov cannot produce comparable results.

Lew, J.-S.↗
NASA NTRS1992

Real-time antenna fault diagnosis experiments at DSS 13

Experimental results obtained when a previously described fault diagnosis system was run online in real time at the 34-m beam waveguide antenna at Deep Space Station (DSS) 13 are described. Experimental conditions and the quality of results are described. A neural network model and a maximum-likelihood Gaussian classifier are compared with and without a Markov component to model temporal context. At the rate of a state update every 6.4 seconds, over a period of roughly 1 hour, the neural-Markov system had zero errors (incorrect state estimates) while monitoring both faulty and normal operations. The overall results indicate that the neural-Markov combination is the most accurate model and has significant practical potential.

Mellstrom, J.↗
NASA NTRS1992

Frequency domain state-space system identification

An algorithm for identifying state-space models from frequency response data of linear systems is presented. A matrix-fraction description of the transfer function is employed to curve-fit the frequency response data, using the least-squares method. The parameters of the matrix-fraction representation are then used to construct the Markov parameters of the system. Finally, state-space models are obtained through the Eigensystem Realization Algorithm using Markov parameters. The main advantage of this approach is that the curve-fitting and the Markov parameter construction are linear problems which avoid the difficulties of nonlinear optimization of other approaches. Another advantage is that it avoids windowing distortions associated with other frequency domain methods.

Chen, Chung-Wen↗
NASA NTRS1992

Advanced techniques in reliability model representation and solution

The current tendency of flight control system designs is towards increased integration of applications and increased distribution of computational elements. The reliability analysis of such systems is difficult because subsystem interactions are increasingly interdependent. Researchers at NASA Langley Research Center have been working for several years to extend the capability of Markov modeling techniques to address these problems. This effort has been focused in the areas of increased model abstraction and increased computational capability. The reliability model generator (RMG) is a software tool that uses as input a graphical object-oriented block diagram of the system. RMG uses a failure-effects algorithm to produce the reliability model from the graphical description. The ASSURE software tool is a parallel processing program that uses the semi-Markov unreliability range evaluator (SURE) solution technique and the abstract semi-Markov specification interface to the SURE tool (ASSIST) modeling language. A failure modes-effects simulation is used by ASSURE. These tools were used to analyze a significant portion of a complex flight control system. The successful combination of the power of graphical representation, automated model generation, and parallel computation leads to the conclusion that distributed fault-tolerant system architectures can now be analyzed.

Palumbo, Daniel L.↗