Search NASA⌕ Search

SEARCH · Search NASA

Results for “Markov decision 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.

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

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2003

Hybrid Discrete-Continuous Markov Decision Processes

This paper proposes a Markov decision process (MDP) model that features both discrete and continuous state variables. We extend previous work by Boyan and Littman on the mono-dimensional time-dependent MDP to multiple dimensions. We present the principle of lazy discretization, and piecewise constant and linear approximations of the model. Having to deal with several continuous dimensions raises several new problems that require new solutions. In the (piecewise) linear case, we use techniques from partially- observable MDPs (POMDPS) to represent value functions as sets of linear functions attached to different partitions of the state space.

Feng, Zhengzhu↗
NASA NTRSDate not supplied

Markov Decision Process based Trajectory Planning for UAVs under Uncertain Wind Conditions

In this paper we propose a Markov Decision Process (MDP) algorithm for path-planning of Unmanned Aviation Vehicles (UAVs) under varying wind conditions. Solutions to path-planning for UAVs are becoming increasingly necessary as autonomous UAVs continue to enter commercial and government spaces. Path-planning is inherently challenging, as UAVs needs to account for dynamically changing flying conditions such as weather, obstacle or no-fly zones, degraded vehicle health and off-nominal battery power consumption. Machine learning methods such as Markov Decision Process (MDPs) have the potential to revolutionize how vehicles navigate in such uncertain environments. Previous papers have demonstrated the use of MDPs to optimize UAV path-planning for energy consumption under time-varying wind distribution. In this study, UAV trajectories from a pre-determined waypoint to target cell, will be computed on a 7X7 grid environment by optimizing parameters for mission assurance and safety limits in addition to the energy consumption, and operation time. The UAV navigates the grid by taking actions to move in either of the eight cardinal and intercardinal directions, under constant thrust profile. The next state of the UAV is calculated by considering its action, transition probability, obstacle cells and the wind speed magnitude and direction. Both constant and stochastic wind will be considered in this paper, the parameters being extracted from real wind measurements in proximity to an experimental UAV flight. One of the studies to be demonstrated in this paper is that as the unmanned airspace gets more complex with multiple vehicles and environmental uncertainties, trade-offs between energy consumption, operation time, risk tolerance, and mission assurance needs to be made. Further, MDPs are capable of fast computation of UAV trajectories under varying wind, hence making them suitable for in-flight path planners.

decision-making↗
NASA NTRS2003

Symbolic Heuristic Search for Factored Markov Decision Processes

We describe a planning algorithm that integrates two approaches to solving Markov decision processes with large state spaces. State abstraction is used to avoid evaluating states individually. Forward search from a start state, guided by an admissible heuristic, is used to avoid evaluating all states. We combine these two approaches in a novel way that exploits symbolic model-checking techniques and demonstrates their usefulness for decision-theoretic planning.

Morris, Robert↗
NASA NTRS2003

Transition-Independent Decentralized Markov Decision Processes

There has been substantial progress with formal models for sequential decision making by individual agents using the Markov decision process (MDP). However, similar treatment of multi-agent systems is lacking. A recent complexity result, showing that solving decentralized MDPs is NEXP-hard, provides a partial explanation. To overcome this complexity barrier, we identify a general class of transition-independent decentralized MDPs that is widely applicable. The class consists of independent collaborating agents that are tied up by a global reward function that depends on both of their histories. We present a novel algorithm for solving this class of problems and examine its properties. The result is the first effective technique to solve optimally a class of decentralized MDPs. This lays the foundation for further work in this area on both exact and approximate solutions.

Becker, Raphen↗
NASA NTRS2018

A Markov Decision Process Framework for Optimal Airport Reconfiguration

The airport runway configuration is defined as a combination set of runways for arrivals and departures used at a point during operation of the airport. An optimal configuration of these runways depends on a number of factors, including traffic demand, wind magnitude and direction, other adverse weather conditions, and noise restrictions, among others. Based on the current state of these factors and predictions of traffic demand and weather conditions, runway configuration changes are made and coordinated between tower controller, other air traffic control facilities, pilots, and ground personnel. Reconfigurations can be quite disruptive to airport operations; minimizing their frequency and scheduling them well in advance is essential for mitigating some of the added workload for controllers and pilots. Unfortunately, deciding on an appropriate time to change is challenging for human decision makers. Not only do multiple factors need to be evaluated, but the uncertainty in their forecasts must also be considered. Previous optimization methods, such as mixed linear integer programming, have been proposed. Although these methods can reason over a large set of variables, they do not systematically handle the uncertainty associated with weather movement, traffic demands, and other variables. In this work, we introduce a Markov Decision Process (MDP)-based decision making framework which can reason effectively over the inherent uncertainties and make optimal decisions on if/when to change the airport configuration. In a prototype implementation, we present a single runway with three aircraft and utilize knowledge of the forecasted wind speed and direction to determine whether to keep or change the current runway configuration. Our aim through this work is to present a framework for airport reconfiguration which can be scalable to additional aircraft, multiple runways, and various input parameters. This technique will optimize the airport reconfiguration procedure by providing a proactive approach, optimizing not just at the next optimal opportunity for a reconfiguration based on varying atmospheric and traffic conditions in the terminal airspace, but also anticipating future necessary reconfigurations. This will eliminate the inefficiencies of frequent changes currently associated with runway reconfiguration procedures.

runway reconfiguration↗
NASA NTRS1999

Cooperation and Coordination Between Fuzzy Reinforcement Learning Agents in Continuous State Partially Observable Markov Decision Processes

Successful operations of future multi-agent intelligent systems require efficient cooperation schemes between agents sharing learning experiences. We consider a pseudo-realistic world in which one or more opportunities appear and disappear in random locations. Agents use fuzzy reinforcement learning to learn which opportunities are most worthy of pursuing based on their promise rewards, expected lifetimes, path lengths and expected path costs. We show that this world is partially observable because the history of an agent influences the distribution of its future states. We consider a cooperation mechanism in which agents share experience by using and-updating one joint behavior policy. We also implement a coordination mechanism for allocating opportunities to different agents in the same world. Our results demonstrate that K cooperative agents each learning in a separate world over N time steps outperform K independent agents each learning in a separate world over K*N time steps, with this result becoming more pronounced as the degree of partial observability in the environment increases. We also show that cooperation between agents learning in the same world decreases performance with respect to independent agents. Since cooperation reduces diversity between agents, we conclude that diversity is a key parameter in the trade off between maximizing utility from cooperation when diversity is low and maximizing utility from competitive coordination when diversity is high.

Berenji, Hamid R.↗
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 NTRS2000

Back to the Future: Consistency-Based Trajectory Tracking

Given a model of a physical process and a sequence of commands and observations received over time, the task of an autonomous controller is to determine the likely states of the process and the actions required to move the process to a desired configuration. We introduce a representation and algorithms for incrementally generating approximate belief states for a restricted but relevant class of partially observable Markov decision processes with very large state spaces. The algorithm presented incrementally generates, rather than revises, an approximate belief state at any point by abstracting and summarizing segments of the likely trajectories of the process. This enables applications to efficiently maintain a partial belief state when it remains consistent with observations and revisit past assumptions about the process' evolution when the belief state is ruled out. The system presented has been implemented and results on examples from the domain of spacecraft control are presented.

Kurien, James↗
NASA NTRS1986

An optimal repartitioning decision policy

A central problem to parallel processing is the determination of an effective partitioning of workload to processors. The effectiveness of any given partition is dependent on the stochastic nature of the workload. The problem of determining when and if the stochastic behavior of the workload has changed enough to warrant the calculation of a new partition is treated. The problem is modeled as a Markov decision process, and an optimal decision policy is derived. Quantification of this policy is usually intractable. A heuristic policy which performs nearly optimally is investigated empirically. The results suggest that the detection of change is the predominant issue in this problem.

Nicol, D. M.↗
NASA NTRS1998

Markov Tracking for Agent Coordination

Partially observable Markov decision processes (POMDPs) axe an attractive representation for representing agent behavior, since they capture uncertainty in both the agent's state and its actions. However, finding an optimal policy for POMDPs in general is computationally difficult. In this paper we present Markov Tracking, a restricted problem of coordinating actions with an agent or process represented as a POMDP Because the actions coordinate with the agent rather than influence its behavior, the optimal solution to this problem can be computed locally and quickly. We also demonstrate the use of the technique on sequential POMDPs, which can be used to model a behavior that follows a linear, acyclic trajectory through a series of states. By imposing a "windowing" restriction that restricts the number of possible alternatives considered at any moment to a fixed size, a coordinating action can be calculated in constant time, making this amenable to coordination with complex agents.

Washington, Richard↗
NASA NTRS2003

Modeling, Analyzing, and Mitigating Dissonance Between Alerting Systems

Alerting systems are becoming pervasive in process operations, which may result in the potential for dissonance or conflict in information from different alerting systems that suggests different threat levels and/or actions to resolve hazards. Little is currently available to help in predicting or solving the dissonance problem. This thesis presents a methodology to model and analyze dissonance between alerting systems, providing both a theoretical foundation for understanding dissonance and a practical basis from which specific problems can be addressed. A state-space representation of multiple alerting system operation is generalized that can be tailored across a variety of applications. Based on the representation, two major causes of dissonance are identified: logic differences and sensor error. Additionally, several possible types of dissonance are identified. A mathematical analysis method is developed to identify the conditions for dissonance originating from logic differences. A probabilistic analysis methodology is developed to estimate the probability of dissonance originating from sensor error, and to compare the relative contribution to dissonance of sensor error against the contribution from logic differences. A hybrid model, which describes the dynamic behavior of the process with multiple alerting systems, is developed to identify dangerous dissonance space, from which the process can lead to disaster. Methodologies to avoid or mitigate dissonance are outlined. Two examples are used to demonstrate the application of the methodology. First, a conceptual In-Trail Spacing example is presented. The methodology is applied to identify the conditions for possible dissonance, to identify relative contribution of logic difference and sensor error, and to identify dangerous dissonance space. Several proposed mitigation methods are demonstrated in this example. In the second example, the methodology is applied to address the dissonance problem between two air traffic alert and avoidance systems: the existing Traffic Alert and Collision Avoidance System (TCAS) vs. the proposed Airborne Conflict Management system (ACM). Conditions on ACM resolution maneuvers are identified to avoid dynamic dissonance between TCAS and ACM. Also included in this report is an Appendix written by Lee Winder about recent and continuing work on alerting systems design. The application of Markov Decision Process (MDP) theory to complex alerting problems is discussed and illustrated with an abstract example system.

Song, Lixia↗
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 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.↗