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.

SourceResearch connectionFrom yearThrough year

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

At least 145 records · Page 8

All sources NASA NTRS DOE OSTI

NASA NTRS1974

Wave propagation in a random medium - A complete set of the moment equations with different wavenumbers

The propagation of waves in a random medium is studied in the 'quasi-optics' and the 'Markov random process' approximations. Under these assumptions, a Fokker-Planck equation satisfied by the characteristic functional of the random wave field is derived. A complete set of moment equations with different transverse coordinates and different wave numbers is then obtained from the Fokker-Planck equation of the characteristic functional. The application of those results to the pulse smearing of the pulsar signal and the frequency correlation function of the wave intensity in interstellar scintillation is briefly discussed.

Lee, L. C.↗

NASA NTRS1980

An application of extremal field guidance in statistical low thrust guidance analysis

The subject of this paper is the application of extremal field guidance to the covariance analysis of low thrust retargeting guidance. The general procedure for low thrust navigation analysis is briefly reviewed. The basic equations of trajectory optimization and extremal field guidance are presented with emphasis on the low thrust problem. The adopted formulation includes thruster on-off times as control variables and accounts for the effects of model parameter variations. A method of solution of the guidance equations is outlined; and the application of the solution in a covariance analysis, including a procedure for the treatment of model parameter variations as either biases or first order Gauss-Markov stochastic processes, is discussed.

Jacobson, R. A.↗

NASA NTRS1982

Optimum equipment maintenance/replacement policy. Part 2: Markov decision approach

Dynamic programming was utilized as an alternative optimization technique to determine an optimal policy over a given time period. According to a joint effect of the probabilistic transition of states and the sequence of decision making, the optimal policy is sought such that a set of decisions optimizes the long-run expected average cost (or profit) per unit time. Provision of an alternative measure for the expected long-run total discounted costs is also considered. A computer program based on the concept of the Markov Decision Process was developed and tested. The program code listing, the statement of a sample problem, and the computed results are presented.

Charng, T.↗

NASA NTRS1990

Space system operations and support cost analysis using Markov chains

This paper evaluates the use of Markov chain process in probabilistic life cycle cost analysis and suggests further uses of the process as a design aid tool. A methodology is developed for estimating operations and support cost and expected life for reusable space transportation systems. Application of the methodology is demonstrated for the case of a hypothetical space transportation vehicle. A sensitivity analysis is carried out to explore the effects of uncertainty in key model inputs.

Unal, Resit↗

NASA NTRS1992

Stochastic stability properties of jump linear systems

Jump linear systems are defined as a family of linear systems with randomly jumping parameters (usually governed by a Markov jump process) and are used to model systems subject to failures or changes in structure. The authors study stochastic stability properties in jump linear systems and the relationship among various moment and sample path stability properties. It is shown that all second moment stability properties are equivalent and are sufficient for almost sure sample path stability, and a testable necessary and sufficient condition for second moment stability is derived. The Lyapunov exponent method for the study of almost sure sample stability is discussed, and a theorem which characterizes the Lyapunov exponents of jump linear systems is presented.

Feng, Xiangbo↗

NASA NTRS1995

Interdecadal Variations in the Alaska Gyre

Climatic dynamic topography variations in the Alaska gyre during the period 1968-1990 are described with an objective analysis of more than 12000 STD and XBT stations, and COADS wind stress data Interannual the dynamic height and SST variations were correlated and were consistent with recently described large-scale climatic shifts in the North Pacific. The gyre was centered more to the east, circulation appeared stronger, and SST was lower during the early to mid-1970s than during the 1980s. The Aleutian low (NP and PNA indices) intensified during the interim, but the response did not appear as a gyre spinup. Instead, the associated wind stress anomalies forced a slowly varying dynamic height anomaly across the eastern and northern part of the gyre through Ekman convergence, which had the effect of displacing the gyre's low somewhat to the WSW in the 1980s. The wind curl spectrum was white, and the slow oceanic response was modeled as stochastic-forced climate variability with a simple first-order Markov autoregression process. Forcing was assumed to be Ekman pumping of the pycnocline, and the damping coefficient was estimated from the data to be approx. 1 yr. A hindcast with observed winds gave estimated dynamic height patterns similar to those observed, with a canonical correlation of 0.79 at 99% confidence. This response was weak in the western half of the gyre, where slow baroclinic variability may have been influenced by long Rossby wave propagation. A simple autoregression simulation using artificial white noise forcing shows the evolution of decadal variations similar in nature to those observed. This result, along with the low frequency correlation between dynamic height and SST, suggests that the upper-ocean climatic variability in this region is primarily wind forced.

Lagerloef, Gary S.E.↗

NASA NTRS2000

Exact Solutions to Time-dependent Mdps

We describe an extension of the Markov decision process model in which a continuous time dimension is included in the state space. This allows for the representation and exact solution of a wide range of problems in which transitions or rewards vary over time. We examine problems based on route planning with public transportation and telescope observation scheduling.

Boyan, Justin A.↗

NASA NTRS2000

Integrated Thermal Response Modeling System For Hypersonic Entry Vehicles

We describe all extension of the Markov decision process model in which a continuous time dimension is included ill the state space. This allows for the representation and exact solution of a wide range of problems in which transitions or rewards vary over time. We examine problems based on route planning with public transportation and telescope observation scheduling.

Chen, Y.-K.↗

NASA NTRS1998

Making the Impossible Possible: Strategies for Fast POMDP Monitoring

Systems modeled as partially observable Markov decision processes (POMDPs) can be tracked quickly with three restrictions: all actions are grouped together, the out-degree of each system state is bounded by a constant, and the number of non-zero elements in the belief state is bounded by a (different) constant. With these restrictions, the tracking algorithm operates in constant time and linear space. The first restriction assumes that the action itself is unobservable. The second restriction defines a subclass of POMDPs that covers however a wide range of problems. The third restriction is an approximation technique that can lead to a potentially vexing problem: an observation may be received that has probability according to the restricted belief state. This problem of impossibility will cause the belief state to collapse. In this paper we discuss the tradeoffs between the constant bound on the belief state and the quality of the solution. We concentrate on strategies for overcoming the impossibility problem and demonstrate initial experimental results that indicate promising directions.

Washington, Richard↗

NASA NTRS2003

Reinforcement Learning for Weakly-Coupled MDPs and an Application to Planetary Rover Control

Weakly-coupled Markov decision processes can be decomposed into subprocesses that interact only through a small set of bottleneck states. We study a hierarchical reinforcement learning algorithm designed to take advantage of this particular type of decomposability. To test our algorithm, we use a decision-making problem faced by autonomous planetary rovers. In this problem, a Mars rover must decide which activities to perform and when to traverse between science sites in order to make the best use of its limited resources. In our experiments, the hierarchical algorithm performs better than Q-learning in the early stages of learning, but unlike Q-learning it converges to a suboptimal policy. This suggests that it may be advantageous to use the hierarchical algorithm when training time is limited.

Bernstein, Daniel S.↗

NASA NTRS2003

Optimal Limited Contingency Planning

For a given problem, the optimal Markov policy over a finite horizon is a conditional plan containing a potentially large number of branches. However, there are applications where it is desirable to strictly limit the number of decision points and branches in a plan. This raises the question of how one goes about finding optimal plans containing only a limited number of branches. In this paper, we present an any-time algorithm for optimal k-contingency planning. It is the first optimal algorithm for limited contingency planning that is not an explicit enumeration of possible contingent plans. By modelling the problem as a partially observable Markov decision process, it implements the Bellman optimality principle and prunes the solution space. We present experimental results of applying this algorithm to some simple test cases.

Meuleau, Nicolas↗

NASA NTRS2004

Unifying Temporal and Structural Credit Assignment Problems

Single-agent reinforcement learners in time-extended domains and multi-agent systems share a common dilemma known as the credit assignment problem. Multi-agent systems have the structural credit assignment problem of determining the contributions of a particular agent to a common task. Instead, time-extended single-agent systems have the temporal credit assignment problem of determining the contribution of a particular action to the quality of the full sequence of actions. Traditionally these two problems are considered different and are handled in separate ways. In this article we show how these two forms of the credit assignment problem are equivalent. In this unified frame-work, a single-agent Markov decision process can be broken down into a single-time-step multi-agent process. Furthermore we show that Monte-Carlo estimation or Q-learning (depending on whether the values of resulting actions in the episode are known at the time of learning) are equivalent to different agent utility functions in a multi-agent system. This equivalence shows how an often neglected issue in multi-agent systems is equivalent to a well-known deficiency in multi-time-step learning and lays the basis for solving time-extended multi-agent problems, where both credit assignment problems are present.

Agogino, Adrian K.↗

NASA NTRS2004

Dynamic Programming for Structured Continuous Markov Decision Problems

We describe an approach for exploiting structure in Markov Decision Processes with continuous state variables. At each step of the dynamic programming, the state space is dynamically partitioned into regions where the value function is the same throughout the region. We first describe the algorithm for piecewise constant representations. We then extend it to piecewise linear representations, using techniques from POMDPs to represent and reason about linear surfaces efficiently. We show that for complex, structured problems, our approach exploits the natural structure so that optimal solutions can be computed efficiently.

Dearden, Richard↗

NASA NTRS2005

Studies of Cosmic Ray Modulation and Energetic Particle Propagation in Time-Dependent 3-Dimensional Heliospheric Magnetic Fields

The primary goal of this project was to perform theoretical calculations of propagation of cosmic rays and energetic particles in 3-dimensional heliospheric magnetic fields. We used Markov stochastic process simulation to achieve to this goal. We developed computation software that can be used to study particle propagation in, as two examples of heliospheric magnetic fields that have to be treated in 3 dimensions, a heliospheric magnetic field suggested by Fisk (1996) and a global heliosphere including the region beyond the termination shock. The results from our model calculations were compared with particle measurements from Ulysses, Earth-based spacecraft such as IMP-8, WIND and ACE, Voyagers and Pioneers in outer heliosphere for tests of the magnetic field models. We particularly looked for features of particle variations that can allow us to significantly distinguish the Fisk magnetic field from the conventional Parker spiral field. The computer code will eventually lead to a new generation of integrated software for solving complicated problems of particle acceleration, propagation and modulation in realistic 3-dimensional heliosphere of realistic magnetic fields and the solar wind with a single computation approach.

Zhang, Ming↗

NASA NTRS2007

Learning Grasp Strategies Composed of Contact Relative Motions

Of central importance to grasp synthesis algorithms are the assumptions made about the object to be grasped and the sensory information that is available. Many approaches avoid the issue of sensing entirely by assuming that complete information is available. In contrast, this paper proposes an approach to grasp synthesis expressed in terms of units of control that simultaneously change the contact configuration and sense information about the object and the relative manipulator-object pose. These units of control, known as contact relative motions (CRMs), allow the grasp synthesis problem to be recast as an optimal control problem where the goal is to find a strategy for executing CRMs that leads to a grasp in the shortest number of steps. An experiment is described that uses Robonaut, the NASA-JSC space humanoid, to show that CRMs are a viable means of synthesizing grasps. However, because of the limited amount of information that a single CRM can sense, the optimal control problem may be partially observable. This paper proposes expressing the problem as a k-order Markov Decision Process (MDP) and solving it using Reinforcement Learning. This approach is tested in a simulation of a two-contact manipulator that learns to grasp an object. Grasp strategies learned in simulation are tested on the physical Robonaut platform and found to lead to grasp configurations consistently.

Platt, Robert, Jr.↗

NASA NTRS2011

Use of Inverse Reinforcement Learning for Identity Prediction

We adopt Markov Decision Processes (MDP) to model sequential decision problems, which have the characteristic that the current decision made by a human decision maker has an uncertain impact on future opportunity. We hypothesize that the individuality of decision makers can be modeled as differences in the reward function under a common MDP model. A machine learning technique, Inverse Reinforcement Learning (IRL), was used to learn an individual's reward function based on limited observation of his or her decision choices. This work serves as an initial investigation for using IRL to analyze decision making, conducted through a human experiment in a cyber shopping environment. Specifically, the ability to determine the demographic identity of users is conducted through prediction analysis and supervised learning. The results show that IRL can be used to correctly identify participants, at a rate of 68% for gender and 66% for one of three college major categories.

Hayes, Roy↗

NASA NTRS2011

Probabilistic Path Planning of Montgolfier Balloons in Strong, Uncertain Wind Fields

Lighter-than-air vehicles such as hot-air balloons have been proposed for exploring Saturn s moon Titan, as well as other bodies with significant atmospheres. For these vehicles to navigate effectively, it is critical to incorporate the effects of surrounding wind fields, especially as these winds will likely be strong relative to the control authority of the vehicle. Predictive models of these wind fields are available, and previous research has considered problems of planning paths subject to these predicted forces. However, such previous work has considered the wind fields as known a priori, whereas in practical applications, the actual wind vector field is not known exactly and may deviate significantly from the wind velocities estimated by the model. A probabilistic 3D path-planning algorithm was developed for balloons to use uncertain wind models to generate time-efficient paths. The nominal goal of the algorithm is to determine what altitude and what horizontal actuation, if any is available on the vehicle, to use to reach a particular goal location in the least expected time, utilizing advantageous winds. The solution also enables one to quickly evaluate the expected time-to-goal from any other location and to avoid regions of large uncertainty. This method is designed for balloons in wind fields but may be generalized for any buoyant vehicle operating in a vector field. To prepare the planning problem, the uncertainty in the wind field is modeled. Then, the problem of reaching a particular goal location is formulated as a Markov decision process (MDP) using a discretized space approach. Solving the MDP provides a policy of what actuation option (how much buoyancy change and, if applicable, horizontal actuation) should be selected at any given location to minimize the expected time-to-goal. The results provide expected time-to-goal values from any given location on the globe in addition to the action policy. This stochastic approach can also provide insights not accessible by deterministic methods; for example, one can evaluate variability and risk associated with different scenarios, rather than only viewing the expected outcome.

Wolf, Michael↗

NASA NTRS2014

Exact and Approximate Probabilistic Symbolic Execution

Probabilistic software analysis seeks to quantify the likelihood of reaching a target event under uncertain environments. Recent approaches compute probabilities of execution paths using symbolic execution, but do not support nondeterminism. Nondeterminism arises naturally when no suitable probabilistic model can capture a program behavior, e.g., for multithreading or distributed systems. In this work, we propose a technique, based on symbolic execution, to synthesize schedulers that resolve nondeterminism to maximize the probability of reaching a target event. To scale to large systems, we also introduce approximate algorithms to search for good schedulers, speeding up established random sampling and reinforcement learning results through the quantification of path probabilities based on symbolic execution. We implemented the techniques in Symbolic PathFinder and evaluated them on nondeterministic Java programs. We show that our algorithms significantly improve upon a state-of- the-art statistical model checking algorithm, originally developed for Markov Decision Processes.

Symbolic Execution↗