Search NASA⌕ Search

SEARCH · Search NASA

Results for “heuristic algorithms”

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 541 records · Page 30

Scheduling algorithm for mission planning and logistics evaluation users' guide

The scheduling algorithm for mission planning and logistics evaluation (SAMPLE) program is a mission planning tool composed of three subsystems; the mission payloads subsystem (MPLS), which generates a list of feasible combinations from a payload model for a given calendar year; GREEDY, which is a heuristic model used to find the best traffic model; and the operations simulation and resources scheduling subsystem (OSARS), which determines traffic model feasibility for available resources. The SAMPLE provides the user with options to allow the execution of MPLS, GREEDY, GREEDY-OSARS, or MPLS-GREEDY-OSARS.

Chang, H.↗

Determining the accuracy of maximum likelihood parameter estimates with colored residuals

An important part of building high fidelity mathematical models based on measured data is calculating the accuracy associated with statistical estimates of the model parameters. Indeed, without some idea of the accuracy of parameter estimates, the estimates themselves have limited value. In this work, an expression based on theoretical analysis was developed to properly compute parameter accuracy measures for maximum likelihood estimates with colored residuals. This result is important because experience from the analysis of measured data reveals that the residuals from maximum likelihood estimation are almost always colored. The calculations involved can be appended to conventional maximum likelihood estimation algorithms. Simulated data runs were used to show that the parameter accuracy measures computed with this technique accurately reflect the quality of the parameter estimates from maximum likelihood estimation without the need for analysis of the output residuals in the frequency domain or heuristically determined multiplication factors. The result is general, although the application studied here is maximum likelihood estimation of aerodynamic model parameters from flight test data.

Morelli, Eugene A.↗

A Multithreaded Algorithm for Network Alignment Via Approximate Matching

Network alignment is an optimization problem to find the best one-to-one map between the vertices of a pair of graphs that overlaps in as many edges as possible. It is a relaxation of the graph isomorphism problem and is closely related to the subgraph isomorphism problem. The best current approaches are entirely heuristic, and are iterative in nature. They generate real-valued heuristic approximations that must be rounded to find integer solutions. This rounding requires solving a bipartite maximum weight matching problem at each step in order to avoid missing high quality solutions. We investigate substituting a parallel, half-approximation for maximum weight matching instead of an exact computation. Our experiments show that the resulting difference in solution quality is negligible. We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor Intel Xeon E7-8870 system (from 10 minutes to 36 seconds).

network alignment, matching, multicore↗

Evaluation of Hybrid FPOG Applications in Regulated and Deregulated Markets Using HERON

Recent changes in the U.S. energy market, such as low natural gas prices and increased electricity production for variable renewable energy (VRE) sources, have led to an economic crisis for existing light-water reactor (LWR) nuclear power plants (NPP). Many owners and operators of LWRs have elected to decommission these plants rather than continue using them as consistent sources of clean baseload power. This has led to exploration of various possibilities to increase the economic viability of these units, including market restructuring to monetize benefits LWRs already provide to the grid through ancillary markets, load following and economic dispatch, and possible integration of secondary systems directly to the NPP for production of additional products through technologies such as hydrogen electrolysis or water desalination. Previous studies have considered the technologies associated with these Integrated Energy Systems (IES) activities, and the analysis of markets for these secondary products. To analyze the economic viability of various system configurations including IES, especially given the uncertainty surrounding load demand, electricity prices, and the availability of VRE resources, the stochastic technoeconomic analysis package HERON (Heuristic Energy Resource Optimization Network) was released earlier this year as an extension of the risk analysis framework RAVEN (Risk Analysis Virtual Environment). HERON focuses foremost on making the complex uncertainty quantification analysis tools approachable for energy systems analysts, also providing general dispatch optimization algorithms for those workflows. HERON continues to be improved and tested as a significant part of the IES viability analyses performed in this work. HERON is not a capacity expansion model. To consider market and grid energy system development in a variety of scenarios, HERON is best used in coupling with modelling tools such as US-REGEN, which sacrifice some of the uncertainty analysis and resolution of HERON's modelling for the ability to efficiently predict the change in the grid energy system's profile due to economic drivers over decades. HERON can then use this information to explore the economic viability of introducing changes to the predicted outcomes, such as the introduction of an IES. In this work, experts at EPRI using US-REGEN provide six projection scenarios for use in HERON stochastic technoeconomic analysis (STEA) in considering the options available for increasing LWR economic viability through introduction of a hydrogen-centric IES using a high-temperature steam electrolysis plant (HTSE), hydrogen storage, and a constant-rate contracted hydrogen consumer. The results obtained are differential in nature; they do not report expected profits for any configuration, but rather report on the possible increase in the NPV of a configuration with respect to a baseline no-IES configuration. Due to the uncertainty captured in the variable net load of the systems, there is likewise uncertainty in the mean values reported. We consider this viability both in terms of a regulated market, where the energy producers and IES are owned and operated by single entity, as well as a deregulated market, where the IES chooses its bid for electricity generation and is then dispatched by the grid system operator. Results indicate that for deregulated markets, the inclusion of the IES is often statistically beneficial. This is especially true in policies that are not favorable towards nuclear, as nuclear is less often dispatched and is forced to deal with frequent idle capacity. In the nominal case as well as the case of carbon tax policies, inclusion of the IES clearly benefited the economic performance of the NPP. In the regulated case, however, there was a trend towards minimizing the IES, likely due to the optimal sizing performed by US-REGEN of the NPP within the system as well as the lack of penalty for idle capacity at the NPP in the regulated market analyses.

99 GENERAL AND MISCELLANEOUS↗

Development and demonstration of an on-board mission planner for helicopters

Mission management tasks can be distributed within a planning hierarchy, where each level of the hierarchy addresses a scope of action, and associated time scale or planning horizon, and requirements for plan generation response time. The current work is focused on the far-field planning subproblem, with a scope and planning horizon encompassing the entire mission and with a response time required to be about two minutes. The far-feld planning problem is posed as a constrained optimization problem and algorithms and structural organizations are proposed for the solution. Algorithms are implemented in a developmental environment, and performance is assessed with respect to optimality and feasibility for the intended application and in comparison with alternative algorithms. This is done for the three major components of far-field planning: goal planning, waypoint path planning, and timeline management. It appears feasible to meet performance requirements on a 10 Mips flyable processor (dedicated to far-field planning) using a heuristically-guided simulated annealing technique for the goal planner, a modified A* search for the waypoint path planner, and a speed scheduling technique developed for this project.

Deutsch, Owen L.↗

A real-time expert system for self-repairing flight control

An integrated environment for specifying, prototyping, and implementing a self-repairing flight-control (SRFC) strategy is described. At an interactive workstation, the user can select paradigms such as rule-based expert systems, state-transition diagrams, and signal-flow graphs and hierarchically nest them, assign timing and priority attributes, establish blackboard-type communication, and specify concurrent execution on single or multiple processors. High-fidelity nonlinear simulations of aircraft and SRFC systems can be performed off-line, with the possibility of changing SRFC rules, inference strategies, and other heuristics to correct for control deficiencies. Finally, the off-line-generated SRFC can be transformed into highly optimized application-specific real-time C-language code. An application of this environment to the design of aircraft fault detection, isolation, and accommodation algorithms is presented in detail.

Gaither, S. A.↗

State-of-the-Art Techniques for Large-Scale Stochastic Unit Commitment

Recent advances in deterministic unit commitment, both formulaic and algorithmic, along with modern algorithmic approaches for stochastic programming, have enabled the solution of stochastic unit commitment problems with hundreds of scenarios on large-scale transmission networks. In this presentation, we will give an overview of these methods, including lazy transmission constraint generation, lower-bounding techniques, and heuristics, all of which can be executed in concert with customized decomposition approaches for optimization under uncertainty. We demonstrate the effectiveness of these techniques on the TAMU Texas7K synthetic transmission network, leveraging realistic high-resolution forecasts based on NREL renewable resource availability data. The software leveraged for these demonstrations is available via the open-source software packages EGRET (for electrical grid optimization) and mpi-sppy (for optimization under uncertainty).

27 ARPA - Advanced Research Projects Agency-Energy↗

Heuristic Dispatch Based on Price Signals for Behind-the-Meter PV-Battery Systems in the System Advisor Model

The economic potential of a behind-the-meter (BTM) PV-battery system depends greatly on how the battery is dispatched. Different utility rates, system sizes, generation and load profiles can all require different dispatch strategies. This paper presents price signals dispatch, a new algorithm for automated economic dispatch of BTM PV-battery systems, which utilizes 24-hour PV and load forecasts, degradation data, and utility rates. The algorithm is integrated with the System Advisor Model (SAM) tool and is tested with a nonlinear generic electrochemical battery model. Price signals dispatch outperforms SAM's existing algorithms in cases requiring a balance between demand charge management and energy arbitrage, and in cases where battery degradation imposes a significant cost.

batteries↗

Heuristic Dispatch Based on Price Signals for Behind-the-Meter PV-Battery Systems in the System Advisor Model

The economic potential of a behind-the-meter (BTM) PV-battery system depends greatly on how the battery is dispatched. Different utility rates, system sizes, generation and load profiles can all require different dispatch strategies. This paper presents price signals dispatch, a new algorithm for automated economic dispatch of BTM PV-battery systems, which utilizes 24-hour PV and load forecasts, degradation data, and utility rates. The algorithm is integrated with the System Advisor Model (SAM) tool and is tested with a nonlinear generic electrochemical battery model. Price signals dispatch outperforms SAM’s existing algorithms in cases requiring a balance between demand charge management and energy arbitrage, and in cases where battery degradation imposes a significant cost.

41 EE - Solar Energy Technologies Office (EE-4S)↗

Fast counting with tensor networks

We introduce tensor network contraction algorithms for counting satisfying assignments of constraint satisfaction problems (#CSPs). We represent each arbitrary #CSP formula as a tensor network, whose full contraction yields the number of satisfying assignments of that formula, and use graph theoretical methods to determine favorable orders of contraction. We employ our heuristics for the solution of #P-hard counting boolean satisfiability (#SAT) problems, namely monotone #1-in-3SAT and #Cubic-Vertex-Cover, and find that they outperform state-of-the-art solvers by a significant margin.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Surrogate Models for Estimating Failure in Brittle and Quasi-Brittle Materials

In brittle fracture applications, failure paths, regions where the failure occurs and damage statistics, are some of the key quantities of interest (QoI). High-fidelity models for brittle failure that accurately predict these QoI exist but are highly computationally intensive, making them infeasible to incorporate in upscaling and uncertainty quantification frameworks. The goal of this paper is to provide a fast heuristic to reasonably estimate quantities such as failure path and damage in the process of brittle failure. Towards this goal, we first present a method to predict failure paths under tensile loading conditions and low-strain rates. The method uses a k-nearest neighbors algorithm built on fracture process zone theory, and identifies the set of all possible pre-existing cracks that are likely to join early to form a large crack. The method then identifies zone of failure and failure paths using weighted graphs algorithms. We compare these failure paths to those computed with a high-fidelity fracture mechanics model called the Hybrid Optimization Software Simulation Suite (HOSS). A probabilistic evolution model for average damage in a system is also developed that is trained using 150 HOSS simulations and tested on 40 simulations. A non-parametric approach based on confidence intervals is used to determine the damage evolution over time along the dominant failure path. For upscaling, damage is the key QoI needed as an input by the continuum models. This needs to be informed accurately by the surrogate models for calculating effective moduli at continuum-scale. We show that for the proposed average damage evolution model, the prediction accuracy on the test data is more than 90%. In terms of the computational time, the proposed models are ≈ O ( 10 6 ) times faster compared to high-fidelity fracture simulations by HOSS. These aspects make the proposed surrogate model attractive for upscaling damage from micro-scale models to continuum models. We would like to emphasize that the surrogate models are not a replacement of physical understanding of fracture propagation. The proposed method in this paper is limited to tensile loading conditions at low-strain rates. This loading condition corresponds to a dominant fracture perpendicular to tensile direction. The proposed method is not applicable for in-plane shear, out-of-plane shear, and higher strain rate loading conditions.

36 MATERIALS SCIENCE↗

Bit Grooming: statistically accurate precision-preserving quantization with compression, evaluated in the netCDF Operators (NCO, v4.4.8+)

Abstract. Geoscientific models and measurements generate false precision (scientifically meaningless data bits) that wastes storage space. False precision can mislead (by implying noise is signal) and be scientifically pointless, especially for measurements. By contrast, lossy compression can be both economical (save space) and heuristic (clarify data limitations) without compromising the scientific integrity of data. Data quantization can thus be appropriate regardless of whether space limitations are a concern. We introduce, implement, and characterize a new lossy compression scheme suitable for IEEE floating-point data. Our new Bit Grooming algorithm alternately shaves (to zero) and sets (to one) the least significant bits of consecutive values to preserve a desired precision. This is a symmetric, two-sided variant of an algorithm sometimes called Bit Shaving that quantizes values solely by zeroing bits. Our variation eliminates the artificial low bias produced by always zeroing bits, and makes Bit Grooming more suitable for arrays and multi-dimensional fields whose mean statistics are important. Bit Grooming relies on standard lossless compression to achieve the actual reduction in storage space, so we tested Bit Grooming by applying the DEFLATE compression algorithm to bit-groomed and full-precision climate data stored in netCDF3, netCDF4, HDF4, and HDF5 formats. Bit Grooming reduces the storage space required by initially uncompressed and compressed climate data by 25–80 and 5–65 %, respectively, for single-precision values (the most common case for climate data) quantized to retain 1–5 decimal digits of precision. The potential reduction is greater for double-precision datasets. When used aggressively (i.e., preserving only 1–2 digits), Bit Grooming produces storage reductions comparable to other quantization techniques such as Linear Packing. Unlike Linear Packing, whose guaranteed precision rapidly degrades within the relatively narrow dynamic range of values that it can compress, Bit Grooming guarantees the specified precision throughout the full floating-point range. Data quantization by Bit Grooming is irreversible (i.e., lossy) yet transparent, meaning that no extra processing is required by data users/readers. Hence Bit Grooming can easily reduce data storage volume without sacrificing scientific precision or imposing extra burdens on users.

58 GEOSCIENCES↗

Integrating Design and Manufacturing for a High Speed Civil Transport Wing

The aerospace industry is currently addressing the problem of integrating design and manufacturing. Because of the difficulties associated with using conventional, procedural techniques and algorithms, it is the authors' belief that the only feasible way to integrate the two concepts is with the development of an appropriate Knowledge-Based System (KBS). The authors propose a methodology for an aircraft producibility assessment, including a KBS, that addresses both procedural and heuristic aspects of integrating design and manufacturing of a High Speed Civil Transport (HSCT) wing. The HSCT was chosen as the focus of this investigation since it is a current NASA/aerospace industry initiative full of technological challenges involving many disciplines. The paper gives a brief background of selected previous supersonic transport studies followed by descriptions of key relevant design and manufacturing methodologies. Georgia Tech's Concurrent Engineering/Integrated Product and Process Development methodology is discussed with reference to this proposed conceptual producibility assessment. Evaluation criteria are presented that relate pertinent product and process parameters to overall product producibility. In addition, the authors' integration methodology and reasons for selecting a KBS to integrate design and manufacturing are presented in this paper. Finally, a proposed KBS is given, as well as statements of future work and overall investigation objectives.

Marx, William J.↗

Formation Design Strategy for SCOPE High-Elliptic Formation Flying Mission

The new formation design strategy using simulated annealing (SA) optimization is presented. The SA algorithm is useful to survey a whole solution space of optimum formation, taking into account realistic constraints composed of continuous and discrete functions. It is revealed that this method is not only applicable for circular orbit, but also for high-elliptic orbit formation flying. The developed algorithm is first tested with a simple cart-wheel motion example, and then applied to the formation design for SCOPE. SCOPE is the next generation geomagnetotail observation mission planned in JAXA, utilizing a formation flying techonology in a high elliptic orbit. A distinctive and useful heuristics is found by investigating SA results, showing the effectiveness of the proposed design process.

Tsuda, Yuichi↗

Heuristic Dispatch Based on Price Signals for Behind-the-Meter PV-Battery Systems in the System Advisor Model: Preprint

The economic potential of a behind-the-meter (BTM) PV-battery system depends greatly on how the battery is dispatched. Different utility rates, system sizes, generation and load profiles can all require different dispatch strategies. This paper presents price signals dispatch, a new algorithm for automated economic dispatch of BTM PV-battery systems, which utilizes 24-hour PV and load forecasts, degradation data, and utility rates. The algorithm is integrated with the System Advisor Model (SAM) tool and is tested with a nonlinear generic electrochemical battery model. Price signals dispatch outperforms SAM’s existing algorithms in cases requiring a balance between demand charge management and energy arbitrage, and in cases where battery degradation imposes a significant cost.

41 EE - Solar Energy Technologies Office (EE-4S)↗

An Improved Coefficient Calculator for the California Energy Commission 6 Parameter Photovoltaic Module Model

This paper describes an improved algorithm for calculating the six parameters required by the California Energy Commission (CEC) photovoltaic (PV) Calculator module model. Rebate applications in California require results from the CEC PV model, and thus depend on an up-to-date database of module characteristics. Currently, adding new modules to the database requires calculating operational coefficients using a general purpose equation solver - a cumbersome process for the 300+ modules added on average every month. The combination of empirical regressions and heuristic methods presented herein achieve automated convergence for 99.87% of the 5487 modules in the CEC database and greatly enhance the accuracy and efficiency by which new modules can be characterized and approved for use. The added robustness also permits general purpose use of the CEC/6 parameter module model by modelers and system analysts when standard module specifications are known, even if the module does not exist in a preprocessed database.

14 SOLAR ENERGY↗

Active Learning with Irrelevant Examples

Active learning algorithms attempt to accelerate the learning process by requesting labels for the most informative items first. In real-world problems, however, there may exist unlabeled items that are irrelevant to the user's classification goals. Queries about these points slow down learning because they provide no information about the problem of interest. We have observed that when irrelevant items are present, active learning can perform worse than random selection, requiring more time (queries) to achieve the same level of accuracy. Therefore, we propose a novel approach, Relevance Bias, in which the active learner combines its default selection heuristic with the output of a simultaneously trained relevance classifier to favor items that are likely to be both informative and relevant. In our experiments on a real-world problem and two benchmark datasets, the Relevance Bias approach significantly improved the learning rate of three different active learning approaches.

machine learning↗

Decomposition and Algorithmic Approaches for Solving Large-Scale Process Family Design Problems

Our most recent work expands the water desalination case study from 76 variants to 10,897 variants using the equation-oriented model built in Pyomo as part of the PARETO project. Using the discretization formulation presented in Stinchfield (2024a), rather than solving for all 10,897 variants simultaneously, we decompose the formulation into subproblems containing subsets of variants from the process family. We solve the overall problem with Progressive Hedging (PH) deployed in parallel on a distributed HPC cluster using the open-source Python package mpi-sppy (Knueven et al., 2023). This approach allowed us to solve this process family design problem to ~1.5% relative optimality gap in about 5 hours; in comparison, Gurobi reached ~50% relative optimality gap in about 6 hours (Stinchfield et al., 2024b). However, this approach still requires discretization of the common unit module design ranges; additionally, PH acts as a heuristic for MILP’s with gap-closing capabilities. Ideally, we would not have to use ML surrogates or discretization to solve this problem, instead solving the process family design problem with the equation-oriented model directly to achieve the most accurate results. However, recall that we did not consider solving the MINLP directly due to complexity and size. In this work, we aim to decompose and solve this large-scale MINLP using a Structured Nonlinear Global Optimization algorithm presented by Cao and Zavala (2019).

Stinchfield, Georgia↗