Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “constraint satisfaction problems”

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

Ensuring Transient Stability With Guaranteed Region of Attraction in DC Microgrids

DC microgrids have promising applications in renewable integration due to their better energy efficiency when connecting DC components. However, they might be unstable since many loads in a DC microgrid are regulated as constant power loads (CPLs) that have a destabilizing negative impedance effect. As a result, the state trajectory displacement caused by abrupt load changes or contingencies can easily lead to instability. Many existing works have been devoted to studying the region of attraction (ROA) of a DC microgrid, in which the system is guaranteed to be asymptotically stable. Nevertheless, existing work either focuses on using numerical methods for ROA approximations that generally have no performance guarantees or cannot ensure a desired ROA for a general DC microgrid. To close this gap, this paper develops an innovative control synthesis algorithm to make a general DC microgrid have a theoretically guaranteed ROA, for example, to cover the entirety of its operating range regarding state trajectories. Here, we first study the nonlinear dynamics of a DC microgrid to derive a novel transient stability condition to rigorously certify whether a given operating range is a subset of the ROA; then, we formulate a control synthesis optimization problem to guarantee the condition’s satisfaction. This condition is a linear constraint, and the optimization problem resembles an optimal power flow problem and has a good computational behavior. Simulation case studies verify the validity of the proposed work.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2019

On Expected Value Strong Controllability

The Probabilistic Simple Temporal Network (PSTN) generalizes Simple Temporal Networks with Uncertainty (STNUs) by introducing probability distributions over the timing of uncontrollable timepoints. PSTNs are controllable if there is a strategy to execute the controllable timepoints while bounding the risk of violating any constraint to a small value. If this risk bound can't be satisfied, PSTNs are not considered controllable. We introduce the Expected Value Probabilistic SimpleTemporal Network (EPSTN), which extends PSTNs by including a benefit to the satisfaction of temporal constraints. We study the problem of Expected Value Strong Controllability (EvSC) of EPSTNs, which seeks a schedule maximizing the expected value of satisfied constraints. We solve the EvSC problem by extending a previously developed linear program, combined with search over constraints to violate at execution time. We describe conditions under which the solution to this linear program is the maximum expected value schedule. We then show how to search for constraints to discard, using the linear program at the core of the search. While the general problem is shown to be exponential, we conclude by providing several methods to bound the complexity of search.

Planning↗
NASA NTRS1991

Balancing antagonistic time and resource utilization constraints in over-subscribed scheduling problems

In this paper, we report work aimed at applying concepts of constraint-based problem structuring and multi-perspective scheduling to an over-subscribed scheduling problem. Previous research has demonstrated the utility of these concepts as a means for effectively balancing conflicting objectives in constraint-relaxable scheduling problems, and our goal here is to provide evidence of their similar potential in the context of HST observation scheduling. To this end, we define and experimentally assess the performance of two time-bounded heuristic scheduling strategies in balancing the tradeoff between resource setup time minimization and satisfaction of absolute time constraints. The first strategy considered is motivated by dispatch-based manufacturing scheduling research, and employs a problem decomposition that concentrates local search on minimizing resource idle time due to setup activities. The second is motivated by research in opportunistic scheduling and advocates a problem decomposition that focuses attention on the goal activities that have the tightest temporal constraints. Analysis of experimental results gives evidence of differential superiority on the part of each strategy in different problem solving circumstances. A composite strategy based on recognition of characteristics of the current problem solving state is then defined and tested to illustrate the potential benefits of constraint-based problem structuring and multi-perspective scheduling in over-subscribe scheduling problems.

Smith, Stephen F.↗
NASA NTRS1991

Method and apparatus for configuration control of redundant robots

A method and apparatus to control a robot or manipulator configuration over the entire motion based on augmentation of the manipulator forward kinematics is disclosed. A set of kinematic functions is defined in Cartesian or joint space to reflect the desirable configuration that will be achieved in addition to the specified end-effector motion. The user-defined kinematic functions and the end-effector Cartesian coordinates are combined to form a set of task-related configuration variables as generalized coordinates for the manipulator. A task-based adaptive scheme is then utilized to directly control the configuration variables so as to achieve tracking of some desired reference trajectories throughout the robot motion. This accomplishes the basic task of desired end-effector motion, while utilizing the redundancy to achieve any additional task through the desired time variation of the kinematic functions. The present invention can also be used for optimization of any kinematic objective function, or for satisfaction of a set of kinematic inequality constraints, as in an obstacle avoidance problem. In contrast to pseudoinverse-based methods, the configuration control scheme ensures cyclic motion of the manipulator, which is an essential requirement for repetitive operations. The control law is simple and computationally very fast, and does not require either the complex manipulator dynamic model or the complicated inverse kinematic transformation. The configuration control scheme can alternatively be implemented in joint space.

Seraji, Homayoun↗
DOE OSTI2020

The Role of Blockchains in Multi-Stakeholder Transactive Energy Systems

Power grids are undergoing major changes due to rapid growth in renewable energy and improvements in battery technology. Prompted by the increasing complexity of power systems, decentralized solutions are emerging that arrange local communities into transactive microgrids. This paper addresses the problem of implementing transactive energy mechanisms in a distributed setting, providing both privacy and safety. Specifically, we design and implement an automated auction and matching system that ensures safety (e.g., satisfaction of line capacity constraints), preserves privacy, and promotes local trade and market efficiency for transactive energy systems. This design problem is challenging because safety, market efficiency, and privacy are competing objectives. We implement our solution as a decentralized trading platform built on blockchain technology and smart contracts. To demonstrate the viability of our platform, we analyze the results of experiments with dozens of embedded devices and energy production and consumption profiles using an actual dataset from the transactive energy domain.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
NASA NTRS2013

Powered Descent Guidance with General Thrust-Pointing Constraints

The Powered Descent Guidance (PDG) algorithm and software for generating Mars pinpoint or precision landing guidance profiles has been enhanced to incorporate thrust-pointing constraints. Pointing constraints would typically be needed for onboard sensor and navigation systems that have specific field-of-view requirements to generate valid ground proximity and terrain-relative state measurements. The original PDG algorithm was designed to enforce both control and state constraints, including maximum and minimum thrust bounds, avoidance of the ground or descent within a glide slope cone, and maximum speed limits. The thrust-bound and thrust-pointing constraints within PDG are non-convex, which in general requires nonlinear optimization methods to generate solutions. The short duration of Mars powered descent requires guaranteed PDG convergence to a solution within a finite time; however, nonlinear optimization methods have no guarantees of convergence to the global optimal or convergence within finite computation time. A lossless convexification developed for the original PDG algorithm relaxed the non-convex thrust bound constraints. This relaxation was theoretically proven to provide valid and optimal solutions for the original, non-convex problem within a convex framework. As with the thrust bound constraint, a relaxation of the thrust-pointing constraint also provides a lossless convexification that ensures the enhanced relaxed PDG algorithm remains convex and retains validity for the original nonconvex problem. The enhanced PDG algorithm provides guidance profiles for pinpoint and precision landing that minimize fuel usage, minimize landing error to the target, and ensure satisfaction of all position and control constraints, including thrust bounds and now thrust-pointing constraints.

Carson, John M., III↗
NASA NTRS2013

Final Report - Regulatory Considerations for Adaptive Systems

This report documents the findings of a preliminary research study into new approaches to the software design assurance of adaptive systems. We suggest a methodology to overcome the software validation and verification difficulties posed by the underlying assumption of non-adaptive software in the requirementsbased- testing verification methods in RTCA/DO-178B and C. An analysis of the relevant RTCA/DO-178B and C objectives is presented showing the reasons for the difficulties that arise in showing satisfaction of the objectives and suggested additional means by which they could be satisfied. We suggest that the software design assurance problem for adaptive systems is principally one of developing correct and complete high level requirements and system level constraints that define the necessary system functional and safety properties to assure the safe use of adaptive systems. We show how analytical techniques such as model based design, mathematical modeling and formal or formal-like methods can be used to both validate the high level functional and safety requirements, establish necessary constraints and provide the verification evidence for the satisfaction of requirements and constraints that supplements conventional testing. Finally the report identifies the follow-on research topics needed to implement this methodology.

Wilkinson, Chris↗
NASA NTRS2004

Employing Sensitivity Derivatives for Robust Optimization under Uncertainty in CFD

A robust optimization is demonstrated on a two-dimensional inviscid airfoil problem in subsonic flow. Given uncertainties in statistically independent, random, normally distributed flow parameters (input variables), an approximate first-order statistical moment method is employed to represent the Computational Fluid Dynamics (CFD) code outputs as expected values with variances. These output quantities are used to form the objective function and constraints. The constraints are cast in probabilistic terms; that is, the probability that a constraint is satisfied is greater than or equal to some desired target probability. Gradient-based robust optimization of this stochastic problem is accomplished through use of both first and second-order sensitivity derivatives. For each robust optimization, the effect of increasing both input standard deviations and target probability of constraint satisfaction are demonstrated. This method provides a means for incorporating uncertainty when considering small deviations from input mean values.

Newman, Perry A.↗
NASA NTRS2010

An Optimizing Space Data-Communications Scheduling Method and Algorithm with Interference Mitigation, Generalized for a Broad Class of Optimization Problems

NASA's space data-communications infrastructure, the Space Network and the Ground Network, provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft via orbiting relay satellites and ground stations. An implementation of the methods and algorithms disclosed herein will be a system that produces globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary search, a class of probabilistic strategies for searching large solution spaces, constitutes the essential technology in this disclosure. Also disclosed are methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithm itself. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally, with applicability to a very broad class of combinatorial optimization problems.

Rash, James L.↗
DOE OSTI2021

Optimal Power Flow in DC Networks with Robust Feasibility and Stability Guarantees

With high penetrations of renewable generation and variable loads, there is significant uncertainty associated with power flows in DC networks such that stability and operational constraint satisfaction are of concern. Most existing DC network optimal power flow (DN-OPF) formulations assume exact knowledge of loading conditions and do not provide stability guarantees. Here, in contrast, this paper studies a DN-OPF formulation which considers both stability and operational constraint satisfaction under uncertainty. The need to account for a range of uncertainty realizations in this paper's robust optimization formulation results in a challenging semi-infinite program (SIP). The proposed solution algorithm reformulates this SIP into a computationally tractable problem by constructing a tight convex inner approximation of the stability set using sufficient conditions for the existence of a feasible and stable power flow solution. Optimal generator set-points are obtained by optimizing over the proposed convex stability set. The validity and effectiveness of the propose algorithm is demonstrated through various DC networks adapted from IEEE test cases.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1988

Knowledge based tools for Hubble Space Telescope planning and scheduling: Constraints and strategies

The Hubble Space Telescope (HST) presents an especially challenging scheduling problem since a year's observing program encompasses tens of thousands of exposures facing numerous coupled constraints. Recent progress in the development of planning and scheduling tools is discussed which augment the existing HST ground system. General methods for representing activities, constraints, and constraint satisfaction, and time segmentation were implemented in a scheduling testbed. The testbed permits planners to evaluate optimal scheduling time intervals, calculate resource usage, and to generate long and medium range plans. Graphical displays of activities, constraints, and plans are an important feature of the system. High-level scheduling strategies using rule based and neural net approaches were implemented.

Miller, Glenn↗
DOE OSTI2022

Learning Stochastic Parametric Differentiable Predictive Control Policies

We present a scalable unsupervised learning-based method for obtaining explicit control policies for model predictive control problems for stochastic linear systems with additive uncertainties subject to nonlinear chance constraints. We call the proposed method stochastic parametric differentiable predictive control (SP-DPC), which extends the recently proposed deterministic DPC policy optimization algorithm. We formulate the SP-DPC as a deterministic approximation to the stochastic parametric constrained optimal control problem via independent sampling of the problem's parameters and uncertainties. This formulation allows us to directly compute the policy gradients via automatic differentiation of the problem's value function, evaluated over sampled parameters and uncertainties. In particular, the computed expectation of the problem's value function is backpropagated through the finite-time closed-loop system rollouts parametrized by a known nominal system dynamics model and neural control policy. We also provide theoretical probabilistic guarantees on closed-loop stability and chance constraints satisfaction for systems controlled by learned neural policies. We demonstrate the computational efficiency and scalability of the proposed policy optimization algorithm in three numerical examples, including systems with a large number of states or subject to nonlinear constraints.

Drgona, Jan↗
DOE OSTI2024

Learning Constrained Parametric Differentiable Predictive Control Policies With Guarantees

We present differentiable predictive control (DPC), a method for offline learning of constrained neural control policies for nonlinear dynamical systems with performance guarantees. We show that the sensitivities of the parametric optimal control problem can be used to obtain direct policy gradients. Specifically, we employ automatic differentiation (AD) to efficiently compute the sensitivities of the model predictive control (MPC) objective function and constraints penalties. To guarantee safety upon deployment, we derive probabilistic guarantees on closed-loop stability and constraint satisfaction based on indicator functions and Hoeffding’s inequality. We empirically demonstrate that the proposed method can learn neural control policies for various parametric optimal control tasks. In particular, we show that the proposed DPC method can stabilize systems with unstable dynamics, track time-varying references, and satisfy nonlinear state and input constraints. Our DPC method has practical time savings compared to alternative approaches for fast and memory-efficient controller design. Specifically, DPC does not depend on a supervisory controller as opposed to approximate MPC based on imitation learning. We demonstrate that, without losing performance, DPC is scalable with greatly reduced demands on memory and computation compared to implicit and explicit MPC while being more sample efficient than model-free reinforcement learning (RL) algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Optimizing the location and configuration of disaster resilience hubs under transportation and electric power network failures

Natural disasters often result in failures of transportation network components and blackouts that imperil the wellbeing of vulnerable populations. In response to these events, resilience hubs have been proposed as a pre-disaster planning strategy to improve access to critical services. This paper introduces an optimization-based approach to locate and configure electric power-generating resilience hubs considering the possibility of failures in transportation and electric power systems. The model's objective is to identify hub locations and configurations that maximize transportation accessibility to the hubs and maximize the satisfaction of basic energy needs through hub-generated electric power. Besides a budget constraint, the model accounts for limits on the levels of hub energy generation vis-à-vis community energy demands, and on the transportation network distance of communities to hubs. Three heuristics are presented for the proposed planning problem. The first heuristic is a genetic algorithm (GA) with problem-specific solution generation procedures. The other two heuristics implement greedy search techniques. Numerical experiments were conducted, using data from rural Puerto Rico, to illustrate the application of the proposed model and heuristics, and examine their performance. In the numerical experiments, the GA heuristic found better solutions than the greedy heuristics. Additionally, design solutions consisting of spatially dispersed hubs with low energy generation capacity were better than solutions with spatially concentrated high-capacity hubs. Lastly, across a wide range of hub demand scenarios, only a small number of candidate hub locations consistently ranked among the best locations for establishing a hub.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
NASA NTRS2014

An Optimizing Space Data-Communications Scheduling Method and Algorithm with Interference Mitigation, Generalized for a Broad Class of Optimization Problems

NASA's space data-communications infrastructure-the Space Network and the Ground Network-provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft. The Space Network operates several orbiting geostationary platforms (the Tracking and Data Relay Satellite System (TDRSS)), each with its own servicedelivery antennas onboard. The Ground Network operates service-delivery antennas at ground stations located around the world. Together, these networks enable data transfer between user spacecraft and their mission control centers on Earth. Scheduling data-communications events for spacecraft that use the NASA communications infrastructure-the relay satellites and the ground stations-can be accomplished today with software having an operational heritage dating from the 1980s or earlier. An implementation of the scheduling methods and algorithms disclosed and formally specified herein will produce globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary algorithms, a class of probabilistic strategies for searching large solution spaces, is the essential technology invoked and exploited in this disclosure. Also disclosed are secondary methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithms themselves. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure within the expected range of future users and space- or ground-based service-delivery assets. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally. The generalized methods and algorithms are applicable to a very broad class of combinatorial-optimization problems that encompasses, among many others, the problem of generating optimal space-data communications schedules.

ground stations↗
NASA NTRS2006

Strict Constraint Feasibility in Analysis and Design of Uncertain Systems

This paper proposes a methodology for the analysis and design optimization of models subject to parametric uncertainty, where hard inequality constraints are present. Hard constraints are those that must be satisfied for all parameter realizations prescribed by the uncertainty model. Emphasis is given to uncertainty models prescribed by norm-bounded perturbations from a nominal parameter value, i.e., hyper-spheres, and by sets of independently bounded uncertain variables, i.e., hyper-rectangles. These models make it possible to consider sets of parameters having comparable as well as dissimilar levels of uncertainty. Two alternative formulations for hyper-rectangular sets are proposed, one based on a transformation of variables and another based on an infinity norm approach. The suite of tools developed enable us to determine if the satisfaction of hard constraints is feasible by identifying critical combinations of uncertain parameters. Since this practice is performed without sampling or partitioning the parameter space, the resulting assessments of robustness are analytically verifiable. Strategies that enable the comparison of the robustness of competing design alternatives, the approximation of the robust design space, and the systematic search for designs with improved robustness characteristics are also proposed. Since the problem formulation is generic and the solution methods only require standard optimization algorithms for their implementation, the tools developed are applicable to a broad range of problems in several disciplines.

Crespo, Luis G.↗
DOE OSTI2022

Error-Bounded Learned Scientific Data Compression with Preservation of Derived Quantities

Scientific applications continue to grow and produce extremely large amounts of data, which require efficient compression algorithms for long-term storage. Compression errors in scientific applications can have a deleterious impact on downstream processing. Thus, it is crucial to preserve all the “known” Quantities of Interest (QoI) during compression. To address this issue, most existing approaches guarantee the reconstruction error of the original data or primary data (PD), but cannot directly control the problem of preserving the QoI. In this work, we propose a physics-informed compression technique that is composed of two parts: (i) reduction of the PD with bounded errors and (ii) preservation of the QoI. In the first step, we combine tensor decompositions, autoencoders, product quantizers, and error-bounded lossy compressors to bound the reconstruction error at high levels of compression. In the second step, we use constraint satisfaction post-processing followed by quantization to preserve the QoI. To illustrate the challenges of reducing the reconstruction errors of the PD and QoI, we focus on simulation data generated by a large-scale fusion code, XGC, which can produce tens of petabytes in a single day. The results show that our approach can achieve a high compression amount while accurately preserving the QoI within scientifically acceptable bounds.

97 MATHEMATICS AND COMPUTING↗