Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “constraint satisfaction”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

Experiments with a decision-theoretic scheduler

This paper describes DTS, a decision-theoretic scheduler designed to employ state-of-the-art probabilistic inference technology to speed the search for efficient solutions to constraint-satisfaction problems. Our approach involves assessing the performance of heuristic control strategies that are normally hard-coded into scheduling systems, and using probabilistic inference to aggregate this information in light of features of a given problem. BPS, the Bayesian Problem-Solver, introduced a similar approach to solving single-agent and adversarial graph search problems, yielding orders-of-magnitude improvement over traditional techniques. Initial efforts suggest that similar improvements will be realizable when applied to typical constraint-satisfaction scheduling problems.

Hansson, Othar↗
NASA NTRS1993

Decision-theoretic control of EUVE telescope scheduling

This paper describes a decision theoretic scheduler (DTS) designed to employ state-of-the-art probabilistic inference technology to speed the search for efficient solutions to constraint-satisfaction problems. Our approach involves assessing the performance of heuristic control strategies that are normally hard-coded into scheduling systems and using probabilistic inference to aggregate this information in light of the features of a given problem. The Bayesian Problem-Solver (BPS) introduced a similar approach to solving single agent and adversarial graph search patterns yielding orders-of-magnitude improvement over traditional techniques. Initial efforts suggest that similar improvements will be realizable when applied to typical constraint-satisfaction scheduling problems.

Hansson, Othar↗
NASA NTRS2003

A Graph Based Backtracking Algorithm for Solving General CSPs

Many AI tasks can be formalized as constraint satisfaction problems (CSPs), which involve finding values for variables subject to constraints. While solving a CSP is an NP-complete task in general, tractable classes of CSPs have been identified based on the structure of the underlying constraint graphs. Much effort has been spent on exploiting structural properties of the constraint graph to improve the efficiency of finding a solution. These efforts contributed to development of a class of CSP solving algorithms called decomposition algorithms. The strength of CSP decomposition is that its worst-case complexity depends on the structural properties of the constraint graph and is usually better than the worst-case complexity of search methods. Its practical application is limited, however, since it cannot be applied if the CSP is not decomposable. In this paper, we propose a graph based backtracking algorithm called omega-CDBT, which shares merits and overcomes the weaknesses of both decomposition and search approaches.

Pang, Wanlin↗
NASA NTRS2004

Structure Constraints in a Constraint-Based Planner

In this paper we report our work on a new constraint domain, where variables can take structured values. Earth-science data processing (ESDP) is a planning domain that requires the ability to represent and reason about complex constraints over structured data, such as satellite images. This paper reports on a constraint-based planner for ESDP and similar domains. We discuss our approach for translating a planning problem into a constraint satisfaction problem (CSP) and for representing and reasoning about structured objects and constraints over structures.

Pang, Wan-Lin↗
DOE OSTI2022

Exact constraints and appropriate norms in machine-learned exchange-correlation functionals

Machine learning techniques have received growing attention as an alternative strategy for developing general-purpose density functional approximations, augmenting the historically successful approach of human-designed functionals derived to obey mathematical constraints known for the exact exchange-correlation functional. More recently, efforts have been made to reconcile the two techniques, integrating machine learning and exact-constraint satisfaction. We continue this integrated approach, designing a deep neural network that exploits the exact constraint and appropriate norm philosophy to de-orbitalize the strongly constrained and appropriately normed (SCAN) functional. The deep neural network is trained to replicate the SCAN functional from only electron density and local derivative information, avoiding the use of the orbital-dependent kinetic energy density. The performance and transferability of the machine-learned functional are demonstrated for molecular and periodic systems.

Artificial neural networks↗
NASA NTRS1992

Predit: A temporal predictive framework for scheduling systems

Scheduling can be formalized as a Constraint Satisfaction Problem (CSP). Within this framework activities belonging to a plan are interconnected via temporal constraints that account for slack among them. Temporal representation must include methods for constraints propagation and provide a logic for symbolic and numerical deductions. In this paper we describe a support framework for opportunistic reasoning in constraint directed scheduling. In order to focus the attention of an incremental scheduler on critical problem aspects, some discrete temporal indexes are presented. They are also useful for the prediction of the degree of resources contention. The predictive method expressed through our indexes can be seen as a Knowledge Source for an opportunistic scheduler with a blackboard architecture.

Paolucci, E.↗
DOE OSTI2025

Bayesian Entropy Neural Networks for physics-aware prediction

This article addresses the need for deep learning models to integrate well-defined constraints into their outputs, driven by their application in surrogate models, learning with limited data and partial information, and scenarios requiring flexible model behavior to incorporate non-data sample information. We introduce Bayesian Entropy Neural Networks (BENN), a framework grounded in Maximum Entropy (MaxEnt) principles, designed to impose constraints on Bayesian Neural Network (BNN) predictions. BENN is capable of constraining not only the predicted values but also their derivatives and variances, ensuring a more robust and reliable model output. To achieve simultaneous uncertainty quantification and constraint satisfaction, we employ the method of multipliers approach. This allows for the concurrent estimation of neural network parameters and the Lagrangian multipliers associated with the constraints. Our experiments, spanning diverse applications such as beam deflection modeling and microstructure generation, demonstrate the effectiveness of BENN. The results highlight significant improvements over traditional BNNs and showcase competitive performance relative to contemporary constrained deep learning methods.

14 SOLAR ENERGY↗
DOE OSTI2023

High-throughput exploration of the WMoVTaNbAl refractory multi-principal-element alloys under multiple-property constraints

Development of next-generation gas turbines requires the design and fabrication of novel high-temperature structural materials capable of operating beyond 1300°C. Here, we propose a high-throughput alloy design framework under multiple-property constraints to discover new refractory multi-principal element alloys (MPEAs) for high-temperature applications. The framework treats the development of MPEAs as a composition-agnostic constraint satisfaction problem, i.e., no prescriptions are made concerning the design space before performing investigatory calculations. We target alloys in the WMoVTaNbAl chemistry space that are predicted to meet constraints on the following properties simultaneously: single-phase stability, density, solidus temperature, yield strength at 1300°C, and ductile-to-brittle-transition temperature. These properties are relevant to both applications in gas turbines and manufacturability. A set of 214 MoNbV-rich alloys meet these relevant constraints. These feasible alloys are investigated with density functional theory (DFT) to provide a fundamental electronic basis for their superior properties. Three compositionally representative alloys from the feasible design space (Mo 45 Nb 35 Ta 5 V 15 , Mo 25 Nb 50 V 20 W 5 , and Mo 30 Nb 35 Ta 5 V 25 W 5 ) are selected with a k-medoids-based design scheme for detailed DFT analysis and experimental characterization. The DFT analysis predicted a single-phase BCC at high temperatures with a high yield strength for all three MPEAs, in agreement with CALPHAD (CALculation of PHAse Diagrams) and experiments, respectively. These three alloys are benchmarked against a public database of 1546 MPEAs. Concerning the aforementioned constraints, the Mo 30 Nb 35 Ta 5 V 25 W 5 alloy outperforms these 1546 MPEAs. The present work demonstrates the ability of the proposed design methodology to identify candidate alloys for a given application under multiple property constraints in a combinatorically vast design space.

36 MATERIALS SCIENCE↗
NASA NTRS1994

Solution and reasoning reuse in space planning and scheduling applications

In the space domain, as in other domains, the CSP (Constraint Satisfaction Problems) techniques are increasingly used to represent and solve planning and scheduling problems. But these techniques have been developed to solve CSP's which are composed of fixed sets of variables and constraints, whereas many planning and scheduling problems are dynamic. It is therefore important to develop methods which allow a new solution to be rapidly found, as close as possible to the previous one, when some variables or constraints are added or removed. After presenting some existing approaches, this paper proposes a simple and efficient method, which has been developed on the basis of the dynamic backtracking algorithm. This method allows previous solution and reasoning to be reused in the framework of a CSP which is close to the previous one. Some experimental results on general random CSPs and on operation scheduling problems for remote sensing satellites are given.

Verfaillie, Gerard↗
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

Optimal Management of Grid-Interactive Efficient Buildings via Safe Reinforcement Learning

Reinforcement learning (RL)-based methods have achieved significant success in managing grid-interactive efficient buildings (GEBs). However, RL does not carry intrinsic guarantees of constraint satisfaction, which may lead to severe safety consequences. Besides, in GEB control applications, most existing safe RL approaches rely only on the regularisation parameters in neural networks or penalty of rewards, which often encounter challenges with parameter tuning and lead to catastrophic constraint violations. To provide enforced safety guarantees in controlling GEBs, this paper designs a physics-inspired safe RL method whose decision-making is enhanced through safe interaction with the environment. Different energy resources in GEBs are optimally managed to minimize energy costs and maximize customer comfort. The proposed approach can achieve strict constraint guarantees based on prior knowledge of a set of developed hard steady-state rules. Simulations on the optimal management of GEBs, including heating, ventilation, and air conditioning (HVAC), solar photovoltaics, and energy storage systems, demonstrate the effectiveness of the proposed approach.

Huo, Xiang↗
NASA NTRS1991

The min-conflicts heuristic: Experimental and theoretical results

This paper describes a simple heuristic method for solving large-scale constraint satisfaction and scheduling problems. Given an initial assignment for the variables in a problem, the method operates by searching through the space of possible repairs. The search is guided by an ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. We demonstrate empirically that the method performs orders of magnitude better than traditional backtracking techniques on certain standard problems. For example, the one million queens problem can be solved rapidly using our approach. We also describe practical scheduling applications where the method has been successfully applied. A theoretical analysis is presented to explain why the method works so well on certain types of problems and to predict when it is likely to be most effective.

Minton, Steven↗
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 OSTI2026

Safe Deep Reinforcement Learning for Active Distribution System Model Predictive Control with EVs and DERs

The temporal and spatial mismatch between PV generation and electric vehicle (EV) charging and discharging may cause voltage violations in active distribution networks. Despite the widespread use of deep reinforcement learning (DRL) in power system optimization and control, it lacks guarantees on constraint satisfaction during both training and deployment. This paper proposes a Lagrangian-based safe DRL approach for model predictive control (MPC) of active distribution systems with large-scale integration of PVs, EVs, and energy storage systems (ESSs). A Transformer-LSTM time-series model is proposed to forecast EV charging demand, which is then formulated as a constraint to ensure charging requirements are met. Using this prediction, a Lagrangian-based safe soft actor-critic (SAC) framework is developed for real-time control in a three-phase unbalanced distribution system, enforcing voltage safety constraints while optimizing the cumulative net reward. By integrating the forecasting model with multi-period constraints, the proposed framework jointly coordinates PV systems, EV charging and discharging, and ESS scheduling within the MPC horizon. Numerical experiments on a modified IEEE 123-bus system with real-world data show that, under a high PV penetration scenario, the proposed method increases the net reward by 30.74% and reduces average voltage violations from 0.0011 p.u. to 0.0002 p.u. compared with standard SAC. Compared with the optimal power flow (OPF) approach, it achieves similar voltage security while yielding lower line losses. It also maintains real-time control capability, reducing operation latency to 53.21 ms per 15-minute control interval. The proposed method remains effective under varying PV/EV penetrations and load conditions.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2023

On the Approximability of Random-Hypergraph MAX-3-XORSAT Problems with Quantum Algorithms

Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is poorly understood. We explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be $E = N_{unsat}-N_{sat}$, then spectrally folded quantum optimization will return states with energy $E \leq A E_{GS}$ (where $E_{GS}$ is the ground state energy) in polynomial time, where conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

Kapit, Eliot↗
DOE OSTI2022

3-regular three-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers

With current semiconductor technology reaching its physical limits, special-purpose hardware has emerged as an option to tackle specific computing-intensive challenges. Optimization in the form of solving quadratic unconstrained binary optimization problems, or equivalently Ising spin glasses, has been the focus of several new dedicated hardware platforms. These platforms come in many different flavors, from highly-efficient hardware implementations on digital-logic of established algorithms to proposals of analog hardware implementing new algorithms. In this work, we use a mapping of a specific class of linear equations whose solutions can be found efficiently, to a hard constraint satisfaction problem (three-regular three-XORSAT, or an Ising spin glass) with a 'golf-course' shaped energy landscape, to benchmark several of these different approaches. We perform a scaling and prefactor analysis of the performance of Fujitsu's digital annealer unit (DAU), the D-Wave advantage quantum annealer, a virtual MemComputing machine, Toshiba's simulated bifurcation machine (SBM), the SATonGPU algorithm from Bernaschi et al, and our implementation of parallel tempering. We identify the SATonGPU and DAU as currently having the smallest scaling exponent for this benchmark, with SATonGPU having a small scaling advantage and in addition having by far the smallest prefactor thanks to its use of massive parallelism. Furthermore, our work provides an objective assessment and a snapshot of the promise and limitations of dedicated optimization hardware relative to a particular class of optimization problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗