Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Markov decision processes”

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
DOE OSTI2022

Deep Reinforcement Learning based Model-free On-line Dynamic Multi-Microgrid Formation to Enhance Resilience

Multi-microgrid formation (MMGF) is a promising solution for enhancing power system resilience. This paper proposes a new deep reinforcement learning (RL) based model-free on-line dynamic MMGF scheme. Additionally, the dynamic MMGF problem is formulated as a Markov decision process, and a complete deep RL framework is specially designed for the topologytransformable micro-grids. In order to reduce the large action space caused by flexible switch operations, a topology transformation method is proposed and an action-decoupling Q-value is applied. Then, a convolutional neural network (CNN) based multi-buffer double deep Q-network (CM-DDQN) is developed to further improve the learning ability of the original DQN method. The proposed deep RL method provides real-time computing to support the on-line dynamic MMGF scheme, and the scheme handles a long-term resilience enhancement problem using an adaptive on-line MMGF to defend changeable conditions. The effectiveness of the proposed method is validated using a 7-bus system and the IEEE 123-bus system. The results show strong learning ability, timely response for varying system conditions and convincing resilience enhancement.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2024

Learning Robust Marking Policies for Adaptive Mesh Refinement

Here in this work, we revisit the marking decisions made in the standard adaptive finite element method (AFEM). Experience shows that a naïve marking policy leads to inefficient use of computational resources for adaptive mesh refinement (AMR). Consequently, using AMR in practice often involves ad-hoc or time-consuming offline parameter tuning to set appropriate parameters for the marking subroutine. To address these practical concerns, we recast AMR as a Markov decision process in which refinement parameters can be selected on-the-fly at run time, without the need for pre-tuning by expert users. In this new paradigm, the refinement parameters are also chosen adaptively via a marking policy that can be optimized using methods from reinforcement learning. We use the Poisson equation to demonstrate our techniques on h- and hp-refinement benchmark problems, and our experiments suggest that superior marking policies remain undiscovered for many classical AFEM applications. Furthermore, an unexpected observation from this work is that marking policies trained on one family of PDEs are sometimes robust enough to perform well on problems far outside the training family. For illustration, we show that a simple hp-refinement policy trained on 2D domains with only a single re-entrant corner can be deployed on far more complicated 2D domains, and even 3D domains, without significant performance loss. For reproduction and broader adoption, we accompany this work with an open-source implementation of our methods.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Automated Adversary-in-the-Loop Cyber-Physical Defense Planning

Security of cyber-physical systems (CPS) continues to pose new challenges due to the tight integration and operational complexity of the cyber and physical components. To address these challenges, this article presents a domain-aware, optimization-based approach to determine an effective defense strategy for CPS in an automated fashion—by emulating a strategic adversary in the loop that exploits system vulnerabilities, interconnection of the CPS, and the dynamics of the physical components. Our approach builds on an adversarial decision-making model based on a Markov Decision Process (MDP) that determines the optimal cyber (discrete) and physical (continuous) attack actions over a CPS attack graph. The defense planning problem is modeled as a non-zero-sum game between the adversary and defender. We use a model-free reinforcement learning method to solve the adversary’s problem as a function of the defense strategy. We then employ Bayesian optimization (BO) to find an approximate best-response for the defender to harden the network against the resulting adversary policy. This process is iterated multiple times to improve the strategy for both players. We demonstrate the effectiveness of our approach on a ransomware-inspired graph with a smart building system as the physical process. Numerical studies show that our method converges to a Nash equilibrium for various defender-specific costs of network hardening.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Hybrid-RL-MPC4CLR (Hybird-Reinforcement-Learning-Model-Predictive-Control-for-Reserve-Policy-Assisted-Critical-Load-Restoration-in-Distribution-Grids)

Hybrid-RL-MPC4CLR was developed as a hybrid controller for active distribution grid critical load restoration, combining deep reinforcement learning (RL) and model predictive control (MPC) aiming at maximizing total restored load following an extreme event. The RL determines a policy for quantifying operating reserve requirements, thereby hedging against uncertainty, while the MPC models grid operations incorporating the RL policy actions (i.e., reserve requirements), renewable (wind and solar) power predictions, and load demand forecasts. The developers formulated the reserve requirement determination problem as a sequential decision-making problem based on the Markov Decision Process (MDP) and design an RL learning environment based on the OpenAI Gym framework and MPC simulation. The RL agent reward and MPC objective function aim to maximize and monotonically increase total restored load and minimize load shedding and renewable power curtailment. The software is developed using various software packages in Python. The MPC's optimal power flow (OPF) model is implemented using the Pyomo package, the RL simulation environment is implemented using the MPC simulation with various scenarios of renewable energy and load demand profiles and power outage beginning times, based on the OpenAI Gym framework. The RL agent training is performed using the RLlib Ray package. The RL algorithm is trained offline using historical forecasts of renewable generation and load demand profiles. Simulation analysis and performance tests are conducted using a modified IEEE 13-bus distribution test feeder containing wind turbine, photovoltaic, microturbine, and battery.

Eseye, Abinet Tesfaye↗
DOE OSTI2022

Robotic Planning under Uncertainty in Spatiotemporal Environments in Expeditionary Science

In the expeditionary sciences, spatiotemporally varying environments -- hydrothermal plumes, algal blooms, lava flows, or animal migrations -- are ubiquitous. Mobile robots are uniquely well-suited to study these dynamic, mesoscale natural environments. We formalize expeditionary science as a sequential decision-making problem, modeled using the language of partially-observable Markov decision processes (POMDPs). Solving the expeditionary science POMDP under real-world constraints requires efficient probabilistic modeling and decision-making in problems with complex dynamics and observational models. Previous work in informative path planning, adaptive sampling, and experimental design have shown compelling results, largely in static environments, using data-driven models and information-based rewards. However, these methodologies do not trivially extend to expeditionary science in spatiotemporal environments: they generally do not make use of scientific knowledge such as equations of state dynamics, they focus on information gathering as opposed to scientific task execution, and they make use of decision-making approaches that scale poorly to large, continuous problems with long planning horizons and real-time operational constraints. In this work, we discuss these and other challenges related to probabilistic modeling and decision-making in expeditionary science, and present some of our preliminary work that addresses these gaps. We ground our results in a real expeditionary science deployment of an autonomous underwater vehicle (AUV) in the deep ocean for hydrothermal vent discovery and characterization. Our concluding thoughts highlight remaining work to be done, and the challenges that merit consideration by the reinforcement learning and decision-making community.

Preston, Victoria↗
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.↗
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 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↗
NASA NTRS2010

Probabilistic Motion Planning of Balloons in Strong, Uncertain Wind Fields

This paper introduces a new algorithm for probabilistic motion planning in arbitrary, uncertain vector fields, with emphasis on high-level planning for Montgolfiere balloons in the atmosphere of Titan. The 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 goal location in the fastest expected time. The winds can vary greatly at different altitudes and are strong relative to any feasible horizontal actuation, so the incorporation of the winds is critical for guidance plans. This paper focuses on how to integrate the uncertainty of the wind field into the wind model and how to reach a goal location through the uncertain wind field, using a Markov decision process (MDP). The resulting probabilistic solutions enable more robust guidance plans and more thorough analysis of potential paths than existing methods.

Wolf, Michael T.↗